Golovanov399's blog

Codeforces Round #543 and Technocup 2019 Final Round Editorial
By Golovanov399, history, 6 years ago, translation, In English

We are sorry for not having controlled the situation about the streamed editorial and also for the broadcast message about an unethical behaviour of someone from community: here is explanatory comment to the message. When we tried to move the casino problem one position below, something went wrong leading to it being moved one position above (however, Radewoosh didn't seem to feel that something was wrong, congratulations!).

Nevertheless, we hope that you liked the problems, and those of you who decided to do something else after you knew that the round was made unrated can solve the problems when convenient (if they wish).

Problem A of final/div2 (Technogoblet of Fire)
Problem B of div2 (Mike and Children)
Problem B of final/C div2 (System Testing)
Problem C of final/D div2/A div1 (Diana and Liana)
Problem D of final/F div2/C div1 (Compress String)
Problem E of final/E div2/B div1 (Once in a casino)
Problem F of final/D div1 (Power Tree)
Problem G of final/E div1 (The very same Munchhausen)
Problem H of final/F div1 (Secret Letters)
  • Vote: I like it
  • +157
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Golovanov399 (previous revision, new revision, compare).

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

Anyone please link analysis to contest page.

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

It would be nice if you could provide the codes to the solutions of the problems. I think people would like to see how some things are implemented. I see the idea but don't know how to write it down (I'm still a noob :P)

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

    Same here, but if you really want to know the implementation just go to the Standings of the contest and look for submissions of other people.

    For example in Div2, Diazzz has some nice clean solutions that should be understandable. It took him 3 minutes to solve a task I couldn't do in 2 hours.

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

Hello, guys. Can anybody explain me, how we can check the necessary condition of interest on each test of each solution in task C (div.2) ? I have already made array with start solution treatment time.

→ Reply
»
6 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Diazzz's solution, for Div2 C (System Testing) uses an array used, which signifies that a solution i will be "interesting" only a single time.

I was confused, because in the third example input of the question, processes 1 and 5 will be testing case 36 at 36% completion. So, a total of 7 should be the answer. But if one reads the question carefully, it can be found that the number of interesting solutions is asked, and not the number of times the condition mentioned above is fulfilled. Therefore, even though the condition is met more than one times for a solution, only 1 will be added to the answer.

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

    Thank you Mooncrater. I really stuck with it before I found your remark.

    → Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it
1120D

so the most non-trivial (at least for me) part of this solution, how to calculate the answer, is just omitted in this editorial. lol

→ Reply
»
6 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Please help me with task C(div.2), the solution is not full enough. I am trying to solve it for 4 hours.

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

It is funny that I can use KMP + binary search + dp for problem F div2

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

Div1D: Why do it have to be spanning tree? Making components, which every has sum on nodes equal to 0, isn't sufficient?

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

No mention of DP solution for Div1 D?

We can calculate min cost of (1) setting all leaves in the subtree to zero (or any given number, since it's the same), and (2) setting all leaves in the subtree to any number as long as it's the same.

For (2) we need to set one child subtree to any number (2), and then set all other child subtrees to the same number (1).

For (1) we either set all child subtrees to zero (1), or set the entire subtree to the same number and then buy the root node.

Once we calculated the answer we can do the same process again and collect the resulting set optimal nodes (it seems too expensive to try to collect it on the first run).

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

I realise I'm rather late to this, but there is a simpler O(N) solution to F that doesn't require any convex hulls.

Suppose P sends a letter via R at time t0. Let the next time W sends a letter be at time t1. By considering a few cases, one can show that it is always optimal for W to send that letter via R (it can make that letter more expensive, but by at most the same amount it saves on the cost of P's letter by picking it up earlier).

Next, as noted in the original analysis, if P also sends a letter at time t (t0 < t < t1), it should go via R iff t1-t <= d/c. We can now use DP to answer the question "what is the cost of sending letters i..N if letter i goes via R?" by sweeping i downwards. To compute this, assuming P sends letter i, we need to know

  • the index and time (t1) of the next letter from W

  • the number and cost of letters from P in the interval [t1 — d/c, t1) that come after i, assuming they are collected at t1 by W.

As we consider each i, we also consider it being the first letter to go via R and add d*i to the cost to obtain a candidate solution.

Solution: https://codeforces.me/contest/1120/submission/54658246

→ Reply