Hello! I hope all of you enjoyed my contest!

Tutorial is loading...

**Behind story of A**:

- I tried to make the easiest Div2A ever. Will it work? :)

Tutorial is loading...

**Behind story of B**:

- I tried to block various heuristics. There were some critical heuristics which could pass so many cases. Fortunately I blocked them during testing period, so I hope there won't be much FST this time.

Tutorial is loading...

**Behind story of D2C/D1A**:

- Originally, there was a different problem for this position. But it used XOR. As I made new D2E/D1C problem, I threw old D2C/D1A away and put this.

Tutorial is loading...

**Behind story of D2D/D1B**:

- This problem is the most popular problem among testers. I also like this problem a lot.

Tutorial is loading...

**Behind story of D2E/D1C**:

- Feedback for this problem was too different by testers.
- I made this problem by modifying Number Discovery, which is one of my previous problems.
- If you OEIS this, then you may find you can use Nimber Arithmetic to solve this.

Tutorial is loading...

**Behind story of D1D**:

- This problem was supposed to be D2E at first. But all LGM testers failed this problem during VC, so we thought that this problem's difficulty is high. Meanwhile, I found that old D1D problem can be easily googled, so we removed that problem, push this problem to be D1D, and made another D1C problem. I will share old D1D later.

Tutorial is loading...

**Behind story of D1E**:

- Thanks tzuyu_chou for writing this problem. She is genius in both singing and problemsolving.

Video tutorial for div1A/div2C

Video tutorial for div1B/div2D

McDic orz

what does this "orz" mean?

Bow down! Bow down to the McDic

Best Editorial Ever ....Nice Explanation Of both Problems and Solutions .

For Div1C, I found out that the nth tuple (an, bn, cn) is basically this: (found via OEIS)

an -> nth number with odd number of bits

bn -> nim_multiplcation(2, an) (https://oeis.org/A006015)

cn = an ^ bn.

But I was still not able to solve the problem because I didn't know nim multiplication nor did I find any implementation over the net.

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

Yeah, that is what happened ... I kept on searching for nim multiplcation here and there and wasted too much time. I should have come up with some other approaches ...

A solution with nim multiplcation: 76499145

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

I don't have proof, but in div1C any triple appears to be $$$(x, x \otimes 2, x \otimes 3)$$$, where $$$\otimes$$$ is nim multiplication.

:o

：）

[DELETED]

System testing is finished , Editorials are out , but my submission for Problem — A still shows Pretests Passed . Link : Here

Have I committed some fatal sin for which I am being given such a brutal punishment ?

What should I do now ?

xd

xd

rip

재밌는 문제들 감사합니다! (Thank you for the interesting questions!)

Fastest editorial I have ever seen!

Hey Codeforces, I don't have any idea how to approach problems like Div2.D/Div1.B, can someone give me an advice? I am not sure what should I learn first in order to be able to come with a solution to this problem. Thanks :)

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

Thanks a lot, I will keep practicing then :D. PS: I also like your 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.

i think it is better to provide codes instead of stories

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.

I know that, But I want to see the code of the explanation.

Wtf does that mean. Every code is most likely some variation of the explanation if it passed...

No

Yes

No is no

Dumb is dumb

Who is dumb there?

BABA IS YOU

Who is BABA?

He is husband of your mother

Its always better if editorial provides code or snippet about their approach

Good editorial. I especially liked those behind stories.

My E looks very different, now I'm wondering if it's correct.

Let's focus only on one big strongly connected component. For each vertex $$$V$$$ all the vertices which point to $$$V$$$ are ordered in a path. So, maybe it's possible to somehow form a cycle from all the vertices from the SCC. Let's take any vertex $$$V$$$. Now, from all the vertices which point to the $$$V$$$ let's take the last one on this path, let's call it $$$U$$$. Fix $$$U$$$ before $$$V$$$ on this cycle. Now, in the same manner, find a vertex that will be before $$$U$$$. And so on until we have a full cycle. My guess is that it's correct and that after this process which vertex points to some interval on the cycle which starts in this vertex. With such a form of the graph, we can easily calculate the answer.

Im not gonna lie but div2 was not interesting at all, problems D and E just required some basic observation. I hope future rounds require some more algorithmic skills to solve D and E.

How come did you only solve A then?

The point is not how many problems I solved or not but about the quality of problems, pls dont divert issues like this. (btw that submission to A is after contest :p)

OK, I'm sorry.

Well, I thought they were good :D. It's kinda subjective. Who's to say "making observations" is worse than "algorithmic skills"? I don't think it's so much about "quality of problems" than "style of problems".

I agree it's about style problems and I also liked the problems today. However I do agree with bored69 that imo too many problems are extremely short to code while relying solely on observation. While I know many people enjoy the short to code problems, it is called _code_forces after all, so I think the solution should be longer than 10 lines to solve the problem, and I would enjoy getting to use some standard algorithms more often as long as the problem is still not straight application

Another Radewoosh's pawn

Maybe Radewoosh is my pawn ;)

In Div 2-D explanation, I am not able to understand e-l+m part. Can someone help?

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.

I checked your solution. I am having some doubts. 1- Why did you choose your node as the vertex with a maximum degree? 2- The minimum f condition says if only odd paths are there, the minimum f is 1. forex. like 1--2--3--4(-- is an edge), how only one number can ensure bitwise XOR of 0?

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>

No, it won't be counted twice. edges 1-2 and 2-6 are first removed by subtracting l (e-l) and then added once for their common parent 2(non-leaf node with 2 leaves) through m (e-l+m)

Thank you for interesting and hard problems, McDic, tzuyu_chou!!!

1338B - Edge Weight Assignment Dont get it how the construction works at all. Should't there be some recursion as we do a dfs? How/where do we start, and what to do in "each step", assuming there are steps?

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:

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

Thanks!

Now I think the key observation to come up with all of this is the parity of distances of three leafs.

$$$parity(dist(l1,l2)) \oplus parity(dist(l1,l3)) = parity(dist(l2,l3))$$$

I didnt get the part where you assign 2 to the edge that is not a leaf.

Consider all the edges which not connect any leaf are assigned $$$2$$$, then all the prefix $$$xor$$$ value at node $$$p$$$ (not a leaf) will be either $$$...000$$$ or $$$...010$$$. So when we go to a leaf we can assign a possible value to make the prefix $$$xor$$$ equal to $$$...001$$$.

Suppose we don't assign $$$2$$$ but $$$1$$$ or $$$3$$$ then there will be the case when at node $$$p$$$ (not a leaf but have a leaf child) the prefix $$$xor$$$ may be $$$...001$$$ and go to node $$$v$$$ (the leaf child of $$$p$$$) whether we assign the edge $$$1$$$, $$$2$$$ or $$$3$$$ then the prefix $$$xor$$$ can't be $$$...001$$$ anymore.

Sorry for my bad English !

Thanks to your quick reply,I am able to understand it.Can you please suggest some resources or something that would help me in solving problem cause' I am only able to solve upto problem c everytime?

My suggestions: Solve problems and reflect upon what you have done wrong ... or what's observation you missed (And note them back obviously) ... or new algorithms (search and read for them and do 3 — 5 problems about that topic). Sometimes algorithm have signs, try to see that.

P/s: It's my own opinion anyway. Good luck <3.

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.

Can anybody please explain problem A and its editorial?

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.

In Div1E, How can we calculate the contribution from vertices with no indegree? If v has no indegree, then dis(u,v) is known but how do we find dis(v,u)? Thanks!

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

E intuition?Assume that all nodes have positive in-degree. Then we can arrange the nodes in a cycle $$$c_0,c_1,\ldots, c_{n-1}$$$ such that $$$c_i$$$ has edges to $$$c_{i+1},c_{i+2},\ldots,c_{(i+out(i))\pmod{n}}$$$ where $$$out(i)$$$ denotes the out-degree of node $$$c_i$$$. To find this cycle, start with any vertex $$$x$$$ and topologically sort $$$in(x)$$$. Then repeat with the last node of $$$in(x)$$$ (with respect to the sorted order).

For all $$$i$$$, $$$out(i)>0$$$ and $$$out(i)\le out((i+1)\pmod{n})+1$$$. Suppose that $$$i<j$$$. Then $$$out(i)+i\le out(j)+j$$$ and the distance from $$$c_j$$$ to $$$c_i$$$ is three iff $$$out(i)+i=out(j)+j$$$. Otherwise, it's one or two.

Do anyone else other than me recognize this submission as a hack for a hack and there were two successful hacking attempts. That's a

cheat. 76401969how to find editorial in english for Atcoder Begginer contest 162 on their website it's in japanese..

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

thanks

I've solved A,B,C,D if you want, i can tell u how to solve them

please tell me how you solved D

So you gonna fix i and k such that S[i] != S[k]. So in the range [i + 1, k — 1] you should find the number of characters C different from S[i] as well as S[j]. So, for example, if S[i] = 'R' and S[k] = 'G', C = 'B'. So these different characters can be found using segment tree, maybe there is other method too. Also you should check for the second condition, if (k — i) % 2 == 0 and S[(i + k) / 2] == c, you gonna decrement that number by one.

That's my solution, but I think there is a better solution described in the following video: https://www.youtube.com/watch?v=IOy1GtYLMJA&t=290s

Btw, why ask this here xD

Could someone elaborate a bit more the intuition behind Div1D and how to implement it?

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://codeforces.com/contest/1338/submission/76420228

this was my first contest :) I passed question 1.

$$$O(n^2\log(n))$$$ can be squeezed in E: 76419686.

I beg your pardon, but I think problem statement of div2A should have been a bit clearer in explaining the term 'covering differently'. Thank you.

In Div2 D for finding the maximum f value, what is the proof that there is no other construction possible that can possibly have more distinct weights? For example, consider a tree with the non-leaf nodes having degree 4. In the observation 3 picture, we can add to node 2, a replica structure of its child node 3. That will make node 2's degree 4. How to prove for this case(and in general) that the maximum value of f will not exceed e-l+m?

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.

hi..what is the maximum time in which it's good to solve div2 — A and B.. because i'm practicing only DIV2 A and B question in virtual contest..and still took more than 1 h to solve both...some time i failed to solve B.. Thanks in advance..

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

The only Div2A that I couldn't solve during the round XD

Nice editorial and pictures! McDic One suggestion: It'll be easier to read d1E if you use lowercase letters for vertices and upper case letters for sets.

`If you OEIS this, then you may find you can use Nimber Arithmetic to solve this`

Can anyone tell me what is meaning of OEIS in the story of D2E ?

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

I tried solving div2C by iterating through the array, whenever a[i]>a[i+1] I added to all j=i+1 and j<n lowest power of 2 possible to make it a[i]<=a[i+1]. Lowest power was calculated using a vector of powers of 2. But it does not work, and I am unable to find out why. Can anyone help?

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

Thanks.

Can anyone briefly explain the problem "Powered Addition", I mean full approach and walk through an example.

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

possibleto 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:

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

Again, we do

`answer - 1`

because we can use the smaller powers of 2 to increase it to exactly equal the difference.For the first time for problem A, it took me around 50 minutes to figure out and ironically that was the easiest one liner solution possible. Take the input and print it xD.

Nice Editorial and nice problems. In

div2E/div1C.I've found a strange pattern for the bits in the n-th triple . but I can't manage to code it during the contest. this is my code 76432679 .2D, I understand nothing, damn constructive problems and damn gap between C and D

"Observation 1. You can prove that minimum value of f is at most 3, by following construction;"

Well, how do we know there is no other construction where we would have 4 or more?

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

Why?

"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

"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$$$.

1-2) Oh, so it was about describing a generic technique of assigning values, not about the specific tree on the picture. Then it makes more sense

3) The confusing part here was that I thought it was about the number of a and b in the whole tree, not on the requested path, and didn't understand why.

I'll reread it with this in mind

Thanks

I've got how we come up with f=3 from the comments

However I still don't understand the same part in the editorial "Weight of edges are only determined by degree of two vertices and whether that edge is connected to leaf or not"

On the picture we have a string of non-leaves, all of which have degree 3. And all the leaves obviously have degree 1 So following this statement we're supposed to have the same weights for every edge connecting a non-leaf to a leaf on the picture. However, this is not the case.

Finally become master in this round. I like the problems! Thanks a lot.

HELP! PleaseHi, everyone! My friends has some trouble in his solutions, He has submitted this solution 76367506 during the round, However, after the system pending test, He did not get an AC, but still the Pretest passed. The score for this problem was not added to my friends. He has submitted totally the same code just now, 76438866, and get an AC. Why did this happen? It has effected on my friends ratings, Where can I find the administor to solve the trouble? (sorry for my poor english)

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

Thank you! You are so kind!

Great editorial. Thanks a lot!

in the div 2 B

i do not understand what the 'Sort the list, and make an oscillation centered on middle element like picture below.' means.

i just dont know how to sort it and what should i do in the next step.

please help me!

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 youFirst I thought maximal independent set in div1D, but got Wrong Answer on pretest 4.

Great problemset, a beautifully written editorial, no queueforces, strong pretests and quick system testing makes it a wonderful round! Hope to participate in more rounds authored by you in future!

P.S. : my most special round till date since I finally reached CM !

can someone explain div2-C,i am not able to understand the editorial.

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://codeforces.com/contest/1339/submission/76446573

FinalBoss_ Can you please explain why did you add 1 in log2(dis+1) ?

I guess dis is the max number required to add.Why +1 ?My first submission was same but i didnt add 1 it got wa.

yes dis is the max number required to add. log2(dis+1) is done because... we were asked to find 2^(x-1).

in case all numbers are equal and dis is 0 or if array is already increasing and dis is still 0, then log(0) becomes undefined. Now since we don't need actual value but ceiling of it so adding 1 to dis and then taking log will have same effect but also it will remove ambiguity of log(0).

Thanks, got it.

Can you please explain for this test case n = 5 a = [ 1, 2, 1, 4, 1] For this output is ** 2**. How in 2 steps we will make this array non decreasing?

Same doubt. Hoping someone to answer.

Edit: Got it. Should have read the question carefully. It says select any indices not continuous indices.

for n=5 ans array [ 1 2 1 4 1 ]

Step 1: Select indices : Select 3 and 5 ( begins from 0) Step 2: Increase by 1 then by 2 ( 2^x-1 , put x=1 and then 2) So array becomes : 1 2 4 4 4 which is non-decreasing.

I have doubt in 1339 B -Sorted Adjacent Differences: If the array is: -2 5 5 6 The answer will be 5 -2 5 6 which is wrong Please explain if i am wrong

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

yes,but according to tutorial it is printing 5-2 5 6

according to tutorial it will print 5 5 -2 6.

Can anyone explain O(N) approach for div 2C ? I know how to do it in O(NlogN) but not in O(N)

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.

Here is my thinking about this problem, which is much easier to understand: Lets say we need T seconds to make array becoming non descending. On each seconds from 1 to T we can choose any set of numbers from array to add 2^(t-1). It means that for each element of the array, on each second, we have choice to add or not to add this power of 2. So it means we can choose ANY number to add to each of array element. So the question is now simple: what is the min number M so that if for each a[i] we choose some number from 0 up to M to add to it, we can make array non descending. I just go from left to right, if next a[i+1] is less than a[i] I increase it to be equal a[i].

why do we need to add the 1?

because suppose the highest bit is 2 that will be 100 but the time this would have occurred will be 3 seconds(1,2,4). Due to this, we need to add 1 to the highest bit that we obtain.

Can anyone please explain how the answer of this testcase in problem div2/probC is 3.

4 2 -1 -3 -4

For DIV2D, first root the tree at any leaf (here, leaf = vertex with degree 1), and note that the XOR sum along any root leaf path must be 0. Now, delete all the leaves and the edges that lead from the leaves to their parents. In this graph, to get maximum value of f, assign distinct powers of 2 to each edge. Then re-introduce the leaves and leaf-to-parent edges, and assign them weights such that XOR sum from root to leaf will be zero. Notice that the values assigned to these leaf-to-parent edges will be distinct unless two leaves share the same parents. Thus, the maximum value of f will be n — 1 — (lvs — p), where lvs = number of leaves in this tree and p = number of nodes which have exactly one child leaf.

To get minimum f, do the same thing above (root tree at any leaf, then delete leaves and all leaf-parent edges). Then, in this new graph, assign weight 2 to the edge incident on the root, and to all other edges assign weight 1. Now, reintroduce the leaves and the leaf-parent edges, and assign these edges weights such that XOR sum along the root leaf path is 0. Notice that you will only have to assign weights of either 2 or 3 to these edges. So f <= 3. The only case left is to work out when f = 1.

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?

In lvs, the root is not considered one of the leaves. And in p, parent of root is not included because root does not have a parent.

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 cant understand the editorial of Powered Addition clearly.Please help

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

Who can explain problem A again. I don't undersatand why answer is n

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

Problem Div1(C), Div2(E):Can anyone please elaborate on why this combination on bitmasking works?

Or, how to prove this combination works?

Thanks in advance.

Could someone please elaborate a bit more on Div1 C ? I understand the solution up to the first picture, but I don't understand neither the meaning of the second picture nor the rest of the solution.

Why does my solution to Div2-C is not working . https://codeforces.com/contest/1339/submission/76407068

can somebody please help me out on this .

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.

Can someone please explain division1C/division2E I am not able to understand the approach in the editorial.I got the nim product observation but I don't know how to implement it also i don't get the editorials approach.If anyone could help that would be great.Thanks in advance.

McDic, as for Div1E, isn't $$$R=in(P)\cap Q$$$, instead it is $$$R=in(V)\cap Q$$$? The latter just doesn't make sense if you consider the lemma 3. $$$in(V)$$$ is the subset of all vertices that have at least one outgoing edge, $$$in(P)\cap Q$$$ is the subset of all vertices of $$$Q$$$ that have at least one outgoing edge. Then lemma 3, which says there are edges from set $$$S$$$ to $$$R$$$, can't be true because it says that $$$S$$$ — a subset of $$$Q$$$ without outgoing edges — has edges pointing to $$$R$$$. On contrary, if we set $$$R=in(P)\cap Q$$$ we, can prove lemma 3 by forbidding the configuration from the statement. Also, can't really prove part of lemma 4 that says that $$$R$$$ has no cycles without it.

(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

Ugh, bad boy. You should be more responsible to your round.

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.

Hi, McDic, how does observation 1 of edge weight problem work since the shape of tree is determined by input rather than can be arbitrary constructed as in observation 1? Take example input 3 for instance. Thanks in advance.

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

I must misunderstand your meaning, but doesn't f=2 in the graph since there are weight of 1 and 2?

Or do you mean that the edge on 7-4-3 could be equivalent to a single edge with weight of 3=weight(7,4) xor weight(4,3)=2 xor 1? Thus in this way the observation 1 can be applied?

This picture shows how you can manage $$$f \le 3$$$ in this tree with first observation. By "

You can see that we can make $$$f = 1$$$ in this tree any" I mean you can replace all weights $$$2$$$ to $$$1$$$ to make $$$f = 1$$$.Can anyone please explain me the second test case for Div1A/Div2C(1338A - Powered Addition)?

How is the output 31 and not 32? If it is 31 then we must have added 2^30 in 0 and -1000000000 but that does not make the array non-decreasing in the first test case.

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.

why does the answer for div2-C depends only on largest difference? Can someone explain in detailed manner i am unable to get the logic behind it.

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;

Thank you for your explanation.

Nice editorial.

@Anyone who solved Div2. D during the contest, can you explain how did you actually figure out the solution and was there any specific problem you ever did in past that helped you to solve this problem?

Why this sequence is not correct for n=9, A/C to question Perfect Triples please Any one Help???

9 : 1 2 3 4 3 7 8 4 12

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

Video editorial for Div2D/Div1B:

Hey Codeforces,

Can anyone help me to come up with a better approach to the excluded problem (https://codeforces.com/gym/276159/problem/D1A_old) apart from the brute-force approach which is giving TLE?

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

After a few weeks when I want to solve the problems I just realized the Editorial is so beautiful, those well-illustrated pictures and interesting stories made the Editorial so great!

But I had problems solving D1E. I cannot figure out why the

Lemma 3andLemma 6a/bare correct (And of course the final observations). Can you give proofs for them?UPD: After asking others, now I understood. Anyway, thanks the great Editorial!i found a crazy solution of div1B https://codeforces.com/contest/1338/submission/76346806 can anyone plz explain the logic

Can someone provide insight into the mathematical induction referred to in observation 2 of div1C (Perfect Triples)?