Can we stop the racism towards India? India's population is more than a billion, of course you'd find the good and the bad.

https://mirror.codeforces.com/contest/1249/problem/D1

This problem is rated 1800. I don't consider myself good or have solved a considerable amount of problems, but atleast good enough to identify that this problem rating doesnt deserve to be more than 1200.

The problem asks us for each point on a number line, if it has more than k segments covering it, we need to remove from them until their count is <= k, only catch is that we want the minimal removals, to achieve that if we sweep from left to right the obvious optimal choice is to always remove the segment which is covering the most from the right, aka the segment with the maximum ending, pretty straightforward.

A "self understandable code" is very subjective, I recommend waiting for the full editorial.

For problem F, the problem statement says:

"You choose any vertex of the tree v (including the root or a leaf) and "shake" it. After that, cherries fall from all the leaves that are descendants‡ of vertex v (if vertex v itself is a leaf, then a cherry falls from it). If cherries have already fallen from any leaf before, the tree will break, so such a situation must be avoided."

And it identifies "Descendants of vertex v" as follow:

"‡The descendants of vertex v are all vertices u≠v such that on the shortest path from the root to u, vertex v is encountered."

Which I guess it is obvious enough (at-least for me & that I'm not missing anything) that if I for example choose any node to shake: then I can't shake it again or any other node below it. Why? because from my understanding if I shake a node then all cherries in its children will fall, if I then shake it again or any other node below it, it will also affect the leaves and the rule "If cherries have already fallen from any leaf before, the tree will break, so such a situation must be avoided." would apply. However in the editorial of the analytical solution for F, it claims that I should initially shake the root node, then I can shake anything I want as long as it's not a leaf, how so? Shouldn't the rule still apply?

I would jokingly say my only tip to doing codeforces in your phone is not to do it, because from my experience it's extremely frustrating as everything is very slow (even though I'm a fast typer) and youd need a well prepared ide and that was difficult to find for me, but I would advice you to attempt a virtual contest or solve a couple of problems on your phone before you actually join the contest to get used to it if you really insist

Can someone explain C?? Preferably the pure mathematical solution??

I was thinking it might include some linear diophantine, just had no clue how to get max possible candies...

Okay fine... I might be stupid for missing the "=" edge case in A in my solution and I deserve to be hacked, but I'll excuse myself as I only had 3 minutes total to get the problem accepted so not much time thinking... But how'd the problem creator miss it?! :S

Thank's alot! It was a good contest, keep it up!

Thanks I think I got it.

I am assuming the idea behind this is that O(n^2) means for every iteration i from 1 to n I will also iterate with j from 1 to n, which is not the case here, no, here the worst case would only happen when iteration i is equal to n — 1 (assuming 0-index) and the condition (seen.size() == curr.size()) is satisfied, in this worst case, the whole array is only cleared ONCE in the whole loop, and the iterations prior to i == n — 1 would be simply O(logN) I am not clearing anything just basic if conditions and set.inserts, so even saying that this is the worst case overall is debatable, it probably just isn't.

In other words the solution fits the time perfectly.

Does anybody know the time complexity for the second code for problem C?

I am looping over all elements which is O(n), but every now and then I clear seen, I am assuming the worst case for seen is to be holding almost all of the elements which also makes clearing it O(n), making the worst case to be O(n^2)..

The solution makes absolute sense but how does it pass? Doesn't seem optimal.