McDic's blog

By McDic, history, 7 months ago, In English

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.
Tutorial of div2 B-C #1
 
 
 
 
  • Vote: I like it
  • +346
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it +61 Vote: I do not like it

McDic orz

»
7 months ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
7 months ago, # |
Rev. 2   Vote: I like it +32 Vote: I do not like it

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

  1. an -> nth number with odd number of bits

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

  3. 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.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    Nim Arithmetic is definitely overkill for this problem.

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +71 Vote: I do not like it

    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

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    A solution with nim multiplcation: 76499145

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

»
7 months ago, # |
  Vote: I like it +192 Vote: I do not like it

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.

»
7 months ago, # |
Rev. 3   Vote: I like it -41 Vote: I do not like it

[DELETED]

»
7 months ago, # |
  Vote: I like it +62 Vote: I do not like it

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 ?

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Fastest editorial I have ever seen!

»
7 months ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks a lot, I will keep practicing then :D. PS: I also like your picture :)

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
7 months ago, # |
  Vote: I like it -118 Vote: I do not like it

i think it is better to provide codes instead of stories

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like 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.

»
7 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Good editorial. I especially liked those behind stories.

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

»
7 months ago, # |
  Vote: I like it -62 Vote: I do not like it

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.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +100 Vote: I do not like it

    How come did you only solve A then?

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it -40 Vote: I do not like it

      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)

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +48 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it -11 Vote: I do not like it

          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

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it -9 Vote: I do not like it

          Yeah you're correct style is the better word here. I feel the style of cf div2 contests has changed drastically in the past few months with most of the contests being like the one today and slowly contests like these start to get boring. I really liked the last edu and I hope all aspects of skills are taken care of in future rounds and not just observational skills

»
7 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

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

      Thank you for the explanation. I got it now.

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

      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?

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        1. 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.
        2. 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.
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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>

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

      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)

»
7 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
7 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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?

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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 ^^.

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

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

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

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

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

        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 !

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

          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?

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

            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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody please explain problem A and its editorial?

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

    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.

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

    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.

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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!

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

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

»
7 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it
E intuition?
»
7 months ago, # |
  Vote: I like it +23 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

      thanks

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

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

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          please tell me how you solved D

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Btw, why ask this here xD

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

    They upload English editorial for international users after few days from contest. If u don't want to wait, then just download the editorial and upload on google translator to translate the file.

»
7 months ago, # |
  Vote: I like it +13 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
    Rev. 5   Vote: I like it +42 Vote: I do not like 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

»
7 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
7 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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.

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

    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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

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

    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

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

      Thanks.

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

        please check my code why it gives runtime error while run on some test case

        include <bits/stdc++.h> using namespace std;

        int main() { int t; cin >> t; while(t--) { long long *res = new long long[32]; for(int i=1;i<=32;i++) { res[i]=pow(2,i-1); } int n; cin >> n; long long *arr = new long long[n]; for(int i=0;i<n;i++) { cin >> arr[i]; } int i=0,result=0; while(i < n-1) { if(arr[i] <= arr[i+1]) i++; else { long long ans = arr[i]-arr[i+1]; int diff=0,j; for(j=i+1;j<n;j++) { diff = arr[i]-arr[j]; if(ans <= diff) ans=diff; else { i=j-1; int r=1; while(ans >= res[r]) r++; arr[j-1]+=res[r-1]; result+=(r-1); break; } } if(j == n && diff > 0) { i=j-1; int r=1; while(ans >= res[r]) r++; arr[j-1]+=res[r-1]; result+=(r-1); break; } } } cout << result<<endl;

        } return 0; }

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

      please check my code why it gives runtime error while run on some test case

      include <bits/stdc++.h>

      using namespace std;

      int main() { int t; cin >> t; while(t--) { long long *res = new long long[32]; for(int i=1;i<=32;i++) { res[i]=pow(2,i-1); } int n; cin >> n; long long *arr = new long long[n]; for(int i=0;i<n;i++) { cin >> arr[i]; } int i=0,result=0; while(i < n-1) { if(arr[i] <= arr[i+1]) i++; else { long long ans = arr[i]-arr[i+1]; int diff=0,j; for(j=i+1;j<n;j++) { diff = arr[i]-arr[j]; if(ans <= diff) ans=diff; else { i=j-1; int r=1; while(ans >= res[r]) r++; arr[j-1]+=res[r-1]; result+=(r-1); break; } } if(j == n && diff > 0) { i=j-1; int r=1; while(ans >= res[r]) r++; arr[j-1]+=res[r-1]; result+=(r-1); break; } } } cout << result<<endl; } return 0; }

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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.

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

      Thanks a lot for the explanation bro. You helped me realized that any difference can be represented by sum of a sequence of powers of 2. Damn I'm dumb :(

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

        Maybe this solution can be very helpful- link

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

      Thanks a lot for your explanation!

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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 .

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

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

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

»
7 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +18 Vote: I do not like it

HELP! Please

Hi, 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)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great editorial. Thanks a lot!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

may someone explain little more div2 problem A. Added problem

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

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

    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.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    frank1586 This picture may help you

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

DELETED

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

First I thought maximal independent set in div1D, but got Wrong Answer on pretest 4.

»
7 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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 !

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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

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

      RajatBansal16 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.

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

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

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like 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?

      • »
        »
        »
        »
        7 months ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    Yep , 5 -2 5 6 is wrong , the correct output will be 5 5 -2 6 or 5 5 6 -2 .

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

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

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

      so the logic in the tutotrial is wrong?

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

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

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

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

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

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Mind-Blowing tutorial!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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.

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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].

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

      why do we need to add the 1?

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

        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.

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

4 2 -1 -3 -4

»
7 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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.

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

    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?

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

      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.

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

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I cant understand the editorial of Powered Addition clearly.Please help

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

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone share the code for sorted adjacent differences and powered addition plz?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Div 2 A problem my pretest passed but it isn't evaluated against main test cases. How this can happen?

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

The first question is really simple, but I was actually wrong twice. Ah, I am really Pupil level.

But it ’s really easy, is n’t it?

»
7 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Worst Editorial!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very good editorial. The explanation is appreciable and questions were of nice level.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please elaborate the explanation of div2 C; i was not able to comprehend what to do and why?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Div2 A was definitely the easiest problem! I could just guess it from the sample! it worked!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to get the intuition behind problems like Div 2 B

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 .

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

After doing lot's of problems on the problemsets here and on leetcode and having not to much trouble anymore, I thought I'm finally ready for a contest.

I stuck on A 2 hours.

Even after reading it now, I still don't quite get it. Definitely not the easiest ever, but nice problem, I think I need to sleep a few nights on it to get it.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi folks, I still don't understand the Div2-A. Actually I don't even understand the problem. Maybe it was lack of my english. Can someone explain in simple terms?

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

    In the note of the problem, they show which coverings are legal but maybe someone can show which coverings are wrong and why. I think many people really don't understand the problem. It is just frustrating.

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem E ?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

BEST EDITORIAL ...LUV IT

»
7 months ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

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.

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    (erased)

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

    • »
      »
      »
      23 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I got stuck in this part of your tutorial:  Lemma 2: There exist nodes U in Q,V in P, such that U->V exists.  Let R = in(V) intersection Q. That V you are refering to, is it an specific one that satisfy that condition of Lemma 2? Or is it the set of all of those Vs which satisfy it? I know the problem is 7 months old, but it'd suppose a great deal of help for me.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B ?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve G ?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

    ex1

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

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

      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?

      • »
        »
        »
        »
        6 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In 1338B Edge Weight Assignment(XOR), It is written

Q1 You can prove that minimum value of _ is at most 3

Why at most 3? why it can't be 4? I am not able to figure out from diagram. Please can someone explain the diagram.

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

So answer for minimum value is at most 3. This line is also not clear to me because i am a noob in programming. Please can some expert help me in understanding it.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain me the second test case for Div1A/Div2C(1338A - Powered Addition)?

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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
  • »
    »
    6 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain div2C/div1A .

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like 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;

    • 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}$$$)
    • ...
»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Nice editorial.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

@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?

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Video editorial for Div2D/Div1B:

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

shubhammitt aviroop123 A. Powered Addition My thought ...if we select a number where it breaks the rule of increasing( prev )....and from that point the smallest num till the end ie it should have the maximum difference from the chosen prev let it be mx

then the ans will be if(n == 0 || n == 1) then 0 else 1+log(mx);

this goes well for most of the test cases except for 1 or 2. Can you tell me where I am going wrong? My solution Your text to link here...

It fails on cases like 4 1 3 5 1 you can take test cases and see it gives the correct answer for most of the cases.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi folks,

In 1338E, Div1 E, Can we apply all pair shortest path algorithm ( Floyd-Warshall algorithm/Johnson's algorithm)? ,

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell me the logic of question 2

»
6 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i found a crazy solution of div1B https://codeforces.com/contest/1338/submission/76346806 can anyone plz explain the logic

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The second approach in the tutorial for Div2/D is wonderful. (Labeling the nodes)

I just loved the thought very very much. But it scared me a lot also.

How did someone have such an intuition?

Can someone share please, what actually provoked this!

Observation or some hit and trial or what?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Not related to the contest or the editorial.

I just wanted to ask, how did tzuyu_chou become red in just 15 contests and in the duration of a year? Is that because she is a genius already or Am I just dumb?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

found a O(n) solution for problem 1338A: code here

first check if the number given is lower than the last. if it is, then the array is not non-decreasing, so you have to find how much it takes to add to this number to make it equal to the last number to make this array stay as a non-decreasing array. this can be easily found with a[i-1]-a[i].

since the author decided to make it so you have to add a power of 2, you can easily use a logarithm to find the power of 2's needed to make the array non-decreasing, so find the log2 of a[i-1]-a[i], which then you may add 1 to as the problem stated you had to add 2 to the power of "x — 1"

the answer will be the maximum log2(a[i-1]-a[i]) across all numbers, as if you had one that is lower than the maximum, then you could have just selected that number to add that power of 2 to in a previous "second".

sorry if my explanation was hard to follow, i really don't know how to explain it. if anyone could explain it better than me, please do

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

A isn't easy