Xellos's blog

SRM 692
By Xellos, history, 9 years ago, In English

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
  • Vote: I like it
  • +107
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like 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. :)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      Why no mail?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like 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?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Of course it should TLE. You have O(N2) edges, so this is O(N6). There are hints now.

    → Reply
»
9 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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 pv denote parent of v, and let optv denote the optimal choice in v's subtree. The key observation is that optv ≤ optpv. 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 optv is not  ≤ u, then just do u as you normally would. Otherwise (for the at most one) child u such that optv ≤ u, we store that we have already gone down to optv, so when you look at u, you can start at optv 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.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +21 Vote: I do not like it

I think even chrome missed this SRM. :D

→ Reply
»
9 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -30 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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...)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Can div1 900 be solved by dfs using convex hull?

→ Reply