Whoa, did this SRM just pop up in their calendar? Didn't see it before.

Yeah, "Coder Calendar" didn't include it :/. I discovered that SRM in clist.by today, but already managed to forget about it, so thanks :P.

Dose the information of this SRM appear anywhere earlier than yesterday? I can't believe I miss it!

The one question that I always ask, How to solve Div1 250? :P

I sorted all edges and iterated over all pairs of them, added edges between both in a graph and checked if the whole graph is a strongly connected component. Will this TLE? Or is it wrong?

Why did most Binary Search solutions get TLE in Div1 250 ?

Edit: Also those who hacked, what made you so certain that 2500*2500*Log*(150000) will actually fail ? Was there a high constant factor ?

Here's an alternate solution to the 900 that I did in practice (I didn't know the SRM existed today!!!)

First compute the following functions on the tree: size of v's subtree, and the sum of distances from v to vertices in its subtree. I'll use the notation a ≤ b to mean that a is a descendent of b. Let p_v denote parent of v, and let opt_v denote the optimal choice in v's subtree. The key observation is that opt_v ≤ opt_pv. This is clear.

Now do a dfs. Starting from a vertex, compute the answer for its subtree before proceeding to its children. We can do this simply by walking down into a subtree if and only if it is greater than half of size of v's subtree. Now, when you visit a child u of v, if opt_v is not  ≤ u, then just do u as you normally would. Otherwise (for the at most one) child u such that opt_v ≤ u, we store that we have already gone down to opt_v, so when you look at u, you can start at opt_v when we walk down the tree. The complexity is amortized O(N), if you store all the distance transitions properly when doing the dfs.

Here's some code that does the end, with all distance transitions, etc.

In the first red. there is O(n) solution to div1hard.

I think even chrome missed this SRM. :D

I've upread (upsolve-solve+read) statements for stories. I appreciate what you've done in HardProof and TreeSums (especially in TreeSums). One smart idea and nobody can say that a problem was artificial.

Btw. that div2-easy PriorityQueue looked complicated (harder than usually), but maybe I forgot how easy that problem should be.

Point values of 500 and 900 definitely should be swapped :p. Hardest thing I encountered in easy was that Kate opens files with long lines in read only mode (my plugin includes samples), so I needed to open it in gedit and input few random enters :p. However hardest obstacle in "hard" was to observe that given pseudocode generates an array par so that par[i] stores parent of vertex i+1 xD (why not?, that should be logical :p). Btw just naively lifting centroid one by one from biggest son does the thing, no need for any jumppointers.

Well, only 392 people participated. Am I right, that this is the least number of contestants since SRM 241 in 2005? (missed it as well...)

Can div1 900 be solved by dfs using convex hull?