### ch_egor's blog

By ch_egor, 4 weeks ago, translation, ,

Hi everybody,

This Sunday there will be a XVII Moscow Team Olympiad, high school students competition based in Moscow that is an elimination contest for All-Russian Team Olympiad. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Olympiad for Young Students and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583).

Round will be held at Oct/20/2019 12:05 (Moscow time) and will last for 2 hours. Each division will have 6 problems.

Problems are prepared by wrg0ababd, grikukan, DebNatkh, grphil, voidmax, V--gLaSsH0ldEr593--V, volcolac, Sehnsucht, isaf27, _kun_, Flyrise, Nebuchadnezzar, platypus179, Endagorion under my supervision with great help of GlebsHP, _meshanya_, Endagorion, Zlobober and Helen Andreeva.

Thanks to _kun_ for the round coordination and statement translation, and also thanks for MikeMirzayanov for systems codeforces and polygon, which was used to prepare problems of this olympiad.

Good luck everybody!

UPD1: Winners!

Div. 1:

Div. 2:

Editorial will be published soon.

UPD2: Editorial

• +243

 » 4 weeks ago, # |   0 Score distribution?
•  » » 4 weeks ago, # ^ |   +64 does it matter?
•  » » 4 weeks ago, # ^ |   -43 So is it rated?
 » 4 weeks ago, # | ← Rev. 2 →   +14 This is my first div 1 contest! UPD. Oh nope, too hard. My div1 contest flew away
 » 4 weeks ago, # |   0 How many shared problems are there between div1 and div2?
•  » » 4 weeks ago, # ^ |   -45 Each division will have 6 problems.
•  » » » 4 weeks ago, # ^ |   +18 Question was about shared problems
•  » » 4 weeks ago, # ^ |   +4 Usually Div.2 C is the same as Div.1 A, so I think there will be four.
 » 4 weeks ago, # |   +12 If my rating can increase 33 , I will be so happy XD Good luck everyone :)
•  » » 4 weeks ago, # ^ |   +5 Wow, we have the same rating! Hope for the best results :)
•  » » » 4 weeks ago, # ^ |   +3 We failed together XD I believe we can do it soon:D
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Did you get positive rating? It's bad luck for us QQI think that I will rest for some time, after taking a regional contest yesterday I'm a little tired to solve more problemHope u can do it as fast as possible :)
•  » » » » » 4 weeks ago, # ^ |   0 Wow..I think you should have a rest:D I will take part in a regional contest in Nanjing:) To be honest,I am nervous because I got a bad rank last regional contest:(
•  » » » » » » 4 weeks ago, # ^ |   0 Wish u a good luck and making the best performance! :) Yesterday was my first time traveling to the other city for a contest, actually not having a good outcome make me a little sadmaybe I need some time to adjust myself...I'll take your advice, thanks. XD
 » 4 weeks ago, # |   -55 So where is div3 for guys who cant solve div2.A like me? :D
 » 4 weeks ago, # | ← Rev. 2 →   +21 Multiple contest in a Queue.. Thanks codeforces ...
•  » » 4 weeks ago, # ^ |   0 Yes!
 » 4 weeks ago, # |   +26 A big team of the problem setter!
 » 4 weeks ago, # |   -11 Also a friendly time for Chinese!
 » 4 weeks ago, # |   +148
•  » » 4 weeks ago, # ^ |   +4 Relatable :(
•  » » 4 weeks ago, # ^ |   0 Joining the club :|
•  » » 4 weeks ago, # ^ |   +2 And Really you become pupil..
 » 4 weeks ago, # | ← Rev. 2 →   0 Great
 » 4 weeks ago, # |   +2 Tonight I'm gonna sleep a lot :]
 » 4 weeks ago, # |   +17 Lol, why are grikukan and V--gLaSsH0ldEr593--V both mentioned? Aren't they the same person?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +46 They are different people.grikukan and team never won ICPC.gritukan and team won ICPC 18.V--gLaSsH0ldEr593--V and team won ICPC 19.Updated.
•  » » » 4 weeks ago, # ^ |   +14 gritukan won ICPC 18. Not grikukan.
•  » » » » 4 weeks ago, # ^ |   +83 my head hurts, is this div 1 E?
•  » » » 4 weeks ago, # ^ |   +1 If only I knew this trick when I was competing.
•  » » » 4 weeks ago, # ^ |   0 All three ids link to the same page.. So it's three people using one account?
•  » » » » 4 weeks ago, # ^ |   +12 They are just 3 different handles of same account
•  » » 4 weeks ago, # ^ |   +13 Huh..are people openly allowed to create multiple accounts?
 » 4 weeks ago, # |   -6 I hope I will become CM :)
 » 4 weeks ago, # | ← Rev. 2 →   -21 Good Luck then
 » 4 weeks ago, # |   0 score distribution??
 » 4 weeks ago, # |   +3 Hope to become Blue today. Good luck all!
 » 4 weeks ago, # |   -42 Is the round rated?
•  » » 4 weeks ago, # ^ |   +75 Sure
 » 4 weeks ago, # |   -18 score distribution ?
•  » » 4 weeks ago, # ^ |   +31 You'll find out in a minute, why so impatient?
 » 4 weeks ago, # |   +48 About the order of difficulty......
 » 4 weeks ago, # |   +97 Div1 C is the most frustrating problem ever made
•  » » 4 weeks ago, # ^ |   +9 wth is pretest 4
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   +37 Pretest 4 (i think) is a situation when there actually can be a queue before the tank. Once you understand this situation, you understand the pretest.(idk, maybe it's obvious, but I understood this only after like an hour of solving).
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 You need to read the statement multiple times — there is a queue involved too. (Unfortunately, I made an implementation bug somewhere probably and failed on pretest 10, back to CM for me :/)
•  » » » » 4 weeks ago, # ^ |   0 After two wrong submissions, I realized oh queue is also involved, then I got what is wrong with my code, but didn't get the time to implement it.
•  » » » 4 weeks ago, # ^ |   +8 maybe sth. like 5 10 5 4 3 2 1 
•  » » » » 4 weeks ago, # ^ |   0 what should the answer to be for this instance
•  » » » » » 4 weeks ago, # ^ |   0 51 41 31 21 11 
•  » » » » » 4 weeks ago, # ^ |   +8 At 1-th minute, the fifth people go and take water. But at the 2-th minute, the fourth people want to take some water, and find that all people before him is sitting there, so he will go and wait behind the fifth person.So actually there is also a queue in the place where the water is taken.But during contest, I didn't realize there is a queue, and I checked my code for an hour, thinking there is nothing wrong. LOL
•  » » 4 weeks ago, # ^ |   0 I felt this way about div1 B. Not sure if my solution or implementation was wrong but having to reconstruct made it much more work.
 » 4 weeks ago, # |   0 in Div2-C, what is pretest 7 ?
•  » » 4 weeks ago, # ^ |   0 n = 2; m = 5.
•  » » 4 weeks ago, # ^ |   0 what is the idea of C ?
•  » » » 4 weeks ago, # ^ |   0 Fibonacci
•  » » » 3 weeks ago, # ^ |   0 find a few facts then you can use backtrack and dp to find the answer I thing tutorial is published and you can read it to find your answer Good Luck ;)
 » 4 weeks ago, # |   +43 difficulty balance be like
 » 4 weeks ago, # |   +89 The one, who came up with such a great problem as Div1B : you can go and prepare problems for yourself.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 how to solve easy version of it with n <= 500.
•  » » » 4 weeks ago, # ^ |   0 brute force the two swapping positions and then count the number of satisfied cyclic shifts.
 » 4 weeks ago, # |   +5 I think in every new round setter competes with the previous setters for setting more difficult problems.
 » 4 weeks ago, # |   +10 So I think I made a <= 3 character bug for 2 consecutive rounds......
 » 4 weeks ago, # |   +10 This is what you call a truly imbalanced contest!
 » 4 weeks ago, # |   +93 Wow, B was really hard and annoying for a div1B. Does anyone have an easy solution?I only realised with 2 minutes left that the queue-stuff from C's statement was actually relevant, since for example passenger 2 could get ready to get water at time 1, and passenger 1 at time 2, then passenger 1 sees no empty seats in front of him and goes to the queue. Would have been nice to have a sample that shows that this is possible :/
•  » » 4 weeks ago, # ^ |   +79 OMG ! Div1 C = English test :/
•  » » » 4 weeks ago, # ^ |   0 LOL.
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +108 In case too many passengers will go for boiled water simultaneously, they will form a queueOk, so there is a queue. Nobody likes to stand in a queue.Oh, so no queues? There is an unspoken rule, that in case at some moment several people can go to the tank, than only the leftmost of them will go to the tank, while all others will wait for the next moment.Alright, no queues it is. This is what I was thinking.
•  » » » 4 weeks ago, # ^ |   +8 This is exactly what I was thinking, too. LOL
•  » » 4 weeks ago, # ^ |   +6 I'm not sure if it's that hard as a solution, but it's easy to get lost looking for it. The quantity we're maximising is the number of minimum prefix sums. If we swap parentheses $i$ and $j$, prefix sums $i+1$ through $j$ change — either they increase by 2 or decrease by 2, depending on parenthesis $i$.Obviously, if we don't select all occurrences of the current minimum, the resulting minimum of all prefix sums can only decrease, by at most 2. If we select it, then the resulting minimum can only increase or decrease by at most 2 as well. We can now try all possibilities for the resulting minimum and "increase/decrease", since there are $O(1)$ of them.If we want minimum $m$ with "decrease", all prefix sums in the range $[i+1, j]$ must be at least $m+2$, at least one must be exactly $m+2$ and all prefix sums outside this range must be at least $m$. For a fixed $i$, we can choose the maximum $j$ such that the first condition holds, i.e. prefix sum $j+1$ is $m+1$, and check the other conditions. Since $m$ is fixed for all $i$, this runs in $O(N\log{N})$ and maybe even $O(N)$.If we want minimum $m$ with "increase", all prefix sums in the range $[i+1, j]$ must be at least $m-2$, at least one must be exactly $m-2$ and everything outside this range must be at least $m$. It can be solved in the same way.It needs more ideas, but they're not really that hard.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 My ideas were using a stack: If we push the string on to a stack and keep popping the matched ones, we will be left with $..))((..$ Then you swap the first and last of the leftover on the stack. Do above with string s[n-1]s[0..n-2]. (to tackle $(()())$ case) Print max of the two as answer.
•  » » » 4 weeks ago, # ^ |   +15 You could further simplify it by assuming when we swap parenthesis $i$ and $j$, instead of the prefix sums $i+1$ through $j$ increasing by 2, the remaining prefix sums decrease by 2. Now, if the original minimum is $m$, then you just need to consider 2 cases, where the minimum $m'$ is $m$ or $m - 1$.The above simplification also reduces the search for the segment to $O(n)$, since for each case, you can just loop over the string and keep a count of elements exactly equal to $m' + 2$ and reset whenever you find an element $< m' + 2$Submission for reference: https://codeforces.com/contest/1239/submission/62998813
•  » » » » 4 weeks ago, # ^ |   0 I actually simplified by rotating the string so the minimum is $0$. Then we don't want to increase anything. Still, that's an extra idea and the shortest path to knowing you have a working solution is more along the lines of what I wrote — $O(1)$ cases and queries for range minimum.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +5 First note that any string that can become balanced with one swap, can be rotated to be balanced. So no need to waste the swap here; find the prefix with the minimum sum ( = 1, ) = -1 and move it to the end.If the string is still not balanced, the answer is 0.Otherwise we need to use the swap to maximize the number of balanced parts in the first level (...)(...)(...).There are two cases: (()x()()y): swapping x and y will move the parts between them to level zero and will create one more part to the left, so this swap adds 3 to the base answer. Swapping the two ends of any part in level 0 (...) will leave 1 + the number of parts between them. For example (()()) -> )()()( which is ()()(). In a single pass with a stack, you can consider the two cases for all ends and maximize the answer: 63011541
 » 4 weeks ago, # | ← Rev. 2 →   0 Div 2 D, what would be a correct way to compute a string's beauty? I've tried finding the string's longest suffix where the number of opened parenthesis is greater than the number of closed parenthesis, cycle the string so that become a prefix, then find out the number of concatenations this new string is made with (0 if the string is not valid). Wrong answer on test 8.
•  » » 4 weeks ago, # ^ |   0 You mean div2 D
•  » » » 4 weeks ago, # ^ |   0 Oh yeah, thanks mate
•  » » » » 4 weeks ago, # ^ |   +3 Isn't the number of 0's in the prefix sum of a string equal to its beauty?
•  » » » » » 4 weeks ago, # ^ |   0 how could you explain?
•  » » 4 weeks ago, # ^ |   +3 I did finding and counting all such suffixes such that $N_{closed} - N_{opened}$ in the suffix is less or equal than $min(N_{opened} - N_{closed})$ on all prefixes. Also make sure that overall $N_{opened} = N_{closed}$.
•  » » 4 weeks ago, # ^ |   +11 If the string contains an equal number of 1's and -1's, the beauty equals the number of minimum prefix sums. However I think what you described should work as well. Maybe there's a bug?
•  » » » 4 weeks ago, # ^ |   0 Could be a bug, I'll wait to see the test it fails on and try debugging with it. Thank you for your explanation!
•  » » 4 weeks ago, # ^ |   +3 Using stack and then while inserting least recently used opening bracket may be tracked and counter increased when it matched. (for D1, do for all n rotations)
•  » » 4 weeks ago, # ^ |   +4 String's beauty is number of minimal balances, if balance of all string is 0; (Balance is number of '(' on prefix minus number of ')' on prefix)
 » 4 weeks ago, # |   0 The first problem is poorly explained.
 » 4 weeks ago, # |   +3 how to solve div2 c ??
•  » » 4 weeks ago, # ^ |   -12 Bruteforce + finding pattern for answer
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +5 I sent $\big(m$-th Fibonacci number $+$ $n$-th Fibonacci number $- 1\big)\cdot 2$. No idea why.
•  » » » 4 weeks ago, # ^ |   0 Wow, that's a very clever approach, and a valid one too i think according to dp states... With matrix exponentiation we could have even solved for very large n,m then...
•  » » » » 4 weeks ago, # ^ |   +1 Yes, with $n,m \le 100000$ you can just calculate them directly.
•  » » » » » 4 weeks ago, # ^ |   0 Yes
•  » » » 4 weeks ago, # ^ |   0 Was trying to make the product of Fibonaccis work. Can't prove why this works when n != 1 and/or m != 1. Any suggestions?
•  » » » 4 weeks ago, # ^ |   0 please could you explain the idea behind it
•  » » 4 weeks ago, # ^ |   +2 Consider there is only 1 line. You can use a easy DP to get that there are $S$ ways to color the first line. Except ways $101010...$ and $010101...$ there are $S-2$ ways to color the line with surely $\ge$ one pair of $00$ or $11$.For these $S-2$ ways of coloring the first line ,because they contain substrings $00$ or $11$ ,there is excatly $1$ way to color the rest for each ways. So the contributions to the answer is just $S - 2$For $101010...$ and $010101...$ ,in the rest lines ,there is no way to color $00$ or $11$ in a line but maybe in a column. And you can use the same DP to solve it.
 » 4 weeks ago, # |   0 Did anyone try hard to push cubic solution for Div2D1?
•  » » 4 weeks ago, # ^ |   0 My solution is cubic, it passes pretests
•  » » 4 weeks ago, # ^ |   0 Isn't the intended complexity cubic? My cubic solution passed pretests in 529 ms.
•  » » » 4 weeks ago, # ^ |   0 My cubic is TLE#8. Ok, maybe my solution isn't as cubic as it need to be.
•  » » 4 weeks ago, # ^ |   +4 $O(n^3/2)$ will pass
 » 4 weeks ago, # |   0 HOW TO SOLVE DIV 2C?
•  » » 4 weeks ago, # ^ |   0 try to solve the problem for 1 * m table . then you can see that in only 2 cases second row isnt unique
•  » » 4 weeks ago, # ^ |   +2 Try to make just 1 contiguous equal pair, you'll find that you cannot place any vertical contiguous equal pair if horizontal is present and vice versa, ie, the other one is alternate.Also a row or a column can only repeat at max 2 times in an assignment, and there are only 2 types of those, alternate, so I ran a dp of n*2*2, and another along column m*2*2, and just added their final states at n,m respectively.States were (position, current type of row(column), length of contiguous sequence till then). Also at the end remember to subtract 2 from answer so as to avoid the repetition of case when no contiguous blocks are equal.... Hope it helps!
 » 4 weeks ago, # |   +194 You forgot to sort problems
 » 4 weeks ago, # |   +30 Every contest seems to be highly unbalanced after the tourist balanced round
 » 4 weeks ago, # |   +9 Hi,Regarding Div2D, Can it be proved that a string with equal number of '(' and ')' can be made correct by a certain k-rotation?
•  » » 4 weeks ago, # ^ |   0 Yes, if you push given string on the stack, and pop matching ones, you will be left with something like $...)))(((...$ always, and then you can rotate the mid point to balance everything.
•  » » » 4 weeks ago, # ^ |   0 Oh. That was easy. Thanks!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Yes, you can pick a k-rotation, such that count of '(' minus count of ')' on prefix n-k is minimal
 » 4 weeks ago, # |   +27 Can I meet Balanced Problem Set ever??
 » 4 weeks ago, # |   +1 How to solve div2d easy in O(n3) time.
 » 4 weeks ago, # |   +1 How to solve Div1 D/Div2 F? Does any greedy work for the case when the bipartite graph is completely connected , i.e., just 1 connected component ?
•  » » 4 weeks ago, # ^ |   +13 Edges are actually directed so think of SCC. There's an answer iff there's more than 1 SCC.
•  » » » 4 weeks ago, # ^ |   0 Ya got it, thanks. I wasn't considering directed edges and hence was always getting answer for more than 2 connected components and wasn't able to think how it works for just 1. But on scc the same logic works, just answer no for 1 scc.
•  » » » 4 weeks ago, # ^ |   0 Damn, I was thinking of SCC number but for some reason I directed some edges in both directions >_<
•  » » 4 weeks ago, # ^ |   +5 My solution is, given the input graph, you just need to create strongly connected components and then, if there is only one, output "NO".
 » 4 weeks ago, # |   +6 I think I can get substantial increase in rating in the next round given the distance from my average rating -_-.
 » 4 weeks ago, # |   0 OMG!!!! problem C takes me over 1 hour,but D only 30 minutes.unluckily when I pass all the examples in problem D ,it's 3 minutes after the contest. :(
•  » » 4 weeks ago, # ^ |   +2 Don't you mean D1? D1 is less points than C.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 Yes,however I still get TLE after contest. :(
 » 4 weeks ago, # |   0 Strong pretest and no successful hacking attempt in div 1. Yeah!
 » 4 weeks ago, # |   +104
 » 4 weeks ago, # |   +23 Hardest div1A for me, back to div2..
•  » » 4 weeks ago, # ^ |   +31 welcome :)
•  » » 4 weeks ago, # ^ |   +47 This is the first time I saw Div1A and Div1D of the same diffculty.
•  » » » 4 weeks ago, # ^ |   +26 This is the first time I saw Div1A much harder than Div1D.
 » 4 weeks ago, # |   +6 Today I learned that Python has a preset recursion limit of 1000. Cost me Problem C lol
 » 4 weeks ago, # | ← Rev. 3 →   +9 This round reminds me of the Codeforces Round #588 (Div. 2) on which the problem set was created by Radewoosh
 » 4 weeks ago, # |   +240 A random picture
•  » » 4 weeks ago, # ^ |   +2 What's wrong with that, if B and C were both 1250?
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +60 In fact D1D is also random, but it's not strictly a "random picture" discribed in D1A.I think the main reason is that D1D is 2000, if it's 1250, we'll have a random picture with 3 columns.
•  » » » » 4 weeks ago, # ^ |   0 This guy(gal?) randoms
 » 4 weeks ago, # |   0 setter should not have made div2d only 750 points. It was more hard than a,b,c combined. I earlier thought bf with n4 would pass but it didn't. then i realised that its not as easy as it is mentioned.ch_egor
 » 4 weeks ago, # |   -18 Great contest, fast testing (during and after). Fun problems that required more thinking than edge-cases and writing. Thank you all involved in writing, keep em coming :)
 » 4 weeks ago, # |   +19 These days are crucial for contestants with poor math skills :|
•  » » 4 weeks ago, # ^ |   0 Damn right! Brother
 » 4 weeks ago, # |   0 It was the best round I had participated in from a long time
 » 4 weeks ago, # |   +3 I believe today's contest (Div. 2) was awesome, for me personally at least, with less system test failure's and a good and simply code-able problem C.....Looking forward to such and even better contests in future on codeforces!
 » 4 weeks ago, # |   +61 This round reminds me of Codeforces Round #543 (Div. 1, based on Technocup 2019 Final Round). How on earth is D worth more than B?
 » 4 weeks ago, # |   0 why is this submission got WA on pretest 4?I thought passanger 1 gets the boiled water at 2000000009, because after the first person (idk which index, but seeing the result has suffix 9, it must be 9), every passanger already wanted to take the boiled water, but the leftmost (index=1) will be getting the boiled water first.
•  » » 4 weeks ago, # ^ |   0 Because when passenger 3 wants to cook their noodles, he checks the chairs left to them. In this case no one has left their seats so passenger 3 would definitely get their noodles cooked before passenger 1 does.
 » 4 weeks ago, # |   +1 Why do cubic solutions pass on D1?
•  » » 4 weeks ago, # ^ |   +1 500^3 == 1.25*1e8 It is well within time limit
•  » » » 4 weeks ago, # ^ |   +27 My whole life was a lie.
•  » » » » 4 weeks ago, # ^ |   0 Yes! despite getting to bruteforce solution I didn't submit cause of above calculation and given 1s time limit :(
 » 4 weeks ago, # |   +3 Div 2 Problem E Can someone justify why 3rd value in the answer is less than the 1st one?? Shouldn't it be greater?
•  » » 4 weeks ago, # ^ |   0 Because when passenger 3 wants to cook their noodles, he checks the chairs left to them. In this case no one has left their seats so passenger 3 would definitely get their noodles cooked before passenger 1 does.
•  » » 4 weeks ago, # ^ |   0 I have the same output like you ??? I don't know where i was wrong in reading the statement :V But i don't know why the answer can reach 1e10 when p<=1e9 and ti<=1e9 :V It doesn't make any sense ???? Pls explain too me .Tks you ans sorry for my poor English
 » 4 weeks ago, # |   0 There is a mistake in the statement of problem D. Instead of"Cyclical shifts i and j are considered different, if i/=j"it should be"Cyclical shifts by i and j are considered different, if i/=j".It can be deduced from the examples though.
 » 4 weeks ago, # |   0 how can we prove the solution for div2C ?
•  » » 4 weeks ago, # ^ |   0 If you filled the first row cells and first colm cells you will find that there is only one way to fill the remaining cells
 » 4 weeks ago, # |   0 Can anyone explain the soluition of F?? Why SCC is used in this question.. Thanks in advance
 » 4 weeks ago, # |   0 waiting for editorials: )
 » 4 weeks ago, # |   +11 TIL that seats can be busy.
•  » » 4 weeks ago, # ^ | ← Rev. 4 →   0
 » 4 weeks ago, # |   0 Another Mathforces.
 » 4 weeks ago, # |   +9 I found these submissions: 62996146 62993334. It really looks like they were cheating.
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +1 Codeforces plagiarism checker is really very bad that they can spot these same codes with some variables changed. Nice done buddy, I think admin must look into this once.
 » 4 weeks ago, # | ← Rev. 4 →   +6 The tutorial of C said that it's a strip problem and the solution seems easy... But the question is what is a strip prolem... Am I retarted?
•  » » 3 weeks ago, # ^ |   0 You should look on case when n = 1. It will help to understand whole problem.
•  » » 3 weeks ago, # ^ |   0 It can be solve by easy dp. dp[i][j] — number of such coloring, if last j colors are equal.
•  » » 3 weeks ago, # ^ |   0 The same question =))
 » 3 weeks ago, # |   0 O(n) solution for div2.B is to use count sort ?
 » 3 weeks ago, # |   0 what is the idea behind Div2 C? Didn't get the editorial.
 » 3 weeks ago, # |   0 why am I getting a TLE here: https://codeforces.com/contest/1248/submission/63239483 the Algo is same as the editorial.