what does this "orz" mean?

Nim Arithmetic is definitely overkill for this problem.

We found that during testing and thought it wasn't much of an issue exactly because of that, probably you'd spend more time searching about nim multiplication than if you just solved the problem lol

A solution with nim multiplcation: 76499145

There is no doubt that it is much more complicated than the general solution.

:o

xd

xd

rip

From my experience, Div 2 D tends to vary quite bit. I think the best way to go about it is to just keep on practicing a bunch of div 2 D, and look at editorials if you don't quite understand. Also, nice profile picture :)

Well from my experience, it appears atleast one of C/D almost always involves graphs and/or DP. I'd recommend first learning all about graphs, especially some important techniques like DFS, BFS, multi-source BFS, SCC, bridges, cut-vertices etc.[Graphs are really awesome :] Then later move on to DP.

IMO you should first learn a little advanced algorithms and data structures and etc., also solve-up contests and past ones, i say the best way is to take virtual contests and then solve the rest of the problems excluding the cases you full the contest :). Also solve Div2.E after the contests, it's fine if you cant solve them, just take your time and try your best then go to editorial and make sure you fully understand the editorial and the logic behind it.

That's why the button showing number of solves next to a problem exists. Click on that and you can see many codes and sort by speed, code length, etc.

How come did you only solve A then?

The key construction in the editorial is that for every leaf i, the edge between i and its parent is xor(path(root,parent(i))). This construction guarantees different weights with one exception, what if multiple leaves have same parent? In that case we'll have only one extra distinct weight for all leaves with a common parent. So instead of including weights for all the leaves, we'll include weights only for their parents. Hence, first assume all edges as distinct and include them all(e) , then remove all leaves(l) and finally add those parents (which are non-leaf nodes with atleast one child as leaf (m)). So, we get e-l+m.

What about the case when edges with same weight are counted twice? In the picture Observation 3, the edges (1)-(2) and (2)-(6) should have the same weight. But the formula will count them as separate weights. Can someone please explain>

I agree, everyone seemed to have just done the same thing, take one from the back and one from the front, I just am not able to prove this. How do I come to this conclusion?

This is a way that I came up with to always satisfy 3 distinct colors for every tree.

Choose a leaf (called $$$u$$$) and choose the connected node with this leaf (called $$$r$$$ and obviously this node won't be a leaf, as $$$n >= 3$$$) as the root.

What we are going to construct is we are trying to make: $$$ xor(path(r, v)) = xor(path(r, u)) $$$ for every leaf $$$v$$$. Because when $$$ xor(path(r, v)) = xor(path(r, u)) $$$ then $$$ xor(path(r, v_1)) = xor(path(r, v_2)) ( = xor(path(r, u)))$$$ for every pair of leaves.

We have $$$xor(path(r, v_1)) = xor(path(r, v_2)) $$$ $$$\Leftrightarrow (xor(path(r, lca(v_1, v_2))) \oplus xor(path(lca(v_1, v_2), v_1))) = (xor(path(r, lca(v_1, v_2))) \oplus xor(path(lca(v_1, v_2), v_2)))$$$ $$$\Leftrightarrow xor(path(lca(v_1, v_2), v_1)) = xor(path(lca(v_1, v_2), v_2)) \Rightarrow$$$ Satisfy the condition

So here is what I do:

1. Let the edge between $$$r$$$ and $$$u$$$ have weight $$$1$$$.
2. We dfs from $$$r$$$, save the prefix $$$xor$$$ value from $$$r$$$ to the node $$$p$$$ we are at and dfs to node children $$$v$$$ of $$$p$$$:

• If $$$v$$$ is a leaf, then we need to assign this edge so that the prefix $$$xor$$$ value will be equal to $$$1$$$ ($$$ = xor(path(r, u))$$$).
• If $$$v$$$ is not a leaf, then we assign $$$2$$$ to that edge. Why? Because we need to get rid of the case when the prefix $$$xor$$$ value at node $$$p$$$ (parent of leaf $$$v$$$, for example) is equal to $$$1$$$ ($$$ = xor(path(r, u))$$$) and whatever we assign $$$edge(p, v)$$$ we cannot make the prefix $$$xor$$$ value at leaf $$$v$$$ equal to $$$1$$$ anymore.

P/s: Ask me anything that you may not understand ^^.

To everybody: The editorial has this update. It makes the problem much simpler:

(Update) There is an another way to approach, provided by Darooha.

If you label vertices instead of edges where all leaves have same label and none of neighbors have same label, then you can consider edge weight as xor of two vertices' labels, so this is basically equivalent to original problem.

Now for minimum, you can see that labelling 0 to leaves, and 1,2 to non-leaves are enough, so you can prove minimum value of f is at most 3. In same manner, you can try parity checking to check if f value can be 1 or not.

For maximum, assign 0 to all leaves and assign all different values(21,22,...) to non-leaf vertices, then you can see all edge weights(except leaves connected to same vertex) are different.

You may refer to the picture in the editorial. In this picture, if you put the red one in, you will find there is only one way to fill it( also described in the picture). Hence, since there are N different ways for putting the red one in, the answer is simply N.

Consider you want to find the answer for shape with size N. Let's say you put a Vertical diamond initially then places of all other diamonds are decided. So this is 1 way to put diamonds.

The other way is to put two horizontal diamonds on top left and bottom left and then we are have to find ways to puts diamonds in a shape of size N-1.

Ans(i) = 1 + Ans(i-1)
{1 for the way in which vertical diamond is placed on the leftmost position}

Ans(i) = 1 + Ans(i-1) = i, given ans(1) =1.

If $$$u$$$ has no in-degree then $$$dis(u,v)=1, dis(v,u)=614n$$$ for all $$$u\neq v$$$.

Pay attention to the red line written on the first page of the Japanese editorial .

Btw, why ask this here xD

I approached this problem by considering what happens if we only consider the minimum connected subgraph containing the answer, where the answer is the set of nodes $$$S$$$ that form the nested rubber bands. First, consider each $$$v\in S$$$ as a circle, so we have $$$|S|$$$ nested circles. The other vertices of this minimum connected subgraph must contribute to connecting two or more circles, and we can consider them as line segments.

Colour the line segments red and the circles blue. Then, we'll see that the red vertices lie on a path, because we can trace out a path in this alternate representation of the tree. Furthermore, the blue vertices form an independent set, and each is adjacent to at least one red vertex.

DP states:

For each state, I suppose that the red vertices lie on a path in the subtree rooted at u with one endpoint at u.

• take[u] = number of blue vertices if u is blue

• skip[u] = number of blue vertices if u is red

DP transitions:

• take[u] = max(1 + skip[child]). Since we're interested in a path, we take the max.

• skip[u] = max(#children-1 + max(take[child], skip[child])). If we colour u red, then we can colour all its uncoloured neighbours blue, but we still want to be able to choose for the next node in the path.

To get the answer, consider a path rooted at u. We need to know the best two values of take[child] and max(take[child], skip[child]) to find the answer for such a path.

I'm sure you could fit the dp and get the solution in one dfs function, but here's my rather long and verbose code: https://mirror.codeforces.com/contest/1338/submission/76420228

Because that's the upper bound of the value.

Every edge that isn't adjacent to a leaf doesn't matter. Edges for leaves that are adjacent to the same non-leaf vertex need to be equal. That can be counted as in the editorial because — (leaves — non-leaf vertex adjacent to a leaf) is exactly the number of edges to leaves that are free to receive values.

See this round was tough, but I think top coders take max 15 min for both, at my rating I think even 30 mins would be fine and for you, 45-60 min is the max you should ideally take

This is where you can find insights/recurrences of random sequences.

try 1 0 1 0 1 0 The optimal answer is x = 1 i.e. select indexes 2 , 4 ,6 you get 1 1 1 1 1 1 I hope that is clear

My approach was as follows:

Let's say that the list is [1, 7, 6, 5]. We go through and we look at all the pairs (a[i], a[i+1]). We start with (1,7). It satisfies the property of being non-decreasing, so we do nothing. Next, we go to (7, 6). 6 < 7, meaning we have to add something to "6" to make it bigger. I assert (and will explain below the reason why), that it is possible and optimal to convert the "6" into a "7". The list then becomes [1, 7, 7, 5]. Next, we look at the final pair (7, 5) and do the same: convert the "5" to a "7", so that the final list becomes [1, 7, 7, 7].

When we convert a pair (a, b) to the pair (a, a), it means that we need to add some quantity (a-b) to it. If that quantity is 18, for example, then we can do this with 16 + 2 = 2^4 + 2^1. If that quantity is 15, we can do this with 2^0 + 2^1 + 2^2 + 2^3. In general, there is exactly one way to do the addition of distinct powers of 2 to get from one number to another.

You can find out which powers of 2 you need to add together by converting the difference into binary. The definition of binary is that where there is a "1" you can add the relevant power of 2.

In any case, I'm just saying that it is always possible to do this, and it doesn't matter what the exact powers of 2 are, you just need to know what the biggest power of 2 needed will be. This is because if you're using a bigger power of 2, for example 2^5, it means that seconds 1, 2, 3, 4, 5, 6 have already happened, so you could have, in the past, added 2^0, 2^1, 2^2, 2^3, 2^4 if you needed to do so.

The biggest power of 2 needed can be worked out by taking the logarithm base 2 of the difference, and then rounding down.

The code would then be something like this:

max_power_found = -1
for i in range(len(a) - 1):
  if a[i + 1] < a[i]:
    difference = a[i] - a[i + 1]
    biggest_power = floor(log2(difference))
    max_power_found = max(max_power_found, biggest_power)

    a[i + 1] = a[i]

print(max_power_found + 1)

Note that I initialise max_power_found to -1 so that at the end, if nothing has happened because the array was already non-decreasing, it becomes 0 when you add 1.

Note also that even though we don't need to output the final array, I have the line a[i + 1] = a[i]. This is because the next pair needs to know about the change we just made.

There are (n-1) possible values of i, and for each one we do some constant time computation (logarithm base 2 is very fast), this is an O(n) solution.

Note that even if you didn't know about logarithms, you could probably do it very quickly because log2(10^5) is very small (though I haven't tested to make sure this doesn't TLE):

def biggest_power_needed(difference):
  # Outputs -1 if difference is 0.

  answer = -1
  total = 0
  while total < difference:
    answer++
    total += pow(2, answer)

  if total == difference:
    return answer
  else:
    return answer - 1

Again, we do answer - 1 because we can use the smaller powers of 2 to increase it to exactly equal the difference.

"Well, how do we know there is no other construction where we would have 4 or more?" The problem is asking for the minimum, there is a construction where $$$3$$$ is possible so the minimum is never greater than $$$3$$$

""Weight of edges are only determined by degree of two vertices and whether that edge is connected to leaf or not"

Why?" Because we decided that that's how the construction should look like. Another example of a construction which would work is edges connecting a leaf having a weight of $$$2$$$ or $$$3$$$ depending on the parity leaf's depth and all other edges having a weight of $$$1$$$.

""Because if f=2 then there should be even number of edges for each weight"

Why? There should be some proof by contradiction I suppose" Here's a proof: Notice that we can consider each bit separately and then an assignment works if the condition is satisfied for all bits. Let's say we choose numbers $$$a$$$ and $$$b$$$. If both $$$a$$$ and $$$b$$$ have some bit set to $$$1$$$ then that is the same as the $$$f=1$$$ case. If there is no bit which both $$$a$$$ and $$$b$$$ have set to 1 then that means that there is a bit which $$$a$$$ has set to $$$1$$$ and $$$b$$$ has set to $$$0$$$ and that there is a bit which $$$a$$$ has set to $$$0$$$ and $$$b$$$ has set to $$$1$$$, so each path needs to have an even number of both $$$a$$$ and $$$b$$$.

Weired. You can Send a message to https://mirror.codeforces.com/profile/MikeMirzayanov

Sort the elements in ascending order. Then you go smallest->largest->second smallest->second largest... and so on. If you draw it on paper, you can see that the gaps are always getting smaller because it's a subset of the previous gap.

Imagine the problem is the same, but differences between pairs must be non increasing instead of non decreasing ( | a_ i — a_i-1 | >= | a_i-1 — a_i-2 | ). If we solve this, we can just reverse the answer and we will get an answer to the original problem.

Now, imagine we start with the biggest element to the left. What number should we add next to maximize their difference? The smallest element. So we add it. After that, what number not yet added would maximize the difference of the pair? The second biggest element, and it is not hard to see it will be smaller or equal than the first pair. If we continue to do this, we can get an answer.

So to build it we just sort the initial array and then build it in the following way: a[N] , a[1] , a[N-1] , a[2] , a[N-2] , a[3] ...

After this, don't forget to reverse the answer to solve the original problem.

Submission: 76418078

aspiriner This picture may help you

first of all find the max difference between any two number (O(n)). then you just need to count number of digits in it. which can be done using log2 of that difference. note: ceil function is to be used for ex: 2.5 would be rounded off to 3.

here's my code(which is actually someone else but I copied it and modified a little, but is self explanatory )

https://mirror.codeforces.com/contest/1339/submission/76446573

it is wrong because the required condition is not fulfilled as your answer will make seqeunce like this 7<=7>1.

For array -2 5 5 6 the answer will be 5 5 -2 6

While traversing the array keep a count of what maximum difference have you seen so far from the previous element i.e maximum value uptil that i minus the array value at that i. Then once you found the maximum difference than going for finding the position of the highest bit in this maximum difference. The ans is going to be the value of this highest bit + 1. Make sure to include the edge case that if the maximum difference is 0 then the ans is also 0.

In lvs is root considered one of the leaves and in p is the parent of the root considered as one among p when the parent of root only has root as its child?

Nice explanation but I read your code to understand fully. =)) Code is still the best explanation.

Thanks so much, your explanation helped me understand this problem 2 months later! :) It's so mind-boggling to understand how one can come up with this construction in time during the contest.

The reason I want to post here is to add something to your solution in case anyone after me has the same question. (also to just solidify my own understanding) I actually had this question myself while reading — we know that the XOR from the root to all the different leaves must be zero. But how can one prove that the XOR from one leaf to another is also zero? (a path that does not include the root, but rather just two leaves in the tree?) After all we need to make EVERY path between leaves XOR to 0

The logic is quite simple. As we said before we know XOR of the paths from the root to the two leafs, call them L1 and L2, are both zero. These paths must share some similar segment (specifically its from the LCA(L1, L2) to the root). Call the XOR of this shared segment X. Then we know the XOR from the path from L1 to LCA(L1, L2) = X, and same with the path from L2 to LCA(L1, L2). Because if (x XOR y) = 0, then x = y, and the XOR of the whole path can be broken up the XOR of two segments L1 -> LCA, LCA -> root. (same with L2).

The editorial also explains this logic a bit but I hope what I wrote can help.

I just post my 2 cents above, hope it is easier to understand

ans is equal to n bcz of the vertically standing diamonds in each way there will be only one diamond which would be standing vertically and since the number of diamond in n hence and in n

Well let's take the sequence as 1 4 1 4, your code outputs 3 while it is supposed to output 2 since you can add 1 and 2 to the third element and get a sorted output.

(erased)

oops, sorry, I understood your comment wrong. To be honest, I don't fully understand approach of this problem, so I would like to call author of this problem directly. tzuyu_chou

Oh, I didn't realise that I used the variable $$$V$$$ 2 times. Now I fixed it. When I said $$$in(V) \cap Q$$$ I refered to the $$$V$$$ in Lemma 2. Thanks for pointinh out my mistake.

You can see that we can make $$$f = 1$$$ in this tree anyway.

Select $$$2$$$-nd index at last second only, and $$$3$$$-rd index all the time. Then you get

$$$a = [10^{9}, 0, -10^{9}] \to [10^{9}, 0 + 2^{30}, -10^{9} + 2^{0} + 2^{1} + \ldots + 2^{30}] = [1000000000, 1073741824, 1147483647]$$$

So you can make $$$a$$$ non-decreasing in $$$31$$$ seconds.

Fact 1: $$$2^{0} + 2^{1} + \ldots + 2^{t-1} \lt 2^{t}$$$.

This means if you want to add something equal or bigger than $$$2^{t}$$$ on some position, then you should use more than $$$t$$$ seconds.

Fact 2: Required seconds is determined by maximum bit of difference.

From two facts you can observe that smaller difference leads to shorter time.

I will write few examples below;

• diff = 0 -> 0 second
• diff = 1 -> 1 second ($$$1 = 2^{0}$$$)
• diff = 2 -> 2 seconds ($$$2 = 2^{1}$$$)
• diff = 3 -> 2 seconds ($$$3 = 2^{0} + 2^{1}$$$)
• diff = 4 -> 3 seconds ($$$4 = 2^{2}$$$)
• diff = 5 -> 3 seconds ($$$5 = 2^{0} + 2^{2}$$$)
• diff = 6 -> 3 seconds ($$$6 = 2^{1} + 2^{2}$$$)
• diff = 7 -> 3 seconds ($$$7 = 2^{0} + 2^{1} + 2^{2}$$$)
• ...

Because $$$3$$$ is used twice in your sequence.

$$$x \oplus (x \cdot 2^{30}) = x \cdot (1 + 2^{30})$$$ if $$$x < 2^{30}$$$.