### MikeMirzayanov's blog

By MikeMirzayanov, 4 years ago,

Thanks for taking part in the round. I hope you enjoyed the round. It happens that the statements were really easy to understand (thanks to testers). We've got only 38 questions during a round!

Code
Code
Code
Code
Code
Code
Code

• +39

| Write comment?
 » 4 years ago, # | ← Rev. 3 →   +1 MikeMirzayanov, in code of 1141B - Maximal Continuous Rest should be if (a[i % n] == 1) but there is if (a[i % 2] == 1).
•  » » 4 years ago, # ^ |   +2 Thanks, fixed.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 why is this on my 'recent actions' page
 » 4 years ago, # |   +1 Thank you so much MikeMirzayanov for this round... I enjoy the problems a lot...
 » 4 years ago, # | ← Rev. 3 →   +10 E can be solved using binary search also .
•  » » 4 years ago, # ^ |   +13 Yes, see this
•  » » » 4 years ago, # ^ |   +1 can you please explain , how are you applying binary search, I couldn't solve it in contest because I couldn't find sum to be monotonically increasing or decreasing
•  » » » » 4 years ago, # ^ |   +2 The answer exists only when H becomes zero in the first round, or $\sum_{i=1}^{\ n} d_i <0$ . If $\sum_{i=1}^{\ n} d_i >= 0$ , print "-1". So, after each round H decreases by some amount, now binary search for the first round in which H becomes negative.
•  » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 I also thought to use binary search but could not come up with any idea so i did greedy. Also your code uses the similar idea so binary search can be avoided. Anyway nice to see a binary search solution.
•  » » » 4 years ago, # ^ |   0 +1 for username.
•  » » » » 4 years ago, # ^ |   0 :)
•  » » 4 years ago, # ^ |   0 Yes but its complexity would be high
•  » » » 4 years ago, # ^ |   0 no
•  » » » » 4 years ago, # ^ |   0 You are doing a binary search and in each search, you are iterating the whole array to find the answer.
•  » » » » » 4 years ago, # ^ |   0 nlogn
•  » » » » » » 4 years ago, # ^ |   0 That's what I am saying. It can be done in O(n)
 » 4 years ago, # |   0 Thank you for this good editorial.
 » 4 years ago, # |   0 Can someone please this, why I'm having Memory Limit Exceeded, on the implementation I did, while editorial says the same.51582194Thanks, in advance.
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 Please see the memory taken by your code, it is more than 250 MB.
•  » » » 4 years ago, # ^ |   0 :D that is ~250mb not gb.
•  » » » » 4 years ago, # ^ |   0 Yeah thanks, I just wrongly read that.
•  » » 4 years ago, # ^ |   0 Try using int
•  » » » 4 years ago, # ^ |   0 Nothing happened, did give a try.
•  » » » » 4 years ago, # ^ |   0 Do not use deque
•  » » » » » 4 years ago, # ^ |   0 Any specific reason??
•  » » » » » » 4 years ago, # ^ |   +4 I have heard that deque uses more memory. I just found this also https://stackoverflow.com/questions/16252183/why-is-deque-using-so-much-more-ram-than-vector-in-c Give it a try I think it should work.
•  » » » » » 4 years ago, # ^ |   0 BTW, it got accepted, but it'd be too good if you can explain the reason.Thanks.
•  » » » » » » 4 years ago, # ^ |   +1 Though this implementation is in Java but I think you can look at this also https://codeforces.com/blog/entry/10444
 » 4 years ago, # |   0 How should I approach Problem D in Java? I m not able to get the structure of code for this problem in java.
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 Not sure if you're still looking for a response, but my approach was as follows: Use ArrayDeques for each letter or '?' to store the indices. Then, when matching letters I just polled left and right until either went empty and then matched rest with '?' if I had any '?' remaining. In the meantime, you can track how many pairs you have created and use StringBuilder's insert method to put that at the front of the output. Code: https://codeforces.com/contest/1141/submission/51599198
 » 4 years ago, # |   0 For problem "Same Sum Blocks (Hard)" for finding all the possible sum if I do the loop like this map> > mymap; for(int i=0;i
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 It's a famous CS problem- Interval Scheduling.You sort the pairs by the end points and then greedily choose the disjoint intervals. My solution- https://codeforces.com/contest/1141/submission/51669831
 » 4 years ago, # |   0 Is there an intended slower solution that was meant to pass F1 but not F2 ?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Sure. I did the following. The idea is much more standard but might be trickier to implement if you lack experience at dp. Find all different sums of the segments. Now for each one you can do $dp[i]$ — the maximal number of disjoint segments of this sum up to position $i$. Updates can be done straightforwardly by iterating over all $j < i$ and checking if the sum between $j$ and $i$ is the current one or not. That's $O(n^4)$ at best ($O(n^5)$ if no prefix sums). 51606155Btw you can also AC f2 if you do updates in $O(1)$ instead of $O(n)$ lol. That would be $O(n^3)$. 51606140
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Why your $O(n^3)$ solution passes. :xD. Isn't $n=1500$ too much for $n^3$.
•  » » » » 4 years ago, # ^ |   +3 Welp, I just believed that there are not that many distinct sums such that each of them appear at least twice) Apparently, the number is less than expected $O(n^2)$. I'd be glad to hear the countertest)
•  » » » 4 years ago, # ^ |   0 Hi Mike, Thanks for your reply. I appreciate you taking the time to explain your solutions. :)
•  » » » 3 years ago, # ^ |   0 Isn't the dp part just like finding the LIS?
 » 4 years ago, # |   +1 1141A - Game 23 can be also solved using dfs.
 » 4 years ago, # |   0 For problem G I thought of first painting the k vertices which have maximum number of neighbors i.e. to paint the k maximum neighbor vertices with color 1 and then paint rest of the vertices. The number of colors required would be then the maximum number of neighbors of remaining n-k vertices. I don't know how to implement this also whether this approach is correct or not.Has someone else followed this strategy.
•  » » 4 years ago, # ^ |   0 hello .......
•  » » » 4 years ago, # ^ |   0 you can find the (k+1)th largest degree let's say 'd' and this is the maximum number of color needed to color the graph. Now, you can use DFS to color the edges by initiating some variable let's say 'c' with some integer in between 0 to d-1(assuming 0 indexed color) and each time when you move to unvisited vertex make c = (c + 1)%d.
 » 4 years ago, # |   0 Anyone else having problem with problem G test 24 ?
 » 4 years ago, # |   0 In code of 1141G — Privatization of Roads in Treeland why was it necessary to set f=-1 after color and f became equal?
 » 4 years ago, # |   0 Can someone explain me what went wrong in this (my solution for problem E)
 » 3 years ago, # |   0 In problem G for (auto p: cnt) if (kk > k) D = p.first, kk -= p.second; else break; how we get that D we get from the above loop is the minimum
 » 2 years ago, # | ← Rev. 3 →   0 Interesting problems, thanks.
 » 5 months ago, # |   0 Binary Search Solution for problem G Simple solution
 » 4 weeks ago, # |   0 "vector
 » 4 weeks ago, # |   0 187545653 O(n) solution for B.