### McDic's blog

By McDic, history, 4 years ago,

Hello! I hope all of you enjoyed my contest!

Behind story of A:

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

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.

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.

Behind story of D2D/D1B:

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

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.

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.

Behind story of D1E:

• Thanks tzuyu_chou for writing this problem. She is genius in both singing and problemsolving.
• +346

| Write comment?
 » 4 years ago, # | ← Rev. 3 →   +19
 » 4 years ago, # |   +61 McDic orz
•  » » 4 years ago, # ^ |   +30 what does this "orz" mean?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +36 Bow down! Bow down to the McDic
 » 4 years ago, # |   +14 Best Editorial Ever ....Nice Explanation Of both Problems and Solutions .
 » 4 years ago, # | ← Rev. 2 →   +32 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.
•  » » 4 years ago, # ^ |   +38 Nim Arithmetic is definitely overkill for this problem.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +71 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
•  » » » 4 years ago, # ^ |   +24 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 ...
•  » » 4 years ago, # ^ |   +11 A solution with nim multiplcation: 76499145There is no doubt that it is much more complicated than the general solution.
 » 4 years ago, # |   +192 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.
•  » » 4 years ago, # ^ |   +64 :o
•  » » » 4 years ago, # ^ |   -8 ：）
 » 4 years ago, # | ← Rev. 3 →   -41 [DELETED]
 » 4 years ago, # |   +62 System testing is finished , Editorials are out , but my submission for Problem — A still shows Pretests Passed . Link : HereHave I committed some fatal sin for which I am being given such a brutal punishment ?What should I do now ?
•  » » 4 years ago, # ^ |   0 xd
•  » » 4 years ago, # ^ |   0 xd
•  » » 4 years ago, # ^ |   +4 rip
 » 4 years ago, # |   +5 재밌는 문제들 감사합니다! (Thank you for the interesting questions!)
 » 4 years ago, # |   -7 Fastest editorial I have ever seen!
 » 4 years ago, # | ← Rev. 2 →   +9 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 :)
•  » » 4 years ago, # ^ |   +3 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 :)
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Thanks a lot, I will keep practicing then :D. PS: I also like your picture :)
•  » » 4 years ago, # ^ |   +4 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.
•  » » 4 years ago, # ^ |   +3 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.
 » 4 years ago, # |   -118 i think it is better to provide codes instead of stories
•  » » 4 years ago, # ^ |   +7 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.
•  » » » 4 years ago, # ^ |   -30 I know that, But I want to see the code of the explanation.
•  » » » » 4 years ago, # ^ |   +10 Wtf does that mean. Every code is most likely some variation of the explanation if it passed...
•  » » » » » 4 years ago, # ^ |   -55 No
•  » » » » » » 4 years ago, # ^ |   +20 Yes
•  » » » » » » » 4 years ago, # ^ |   -38 No is no
•  » » » » » » » » 4 years ago, # ^ |   +41 Dumb is dumb
•  » » » » » » » » » 4 years ago, # ^ |   -19 Who is dumb there?
•  » » » » » » » » » 4 years ago, # ^ |   +8 BABA IS YOU
•  » » » » » » » » » 4 years ago, # ^ |   0 Who is BABA?
•  » » » » » » » » » 4 years ago, # ^ |   +8 He is husband of your mother
•  » » » 4 years ago, # ^ |   +6 Its always better if editorial provides code or snippet about their approach
 » 4 years ago, # | ← Rev. 2 →   +6 Good editorial. I especially liked those behind stories.
 » 4 years ago, # |   +8 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.
 » 4 years ago, # |   -62 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.
•  » » 4 years ago, # ^ |   +100 How come did you only solve A then?
•  » » » 4 years ago, # ^ |   -40 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)
•  » » » » 4 years ago, # ^ |   +48 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".
•  » » » » » 4 years ago, # ^ |   -11 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
•  » » » » » » 4 years ago, # ^ |   +77 Another Radewoosh's pawn
•  » » » » » » » 4 years ago, # ^ |   +11 Maybe Radewoosh is my pawn ;)
 » 4 years ago, # |   +2 In Div 2-D explanation, I am not able to understand e-l+m part. Can someone help?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » 4 years ago, # ^ |   0 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?
•  » » » » 4 years ago, # ^ |   0 I had a different approach when I started coding, so i start with that node with maximum degre. In my approach, the necessary condition is that root node should not be leaf, if it is I'll not count one leaf in my dfs leading to a wrong answer. Minimum condition for f is, all leaf nodes should be at a distance of same parity from root, so that every pair of leaves are separated by even no. Of edges.
•  » » 4 years ago, # ^ |   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>
•  » » » 4 years ago, # ^ |   +1 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)
 » 4 years ago, # |   +9 Thank you for interesting and hard problems, McDic, tzuyu_chou!!!
 » 4 years ago, # | ← Rev. 2 →   +1 1338B - Назначение весов ребрам 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?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 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?
•  » » 4 years ago, # ^ |   +18 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 conditionSo here is what I do: Let the edge between $r$ and $u$ have weight $1$. 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 ^^.
•  » » » 4 years ago, # ^ |   0 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))$
•  » » » 4 years ago, # ^ |   0 I didnt get the part where you assign 2 to the edge that is not a leaf.
•  » » » » 4 years ago, # ^ |   0 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 !
•  » » » » » 4 years ago, # ^ |   0 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?
•  » » » » » » 4 years ago, # ^ |   0 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.
•  » » 4 years ago, # ^ |   +13 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.
 » 4 years ago, # |   0 Can anybody please explain problem A and its editorial?
•  » » 4 years ago, # ^ |   0 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.
•  » » 4 years ago, # ^ |   0 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.
 » 4 years ago, # |   +3 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!
•  » » 4 years ago, # ^ |   0 If $u$ has no in-degree then $dis(u,v)=1, dis(v,u)=614n$ for all $u\neq v$.
 » 4 years ago, # | ← Rev. 3 →   +1 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  » 4 years ago, # | +23 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. 76401969  » 4 years ago, # | 0 how to find editorial in english for Atcoder Begginer contest 162 on their website it's in japanese.. •  » » 4 years ago, # ^ | 0 Pay attention to the red line written on the first page of the Japanese editorial . •  » » » 4 years ago, # ^ | 0 thanks •  » » » » 4 years ago, # ^ | 0 I've solved A,B,C,D if you want, i can tell u how to solve them •  » » » » » 4 years ago, # ^ | ← Rev. 2 → 0 please tell me how you solved D •  » » » » » » 4 years ago, # ^ | ← Rev. 2 → 0 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. •  » » » » » » » 4 years ago, # ^ | 0 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 •  » » 4 years ago, # ^ | +11 Btw, why ask this here xD  » 4 years ago, # | +13 Could someone elaborate a bit more the intuition behind Div1D and how to implement it? •  » » 4 years ago, # ^ | ← Rev. 5 → +42 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  » 4 years ago, # | +12 this was my first contest :) I passed question 1.  » 4 years ago, # | +9$O(n^2\log(n))$can be squeezed in E: 76419686.  » 4 years ago, # | ← Rev. 2 → +8 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.  » 4 years ago, # | 0 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? •  » » 4 years ago, # ^ | +7 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.  » 4 years ago, # | ← Rev. 2 → 0 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.. •  » » 4 years ago, # ^ | 0 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  » 4 years ago, # | 0 The only Div2A that I couldn't solve during the round XD  » 4 years ago, # | +8 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.  » 4 years ago, # | 0 If you OEIS this, then you may find you can use Nimber Arithmetic to solve thisCan anyone tell me what is meaning of OEIS in the story of D2E ? •  » » 4 years ago, # ^ | ← Rev. 2 → +1 This is where you can find insights/recurrences of random sequences.  » 4 years ago, # | 0 I tried solving div2C by iterating through the array, whenever a[i]>a[i+1] I added to all j=i+1 and j •  » » 4 years ago, # ^ | 0 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 •  » » » 4 years ago, # ^ | 0 Thanks.  » 4 years ago, # | 0 Can anyone briefly explain the problem "Powered Addition", I mean full approach and walk through an example. •  » » 4 years ago, # ^ | 0 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.  » 4 years ago, # | +3 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.  » 4 years ago, # | +1 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 .  » 4 years ago, # | 0 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 •  » » 4 years ago, # ^ | +26 "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$. •  » » » 4 years ago, # ^ | +8 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 sense3) 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 mindThanks •  » » » 4 years ago, # ^ | ← Rev. 2 → 0 I've got how we come up with f=3 from the commentsHowever 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.  » 4 years ago, # | +11 Finally become master in this round. I like the problems! Thanks a lot.  » 4 years ago, # | +18 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) •  » » 4 years ago, # ^ | +3 Weired. You can Send a message to https://codeforces.com/profile/MikeMirzayanov •  » » » 4 years ago, # ^ | +5 Thank you! You are so kind!  » 4 years ago, # | 0 Great editorial. Thanks a lot!  » 4 years ago, # | 0 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! •  » » 4 years ago, # ^ | +1 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. •  » » 4 years ago, # ^ | +3 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 •  » » 4 years ago, # ^ | ← Rev. 2 → +4 aspiriner This picture may help you  » 4 years ago, # | 0 First I thought maximal independent set in div1D, but got Wrong Answer on pretest 4.  » 4 years ago, # | +10 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 !  » 4 years ago, # | 0 can someone explain div2-C,i am not able to understand the editorial. •  » » 4 years ago, # ^ | 0 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 •  » » » 4 years ago, # ^ | 0 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. •  » » » » 4 years ago, # ^ | 0 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). •  » » » » » 4 years ago, # ^ | 0 Thanks, got it. •  » » » 4 years ago, # ^ | 0 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? •  » » » » 4 years ago, # ^ | ← Rev. 2 → +1 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.  » 4 years ago, # | 0 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 •  » » 4 years ago, # ^ | 0 it is wrong because the required condition is not fulfilled as your answer will make seqeunce like this 7<=7>1. •  » » 4 years ago, # ^ | 0 For array -2 5 5 6 the answer will be 5 5 -2 6 •  » » » 4 years ago, # ^ | 0 yes,but according to tutorial it is printing 5-2 5 6 •  » » » » 4 years ago, # ^ | 0 according to tutorial it will print 5 5 -2 6.  » 4 years ago, # | 0 Can anyone explain O(N) approach for div 2C ? I know how to do it in O(NlogN) but not in O(N) •  » » 4 years ago, # ^ | 0 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. •  » » » 4 years ago, # ^ | ← Rev. 3 → 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]. •  » » » 4 years ago, # ^ | 0 why do we need to add the 1? •  » » » » 4 years ago, # ^ | 0 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.  » 4 years ago, # | ← Rev. 2 → 0 Can anyone please explain how the answer of this testcase in problem div2/probC is 3.4 2 -1 -3 -4  » 4 years ago, # | +2 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. •  » » 4 years ago, # ^ | +5 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? •  » » » 4 years ago, # ^ | 0 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. •  » » 4 years ago, # ^ | +5 Nice explanation but I read your code to understand fully. =)) Code is still the best explanation. •  » » 3 years ago, # ^ | 0 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 0The 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.  » 4 years ago, # | ← Rev. 2 → 0 I cant understand the editorial of Powered Addition clearly.Please help •  » » 4 years ago, # ^ | 0 I just post my 2 cents above, hope it is easier to understand  » 4 years ago, # | 0 Who can explain problem A again. I don't undersatand why answer is n •  » » 4 years ago, # ^ | 0 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  » 4 years ago, # | +8 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.  » 4 years ago, # | +8 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.  » 4 years ago, # | 0 Why does my solution to Div2-C is not working . https://codeforces.com/contest/1339/submission/76407068can somebody please help me out on this . •  » » 4 years ago, # ^ | ← Rev. 2 → 0 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.  » 4 years ago, # | ← Rev. 2 → 0 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.  » 4 years ago, # | ← Rev. 3 → +8 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. •  » » 4 years ago, # ^ | ← Rev. 3 → 0 (erased) •  » » 4 years ago, # ^ | ← Rev. 2 → 0 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 •  » » » 4 years ago, # ^ | +20 Ugh, bad boy. You should be more responsible to your round. •  » » 4 years ago, # ^ | +2 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.  » 4 years ago, # | 0 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. •  » » 4 years ago, # ^ | 0 You can see that we can make$f = 1$in this tree anyway. •  » » » 4 years ago, # ^ | 0 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? •  » » » » 4 years ago, # ^ | ← Rev. 2 → 0 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$.  » 4 years ago, # | 0 Can anyone please explain me the second test case for Div1A/Div2C(1338A - Прибавление степеней)? Input: 6 3 1000000000 0 -1000000000 1 6 2 -1000000000 1000000000 2 1000000000 -1000000000 2 1000000000 1000000000 2 -1000000000 -1000000000 Output: 31 0 0 31 0 0 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. •  » » 4 years ago, # ^ | ← Rev. 3 → 0 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.  » 4 years ago, # | 0 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. •  » » 4 years ago, # ^ | ← Rev. 2 → 0 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}$) ... •  » » » 4 years ago, # ^ | 0 Thank you for your explanation.  » 4 years ago, # | +5 Nice editorial.  » 4 years ago, # | 0 @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?  » 4 years ago, # | ← Rev. 2 → 0 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 •  » » 4 years ago, # ^ | 0 Because$3$is used twice in your sequence.  » 4 years ago, # | 0 Video editorial for Div2D/Div1B:  » 4 years ago, # | 0 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? •  » » 4 years ago, # ^ | ← Rev. 2 → 0$x \oplus (x \cdot 2^{30}) = x \cdot (1 + 2^{30})$if$x < 2^{30}\$.
 » 4 years ago, # | ← Rev. 3 →   0 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 3 and Lemma 6a/b are 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!
 » 4 years ago, # |   0 i found a crazy solution of div1B https://codeforces.com/contest/1338/submission/76346806 can anyone plz explain the logic
 » 4 years ago, # |   0 Can someone provide insight into the mathematical induction referred to in observation 2 of div1C (Perfect Triples)?
 » 3 years ago, # | ← Rev. 3 →   0 B was tough
 » 3 months ago, # |   0 In div2B can we solve the problem using a hashMap, like storing the values of differences of array and their indexes?
 » 6 weeks ago, # | ← Rev. 3 →   0 Problem Div2C is good