Seeing as there's no blogpost from chrome about the round a few hours before it...

TC SRM 692 starts soon. If you're up at night, you can participate!

**UPD**: Contest over! As you may have noticed, I was the writer; it's worth it to read the problem of both divisions just for the stories.

**Hints:**

**TreeSums**

**LinenCenter**

**HardProof**

**Dubs**

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!

It was mentioned here and in "Topcoder Data Science Newsletter — 06/3/16".

We couldn't update it in calendar due to some technical issues, now it is fixed. Now you can see next SRM will be on June 25 — don't miss it. :)

Why no mail?

"Topcoder Data Science Newsletter — 06/3/16" — this is the title of that email.

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?

Of course it should TLE. You have

O(N^{2}) edges, so this isO(N^{6}). There are hints now.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 ?

Maybe they suck. My binsearch passes, and it's written in Java. And I don't even code in Java if I can choose.

UPD: Downvote logic on CF again. If there's a solution which comfortably passes in a slow language, then it makes sense that any solution in that or faster language that fails would be bad in some way.

Mine passed in 1.4s in practice, using C++.

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 fromvto vertices in its subtree. I'll use the notationa≤bto mean thatais a descendent ofb. Letp_{v}denote parent ofv, and letopt_{v}denote the optimal choice inv's subtree. The key observation is thatopt_{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 childuofv, ifopt_{v}is not ≤u, then just douas you normally would. Otherwise (for the at most one) childusuch thatopt_{v}≤u, we store that we have already gone down toopt_{v}, so when you look atu, you can start atopt_{v}when we walk down the tree. The complexity is amortizedO(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...)

It was a night round, these have notoriously low participation... plus it wasn't in calendars. In fact, I spent a lot of time just trying to find a link to the starting time.

I'm surprised nearly 400 people heard about this round, missed it too...

Can div1 900 be solved by dfs using convex hull?