STommydx's blog

Codeforces Round #457 (Div. 2) Editorial
By STommydx, history, 7 years ago, In English

I would like to take this opportunity to express my deepest apology to all of you who take your own precious time to participate in this unrated round. Also, apologies to vintage_Vlad_Makeev who really helped a lot in preparing the round and MikeMirzayanov who helped to host the round, I did not do a good job in managing the round. As the main author of this round, I'm undoubtedly responsible for the mistake that not writing a brute force solution to test the correctness of the intended solution. It is my responsibility to make sure everything is right before the round starts. I am really sorry that the round must be unrated to ensure fairness to all contestants.

I hope all of you can learn something from the contest. Do not claim a greedy solution absolutely correct (like me :C) unless you have proved it. On the bright side, I'm really glad that some of you found problem D and E interesting as said in some comments in the announcement blog post. I admit that problem D may seem to be a quite standard data structure problem but we think it would be fun for less experienced contestants to think how to put the concepts learnt together.

Just a little unimportant fact: The original div2B problem was a harder data structure problem which involves a slightly complicate mathematical proof (which the current one doesn't have :C). We replaced it because it is too difficult for div2B as the coordinator suggested.

916A - Джейми и откладывание будильника

idea: STommydx, preparation: southball

Let's use brute force the find the answer. We first set the alarm time as hh: mm and initialize the answer as 0. While the time is not lucky, set the alarm time to x minute before and add 1 to the answer.

Why does this solution run in time? As x ≤ 60, hh decrease at most 1 for every iteration. Also, after at most 60 iterations, hh must decrease at least once. All time representation that hh = 07 (07:XX) is lucky so at most 24 times decrement of hh will lead to a lucky time. Therefore, the max. number of iteration possible is 24 * 60 = 1440 which is very small for 1 sec TL.

In fact, the largest possible answer is 390 where x = 2, hh = 06 and mm = 58.

My implementation: 34342125

916B - Джейми и двоичная последовательность (изменена после раунда)

idea: southball, preparation: STommydx

The main idea of the solution is 2x = 2·2x - 1, that means you can replace 1 x element with 2 (x - 1) elements. To start with, express n in binary — powers of two. As we can only increase the number of elements, there is no solution if there exists more than k elements.

Let's fix the y value first. Observe that we can decrease the y value only if all y can be changed to y - 1. So we scan from the largest power and try to break it down if doing so does not produce more than k elements. After y is fixed, we can greedily decrease the smallest element while the number of elements is less than k.

My implementation: 34342011

916C - Джейми и интересный граф

idea: STommydx, preparation: STommydx

First, observe that only n - 1 edges are required to fulfil the requirement, so we will make the other m - n + 1 edges with a very large number so they would not contribute to the shortest path or the MST. Now, the problem is reduced to building a tree with prime weight sum and two nodes in the tree have prime distance.

Recall that a path graph is also a tree! If we join (i, i + 1) for all 1 ≤ i < n, the shortest path will lie on the whole tree. We are left with a problem finding n - 1 numbers that sum to a prime. Let's make 1 edge with weight p - n + 2 and others with weight 1. Choosing a prime slightly larger than n (e.g. 100003) will fulfil the requirement for all cases.

My implementation: 34342305

916D - Джейми и список дел

idea: STommydx, preparation: STommydx

Let's solve a version that does not consist of undo operation first. The task can be divided to two parts: finding the priority of a string and finding the rank of a priority. Both parts can be solved using trie trees. The first part is basic string trie with get and set operation so I will not describe it here in details. The second part is finding a rank of the number which can be supported by a binary trie.

To support the undo operation, observe that each operation only add at most 31 nodes to the trie trees. Therefore, we can make use the idea of persistent data structure and store all versions by reusing old versions of the data structure with pointers. Remember to flush the output after each query operation.

As pointed out by some of you, there exists alternative solutions using persistent dynamic segment trees.

My implementation: 34342389 (sorry for a bit messy)

916E - Джейми и дерево

idea: longhuenchan, preparation: longhuenchan

Let's solve the problem without operation 1 first. That means the subtree of a vertex does not change.

For operation 2, the subtree of smallest size that contains u and v means the lowest common ancestor (lca) of u and v, and we update the subtree of lca. For operation 3, we query the sum of the subtree rooted at the given vertex. To do this, we can flatten a tree into an one dimensional array by considering the DFS order of the vertices starting from vertex 1. If a vertex has DFS order x and its subtree has size y, then the update/query range is [x..x + y - 1]. This can be done by standard data structures, such as binary indexed tree with range update function, or segment tree with lazy propagation.

Things get more complicated when the root of the tree r changes. One should notice that in order to reduce time complexity, we should not recalculate everything when r changes. We just need to keep a variable storing the current root. Now let's discuss the two main problems we face (In the following context, subtree of a vertex is defined according to vertex 1 unless otherwise stated):

How to find the LCA of u and v using the precomputed LCA table that assumes the root is vertex 1? Let's separate the situation into several cases. If both u and v are in the subtree of r, then query the LCA directly is fine. If exactly one of u and v is in the subtree of r, the LCA must be r. If none of u and v is in the subtree of r, we can first find the lowest nodes p and q such that p is an ancestor of both u and r, and q is an ancestor of both v and r. If p and q are different, we choose the deeper one. If they are the same, then we query the LCA directly. Combining the above cases, one may find the LCA is the lowest vertex among lca(u, v), lca(u, r), lca(v, r).

After we have found the origin w of update (for query, it is given), how to identify the subtree of a vertex and carry out updates/queries on it? Again, separate the situation into several cases. If w = r, update/query the whole tree. If w is in the subtree of r, or w isn't an ancestor of r, update/query the subtree of w. Otherwise, update/query the whole tree, then undo update/exclude the results of the subtree of w', such that w' is a child of w and the subtree of w' contains r.

The above ideas can be verified by working with small trees on paper.

longhuenchan's implementation: 34352491

We are glad to see some more elegant implementations by the contestants.

Feel free to discuss the problems below. I am happy to listen to feedback and answer questions from you guys. :)

  • Vote: I like it
  • +191
  • Vote: I do not like it

Comments Comments (39)
| Write comment?
»
7 years ago, # |
  Vote: I like it +65 Vote: I do not like it

Please provide editorial for Problem E also. Don't feel bad shit happens. Cheers to spirit of problem setters. :)

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

I followed the editorial for problem B but it still gives me WA. Can anybody tell me what I am doing wrong ? My solution

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

    So we scan from the largest power and try to break it down if doing so does not produce more than k elements.

    It seems that you have made a mistake on this step in your solution. You should try to break down all largest elements simultaneously(not just one by one).

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

    First decrease the y value only if all y can be changed to y - 1. And then in order to get the lexicographically largest one, split the smallest number. For example, while input is 7 9 , the output should be Yes
    0 0 0 0 0 0 -1 -2 -3 -3 , not Yes 0 0 0 0 -1 -1 -1 -1 -1 -1

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

It is interesting for me to attend such a contest though I have spent a lot of time in B in contest. But, you know, these thing always happen, please feel free about that.

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

For problem E, shouldn't the statement "the subtree of smallest size" should be the path between the nodes u to v. Because the path between the nodes u to v will be a subtree of the original tree and it will be the smallest subtree which contains both the nodes u and v.

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

Problem E, let curr be the current root of the tree. Assume lca(u, v) is lowest common ancestor of u and v on tree rooted at vertex 1. Let x  =  lca(u,  v), y  =  lca(u,  curr), z  =  lca(v,  curr), then the lowest vertex among x, y and z on tree rooted at 1 will be lowest common ancestor of u and v on tree rooted at curr.

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

I can't understand this part of code from problem B ( especially, what you are doing with 'm' ). Can you explain it more detailed, STommydx ?

for(int i=63;i>=-63;i--){
		if(m + cnt[i] <= k)
			m += cnt[i], cnt[i - 1] += cnt[i] * 2, cnt[i] = 0;
		else
			break;
	}
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    I used the variable m to keep track of the number of elements in the current answer. The code segment above is trying to fix the y value, that is, making the max. element smallest. Consider the current max. is i and we have cnt[i] instances of i. We can decrease the max only if we replace all i with (i - 1), that is replacing cnt[i] i s with cnt[i] * 2 (i - 1) s. So, if this operation will not make the number of elements larger than k, we do it. Otherwise, we proceed to the next step — breaking down the smallest element greedily.

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

Is there any reason why you so many tests on problem A?

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

    There were originally about 120 test cases set by the author. During contest, there were a lot of successful hacks on problem A. The hack cases were then added to the test set, resulting in the unintended huge amount of test cases.

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

Can anyone please, give me a further instructions on solving problem D.

or a link to a binary trie or persistent data structure explanation .

Thanks in advance :) .

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

how to do originally Problem B? what is slightly complicate mathematical proof you say?

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

    The original Div2B was cancelled as suggested by the coordinator it was too difficult, while there was a rigid proof of the correctness of the solution. It was then replaced by the current Div2B which fails.

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

      what i want to know is the solution for the original one which is more complicate

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

Does anybody know a similar problem to E? (For practice) Thanks!

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

What is wrong with solution for prob B? can anyone please explain?

http://mirror.codeforces.com/contest/916/submission/34405736

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

    your code ignore the condition that the output should be lexicographically largest , for example :

    7 5

    correct output is 1 1 1 -1 -1

    your output 1 1 0 0 0

    notice that the 1 1 1 -1 -1 is lexicographically larger . hope you get it :) .

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

The first example of the Problem C, clearly contains a loop, violating the last "interesting" graphs' property.

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

    Hi, the graph contains a cycle, but not a loop. A loop is a vertex connected to itself. See here

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

I have a question for Problem B

multisets int r=*s.begin(); s.erase(s.begin()); //s.erase(r);

i got TLE for using " s.erase(r) " and it runs over 2000ms ,while s.erase(s.begin()) not even 100ms

r is always the beginning in the set why it takes so long long long time...

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

    Hi, see here. I quote: "For the first version (erase(position)), amortized constant. For the second version (erase(val)), logarithmic in container size".

    Using an iterator is constant time so it is a lot faster. I didn't know the difference was that large tho.

    Hope this helps!

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

In problem E, how to find w' such that w' is a child of w and the subtree of w' contains r. ?

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

Trying to solve B hundreds of times, failing miserably, then I decided to read your submission and felt like a freaking idiot. :(

Despite the critical mistakes (which led to the unrated verdict), still thanks for the round. ;)

→ Reply