Hola Codeforces!
I am happy to invite you to Codeforces Round 856 (Div. 2), which will take place on Mar/04/2023 20:35 (Moscow time). Notice the unusual time! The round will be rated for participants with rating lower than 2100. You will have 2 hours to solve 5 problems. The problems were authored and prepared by me.
I would like to thank the following people who made the round possible:
- pashka for coordination, help in problem preparation and translating the statements.
- errorgorn, mjhun, BucketPotato, darkkcyan, MarcosK, CodigoL, perdu, AngrySeal, SebaMarin, Crazypy, CarusoX, alwyn, khangai11, byakko, rchaves, pizzaroot, YOK, rekomodo, helcsnewsxd, AEBOV and EyadBT for testing and providing valuable feedback.
- MikeMirzayanov for the great Codeforces and Polygon platforms.
See you in the standings!
UPD:
Scoring distribution: $$$750$$$ — $$$1000$$$ — $$$1250$$$ — $$$2000$$$ — $$$2750$$$
UPD: Editorial
UPD: Congratulations to the winners!
Official winners:
Unofficial winners:
Veryyyyyyyy unusual time! (^-^)
Please change time to usual.
Randomness is the beauty of codeforces.
Heisenberg would agree.
OP has set two contests and the times are
March 4 2022 21:05 — March 4 2022 23:05 and
March 4 2023 23:05 — March 5 2023 01:05 (times are in IST UTC+5.5).
Without paying attention to the year it may seem two contests happen back to back without any break. A real coincidence
They say he is the real life Sōsuke Aizen(Bleach Reference).
Omg, it starts at 00:35 in Vietnam, not a comfortable time for me.
01:35 in China
22:35 in Tajikistan
23:35 in Kazakhstan
23.05 in India
23:05 in India
Haan ye karlo pehle
very good time for me, 6:35 in NZ. The usual time in NZ is 3:35
The common CF contest is 6:35 am for US west T_T. And solving problems with a frozen dizzy brain is a skillset we have
True. I always do better on early morning contests due to all the practice on codeforces.
very excited about Argentinian round, and congrats once again to you and your team for getting LATAM Champions! all the best, hoping to see some nice problems in this round
Will there be hacking phase in this too. I wanna try my luck in hacking too.....kekw
You can attempt hacking only if you solve a problem and lock it.
In 855 (Div 3), there was no option of locking, it was open hacking after contest.
Is it there in 866 (Div 2) too, or it's just that hacking allowed in Room :(
Usually it's rooms in div 1, div 2 and div 1+2. There is no open hacking phase.
contribution can affect the rating?
no it is worthless
23.05 in India, but still i will give this contest. hope i'll get to learn something new from the contest. all the best to everyone.
You are giving you first contest at uncomfortable time, good experience for you.
MESSI is the champion!
I got -70 last round :( I hope I can get some of that back. Good luck to all participants!
bro, you were almost 1600.. hope you become expert this time
I hope so. Thanks
So did I ):
We're together in this
A round with unusual time and longer duration than normal div2 round!
Midnight contest go brr brr!
as a tester, I think this will be a great contest.
bro I got a question.
How do you guys make test cases?
I know this is a very abstract question.
But I've been thinking about this for a while.
Kindly explain with a relevant example when convenient.
All the best for your tester role!!!
I was querious about the same things.. can someone pls explain
People write code to generate test cases
checkout testlib.h on github
Why is the round is on unusual time if it is not based on some onsite round?
Author's time zone is GMT-3. Same issue with football tournaments such as Copa America and World Cups hosted in South America xD
I'm glad that I ended up testing a South American round. Expect great problems :3
Wish i do well in this div
is c2 ladders a good way to increase someone ratings or should I try something else?
whatever the answer maybe is it the right place to ask this question?
Really appreciate the unusual time, I'll get a little extra sleep instead of waking up at 6:00.
late night contest
Rare American friendly contest time :D for once I won’t need to wake up at 6am to attend
But I still will for the leetcode biweekly lol
BTW where is the # before the number on the contest page? I can't find it anymore in any numbered contests...
If this is a persistent change, I must join the round as a memory though it starts at 02:35(UTC+9) :)
[redacted]
Quite excited to participate in this Latam round ❤️
I am a beginner do you encourage me to participate?
No
Thank you but I would take experts advice in consideration.
Do it
very 《good》 time to compete for Chinese...
01：35 at night in China
i think this contest originally was 2.5 hours to solve 6 problems~! :|
How does the change in rating gets affected by the number of people
So sad I can't say " Hope this is my CM promotion contest "
I need 120 this time :(
you can ,it is possible , inshallah :)
Hope so , Thanks !
And hope you reach Expert today inshallah
I like the timing. Please host more contests at this time.
Comfortable time for night owls (UTC+6)
It is a good time.
Omg, it starts at 1:35 in China, not a comfortable time for me.
What do you think is a good time for us?
I think starting the competition at 19:00 is a good time.
Waiting for something good
Score distribution where?
Finally a contest with a good start time for US west coast participants! Would love to see more contests at this time.
today I drove for 8 hours, around 300 km. Pretty scary road. I am tired as F**K. I was looking forward to this round but didn't see the timings. I feel like attending the round, but I might be too sleepy to attend it. upvote if I should take part, downvote if I should take rest !!!!
Really Good and straightforward problems.
Tried my best. Got stuck on B for LONG LONG (56 Minutes long) time, and solve C in 18 minutes. Feel disheartened for not seeing the pattern in B quickly :( .
looking at the score distribution , i can predict it will be an unbalanced contest and will have a huge difficulty gap between C and D
This aged well!
THE BEST CONTEST OF MY LIFE
congo
This round needs an extra problem F.
how to solve E ?
How to solve D?
A was unique for a problem A. I actually solved C faster than A and B, so I thought C was cute. B made me want to pull my hair out. I basically reached the maximum penalty then bashed it until I saw AC.
My solution for $$$D$$$:
This problem has an $$$O(nlog^2n)$$$ solution.
Note $$$diff$$$ as the number of different prime numbers.If $$$diff<n$$$,no solution.
Note the number of occurrences of $$$x$$$ is $$$cnt_ x$$$.
Construct polynomial: $$$(1+cnt_{p_1}X)(1+cnt_{p_2}X)...(1+cnt_{p_{diff}}X)$$$
Expand this polynomial and note the coefficient of $$$X^n$$$ is $$$facn$$$.
The answer is:$$$facn\frac{n!}{(\Pi cnt_i!)}$$$.
Suppose we have arranged the base number.Next,let's arrange the index.
If all the numbers are different, the scheme number is obviously $$$n!$$$;
Note the number of occurrences of $$$x$$$ is $$$cnt_ x>1$$$.If $$$x$$$ is not a prime,number of schemes $$$/=cnt_x!$$$;
If $$$x$$$ is a prime and not selected as the base number,number of schemes $$$/=cnt_x!$$$;
Otherwise,number of schemes $$$/=(cnt_x-1)!$$$.
Note $$$K=n!/(\Pi cnt_i!)$$$,from the above analysis, we know that if $$$p$$$ is selected as the base number,$$$K$$$ should be multiplied by $$$cnt_ p$$$.
How can we find coeff of X_{n} in nlogn
NTT
This is exactly the formula I came up with but couldn't implement properly because I had never used fft before.
How do you expand polynomial in O(n log n) ? Is dividing in the middle and combining them with FFT O(n logn) or O(n log^2n)?
You're right,I think it's $$$O(nlog^2n)$$$
can you use DP to solve this?
jiangly solve this using dp. Check his submisson
A>>>B
For me it was opposite. Got Fst on B. Haha solved a in 5 min.
Was E tree hashing?
Yes.
++
Got D accepted 1 minute before the end of the contest. I am feeling so happy right now.
how to solve B?
Turn all 1's to 2's in one iteration . Once that is done , check for every 'i', whether A[i+1] is divisible by A[i]. If yes, increment A[i+1] by 1 and move on.
you basically increment all the elements that are 1 after this you traverse whole array and if a[i+1] is divisible by a[i], increment a[i+1], this solution will assure that the array already corrected will not be messed up, and the moves required will be always less than 2n
Can you suggest a test case please, couldn't find why it doesn't work
this solution can exceed the 2*n moves limit sample test: 1 120
your algorithm will take 5 steps to make good array in this sample while allowed moves are only 4
omg, couldn't find it 2 hours, thanks a lot!
just two numbers 1 and n! Then you need yours algorithm needs n operations (1->2-> ... -> n+1)
1,1,2. In this case, it will become 2,2,2 and it will not pass.
no, it will be 2 3 2
1 2 1 60
Testcases=1 n=2 Elements 1,60
I loved problem D, thanks! (might be biased because I am a math major ^^').
How did you solved it?
Step 3: How do we get a valid prime decomposition? - First, we need to pick exactly $$$n$$$ distinct primes. (also note that for two different sets of primes, they will never give a same number, no matter how the powers are picked) - Then, we need to count the number of non-equivalent ways of putting the exponents. This is $$$n!$$$ divided by the product of the factorial of the exponents. - When summing over all the possible arrangements of the expronents, a prime a number has a contribution of 1 over its number of occurences if is not in the decompposition, and 1 otherwise. To compute the sum, I realized it was just the elementary symmetric polynomial of degree (number of prime numbers — n) computed on the inverse of the counts of the prime numbers.
Step 4: The elementary symmetric polynomial can be computed with dynamic programming.
In step 3 what do you mean by "a prime a number has a contribution of 1 over its number of occurences if is not in the decompposition, and 1 otherwise" ?
How do you realize "To compute the sum, I realized it was just the elementary symmetric polynomial of degree (number of prime numbers — n) computed on the inverse of the counts of the prime numbers." ?
Any resources ?
Reading again my last message, I realized the explanation was terrible. x’)
Denote by $$$\alpha_i$$$ the number of occurrences for the non-prime numbers and by $$$\beta_i$$$ the number of occurrences for the prime numbers $$$p_i$$$.
When picking exactly $$$n$$$ distinct prime numbers, the number of valid decompositions is $$$\displaystyle\frac{n!}{\prod \alpha_i! \prod (\beta_i - 1)!} \prod \left( 1 ~\text{if}~ p_i ~\text{is used else}~ {\beta_i}^{-1} \right)$$$
The right product is what I meant by "a prime a number has a contribution of 1 over its number of occurrences if is not in the decomposition, and 1 otherwise". The left factor does not depend on the primes which were picked.
In order to compute the sum of all the right products, I rephrased it as “I want all the ways to pick $$$n$$$ 1’s (for the primes that divide the number) and fill the rest with the inverse of the number of occurrences”. This is can be computed as the coefficient in front of $$$X^n$$$ in $$$\prod (X + {\beta_i}^{-1})$$$ (You can see that a bit like the combinatorics argument for $$$(1+X)^n = \sum \binom{n}{k} x^k $$$: to get $$$x^k$$$, you need to pick $$$k$$$ positions for $$$x$$$ among the $$$n$$$ possible positions).
In order to compute this coefficient, you can use a mix of FFT and Divide & Conquer which runs in $$$O(n log^2 n)$$$ but I did not want to bother with that and I checked the problem constraints: a $$$O(n^2)$$$ algorithm will do the job.
To compute this coefficient, I used the first equation in the properties section the Wikipedia article on elementary symmetric polynomial (I actually knew it from my studies). Evaluating elementary symmetric polynomials can be done by dynamic programming thanks to the following equations (I also knew them from my studies).
Notation $$${e_i}^{(j)}$$$ is the $$$i$$$-th elementary symmetric polynomial on $$$j$$$ variables.
EDIT: I missclicked on "post" instead of "preview". I am going to edit this post with the full answer.
EDIT 2: I finished updating the message.
Thank you so much for detailed explanation, people like you make codeforces a better place :)
A's problem statement was deceptively simple, I thought there should be a two liner solution but I couldn't find one. However, I think I did come up with an elegant sorting solution for A:
Yours solution is good. But there will be no more than 2 substrings that contain (n-1) size. Just find those two substrings and reverse any of them, if those two substring matches, the ans is "YES", otherwise "NO".
rank 2800 and got -10 rough contest
D solution: first group the number by their count. Then solve base on this. We will split the problems into two combination: The base and the power. The base has to be unique
Let's call DP[i][j] mean at index ith, we have j prime factors left. This would uniquely determine the number of the power slots left, because if there are X numbers from i + 1 to the end, and j number has been used as base, then there are j — X numbers that were used in the power slots. This means there are n — (j — X) slots left to be used as Power. The number of ways to select number i into factor slots is (n — (j — X) choose count if i. Do the same if the number at i is prime but with one less prime count.
from there just do a count of unique combination
how to solve problem C?
just observe that if the d is the size of your subsequence, then you should not have anything that is less than d, since you can always remove it and make the value larger.
so to solve for ith, let say you add ith into your subsequence, then you start removing the smallest element until the value of this element is not smaller than the size. That'd be your answer.
can you please elaborate it with an example it's still not clear to me
Easier, more straightforward way to do this is by going in reverse. You start by computing the best answer for the whole array. That's easy to do because you just greedily go from the last number until you can't add the number without decreasing the m parameter. How do you do that? First, let's make use of one observation — for a segment (l, r) the numbers that you are going to use in the optimal solution are going to be the largest numbers because the formula is their product divided by c! where c is their amount. Now, after this step, we should have two things : the answer for k = n and the index where the next number lies (going through the reversed sequence). Now, simply iterate from the end to the beginning, removing numbers one by one and greedily adding numbers from index and moving it towards the start as long as it doesn't decrease m. We don't actually care about the exact value of m. Why? Because the formula is the product divided by c!, if we want to add a number, we would multiply m by it and then divide m by (c + 1) we can notice that as long as our number is larger or equal to c+1, m doesn't decrease.
You can find the implementation in my submissions
So basically we are just moving from right to left and we keep moving until and unless Ai<m (here m is 1,2,3...n) because if m becomes greater than Ai and if we take it then it (Ai/m) doesn't contribute in maximizing so as soon as we encounter it we will break at that point and length of maximized scored subsequence would be r-l+1.Am I thinking in the right way? If I am thinking in the right way how do I implement the above approach using Binary search. I think I might get TLE if I do something else other than BS because for every point we ned to get (l,r) and that would take O(n^2). Right?
it's O(N), let me say it in a simpler way
First observation is that we always want to take the highest numbers possible. You are right with the Ai < m, yes. The length is r — l + 1 but you can notice that it's not going to be O(n^2) since we are always going to move l at most n times (since we only ever move it to the left) and r exactly n times (by "removing" elements). And since every move results in a new subsequence we will have not more than 2 * n subsequences which results in O(n) solution. It's called the "sliding window" technique if you want to read more about it.
thank you for clearing out my query sensei(I hope you do watch anime)
Nice math problems :)
Can you tell we if i am right. D:
Let's call b a set consisting all numbers from a, p a set of all primes in a, k is length of this set, then:
ans =
(n! * C(k, n) + sum(used[p[i]]) * C(k — 1, n — 1) ) / product(used[b[i]])
i just used wrong modulo, but i am pretty sure this should work...
Easy A-C, hard D and E
cheems_ABC-buff_doge_DE.png
What is the rating for problem A?
clist.by estimates it at 789
Can someone explain why my solution is MLE https://codeforces.com/contest/1794/submission/196011471
I can't believe that this is no pinned on main page somehow:)
https://codeforces.com/blog/entry/70237
pov: aped B with dp after trying and failing to come up with anything ;-;
I reached max penalty for B and wrote random code until I saw green.
just noticed mateoCV always comes on 4th march with amazing contest.
Can't get any approach for problem C anybody please let me know in what direction should i think for it.
Binary search
It can be done in O(n)
I think binary search is more intuitive in this problem
idk, for me sliding window seems like the most straightforward, obvious solution
Consider some arbitrary non-decreasing prefix and the subsequence for its cost. Then extend the prefix by one integer so that it is still non-decreasing and again find its cost subsequence. Do this a few times with some different cases and see if you can make an observation about how the subsequence for the new cost changes from the previous.
Maybe that's too subtle of a hint, but the editorial is also out if you're stuck for too long.
Ratings updated preliminary, it will be recalculated after removing the cheaters.
Is this already done? My delta remain unchanged, which is rare if it is done.
Any predictions for rating problem D?
Cool. Thanks :)
what does the "Luck" tab mean ?
Probability I would solve the problem during contest (based on my rating)
For problem E, I thought lets make the 2 lists pri, comp where pri stores the count(non zero) of each prime element and similarly comp for composite. Let us denote them by pri={x1,x2,x3....}, comp={y1,y2,y3....}. Then my answer is ((x1+x2+x3....+y1+y2+y3.....-n)!/((x1!)(x2!)(x3!)....(y1!)(y2!).....))*(Sum of elements in pri taken n at a time). The idea is that lets select the primes which will be in the base then the powers can be arranged as (x1+x2+x3....+y1+y2+y3.....-n)!, then just to remove the repetition we will divide it by x1!,x2!....and for yi if we have used yi the divide by (yi-1)! else divide by yi! and for that I used the sum of element thing.
Here is my submission:196054295
Can anybody find my mistake ? And sorry for bad English.
Thanks for the nice round !
Here is my feedback about each problem
To me, this is truly what a perfect div2 A should be!
not A + B problem
there is some idea to have
the statement can be understood without any knowledge
no random math involving gcd and lcm
the problem doesn't push beginners to guess some formula and submit till they get AC
The problem is good but it might be a bit too easy as a div2 B (although I think that creating a perfect div2 B is extremely hard). Still, it is quite a cool problem.
Very cute problem, it probably is almost perfect as a div2 C (maybe a little bit too easy though?). The issue might be that the solution is really short so it's possible to kind of guess it ? idk, it's pretty hard to estimate the difficulty of a problem when you solve it "fast"
Really cool D. I feel a bit dumb as I had the correct dp states somewhere on my paper and I ended up skipping the problem too fast
tree hashing is fun, however it's a bit unfortunate that the last div3 also had tree hashing in it... :(
The problem is probably a bit too easy compared to regular div2 F. However div2F is most of the time only solved by non div2 contestants so I guess it's not that much of a problem ?
I'm looking forward to take part in other rounds that you set!
+1 specifically for the comments on div2A
Solved.
Why round not rated for me (2071 rate) MikeMirzayanov?
Due to the uncomfortable time in China I didn't have a chance to participate in this great contest. However, after my virtual participation today I'd like to express some of my points so far. Here are them:
However, though some problems exists, the whole quality are definitely all right. And Thanks for the authors' and testers' hard work in the contest!
What is the rating for question C ?
Why am I getting WA on test 9 ? My code I have used bottom-up dp. Could someone help.
please upvote::https://codeforces.com/blog/entry/113556#comments
muchas gracias aficiónados esto para vosotros SIUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
i think it is from the best contests i see in my journy till now.
MikeMirzayanov I got a rules violation for my A solution. I didn't copy or leak my solution. It's a pure coincidence the solutions are so similar.