Блог пользователя Xellos

Автор Xellos, история, 8 лет назад, По-английски

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
  • Проголосовать: нравится
  • +107
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

I think even chrome missed this SRM. :D

»
8 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится -30 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Can div1 900 be solved by dfs using convex hull?