By pikmike, history, 6 months ago, translation,

Hello Codeforces!

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Ne0n25 Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 kefaa2 7 135
2 MiFaFaOvO 7 145
3 neal 7 161
4 uwi 7 191
5 CWOI 7 196

Congratulations to the best hackers:

Rank Competitor Hack Count
1 MarcosK 134:-15
2 _apurv_ 28
3 racsosabe 24:-1
4 sv_restart 18:-3
5 Norrius 16
773 successful hacks and 620 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A hochesh 0:00
B Kirill22 0:02
C i.e 0:03
D neal 0:08
E andrew 0:09
F MiFaFaOvO 0:33
G gisp_zjz 0:31

UPD: Editorial is out

• +207

 » 6 months ago, # |   +13 Good luck everyone!
•  » » 6 months ago, # ^ |   +36 Wow that helped!
•  » » » 6 months ago, # ^ |   +28 Why do people feel the need to be snark over benign well-wishes?
•  » » » » 6 months ago, # ^ |   -12 Well, he's DankCommenter.
•  » » 6 months ago, # ^ |   +12 What does "Unexpected verdict" means in hack verdict?
•  » » 6 months ago, # ^ |   0 thanku i got d this tym. :)
 » 6 months ago, # |   -47 7 problems in 2 hours! sounds like high rating :3
•  » » 6 months ago, # ^ |   -54 You think 7 problems in 2 hours is a lot? It is not a lot compared to that
•  » » » 6 months ago, # ^ |   -38 But in this contest there were 3 bilateral questions (B1 and B2), (C1 and C2), (D1 and D2).
•  » » » » 6 months ago, # ^ |   -45 That is true, but after this contest everyone complained about too much subtasks. It doesn't make sense for 3 problems to have subtasks in 1 contest! Codeforces is not OI style. It is supposed to be CPC style! You might need to check this and this
•  » » 6 months ago, # ^ |   -20 thanks for the information :(
 » 6 months ago, # |   0 thanks a lot..pikmike
 » 6 months ago, # |   +32 Wasn't this contest supposed to be like 3 weeks ago?I remember registering to an Educational Round and it dissapeard, and I really wondered why.
•  » » 6 months ago, # ^ |   +9 Yes,it is.And I guess there is a problem of test data found by careful questioners.
 » 6 months ago, # |   -38 I hope this contest will help me forget the past few contests and get over them. The setters look good for this one, although a few names are somewhat a matter of concern.
 » 6 months ago, # |   0 Seems more like a Speed Test.. XD
 » 6 months ago, # |   0 We want short description.So please.......
 » 6 months ago, # | ← Rev. 4 →   -44 thanks for so many upvotes :)
 » 6 months ago, # | ← Rev. 2 →   -10 .
 » 6 months ago, # |   -9 Hope to get blue today!
 » 6 months ago, # |   0 Hi, just wanted to know when will the scoring distribution be put up?
•  » » 6 months ago, # ^ |   +12 "It will be held on extended ICPC rules"
•  » » » 6 months ago, # ^ |   0 Thanks.
 » 6 months ago, # |   0 What's the imaginary scoring distribution
•  » » 6 months ago, # ^ |   +9 Each problem is worth [10000 — # of minutes to solve] points.
 » 6 months ago, # |   +55
 » 6 months ago, # |   +14 ME: After 1 successful submission. Let's see friends standing :)
 » 6 months ago, # |   -27 speedforces
 » 6 months ago, # |   +2 I really need to code more because I got the idea of C in one min but it took me more than an hour to code it correctly it's my fault
 » 6 months ago, # |   -15 why C is giving right answer on my ide and WA on codeforces ide for test case 1??please tell
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 Because of precision error. Output can sometimes be 4.99999999999 while its actually 5. So just ciel if the difference is less than an epsilon value like 1e-9, else just floor. ll getLog(ll v) { double z = log2(v)/log2(k); ll a = (ll)z; if(fabs(z-(a+1)) < 1e-9) return a+1; return a; } 
•  » » » 6 months ago, # ^ |   -28 thanks but it's late...no problem next time
•  » » » » 6 months ago, # ^ |   +10 Well you weren't going to get a response during the contest anyways. Would be considered cheating I guess.
•  » » » » » 6 months ago, # ^ |   -13 no but it's not accepted...btw and I didn't copy the logic...and I during the contest I thought...the leading team will be answing..not the contestants
•  » » » » 6 months ago, # ^ |   0 I faced the same issue. Thanks for the info, ll take care of it next time. A doubt though, why are the other online ides giving the correct answer?
•  » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 I'm not sure tbh but I'd guess it depends on the compiler or PC architecture or maybe even just luck.Just be careful when using doubles and always use the difference instead to checking equality directly or try to avoid using them whenever possible.
 » 6 months ago, # |   0 Imagine being able to solve problems yourself ;) http://www.usaco.org/index.php?page=viewproblem2&cpid=648 (Problem E)
•  » » 6 months ago, # ^ |   +5 this round educated me on how to organize my folders better... I spent so long looking for my 262144 code ((
•  » » 6 months ago, # ^ |   0 In that problem, the move is the same, but the goal is to maximize the max element. Is it necessarily true that the resulting array is also the shortest possible array?
•  » » 6 months ago, # ^ |   0 The goal of both the problems seems bit different. In today's question, they asked to minimise the length of array, whereas in the link they have asked to maximise the largest remaining element. Am I missing something?
•  » » » 6 months ago, # ^ |   0 No you are not missing something, but the dp in both problems is exactly the same if you read the solution except this problem requires one more (obvious) step.
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 [Deleted]
 » 6 months ago, # |   +6 How to solve E?
•  » » 6 months ago, # ^ |   0 bruh read comment above smh http://www.usaco.org/current/data/sol_262144_platinum_open16.html
•  » » 6 months ago, # ^ |   0 I know it's some stuff about Sprague–Grundy theorem, but I still can't solve it.
•  » » » 6 months ago, # ^ |   +10 I think you are thinking of F...
•  » » » » 6 months ago, # ^ |   0 Oh, you're right, E is the last second problem in most Div2...
 » 6 months ago, # |   +4 How to solve D problem?
•  » » 6 months ago, # ^ |   +69 Let's construct the answer step by step. Consider a sorted array of length $n - 1$ for a moment, which contains no repetitions and whose elements range from $1$ to $m$.There are ${m}\choose{n - 1}$ different arrays with this property (since there are no repetitions, one choice of $n - 1$ numbers from $m$ available corresponds to exactly one ordering of them).Now we can pick the maximum and throw some elements from the array to its right (in decreasing order), others remaining to its left. There is a total of $2^{n - 2}$ subsets of numbers that we can position to the right of our maximum, each subset corresponding to exactly one ordering (length $n - 1$, and we're not considering the maximum itself).Finally, we pick one of the numbers (but not the maximum) and add its duplicate to our array. There are $n - 2$ different choices for this. Also we must consider that we don't care whether the chosen element is on the right or on the left, since its copy will appear on another side, and we cannot distinguish between them. So, we need to divide the final answer by $2$.Thus, the answer is ${m}\choose{n - 1}$$\cdot 2^{n - 3} \cdot (n - 2). •  » » » 6 months ago, # ^ | 0 Didn't understand why you divided the answer by 2 at the very end. For example, 1 2 5 4 3, we can have 1 as duplicate and get 1 2 5 4 3 1 and do the same for every n-2 number (1,2,3,4). So why divide by 2? •  » » » » 6 months ago, # ^ | +2 "There is a total of 2^{n−2} subsets of numbers that we can position to the right of our maximum". If you choose 1 as the duplicate, you'll get the same resulting array if you move {1, 3, 4} to the right and if you move {3, 4} to the right in step 2 — either way there will be a 1 on both sides. •  » » » » 6 months ago, # ^ | ← Rev. 2 → +10 Another way of seeing this is, the repeating element has to be on both the sides of the peak element. For each of the non repeating element, you have 2 choices, either the left side or the right side. Therefore, (n-3) elements having 2 options each giving 2^(n-3) ways in total. •  » » » » » 6 months ago, # ^ | 0 This is equivalent to chosing a subset of elements placed on a given side •  » » » 6 months ago, # ^ | ← Rev. 2 → +18 Thanks for an excellent explanation. Understanding this made me realize that there's another way to think about it (minor differences) : Pick (n-1) unique elements ranging from 1 to m. (The reason for n-1 instead of n is that one of these will eventually be duplicated, resulting in a total of n). This can be done in C(m, n-1) ways. From these (n-1) elements, pick the largest number. This can be done in only one way. From the remaining (n-2) elements, pick the duplicate. This duplicate will go on both sides (ensuring that we have at least one element to the left and right of the maximum). There's (n-2) ways of doing this. The remaining (n-3) numbers can go either to the left or to the right of the maximum. There's 2^(n-3) ways of doing this. Total number of ways = C(m, n-1) * (n-2) * 2^(n-3)  •  » » » » 6 months ago, # ^ | +1 Nice explanation, Thanks! •  » » » 6 months ago, # ^ | 0 can you tell why are we taking n — 1 elements from m and not n elements •  » » » » 6 months ago, # ^ | +2 The reason for n-1 instead of n is that one of these will eventually be duplicated, resulting in a total of n (explained above by @sh_maestro). •  » » » 6 months ago, # ^ | ← Rev. 2 → 0 How to calculate it without overflowing long long? I can take the modulo when I multiply but it can make the result incorrect when I divide. •  » » » » 6 months ago, # ^ | +8 The correct way to do division is using modular inverse. •  » » » 6 months ago, # ^ | 0 You can exclude the duplicate element from the set along with the maximum, so that you consider a set of n-3 elements. Then you don't need to divide by 2 afterwards. •  » » » 6 months ago, # ^ | 0 Helped alot!! Thanks. •  » » » 5 months ago, # ^ | 0 Very nicely explained went straight into my head thanks for it!! •  » » 6 months ago, # ^ | ← Rev. 2 → 0 I have found the formula C_{m}^{n-1} (n-2) 2^{n-3}.  » 6 months ago, # | +1 What was test case 4 of problem C?? •  » » 6 months ago, # ^ | +1 What was it really? •  » » 6 months ago, # ^ | 0 Its something like 2 421 16  » 6 months ago, # | +1 Is D is formula based ?? if yes!! then what's the formula •  » » 6 months ago, # ^ | +34 Yes! The answer is: m\choose (n-1)$$ * (n-2) * 2^{(n-3)}$We choose $( n - 1 )$ values from $1$ to $m$. Except the max value, each value can be chosen to duplicate ( in $(n-2)$ ways ). The remaining $(n-3)$ values ( except the max and duplicate value ) can be split into two ways, either on the left or right of the max value ( $2^{(n-3)}$ ways ).
•  » » » 6 months ago, # ^ |   0 can you explain why 2^(n-3)?
•  » » » » 6 months ago, # ^ |   0 Each element is given 2 options, either to be on the left or right of the max value. For example, if there is 1 element. It can either be L or R of the max value. If there are 2 elements, there are 4( $2^2$ ) ways: LL, LR, RR, RL. Similarly for $n-3$ elements, there are $2^{n-3}$ ways.
 » 6 months ago, # | ← Rev. 2 →   +5 Can somebody tell me if a[l]~a[r] can be merged to one element.Whether this element is fixed?
•  » » 6 months ago, # ^ |   +2 Yes, this element seems to be fixed. Proof : define a quantity for your array S = sum of all 2^(a[i]) where a[i] is an array element Then notice, that in one operation, two nearby elements each with value x contributing 2^x each to the sum disappear and leave x+1 in their place which contributes 2^(x+1) as 2^x + 2^x = 2^(x+1) therefore this quantity which we defined, S never changes hence if a[l] to a[r] is merged into a single element, it is uniquely determined.
 » 6 months ago, # | ← Rev. 3 →   +8 Solved problem E in $O(n^3 \cdot \text{MaxValue}/64)$ with bitsets. submission
•  » » 6 months ago, # ^ |   0 Whether AMAX matters a lot?? I pass the pretests in O(n^3) .
•  » » » 6 months ago, # ^ |   0 Just dp...
 » 6 months ago, # | ← Rev. 2 →   0 F, What's the tail-period-length of $(x,y,z)$? or just prep a $5^3$ offline memo?
•  » » 6 months ago, # ^ |   +13 If you bruteforce period, you will see that it never exceeds 10. So you can precalculate all answers for all $(x, y, z)$ for numbers up to LCM(2, ..., 10) = 2520, and with this you can easily answer queries.
•  » » » 6 months ago, # ^ | ← Rev. 3 →   0 I know it never exceed 10. I wanna know is there a relation $f(x,y,z)$... but wow, prep a long array is great.since I just got a naive idea, prep a length about 100, then for >100, use period-length to fit in (50..100).
 » 6 months ago, # | ← Rev. 2 →   +26 I found G much easier than E and F
•  » » 6 months ago, # ^ |   0 I arrived at G's solution within 5 minutes after reading the question, whereas I spent 40+ minutes on F during and I'm still totally clueless.
•  » » » 5 months ago, # ^ |   0 At last, I found one of my sons. I hope I also find my right child soon.
•  » » 6 months ago, # ^ |   +3 For me E is much easier than D, F or G... I stuck at D for 50mins, but I solved E in just 10mins.Can you give me some hints on G?
 » 6 months ago, # |   +42 Problem F sentence was SUPER. HARD. TROLLING."previous" and "no matter when" at the same sentence.. So It can be translated many ways.I spend more than 1 hours at this problem...T^T
•  » » 6 months ago, # ^ |   +16 me, too. thought can used only once.
•  » » 6 months ago, # ^ |   +4 same thing hold me for 20 minutes
 » 6 months ago, # |   0
 » 6 months ago, # | ← Rev. 2 →   0 why following logic is not working for question D?? C= combination M= modulus for(ll i=n-1;i<=m;i++) { ans=(ans+((C(i-1,n-2,M)*(n-2))%M))%M; } 
•  » » 6 months ago, # ^ |   +1 I guess, you're forgetting the 2^(n-3), you should multiply the answer obtained above with 2^(n-3). Have a look at the following submission.
•  » » » 6 months ago, # ^ |   0 it worked ,but why we considered 2^(n-3) ,shouldn't it be 2^(n-2);as we arranging n-2 d/f types of elements??
•  » » » » 6 months ago, # ^ |   0 Look at lollihunter's comment above and the two comments below it. https://codeforces.com/blog/entry/74572?#comment-587286
•  » » » 6 months ago, # ^ |   0 Bro, how to find Combination Fast, formula is working for smaller values ,but when input is large ,it takes very long time to get answer, and hence TLE??
•  » » » » 6 months ago, # ^ |   0
 » 6 months ago, # |   +4 Can someone explain solution of E in detail. Thanks in advance.
•  » » 6 months ago, # ^ | ← Rev. 3 →   +11 Dp Solition:for every subarray check if it possible to convert it into single integer value denote this as val(arr[i : j ]) => integer for any i , j pair 0 <= i <= j < nfor every subarray [i, j] iterate over i<= z < j such that: if( val(arr[i : z]) == val(arr[z+1 : j])): val(arr[i : j ] ) = val(arr[i : z ] ) + 1
 » 6 months ago, # |   +2 What Test case 4 of C problem....?? question seemed easy but still was not able to pass it :-(
•  » » 6 months ago, # ^ |   0 yes same problem
 » 6 months ago, # |   +15 No Screencast? tmwilliamlin168
•  » » 6 months ago, # ^ |   +31 I accidentally turned on my facecam when I recorded my screencast, and I'm not sure if I want to make it public :/I still made explanations, for those who are interested: https://www.youtube.com/watch?v=ytOManO7GO0
•  » » » 6 months ago, # ^ |   +4 Thank you..!
•  » » » 6 months ago, # ^ |   +67 I would love to see screencast of your face, even without sound and code ^_^
•  » » » 6 months ago, # ^ |   +1 Hii Can anyone plsss check this submission. He obfuscated all the codes. Is this Cheating https://codeforces.com/contest/1312/submission/72814153
•  » » » » 6 months ago, # ^ |   0 No it shouldn't be...
•  » » » » 6 months ago, # ^ |   0 What language is this???
•  » » » 6 months ago, # ^ |   +17 Thank you for making this explanation video! It is nice to learn from a high ranked coder like you by tracing your thought process. Subscribed to your youtube channel :)
 » 6 months ago, # | ← Rev. 2 →   +6 Why there is an "Unexpected verdict" when I try to hack solution of C?
 » 6 months ago, # |   +16 How to solve F? I recalled Grundy Number technique, but the range is too large to use Grundy Number. Thus I tried to find the period, but I cannot find any period.
•  » » 6 months ago, # ^ |   +21 I think the period is quite obvious once you print them out. https://i.imgur.com/NsO0kXP.jpg
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 Wow! Thanks for sharing your idea
 » 6 months ago, # |   0 For Div2 E, I tried a greedy solution using stack, going left to right, and it failed. Can someone help me how to prove it wrong ?
•  » » 6 months ago, # ^ |   +11 7 7 5 5 6 8 Going left to right gives, 8 7 8 Optimal Strategy gives, 7 9
•  » » 6 months ago, # ^ |   +9 Try 1 1 1 2
•  » » 6 months ago, # ^ |   +1 Greedy wont work. If processing left to right -> 5 3 3 3 4 -> 5 4 3 4. Whereas, you could have, -> 5 3 4 4 -> 5 3 5Same problem if you process right to left. Just invert the array.
 » 6 months ago, # |   -14 SpeedForces.
 » 6 months ago, # | ← Rev. 3 →   0 Why this wont work for D:nCr(m-i,n-2)*(n-2) for i>=1Fix 2 ends with a number i, so we have to fill n-2 places with numbers from i+1 to m (ie nCr(m-i,n-2)) , and we can have n-2 positions for the biggest number so multiply by n-2
•  » » 6 months ago, # ^ |   +4 This assumes that the repeat number is necessarily the smallest number, which is not necessarily the case.
•  » » » 6 months ago, # ^ |   0 You know what's wrong with this approach — We fix the value $v$ and position $p$ of the peak value. Numbers on left of peak are $p-1$ and on right are $n-p$. Now we have to choose total of $n-2$ values less than $v$ to place on non-peak position. Let $x$ = $min(p-1, n-p)$. Then $R$ = $\sum_{p = 2}^{n-1}\sum_{v = n-1}^mC_{x}^{n-2}C_{n-2}^{v-1}$.
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 It's fine — You missed a multiplying factor $x$ because you can choose any of them on the bigger side. 72880191
•  » » 6 months ago, # ^ |   0 i did the same
 » 6 months ago, # |   +7 Missed E by 2 minutes
 » 6 months ago, # |   +1 Can D be solved with DP, if yes please share dp states
•  » » 6 months ago, # ^ |   0 If it can, then I think it will be only as a by-product of the closed form solution.
 » 6 months ago, # |   +12 I hate the fact that in educational codeforces we dont get the editorial before the next day.
•  » » 6 months ago, # ^ |   +7 Hii Can anyone plsss check this submission. He obfuscated all the codes. Is this Cheating https://codeforces.com/contest/1312/submission/72814153
•  » » » 6 months ago, # ^ |   0 Bad girl doing bad things.
 » 6 months ago, # | ← Rev. 2 →   +18 I think there is something wrong with checker of problem C. I tried to hack one submission that should give WA and I got "unexpected verdict" (id of hack is 621220).
•  » » 6 months ago, # ^ |   0 Oh, it seems the problem with the checker is when n=1. I tried to hack with n=2 and got successful hacking attempt. Please, fix that :)
•  » » » 6 months ago, # ^ |   0 What is the hack?
 » 6 months ago, # |   0 How to get 3 for the 4th string in the first testcase (problem G)? It looks impossible to me.
•  » » 6 months ago, # ^ |   0 Apparently, to get 3 you need to type 'i', 'q' and then use autocompletion
•  » » » 6 months ago, # ^ |   0 Thank you!
 » 6 months ago, # |   +20 In problem F, how to find upper bound on precalculation ?What I did is calculate 3 grundy values for 3 different attacks for a particular castle. Since x,y,z <= 5 , we need atleast 5 states to repeat.First value can be from 0 to 3 and 2nd,3rd value can be from 0 to 2. So I thought (4*3*3)^5 is an upper_bound which is not the case.
•  » » 6 months ago, # ^ |   +8 Brute force shows that the upper bound for the period and pre-period is at most $36$, but proving it can be really painful.Well, one can prove some reasonable bounds like $10^5$ intuitively.
•  » » » 6 months ago, # ^ |   +12 More reasonable bound should be around 10^4, given t <= 1000 and time 3s. Unless and until there is some magic :D
•  » » » » 6 months ago, # ^ |   +14 There is some magic.Originally, when I was preparing this problem, I decided to set $x, y, z \le 3$ so it would be clear that there are not so many states — the most generous upper bound is $4^9$ in this case.Then my colleagues told me that it could be possible to analyze all cases of $x, y, z$ since there were only $27$ of them, and most of them were symmetric to some other cases or trivial. I didn't want such solutions, so I've decided to check how far I could push the bounds.At some point, the bounds were $x, y, z \le 20$, leading to really large upper bounds, but surprisingly small periods when checked by brute force (if I remember correctly, even on such large constraints the longest period with pre-period was less than $500$). But these constraints were (intuitively) very unreasonable, so I've decided to drop them to $5$.I think that it's possible to prove that the period is something like $O(\max^2(x, y, z))$, but it surely will be a lot of work :)
•  » » » » » 6 months ago, # ^ |   +23 Yes, good to keep it lower otherwise I would rather think about the different solution. Nonetheless it was a good problem.
 » 6 months ago, # |   +1 https://codeforces.com/contest/1312/challenge/72826639 Hack my solution... I assumed no of steps are <=35 :((
•  » » 6 months ago, # ^ |   0 Happens bro :(
 » 6 months ago, # |   +11 What is Unexpected verdict in Hacks?
•  » » 6 months ago, # ^ |   +12 (probably) checker failed while judging
•  » » » 6 months ago, # ^ |   +9 Thank you!
 » 6 months ago, # | ← Rev. 2 →   0 Problem E, My greedy solution got WA on TC38 :( Can anyone help? Is the WA due to some corner case? Link
 » 6 months ago, # |   +17 Seems like checker for problem C not works. I got "Unexpected verdict" while hack others.
 » 6 months ago, # |   0 WHY WHEN I HACK PROBLEM C I SEE "UNKNOWN VERDICT"?
•  » » 6 months ago, # ^ |   0 yes same here
•  » » » 6 months ago, # ^ |   0 the verdict says illegal contest id
•  » » 6 months ago, # ^ | ← Rev. 3 →   +1 because maybe the checker itself fails for that test case like some sort of TLE or RE.
•  » » 6 months ago, # ^ |   0 Try to hack it for multiple number of test cases(more than 1)
 » 6 months ago, # | ← Rev. 3 →   +45 E can probably be solved in n^2 — 72819557explanation: let $dp[i]$ be number of answer for subarray $i..n$. If $i..j$ can be combined to get a single value we can write $dp[i] = min(dp[i],1+dp[j+1])$, to check if $i..j$ can be combined to get a single value, we can greedily merge from left to right, means if we get two adjacent equal values (If multiple such take leftmost) , we can erase them both and write a single value in their place. I have implemented this using stack
•  » » 6 months ago, # ^ |   0 Could you please explain your solution
•  » » » 6 months ago, # ^ | ← Rev. 3 →   +4 I have added explanation to my comment
•  » » 6 months ago, # ^ |   0 Do you know the proof for why if segment $i...j$ can be merged into one element, the order of operation won't matter and we will always get the same one element?
•  » » » 6 months ago, # ^ |   +3 No, I don't know the proof
•  » » » 6 months ago, # ^ |   0 Every element x was there at the beginning, or it was merged by two x-1. Independend of any other elements.Since the merge of two x-2 to one x-1 was before the merge of the two x-1 to x, there is only one possible tree-like path of merge ordering.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +8 I've used the same approach (left-to-right greedy with stack merge of [L, R] into segment of length 1), though didn't bother optimizing from $N^3$ to $N^2$ 72829878 Do you know the proof for why if segment i...j can be merged into one element, the order of operation won't matter and we will always get the same one element? Since we always transform adjacent, $a, a$ into $a+1$, the $Sum(2^{a_i})$ is an invariant, so if $a_L, a_{L+1}, ... , a_{R}$ could be merged into some value $U$, then $U = log_2 (2^{a_L} + 2^{a_L+1} + ... + 2^{a_R})$(if I correctly understood Your question...) the order of operation won't matter Again, I'm not sure that I understood Your question, but I think it does: we can merge [1,1,1,1] into [3] ([1,1,1,1] -> [2,1,1] -> [2,2] -> [3]), but if we were to merge second and third 1, we would get [1,2,1] and no further merges are possible (but left-to-right greedy seems to work...)
 » 6 months ago, # |   +8 Hii Can anyone plsss check this submission. He obfuscated all the codes. Is this Cheating https://codeforces.com/contest/1312/submission/72814153
•  » » 6 months ago, # ^ |   0 Writing your variable names in Russian doesn't make it obfuscation.
•  » » » 6 months ago, # ^ |   0 No Its not Russian.
•  » » » » 6 months ago, # ^ |   +16 YPFARROLCS obviously means sexy llama in Russian
•  » » » » » 6 months ago, # ^ |   0 For each and everything defining it and making it not understandable is itself obfuscating. His accounts are aldready banned previously. Do check once His accounts are buihoatpt2k3provip buihoatpt2k3
•  » » » 6 months ago, # ^ |   0 Umm that doesn't look like russian ? lol. Even if it is.. why tf would you replace a + sign with ECFEFMHJACSV lmao
•  » » » » 6 months ago, # ^ |   0 Yes . For each and everything. Previously his 2 accounts are banned
 » 6 months ago, # |   -21 This contest was weird. G was trivial tree DP with segment trees and hashing whereas A was way too hard for a div2A.
 » 6 months ago, # |   +50 One of the author's solution for the problem C had stupid bug so there are many hacks with unexpected verdict. Now everything is fixed and you can hack this problem. The round most probably will be rated because the initial test set didn't contain the tests that cause the bug. We are deeply sorry for this issue.
•  » » 6 months ago, # ^ |   -11 Hii Can you plsss check this submission. He obfuscated all the codes. Is this Cheating https://codeforces.com/contest/1312/submission/72814153
 » 6 months ago, # | ← Rev. 2 →   +2 Greedy + Divide and conquer solution for E :The greedy observation is that, minimum value in the array must be combined if possible.Now consider a subarray having equal minimum elements.Case 1 : It's length is even, then combine each pair is optimalCase 2 : It's length is odd, then you should combine first few even elements, left one element which will break array into two, combine last remaining even elements.Now call solve function for these 2 partitioned array, Do this for each possible breaking element at odd positions in subarray.During contest, for Case 2, I called solve for the whole array again instead of 2 partitioned array. Which I hacked after the contest.Update : Sorry, but this solution is also hacked by me.
•  » » 6 months ago, # ^ |   +3 I was thinking along these lines but couldn't complete it. The obstacle for me was in case 2 when you have exactly three identical elements, say 1 1 1. In that case you should combine either the left two 1's, or the right two 1's: for instance with$A = [1,1,1,2]$, it is optimal to combine the right two: 1 (1 1) 2 $\rightarrow$ 1 2 2, but:$A= [3,2,1,1,1,2]$, it is optimal to combine the left two: 3 2 (1 1) 1 2 $\rightarrow$ 3 2 2 1 2In general it seems hard to decide whether the left or right is better. Maybe you should count how long the consecutive "boundary" sequence 1,2,3,... is on both sides; like in the last example it extends till 3 on the left side but only till 2 on the right, so we chose left. But deciding this seems hard in general, since you can also have a sequence like 1,2,(2,2),4,5,6,(chain of 64 2s),8, which is equivalent to 1,2,...,8. (then I gave up)
•  » » 6 months ago, # ^ |   +8 Isn't the case 2 makes it exponential ? What is the time complexity then ?
•  » » » 6 months ago, # ^ |   +1 Yes it is. Initially it passed at around 30ms so I thought there must be some magic, but when I calculated time complexity I got exponential so I hacked it.
 » 6 months ago, # |   +4 Can anybody suggest similar equation-finding problems as D.
•  » » 6 months ago, # ^ |   +9 I think you can find similar problems in many Permutation and Combinations books of high school.
 » 6 months ago, # |   +2 Why the test cases for C problem were so bad? Is it necessary for problem creators to add weak test cases so that participants will try to hack others?
 » 6 months ago, # |   +2 Hack my C if you're cool
•  » » 6 months ago, # ^ |   +42 Done :P
•  » » 6 months ago, # ^ |   0 Is "hack me" used in place of "bite me" in the local slang?
 » 6 months ago, # |   0 On E Will time n^3 hack?
 » 6 months ago, # |   0 can explain me problem g sample one? how build a 10th string with 3 operation? i think i dont understand problem.
 » 6 months ago, # |   +16 Why are so many solutions for C failing?
•  » » 6 months ago, # ^ | ← Rev. 2 →   +7 WEAK testcases. Really weak in my opinion.
•  » » » 6 months ago, # ^ |   0 That's true.I forgot an important situation and it still pass the test.
•  » » » » 6 months ago, # ^ |   0 Same here !!
•  » » » » 6 months ago, # ^ |   +1 Yes I also made a silly mistake.
•  » » 6 months ago, # ^ | ← Rev. 2 →   -12 I've hacked you. sorry
 » 6 months ago, # |   0 Can anyone hack this brute force solution of mine and get TLE? https://codeforces.com/contest/1312/challenge/72834695
 » 6 months ago, # |   0 How to solve problem E ?
 » 6 months ago, # |   0 Can sb hack my C?
•  » » 6 months ago, # ^ |   0 your code seems correct for now
•  » » » 6 months ago, # ^ |   0 thx homie
 » 6 months ago, # |   0 How to solve problem D ?
•  » » 6 months ago, # ^ | ← Rev. 2 →   +21 Since one element has to be repeated, choose any (n-1) numbers from 1 to m to fill the array. This can be done in $\binom{m}{n-1}$ ways.Out of these n-1 numbers, one has to be repeated. Since we need a peak element, it cannot be repeated leaving us with n-2 numbers. Hence we can choose the repeating element in $\binom{n-2}{1}$ ways. We are left with (n-2) elements to be arranged on both the sides of the peak. Notice that we require strictly increasing and decreasing sequences on the left and right of the peak element, therefore the repeating element will never be on the same side. For the remaining (n-3) non repeating elements, every element has 2 options : to go either on the left or on the right of the peak. Therefore, number of ways of doing this is $2^{n-3}$.Final answer : $\binom{m}{n-1}$ x $\binom{n-2}{1}$ x $2^{n-3}$
 » 6 months ago, # |   0 Hello Sir, I would like to bring your notice to the fact that some people are using multiple accounts for participating in contests and they hack their own solution to get points.For Instance: https://codeforces.com/profile/rajankur this user has another account with URL as follows: https://codeforces.com/profile/CryBaby This is his secondary account and he used his primary account to hack his own solution which he submitted from his secondary account.Hacked Solution- https://codeforces.com/contest/1312/submission/72825800 Same solution from different account- https://codeforces.com/contest/1312/submission/72845580Just wanted to inform you about all these things going on and I hope that serious actions will be taken against such people (cheats).Thank You
•  » » 6 months ago, # ^ |   -64 Indian people suck, especially you, fuc you
 » 6 months ago, # |   -7 Can anyone hack my C ?
 » 6 months ago, # |   0 How to solve problem D? Explain please
•  » » 6 months ago, # ^ |   -8 has been answered previously..
 » 6 months ago, # |   0 there should be marks for successfully Hacking.
 » 6 months ago, # |   0 I wonder if there is any official editorial or somrthing
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 Usually it becomes available just after hacking phase, when the contest is finished.
 » 6 months ago, # | ← Rev. 2 →   0 How to solve C with Bitmask ?? Can anyone help?
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 Instead of keeping the count for the ith index, just set it to 1. such that pow(k ,i) is neededif any ith index is required and in bitmask if it is already set to 1, in that case you can't use it again simple print("NO"), returnafter iterating all over the index in arrayprint("YES") , if not return
 » 6 months ago, # |   0 Why it is showing participants with rating more than 2100 in the official standing?
•  » » 6 months ago, # ^ |   0 Select [Division 2] in top right
•  » » » 6 months ago, # ^ |   0 Then also it is showing participants with rating mare than 2100 in division 1 official standing.
•  » » » » 6 months ago, # ^ |   +11 It was official contest for everyone but rated for only division 2.
 » 6 months ago, # |   0 What's wrong with my solution to C, i get runtime error?
•  » » 6 months ago, # ^ | ← Rev. 4 →   0 please write the link of your solution in your comment.just erase break in line 43 and you will get accepted.after using break at that line, last of your current input used for next query and sometime result will be run time error.
•  » » » 6 months ago, # ^ |   0 Sorry i should've done that, and thanks for the help that was really dump
 » 6 months ago, # |   +9 When will the editorials be released?
 » 6 months ago, # |   +20 Please somebody tell the editorial releaser to do his job!
 » 6 months ago, # |   +7 pikmike when are the editorial gonna be published?
 » 6 months ago, # | ← Rev. 2 →   -8 My solution for E: I did not have enough time to implement complete solution during the contest because I realized it after good amount of time.So here it goes,finally minimum reduced sequence will have each element constituting some contiguous ranges of number. So for all ranges we need to figure out if that range could be reduced to a single number.Now here is a tricky part, if the range can be reduced to a single number?If we can do so, then frequency of all contiguous equal elements in the range must be a power of 2 or so, because it cannot be odd at any step of reduction or something like that.But the key point is, now we can greedily pick the elements and merge them using a stack, ie, push element to stack, merge top 2 elements of stack till you can and so on.So for each range check if the range becomes stack reducible and using a 1d dp, we can implement the rest of simpler part.Edit : Time Complexity = O(N^2)
 » 6 months ago, # |   0 Auto comment: topic has been updated by pikmike (previous revision, new revision, compare).
•  » » 6 months ago, # ^ |   0 TNX!
 » 6 months ago, # |   +10 An off-topic question — can I undo an upvote made by mistake?
 » 6 months ago, # |   0 Actually, both accounts are mines. For some problem, I submit that from my both account. I am really sorry and I ensure that this type situation will not be repeated.
 » 6 months ago, # |   0 great round!!!! short statements and very combinatorics I wish every round were like this
 » 6 months ago, # |   0 When will the questions of the competition be put into the question bank?
 » 6 months ago, # | ← Rev. 2 →   0 I would like to share another problem E's solution solving in $O(n^2)$.Submission: 72874158Without loss of generality, I assumed all numbers are combined to the right.I changed dp[L][R]={can combine?, val} into three arrays, all of the indexs below are 0-based.ans[i]: minimum length from $0 \text{~} i$dp[i][k]: the minimum length if the $i$'th element was combined to $a[i]+k$, 0 represents it's unachievablecame[i][k]: if the $i$'th element was combined to $a[i]+k$, came[i][k] equals to the left boundary of this combination( aka. L in dp[L][R] and R represents $i$) If the array is [7, 5, 4, 4, 6].came[3][1]=1, dp[3][1]=3came[3][2]=0, dp[3][2]=2, ans[2]=2came[4][1]=came[3][2]=1, dp[4][1]=2came[4][2]=came[3][2]-1=0, dp[4][2]=1, ans[4]=1So the answer is ans[4]=1.
 » 6 months ago, # |   +5 why all winners are div1 participants??