### MateoCV's blog

By MateoCV, 3 weeks ago,

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:

See you in the standings!

UPD:

Scoring distribution: $750$ — $1000$ — $1250$ — $2000$ — $2750$

UPD: Editorial

UPD: Congratulations to the winners!

Official winners:

Unofficial winners:

• +608

 » 3 weeks ago, # | ← Rev. 2 →   +5 Veryyyyyyyy unusual time! (^-^)
•  » » 3 weeks ago, # ^ |   -18 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup button { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } This contest will have least number of participants in this year
 » 3 weeks ago, # |   -47 Please change time to usual.
•  » » 3 weeks ago, # ^ |   +47 Randomness is the beauty of codeforces.
•  » » » 3 weeks ago, # ^ |   0 We could not, for example, arrive at a principle like that of entropy without introducing some additional principle, such as randomness, to this topography.U get it? I don't, if u do pls enlighten me Sir.
•  » » » 3 weeks ago, # ^ |   +8 Heisenberg would agree.
 » 3 weeks ago, # | ← Rev. 2 →   +209 OP has set two contests and the times areMarch 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
•  » » 2 weeks ago, # ^ |   +3 They say he is the real life Sōsuke Aizen(Bleach Reference).
 » 3 weeks ago, # |   -19 Omg, it starts at 00:35 in Vietnam, not a comfortable time for me.
•  » » 3 weeks ago, # ^ |   +51 01:35 in China
•  » » » 3 weeks ago, # ^ |   0 22:35 in Tajikistan
•  » » » » 3 weeks ago, # ^ |   0 23:35 in Kazakhstan
•  » » » » » 2 weeks ago, # ^ |   +3 23.05 in India
•  » » » 3 weeks ago, # ^ |   0 NO！！！GOD！！！What a hell of a time！！！
•  » » 3 weeks ago, # ^ |   +6 23:05 in India
•  » » » 2 weeks ago, # ^ |   +6 Haan ye karlo pehle
•  » » 3 weeks ago, # ^ |   +7 very good time for me, 6:35 in NZ. The usual time in NZ is 3:35
•  » » 2 weeks ago, # ^ |   +5 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
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   +6 True. I always do better on early morning contests due to all the practice on codeforces.
 » 3 weeks ago, # |   +46 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
•  » » 3 weeks ago, # ^ | ← Rev. 10 →   0 Thank you MateoCV for the invented tasks and the round
 » 3 weeks ago, # |   -19 Shortest announcement
 » 3 weeks ago, # |   0 Will there be hacking phase in this too. I wanna try my luck in hacking too.....kekw
•  » » 3 weeks ago, # ^ |   +10 You can attempt hacking only if you solve a problem and lock it.
•  » » » 3 weeks ago, # ^ |   -8 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 :(
•  » » » » 3 weeks ago, # ^ |   +5 Usually it's rooms in div 1, div 2 and div 1+2. There is no open hacking phase.
 » 3 weeks ago, # |   -6 it's very good
 » 3 weeks ago, # |   -14 contribution can affect the rating?
•  » » 2 weeks ago, # ^ |   0 no it is worthless
 » 3 weeks ago, # |   0 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.
•  » » 3 weeks ago, # ^ |   +5 You are giving you first contest at uncomfortable time, good experience for you.
•  » » » 2 weeks ago, # ^ |   0 In the second contest with awkward timing and not the first contest!
 » 3 weeks ago, # |   0 MESSI is the champion!
 » 3 weeks ago, # |   0 I got -70 last round :( I hope I can get some of that back. Good luck to all participants!
•  » » 3 weeks ago, # ^ |   +6 bro, you were almost 1600.. hope you become expert this time
•  » » » 2 weeks ago, # ^ |   0 I hope so. Thanks
•  » » 2 weeks ago, # ^ |   0 So did I ):
•  » » » 2 weeks ago, # ^ |   +3 We're together in this
 » 3 weeks ago, # |   +2 A round with unusual time and longer duration than normal div2 round!
 » 3 weeks ago, # |   +2 Midnight contest go brr brr!
 » 3 weeks ago, # |   +22 as a tester, I think this will be a great contest.
•  » » 3 weeks ago, # ^ |   0 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!!!
•  » » » 3 weeks ago, # ^ |   0 I was querious about the same things.. can someone pls explain
•  » » » 2 weeks ago, # ^ |   0 People write code to generate test casescheckout testlib.h on github
 » 3 weeks ago, # |   0 Why is the round is on unusual time if it is not based on some onsite round?
•  » » 3 weeks ago, # ^ |   0 Author's time zone is GMT-3. Same issue with football tournaments such as Copa America and World Cups hosted in South America xD
 » 3 weeks ago, # |   +4 I'm glad that I ended up testing a South American round. Expect great problems :3
 » 3 weeks ago, # |   -31 Thanks you MateoCV for lisening mehttps://codeforces.com/blog/entry/112137hope to see first egyptian lgm this roundEGYPSHIAN LGM TIME IS COME!!!!!!!!
 » 3 weeks ago, # |   +1 Wish i do well in this div
 » 3 weeks ago, # |   0 When scoring distribution will announced?
 » 3 weeks ago, # |   0 is c2 ladders a good way to increase someone ratings or should I try something else?
•  » » 3 weeks ago, # ^ |   0 whatever the answer maybe is it the right place to ask this question?
 » 3 weeks ago, # |   +74 Really appreciate the unusual time, I'll get a little extra sleep instead of waking up at 6:00.
•  » » 2 weeks ago, # ^ |   0 Like me.
 » 3 weeks ago, # |   0 late night contest
 » 3 weeks ago, # |   +47 Rare American friendly contest time :D for once I won’t need to wake up at 6am to attend
•  » » 3 weeks ago, # ^ |   +17 But I still will for the leetcode biweekly lol
 » 3 weeks ago, # |   +34 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) :)
•  » » 2 weeks ago, # ^ |   0 I have this question too
 » 3 weeks ago, # | ← Rev. 2 →   +1 [redacted]
 » 3 weeks ago, # |   0 Quite excited to participate in this Latam round ❤️
 » 3 weeks ago, # |   -12 I think the time is a bit unreasonable.
•  » » 3 weeks ago, # ^ |   -11 I think so too
•  » » 3 weeks ago, # ^ |   0 It doesn't matter,you will AK it as usual.
 » 3 weeks ago, # |   0 I am a beginner do you encourage me to participate?
•  » » 3 weeks ago, # ^ |   +16 No
•  » » » 3 weeks ago, # ^ |   0 Thank you but I would take experts advice in consideration.
•  » » » » 2 weeks ago, # ^ |   0 Do it
 » 3 weeks ago, # |   -11 8 pm in india
•  » » 3 weeks ago, # ^ |   0 11 PM
 » 3 weeks ago, # |   -13 very 《good》 time to compete for Chinese...
•  » » 3 weeks ago, # ^ |   -13 01：35 at night in China
 » 3 weeks ago, # |   0 Vamos Argentina The world Champion campeons del mundo
 » 3 weeks ago, # |   0 i think this contest originally was 2.5 hours to solve 6 problems~! :|
 » 3 weeks ago, # |   0 How does the change in rating gets affected by the number of people
 » 3 weeks ago, # |   -19 OMG i hope at this hour there will be no indian cheaters. To indian cheaters, please go to sleep. Don't ruin everyone' fun with your small pp energy, go cheat elsewhere
 » 2 weeks ago, # |   0 Good time for south-asians. Hope I can at least solve one :)
 » 2 weeks ago, # |   0 So sad I can't say " Hope this is my CM promotion contest "I need 120 this time :(
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   +6 you can ,it is possible , inshallah :)
•  » » » 2 weeks ago, # ^ |   +6 Hope so , Thanks !And hope you reach Expert today inshallah
 » 2 weeks ago, # |   +1 I like the timing. Please host more contests at this time.
 » 2 weeks ago, # |   0 Hope this time I will be Pupil
•  » » 2 weeks ago, # ^ |   0 omedeto
•  » » » 2 weeks ago, # ^ |   0 Thank You
 » 2 weeks ago, # |   0 omg unusual time
 » 2 weeks ago, # |   +7 Comfortable time for night owls (UTC+6)
 » 2 weeks ago, # |   +1 It is a good time.
 » 2 weeks ago, # |   +1 Omg, it starts at 1:35 in China, not a comfortable time for me.
•  » » 2 weeks ago, # ^ |   0 What do you think is a good time for us?
•  » » » 2 weeks ago, # ^ |   +3 I think starting the competition at 19:00 is a good time.
•  » » » » 2 weeks ago, # ^ |   0 I agree
 » 2 weeks ago, # |   +5 Waiting for something good
 » 2 weeks ago, # |   +6 Score distribution where?
 » 2 weeks ago, # |   +7 Finally a contest with a good start time for US west coast participants! Would love to see more contests at this time.
•  » » 2 weeks ago, # ^ |   0 username doesn't fit into the comment though
 » 2 weeks ago, # |   +80 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 !!!!
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   +8 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 :( .
 » 2 weeks ago, # | ← Rev. 2 →   0 22:35 in Turkmenistan.unusual time.everybody Good luck!
 » 2 weeks ago, # |   +25 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
•  » » 2 weeks ago, # ^ |   0 This aged well!
•  » » 2 weeks ago, # ^ |   0 should've trusted your instincts...
 » 2 weeks ago, # |   0 It seems to be hard ;)
 » 2 weeks ago, # |   0 GLHF
 » 2 weeks ago, # | ← Rev. 2 →   0 THE BEST CONTEST OF MY LIFE
•  » » 2 weeks ago, # ^ |   0 congo
 » 2 weeks ago, # |   0 can you open the regestiration again. i forgot that.i solved three three problems.i need this contest please
 » 2 weeks ago, # |   +45 This round needs an extra problem F.
 » 2 weeks ago, # |   +21 how to solve E ?
 » 2 weeks ago, # |   +3 How to solve D?
 » 2 weeks ago, # |   +6 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.
 » 2 weeks ago, # | ← Rev. 2 →   +37 My solution for $D$:This problem has an $O(nlog^2n)$ solution.Note $diff$ as the number of different prime numbers.If $diff1$.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$.
•  » » 2 weeks ago, # ^ |   +3 How can we find coeff of X_{n} in nlogn
•  » » » 2 weeks ago, # ^ |   0 NTT
•  » » » » 2 weeks ago, # ^ |   +10
•  » » 2 weeks ago, # ^ |   0 This is exactly the formula I came up with but couldn't implement properly because I had never used fft before.
•  » » 2 weeks ago, # ^ |   +6 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)?
•  » » » 2 weeks ago, # ^ |   +4 You're right,I think it's $O(nlog^2n)$
•  » » 2 weeks ago, # ^ |   0 can you use DP to solve this?
•  » » » 2 weeks ago, # ^ |   0 jiangly solve this using dp. Check his submisson
 » 2 weeks ago, # |   +33 A>>>B
•  » » 2 weeks ago, # ^ |   0 For me it was opposite. Got Fst on B. Haha solved a in 5 min.
 » 2 weeks ago, # |   0 Misinterpreted the C´s formula but learned something today, Thanks for the contest.
 » 2 weeks ago, # |   0 Was E tree hashing?
•  » » 2 weeks ago, # ^ |   +6 Yes.
•  » » 2 weeks ago, # ^ |   0 ++
 » 2 weeks ago, # |   +22 Got D accepted 1 minute before the end of the contest. I am feeling so happy right now.
 » 2 weeks ago, # |   0 how to solve B?
•  » » 2 weeks ago, # ^ |   +3 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.
•  » » 2 weeks ago, # ^ |   0 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
•  » » » 2 weeks ago, # ^ |   0 for (int i = n - 1; i > 0; --i) { while (a[i] % a[i - 1] == 0){ a[i-1]++; } } Can you suggest a test case please, couldn't find why it doesn't work
•  » » » » 2 weeks ago, # ^ |   0 this solution can exceed the 2*n moves limit sample test: 1 120your algorithm will take 5 steps to make good array in this sample while allowed moves are only 4
•  » » » » » 2 weeks ago, # ^ |   0 omg, couldn't find it 2 hours, thanks a lot!
•  » » » » » » 2 weeks ago, # ^ |   0 just two numbers 1 and n! Then you need yours algorithm needs n operations (1->2-> ... -> n+1)
•  » » » » 2 weeks ago, # ^ |   0 1,1,2. In this case, it will become 2,2,2 and it will not pass.
•  » » » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 no, it will be 2 3 2
•  » » » » 2 weeks ago, # ^ |   0 1 2 1 60
•  » » » » » 2 weeks ago, # ^ |   0 Testcases=1 n=2 Elements 1,60
 » 2 weeks ago, # |   +7 I loved problem D, thanks! (might be biased because I am a math major ^^').
•  » » 2 weeks ago, # ^ |   0 How did you solved it?
•  » » » 2 weeks ago, # ^ |   +3 Step 1: Find the number of occurences of each number in the input. Step 2: Split the numbers and their counts into two parts: primes and non-prime numbers. 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.
•  » » » » 2 weeks ago, # ^ |   +3 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 ?
•  » » » » » 2 weeks ago, # ^ | ← Rev. 4 →   +3 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. $\forall j, {e_0}^{(j)} = 1 ~\text{and}~ \forall j, \forall i > j, {e_i}^{(j)} = 0$ ${e_{i + 1}}^{(j + 1)}(x_1, …, x_{j+1}) = {e_{i + 1}}^{(j)}(x_1, …, x_j) + x_{j+1} {e_{i}}^{(j)}(x_1, …, x_j)$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.
•  » » » » » » 2 weeks ago, # ^ |   +3 Thank you so much for detailed explanation, people like you make codeforces a better place :)
 » 2 weeks ago, # |   0 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: void solve(){ int n; cin >> n; vector v; for(int i = 0; i < 2*n-2; i++){ string temp = ""; cin >> temp; v.push_back(temp); } sort(v.begin(), v.end(), [] (string& a, string& b){return a.length()
•  » » 2 weeks ago, # ^ |   +3 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".
•  » » » 8 days ago, # ^ |   0 What an Elegant Solution, Wow impressive problem A, I didn't give this contest as I couldn't solve A so left it and in India it was midnight. Now I realise this contest has very impressive problems, so I'm solving problems now.
 » 2 weeks ago, # |   0 Let me say it's a clear statements, thank you.
 » 2 weeks ago, # |   +3 rank 2800 and got -10 rough contest
 » 2 weeks ago, # |   +7 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 uniqueLet'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
 » 2 weeks ago, # |   0 how to solve problem C?
•  » » 2 weeks ago, # ^ |   +7 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.
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 can you please elaborate it with an example it's still not clear to me
•  » » » » 2 weeks ago, # ^ |   0 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
•  » » » » » 2 weeks ago, # ^ |   0 So basically we are just moving from right to left and we keep moving until and unless Ai
•  » » » » » » 2 weeks ago, # ^ |   0 it's O(N), let me say it in a simpler wayFirst 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.
•  » » » » » » » 2 weeks ago, # ^ |   +3 thank you for clearing out my query sensei(I hope you do watch anime)
•  » » » » 2 weeks ago, # ^ |   0 My humble attempt to explain: -> https://www.youtube.com/watch?v=yJB3TEus8SA&ab_channel=CodebyShuvam
 » 2 weeks ago, # |   +6 Nice math problems :)
 » 2 weeks ago, # |   0 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 = SPOILER, maybe...(n! * C(k, n) + sum(used[p[i]]) * C(k — 1, n — 1) ) / product(used[b[i]])
•  » » 2 weeks ago, # ^ |   0 i just used wrong modulo, but i am pretty sure this should work...
 » 2 weeks ago, # | ← Rev. 2 →   0 What do you guys think was the rating number for problem A?
 » 2 weeks ago, # |   0 Easy A-C, hard D and E
•  » » 2 weeks ago, # ^ |   0 cheems_ABC-buff_doge_DE.png
•  » » » 2 weeks ago, # ^ |   0 What is the rating for problem A?
•  » » » » 2 weeks ago, # ^ |   0 clist.by estimates it at 789
 » 2 weeks ago, # |   0 Can someone explain why my solution is MLE https://codeforces.com/contest/1794/submission/196011471
•  » » 2 weeks ago, # ^ |   +6 I can't believe that this is no pinned on main page somehow:)https://codeforces.com/blog/entry/70237
•  » » » 2 weeks ago, # ^ |   0 I thank you for helping me understand the gap in my knowledge
 » 2 weeks ago, # |   0 here after the contest. I am a night owl so this is the best time for me. Hope more contests can happen around this time. The first question implementation took really long time for me. B was surprisingly much easier.
 » 2 weeks ago, # |   +9 pov: aped B with dp after trying and failing to come up with anything ;-; Spoiler
•  » » 2 weeks ago, # ^ |   +6 I reached max penalty for B and wrote random code until I saw green.
 » 2 weeks ago, # | ← Rev. 2 →   +10 just noticed mateoCV always comes on 4th march with amazing contest.
 » 2 weeks ago, # |   0 Can't get any approach for problem C anybody please let me know in what direction should i think for it.
•  » » 2 weeks ago, # ^ |   0 Binary search
•  » » » 2 weeks ago, # ^ |   0 thank you I will try to think in that direction
•  » » » 2 weeks ago, # ^ |   0 It can be done in O(n)
•  » » » » 2 weeks ago, # ^ |   0 I think binary search is more intuitive in this problem
•  » » » » » 2 weeks ago, # ^ |   0 idk, for me sliding window seems like the most straightforward, obvious solution
•  » » 2 weeks ago, # ^ |   0 HintConsider 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.
•  » » » 2 weeks ago, # ^ |   0 got some sort of idea thank you for helping me out.
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 In C you need maintain the multiset, where the min element is >= size of set. The answer is size of set on each step. So the approach is just to find math observation and then implement it.
•  » » » 2 weeks ago, # ^ |   0 Ohhh I see thank you it's completely clear now i think i will be able to solve it easily
•  » » 2 weeks ago, # ^ |   0 My humble attempt to explain: -> https://www.youtube.com/watch?v=yJB3TEus8SA&ab_channel=CodebyShuvam
•  » » » 2 weeks ago, # ^ |   0 thank you will for sure give it a look.
 » 2 weeks ago, # |   +8 Ratings updated preliminary, it will be recalculated after removing the cheaters.
•  » » 12 days ago, # ^ | ← Rev. 2 →   0 Is this already done? My delta remain unchanged, which is rare if it is done.
 » 2 weeks ago, # | ← Rev. 4 →   -27 it is a good contest
 » 2 weeks ago, # |   0 Any predictions for rating problem D?
•  » » 2 weeks ago, # ^ |   +14 clist.by
•  » » » 2 weeks ago, # ^ |   0 Cool. Thanks :)
•  » » » 2 weeks ago, # ^ |   0 what does the "Luck" tab mean ?
•  » » » » 2 weeks ago, # ^ |   +9 Probability I would solve the problem during contest (based on my rating)
 » 2 weeks ago, # | ← Rev. 3 →   0 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:196054295Can anybody find my mistake ? And sorry for bad English.
 » 2 weeks ago, # |   0 first question was tricky.
 » 2 weeks ago, # | ← Rev. 2 →   +16 Thanks for the nice round !Here is my feedback about each problem ATo 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 BThe 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. CVery 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" DReally 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 Etree 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!
•  » » 2 weeks ago, # ^ |   0 +1 specifically for the comments on div2A
 » 2 weeks ago, # | ← Rev. 3 →   0 Solved.
 » 2 weeks ago, # |   0 Why round not rated for me (2071 rate) MikeMirzayanov?
 » 2 weeks ago, # | ← Rev. 3 →   0 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: for A,B and C, I don't have many words to say. They are intersting but just a little easy. for D, I think it's not very proper to place a simple and standard dp on the position of the last two problems of div2 contests. However, solving this problem did strengthen my dp skills. for E, I think it's too easy to be a div2 E. You can solve it quickly as long as you have once learned tree hashing. And the annoying part of hacks in selecting modular numbers is also boring. Anyway, the E should be replaced in order to make a more balanced and interesting problemset. However, though some problems exists, the whole quality are definitely all right. And Thanks for the authors' and testers' hard work in the contest!
 » 2 weeks ago, # |   0 What is the rating for question C ?
•  » » 2 weeks ago, # ^ |   0 1200
 » 2 weeks ago, # |   0 Why am I getting WA on test 9 ? My code I have used bottom-up dp. Could someone help.