zltzlt's blog

Codeforces Round 949 (Div. 2) Editorial
By zltzlt, history, 6 months ago, In English

Thank you for participating! Sorry for being much harder than usual Div. 2 :( But we still hope you find some of our problems interesting.

Rating predictions (Inspired by sum's editorial)

1981A - Turtle and Piggy Are Playing a Game

Idea: zltzlt

Hint 1
Hint 2
Solution
Code

1981B - Turtle and an Infinite Sequence

Idea: zltzlt

Hint 1
Hint 2
Solution 1
Solution 2
Code for Solution 1
Code for Solution 2

1981C - Turtle and an Incomplete Sequence

Idea: zltzlt

Hint 1
Hint 2
Solution
Code

1981D - Turtle and Multiplication

Idea: sinsop90

Hint 1
Hint 2
Solution
Code

1981E - Turtle and Intersected Segments

Idea: zltzlt
Developed by 244mhq.

Hint 1
Hint 2
Solution
Code

1981F - Turtle and Paths on a Tree

Idea: yinhee
Developed by 244mhq and zltzlt.
Thanks AFewSuns and crazy_sea for discovering Solution 2, which runs faster than Solution 1!

Hint 1
Hint 2
Solution 1
Solution 2
Code for Solution 1
Code for Solution 2
  • Vote: I like it
  • +250
  • Vote: I do not like it

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

Auto comment: topic has been updated by zltzlt (previous revision, new revision, compare).

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

Look at the standings. It seems your F is too hard for a div2 so it works like a 5-problem round. Is that good?

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

    I will elaborate on that.

    You're right, it wasn't expected and that's mostly my fault -- I was able to come up with $$$O(n^2)$$$ solution pretty easily and thought that a lot of people will think about solution $$$O(n \cdot bound)$$$ after some time. In general, I don't want for last problem to be that hard and I will try to listen to feedback of other people more carefully. I still hope that people had fun thinking about this problem (and others problem of the round).

    And one more point -- we intentionally didn't put in pretests tests where you need to use very big value of bound (maximum one that zltzlt was able to construct was around 3k and you can pass pretests with around 1k). I also want to elaborate on that. In general, I would vote for pretests to be as strong as possible, but here it was kinda special -- we didn't want people to try to squeeze solutions just with pure guessing (and since I've underestimated the problem, I thought that a lot of people will try to do so), that's why I agreed to not use such tests into pretests. In retrospect, I would insist on putting them (because problem already turned out to be too hard), and I fell sorry for maspy, congratulations on the win though!

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
      ← Rev. 2   Vote: I like it +78 Vote: I do not like it

      I proved that the required upper bound is $$$O(N / \log N)$$$, but because creating a test case that achieves that upper bound also seemed non-trivial, I didn't seriously consider the constant factor. I ended up submitting with a slightly conservative estimate, taking into account the possibility of tight TL or ML. (Also, since the pretest succeeded with a limit of 1K, I submitted with a limit of 2K.)

      While it might have been better to have some cases in the pretests closer to optimality, I think it's great that there were test cases in the system tests that required quite large upper bounds. Thanks for preparing a good contest!

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

    look at the tester predictions, it is hard to be very accurate in predicting difficulties. F isnt very relevant for div2'ers anyways (only about 10 solve an average F?) that numbeer only decreased by 10.

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it -20 Vote: I do not like it
      F isnt very relevant for div2'ers anyways

      So, why are they in div2 contests?

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

    A problem having no solve is different from not having a problem.

    Do you think everyone who didn't solve that problem just quit after solving 5 problems?

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

Sorry for wrongly predicted the difficulty of problem F. As the writer, I wrongly predicted the difficulty to solve O(n^2) sol as well as calculating the maximum of MEX. So as is said above, guys can just consider it as a joke now:(

→ Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

Very surprised this didn't pass D:

https://codeforces.me/contest/1981/submission/263490566

Time complexity should be $$$O(Nlog\sqrt{N})$$$

Edit: nvm I forgot to consider that it was multi-tested

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

problem C has quite a bit heavy implementation.

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

    Not really, it took me about 20 minutes to implement.

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

    In thought it is hard to implement but in code not really. Using bitmask simplify it.

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

C has a significantly simpler $$$\mathcal O\left(n \log\left(n\right)\right)$$$ solution. Notice that instead of stopping at the LCA, if the path has missing entries, it is valid to continue farther up the tree. The path only has to stop when it runs out of missing entries or it reaches the root. Therefore, assuming at least one entry is not missing, a simple solution is to repeatedly choose the largest entry $$$x$$$ with missing neighbors and replace those missing neighbors with $$$\left\lfloor\frac x2\right\rfloor$$$ (or $$$2$$$ if $$$x = 1$$$). This can be implemented in about 20 lines with a priority queue:

Implementation
→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Wow great idea

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

    I did this but got some stupid rte on testcase 4.

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

    I could not understand your solution very well. It sounds like a great idea. Can you please explain in more detail (possibly with your thinking approach). Thank you

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

      For example, consider the sequence [9, -1, -1, -1, -1, -1, -1, 5]. The solution presented in the editorial is to find the unique simple path from 9 to 5 in the binary tree ([9, 4, 2, 5]) and then alternate between 5 and 10, resulting in the sequence [9, 4, 2, 5, 10, 5, 10, 5]. Most of the complicated logic in the solution is for finding this path, and in particular, for finding 2, the LCA of 9 and 5.

      My solution is to repeatedly find the largest entry with a missing neighbor and set its missing neighbor(s) to its value divided by two. In this example, 9 is initially the largest such entry, so set its missing neighbor to floor(9/2) = 4. Then, 5 is the largest such entry, so set its missing neighbor to floor(5/2) = 2. If the largest such entry is ever 1, we cannot set its neighbor to floor(1/2) = 0, so set it to 2 instead. Ties are broken arbitrarily. The full sequence of operations in this example is:

      9 - - - - - - 5
9 4 - - - - - 5
9 4 - - - - 2 5
9 4 2 - - - 2 5
9 4 2 1 - - 2 5
9 4 2 1 - 1 2 5
9 4 2 1 2 1 2 5

      For the last sample input, in the first step, 7 is the largest number, so set its missing neighbors to floor(7/2) = 3. Then, there are four 3's, each of which has at least one missing neighbor, so choose one arbitrarily (here I chose the first one). Then, there are two 1's and three 3's with missing neighbors, so chose one of the 3's arbitrarily (here I chose the last one). This case proceeds as follows:

      - - 3 - - - - 7 - - 3 - -
- - 3 - - - 3 7 3 - 3 - -
- 1 3 1 - - 3 7 3 - 3 - -
- 1 3 1 - - 3 7 3 1 3 1 -
- 1 3 1 - 1 3 7 3 1 3 1 -
2 1 3 1 - 1 3 7 3 1 3 1 -
2 1 3 1 2 1 3 7 3 1 3 1 -
2 1 3 1 2 1 3 7 3 1 3 1 2

      In the binary tree, this corresponds to choosing a path that gets as close to the root as possible and using the cycle 1 2 1 2 ... to fill any remaining space. This can be implemented easily using a priority queue.

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

        I got what you were trying to do , and i myself got the intuition maybe we can find the largest and insert half on each of its side , but i wasnt particularly able to get a conclusive proof to why this should work , I cannot think of a testcase at particular , but it just seemed to me that , there may exist a case where this solution wont work , do you have any proof as such why was this working , it will help me a lot in maybe understanding your thinking better or anything in such .

        Thank you in advance.

        → Reply
        • »
          »
          »
          »
          »
          6 months ago, # ^ |
          ← Rev. 3   Vote: I like it +8 Vote: I do not like it

          Assume that at least one space is not missing and that a solution exists. The other cases are easy: if all entries are missing, we can just set the first entry to $$$1$$$ and use the same algorithm, and to check whether there is no solution, we can just use the same algorithm and do a linear-time check at the end that the constraints are satisfied. Removing these steps and I/O, the remaining implementation is:

          Implementation

          Also note that the output is bounded by $$$\max\left(2, \max_i a_i\right)$$$, so it cannot exceed $$$10^9$$$.

          Now, consider each nonempty consecutive run of missing spaces. There are two cases here: either the run is a prefix/suffix of the array or it is a subarray with non-missing entries on either side.

          In the suffix/prefix case, the algorithm will start from the non-missing element adjacent to the run and iteratively add values that meet the constraints.

          Example

          The second case is slightly trickier. Let $$$a_i$$$ and $$$a_j$$$, $$$i < j$$$, be the entries on either side of the run. Consider the binary tree described in the editorial where $$$1$$$ is the root, $$$n$$$'s children are $$$2n$$$ and $$$2n+1$$$, and $$$n$$$'s parent is $$$\left\lfloor\frac n2\right\rfloor$$$. The solution, which we assume exists, will be a walk from $$$a_i$$$ to $$$a_j$$$ in this tree.

          Such a walk must consist of a simple path from $$$a_i$$$ to $$$a_j$$$ (which is unique in a tree) and some circuits. Trees are bipartite, so these circuits must have even length. Since we are assuming a solution exists, then, letting $$$d\left(a, b\right)$$$ be the distance from $$$a$$$ to $$$b$$$ in the tree, $$$j - i = d\left(a_i, a_j\right) + 2k$$$ for some integer $$$k \ge 0$$$ ($$$2k$$$ is the total length of the circuits and $$$d\left(a_i, a_j\right)$$$ is the length of the simple path).

          Example

          When this is true, this algorithm constructs such a walk. It does this by repeatedly choosing the deepest endpoint (this will be the endpoint with the greater value, ignoring ties) and connecting it to its parent. This will reach the LCA after $$$d\left(a_i, a_j\right)-1$$$ steps and have $$$2k$$$ steps left.

          Then, it constructs an even-length circuit to fill the remaining length. First, it alternately connects the left/right endpoint to its parent, so after any even number of steps, a circuit is formed. Then, if there are still any missing entries, it completes the circuit with alternating 1's and 2's.

          Example 1
          Example 2
          → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Say you have two numbers a and b with b>a and with x negative ones between them. The main claim is that if there exists a way to replace these x negative ones with some positive integers to satisfy the problem's condition, then there exist a way in which the number just before b is floor(b/2). This is because say you had 2*b or 2*b+1 just before b, then at some point between a and 2*b+1 you must have reached b. Keep doing this recursively till you reach a point when the number just before b is b/2. Fill the numbers between this point and our originial b with b/2 and b alternatively.

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

Question B Detailed Video Editorial

https://youtu.be/Gb5nnpg0TDk

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

    Thank you so much for this. Literally a life saver

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

Can someone explain what might be wrong with this solution for problem C? https://codeforces.me/contest/1981/submission/263494280

Thanks !

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

C's editorial is not friendly as a regular C. LCA is not something that most people thinking about in this position. There's still a solution without using such advanced topic, but why the author didn't do that?

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

    I solved C in the contest and I don't understand what the editorial is talking about.

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

Why downvote editorial?

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

Problem C, I use brute-force searching with "merge intervals" to get an AC. Hacks welcome.

263496224

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

    can you please explain your solution , what you did using merge intervals and how that concept is being used here ?

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

    Can you please explain your solution

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

    Can anyone explain what is wrong with this solution 263791858 for C

    → Reply
  • »
    »
    6 months ago, # ^ |
    ← Rev. 5   Vote: I like it +3 Vote: I do not like it

    Explanation:

    For each step, value x can be transformed into either of x/2, 2*x, or 2*x+1.

    If we deal with a interval of integers [left, right], it will become a union of 2 intervals:

    • [left/2, right/2]
    • [2*left, 2*right+1]
    • Both intervals are clamped within [1, 1e9].

    Therefore, for each step, we operate on the set of continous intervals (type Intervals in my code), and use the good-old leetcode's "merge interval" solution (ivls_shrink in my code) after each step.

    Finally, after the specified number of steps, we see if the target value is an element of the the final intervals, and fill back the numbers by looking up the stored history.

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

Here are my 2 submissions for problem B 263489923 and 263504667 .The first submission gives AC while the second submission gives a WA. The difference between the two submissions is that in the 1st submission ,in the end I have written 

ll st=max(n-m,(ll)0);
ll e=n+m;
ans|=e;
ans|=(st);

and therefore it gives AC. I can't really figure out if we don't write these two lines ,why my code gives WA ,or are the tests weak ?

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

Can someone explain, how in problem C

This code

is generating the path between the two nodes ?

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

    I'll try explaining whatever I've understood.

    Spoiler
    → Reply
»
6 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Love the first hint of the problem E

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

For problem $$$C$$$, i found this logic. In order to go from one positive value to next positive value, we find the minimum no. of operations required, then if the required operations is less than given steps and has same parity as required, it is possible to go from one value to next, otherwise just return -1. This we do for all such positive values. Then, for first and last element, we just fill remaining -1s by doing *2, /2 and so on.
HOW TO FIND OPERATIONS EFFECTIVELY?
Let's say for example, we want to make 3 to 9, this can be done in 4 operations but how?
$$$(3)_1$$$$$$_0$$$ $$$=$$$ $$$(11)_2$$$ and $$$(9)_1$$$$$$_0$$$ $$$=$$$ $$$(1001)_2$$$, we just find the common bits from MSB in both, don't change them and first delete the uncommon ones from val1(here 3) and insert uncommon ones from val2(here 9). Here, common bits are only MSB, so operations required will be 1(for deletion from 3) and 3(from addition from 9), so total 4.
During removing, do /2 operation, doing addition and bit is 0, do *2 operation, bit is 1, do *2+1 operation. We do this for all pairs of positive values of a.
Submission Link :- 263497185

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

what even is that solution to C lmao how can people even think about it as traversing a binary tree at all that's needlessly complicated and sounds like something that should be used within a moderately difficult Div2D. Instead, uhhh, my solution is much simplier, only kinda implementation heavy.

(before the yapping, here's the submission: https://codeforces.me/contest/1981/submission/263477772)

The condition that either val[i] has to be the rounded down value of val[i+1]/2 or the other way around can be interpeted as "when moving from an element to the next one, add or remove a bit from the back". This means that, as long as there exists a valid chain of suffix add/remove operation to "transition" between all non-empty values, there exists a valid sequence (for the prefix and suffix empty numbers, just fill them with random shit that still satisfies the condition).

My algo goes as follows:

1) Chug every non-empty number into a vector, alongside with their position.

2) When considering 2 consecutive non-empty number, consider their bit sequence. Shove all of them into 2 corresponding deque, dq1 for the first number and dq2 for the second one

3) When transforming from the first number to the 2nd one by suffix addition/deletion operations, we will want to keep the common prefix. Pop all of these out of the front of the 2 dqs. Then, delete the suffix of number 1 until it's empty (by constantly /2-ing the current value), then add the bits accordingly (by doubling the previous number, then either add 0 or 1 depending on the number on the front of dq2). Call the total amount of bit removal/addition operations num

4) When transforming from a number at position i to position j, a total of (j-i) operations are needed. After we're done with transforming val[i] into val[j], just keep adding in a bit and then remove it in the next step. If (j-i-num) (the amount of "filler" operations) is non-negative and divisible by 2, the transition is possible. Otherwise, return -1.

(would say that it's only a bit less complicated than the binary tree solution, this is kinda complicated for a div2C lmao)

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

    wait nvm it's actually the same thing lmao.

    at least the requirement is only 2 dqs instead of actually having to implement LCA. Though the LCA of 2 numbers in a complete binary tree is their prefix bit sequence or something anyways, so, uhhhhh

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

      You don't even need two deques; see my submission: 263480468.

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

        ...for all that matters, I highly doubt that this dumb fuck who failed to get Expert 8 times in a row could compare with the efficiency and beauty of the legendary Tourist, but you do you

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

          I highly doubt that this dumb fuck who writes author: tourist on the top of his code while not being even 1/1000th of tourist's skill could compare with the efficiency and beauty of tourist either.

          → Reply
»
6 months ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

C has a much harder solution in tutorial , I did something which i feel is much simpler we just need to fill numbers between two non -1 numbers ,other than that its easy .Firstly store all the index where v[i]!=-1 then between two such indices we need to fill such that conditions are fullfilled , so say we want to fill numbers between l and r indices ,if v[l-1]>v[r+1] fill v[l] with v[l]/2 else v[r] with v[r]/2, we will try and get the two numbers as close as possible and minimum as possible(if we fill from both sides we can maintain the conditions more easily as from at least one side the number will be either half of the previous or next) , so basically they will both reach 1 at end after dividing by two as much as possible , after that we can just continue filling 2 and 1 alternatively ,after all this we should check if conditions are satisfied as there are cases where the numbers cannot come as close to each other https://codeforces.me/contest/1981/submission/263488558

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

C really has so much implementation.Hope it can be easier nxt time.qaq

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

Can i get a counter test case for my solution of second problem

link: https://codeforces.me/contest/1981/submission/263471361

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

zltzlt Can you please explain why the following is true in Task B?

When $$$\left\lfloor\frac{l}{2^{d + 1}}\right\rfloor \ne \left\lfloor\frac{r}{2^{d + 1}}\right\rfloor$$$, $$$dth$$$ digit will be flipped at least twice between $$$[l,r]$$$

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

    Because the $$$d$$$-th bit of $$$l$$$ and the $$$d$$$-th bit of $$$r$$$ are both $$$0$$$, and since $$$\left\lfloor\frac{l}{2^{d + 1}}\right\rfloor \ne \left\lfloor\frac{r}{2^{d + 1}}\right\rfloor$$$ there exists an $$$x$$$ in range $$$[l, r]$$$ such that the $$$d$$$-th bit of $$$x$$$ is $$$1$$$.

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

In problem D
we can choose $$$x$$$ primes such that we can make $$$\ x \ * (x \ + \ 1) \ / \ 2 \ >= \ n \ - \ 1$$$ pairs,
but don't know how to make such an arrangement.
please tell me i'm in correct direction or not. Thanks!

→ Reply
»
6 months ago, # |
  Vote: I like it +27 Vote: I do not like it
clist rating
→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain why my following approach for the problem B fails:

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

    Implementation issue I think. Double check

    for (int j = i - 1; j >= 0; j--)
{
       if (((fst >> j) & 1LL))
       {
            fst = fst ^ (1LL << j);
       }
}

    I believe all it does is convert fst to 0.

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

https://codeforces.me/contest/1981/submission/263527099

--> wrong submission

https://codeforces.me/contest/1981/submission/263500175

--> correct submission

why (temp.size()-1)>len --> is performing differently when I substitute siz = temp.size()

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

Can anyone please tell the mistake in this code, getting WA.

https://codeforces.me/contest/1981/submission/263510295

Thank you!

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

Someone will never think such complex solution in problem C!

I solved C with Two Pointers method, just filling the -1 gaps in the array!

My solution: 263542553

Time Complexity: O(n)

Uphacks are welcome!

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

    i have done 2 pointer filling with LCA at common number we get by dividing two . soln.

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

    hey very good solution, but could you explain that greedy nature you used. if (arr[L] >= arr[R]) { if (arr[L] > 1) { arr[L + 1] = arr[L] >> 1; L++; } else { // 1 cannot be divided by 2, cz all a[i] >= 1 arr[R — 1] = arr[R] << 1; R--; } } else if (arr[L] < arr[R]) { if (arr[R] > 1) { arr[R — 1] = arr[R] >> 1; R--; } else { arr[L + 1] = arr[L] << 1; L++; } }

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      Okkayy... Suppose you have a gap like: [4, -1, -1, -1, 3]

      • Now, consider two numbers outside the gap, 4 and 3, as 4 >= 3, the gap: [4, 2, -1, -1, 3] [4 >>= 1 means dividing by 2, so 4/2 is 2]
      • Now, consider 2 and 3, 3 >= 2, then: [4, 2, -1, 1, 3]
      • Then, 2 >= 1, then [4, 2, 1, 1, 3]
      • If the filled-gap is valid, continue to next gap!
      • But in this case, this is invalid, which will be checked on later step and print -1

      Consider the same gap with an extra -1! Then finally we will get [4, 2, 1, -1, 1, 3]

      • Here 1 >= 1, but here we cannot divide 1 by 2, because by rule, all a[i] >= 1, so multiply by 2, then we are getting [4, 2, 1, 2, 1, 3].
      • This is correct solution!

      Now, imagine different gaps and try yourself to fill it up!

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

        thanks, got it very nice approach

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

        what was the intution behind such approach ? How can a newbie comeup with some intution like this ?

        → Reply
        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          • I didn't learn to code binary tree as mentioned in the editorial yet. So I had to think as much as I can code, easier way!

          Consider a gap: [4, _, 16], here you can use 8 in the gap. Means multiplying by two the smaller side (4 <= 16). [4, 8, 16] is valid. [4, 8, 4] is valid for [4, _, 4]. In my previous comment I showed division approach. But,

          Q. Why division? Why not multiplication?

          In the problem statement, you see a floor function is used. So I got the idea not to multiply numbers as much as I can, because multiplying a numbers minimizes the usage of the floor function, as a result two non-equal number will be mismatched!

          • Consider [4, _, 5], but [4, 8, 5] is invalid. Where [4, 2, 5] is valid option!
          • The reason is a number x cannot have multiple floor(x/2)!
          • But two different numbers x and y can have same floor(x/2) = floor(y/2)

          So, there is an observation that using division can minimize the difference between two numbers (e.g. 4 and 5 etc.), but using multiplication never minimizes the difference! And integer dividing already doing floor!

          Q. Why are we using multiplication in 1?

          This answer was already given in my previous comment. As we always divide the bigger one, we will get 1 when both side have 1s, so these are already equal sides. Multiplication can be used when there is no value differences between two sides! As multiplication doesn't remove value differences between the sides.

          The case [1, _, 1] is similar to [4, _, 4] which is mentioned above.

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

    Very similar idea with better implementation, i guess,: 265693364.

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

Basic idea of D was almost exactly same as https://codeforces.me/problemset/problem/367/C

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

Super short solution for B.

int a = max(0ll, n-m), b=n+m; int ans = (b | ((1<<__lg(a^b))-1)); if(!m){ cout << n << endl; continue; } cout << ans << endl

I just used the xor to account for the spread and chose the largest element that I can reach (m+n) as the base. The idea being that the largest bit in xor is the largest bit that spreads and all bits less than that would also spread.

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

simple bruteforce for problem solution

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

i like problem c though i use brute force to find the path during the contest...

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

Why do these writers write code that is not understandable.I agree you guys are pro but that doesnot mean every one can understand it.What does this means ,I am unable to understand for B: void solve() { ll n, m; scanf("%lld%lld", &n, &m); ll l = max(0LL, n — m), r = n + m, ans = 0; for (int i = 31; ; --i) { if ((l & (1LL << i)) || (r & (1LL << i)) || (l >> (i + 1)) != (r >> (i + 1))) { ans |= (1LL << i); } } printf("%lld\n", ans); }

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

please, why my code wrong (problem B)

include <bits/stdc++.h>

using namespace std;

long long cases, m, n;

int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

cin >> cases;
for (int t = 1; t <= cases; t++)
{
    cin >> n >> m;

    if (m == 0) cout << n << "\n";
    else {
       int len = __lg(m + n), sum = m + n, lim = 0;
       for (long long i = (1LL << len); i >= 1; i = i >> 1) {
         if ((sum & i) > 0 && (n & i) == 0) {
          lim = i;
          break;
         }
       }
       for (long long i = 1; i <= lim; i = i << 1) {
         n = n | i;
       } cout << n << "\n";
    }
}

return 0;

}

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

thanks, it has been fixed. I forgot to OR minn, i just think it is not important

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

long long cases, m, n;

string binary(int n) { string ans = ""; while (n > 0) { ans = char(n%2 + '0') + ans; n = n / 2; } return ans; }

int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

freopen("testCode.inp", "r", stdin);
freopen("testCode.out", "w", stdout);

cin >> cases;
for (int t = 1; t <= cases; t++)
{
    cin >> n >> m;

    if (m == 0) cout << n << "\n";
    else {
       int minn = max(0LL, n - m), maxx = n + m;
       int lim1 = 0, lim2 = 0;

       for (long long i = (1LL << __lg(maxx)); i >= 1; i = i >> 1)
         if ((maxx & i) && !(n & i)) {lim1 = i; break;}
       for (long long i = (1LL << __lg(minn)); i >= 1; i = i >> 1)
         if ((minn & i) && !(n & i)) {lim2 = i; break;}

       for (long long i = 1; i <= max(lim1, lim2); i = i << 1) 
         n |= i;
       cout << n << "\n";
    }
}

return 0;

}

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

Hello In question D. Let the number of vertices in the complete graph be m. If m is odd, then the degree of each node is even, so this graph contains an Eulerian path, and the path length is equal to the number of edges, which is m(m+1)2.

But how the edges should be mc2 which is (m*(m-1)) / 2.

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

Can someone explain why are we looking at only the endpoints of the required sub array to look at in problem B?

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

In problem D if I tried to keep extra edges(when K is even) in the last 2 end points I get WA (https://codeforces.me/contest/1981/submission/263673037) but if i keep the first and the last end points I get AC (https://codeforces.me/contest/1981/submission/263675186)

Can someone explain what is the cause ?

Ex. n = 9, we get k = 4

If i distribute the edges such that degree looks like this 5 4 4 5 I get AC but if I distribute it as 4 4 5 5 I get WA as in the Eularian Path there are 2 pairs with same product. Why is my implementation going wrong in this type of distribution.

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

    I believe it's because for finding an euler path, it is important where you are starting.

    If the number of vertices V is odd, it doesn't matter because each vertex has an even degree.

    If the number of vertices V is even, you presumably remove the edges until only 2 of the nodes have an odd degree. In that case, you have to start the dfs from some vertex with odd degree. The algorithm relies on the fact that if you start on a vertex with odd degree, you can only end on the other node with odd degree (all other nodes have even degree), because if you enter nodes with even degree through an edge, you are guaranteed to have another edge to exit the node from.

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

      Thank you very much, I did not know that. I changed the starting vertex to the last vertex and got AC.

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

Ignoring the difficulty, I think this round is more edu than edu round.

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

just found this submission for D, and to me it seems very random. Can anybody explain why this part is correct (if it is) act=(act+seguentSalt[act]++)%mida

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

B was solvable. I was stuck finding the pattern, rather I should have just wrote k th term of ai :(

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

Can there be any easier approach for C. can someone suggest without tree and a more intuitive solution for this..??

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

    i mean only the explanation for finding an array knowing both the ends(a1 and an-1) might suffice!

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

    Check my submission: 265693364. It is quite intuitive in both logic and implementation. The idea is to find two non-negative elements and use two pointers to fill the in-between -1s by dividing the greater one by 2 and writing on the left/right side accordingly. Mathematically: if(v[right] >= v[left]) {v[right - 1] = v[right] / 2;right--;} else { v[left + 1] = v[left] / 2; left++; }

    And to handle edge cases, I have defined a vector of size n + 2, putting 0s on either side.

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

in fleury algorithm dont we have to check if the edge we are traversing is a bridge or not ? i read the code above for problem D afew times and i still dont get how they are handling it

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

    Hello, I had the same problem trying to implement my function to find an eulerian path. I believe the author's solution doesn't use Fleury after all. In fact, it's some sort of Hierholzer's algorithm. You can try seeing that this method returns a valid eulerian path (or cycle) given dfs is first called on a vertice with odd degree (if there is one).

    Now I'll always remember this simple method of finding the eulerian tour.

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

      i solved it using Hierholzer's algorithm but it doesnt seem like Hierholzer's algorithm because in Hierholzer's algorithm you have to remove the edge u add when m is odd cuz the algorithm only finds cycles and not paths but in the authors solution they dont seem to remove any edge iam so lost trying to understand the intuition behind the authors solution honestly

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

        Here's what I came up with : You run a dfs starting on an odd degree. It will then end on the other odd degree. But your path may not be complete. In fact, you can see that, when exiting a call to dfs, the remaining calls to dfs will insert loops at the path you are currently in.

        In the end you have a valid path that visits all the edges.

        Now with your remark I remember that there may have been an easy method where you remove the first and last edges, indeed ... But it should be about as easy to implement.

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

          i feel so dumb we forgot the fact that we are dealing with a complete graph thats why it'll always end with a complete path on the other odd vertex

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

            Well, when you reach the first end of a dfs function, the path may not be complete. But it will for sure be on the other vertex with odd degree. That's because when you enter a vertex, if it initially had an even degree, then when you leave it it will have an even degree again : either 0 and you don't come back to it, or something positive and you will be able to exit it again.

            Now when it backtracks through the dfs, it will find other paths that will have to be loops (similar proof).

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

              it took me a minute there but i see what you mean, now i think the only time we need to add and edge between the odd vertices is when we are starting from an arbitrary vertex but if we are only starting from one of the 2 odd vertices then there is no need for me to add that extra edge

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

      Sorry for making mistakes. We should use Hierholzer's algorithm in this problem.

      → Reply
  • »
    »
    6 months ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    Also, I've seen your code. Note that you don't need to binary search the right $$$m$$$ at the beginning. It's something that was suggested by the editorial I know, but in fact you can do a linear search ; the complexity is perfectly fine.

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

      yea also another thing so weird i dont seem to understand is that if we use the Hierholzer's algorithm starting from an odd vertex without adding the edge that we remove later it'll work for some reason i cant seem to wrap my head around this algo

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

      why does it need to be an Eulerian path?

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

may someone tell me why my code get wrong answer in the sample 1 1000000? https://codeforces.me/contest/1981/submission/264373070

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

I cannot understand this fact The left$$$1$$$spreading to$$$a_n$$$takes$$$x+1$$$seconds, and the right$$$1$$$spreading to$$$a_n$$$takes$$$2^d−x$$$seconds. Suppose, I am taking 10001101 number in binary, then how the bits are spreading in it from left to right and right to left?

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

    Umm Actually we are talking about dth bit there so when x lies in range 0 <= x <= 2^d — 1 let say d = 2 here then 0 <= x <= 3 now imagine a number line from 0 to 3. x is the point where the number lies on that number line. on that number line -1 and 2^d will be only numbers whose dth bit will be set for more clear view

    • 0 -> 0
    • 1 -> 1
    • 2 -> 10
    • 3 -> 11

    now see here for 2nd bit can only be set because of 4 and -1 now x is the point where you actually number lies in this number line (How far is it from 0) the distance is simply the time taken to set the bit as you can tell from left it will be x + 1 and from right it will be 2^d — x so basically we are just shifting some number to number line of 0 — (2^d — 1) . I hope this does not confuse you more I understood it this way. Correct me if I am wrong somewhere

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

Can anyone explain me the second solution of problem B?

How/Why [l / 2^(d + 1)] != [r / 2^(d + 1)], d-th bit of answer is 1? I'm confused at "flipped.

Thanks alot!

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

    Consider ith bit (from right), we know the bit is off in l and r otherwise we would already include it in answer. Now for number between l-1 and r-1 (inclusive) we have to check whether ith bit is on any time. Notice when you write consecutive numbers, ith bit is on for 2^(i-1) times consecutively and then off for 2^(i-1) times (consecutively). For eg, look at the 3rd bit from right between the numbers 16 and 24

    • 16 -> 10000
    • 17 -> 10001
    • 18 -> 10010
    • 19 -> 10011
    • 20 -> 10100
    • 21 -> 10101
    • 22 -> 10110
    • 23 -> 10111
    • 24 -> 11000

    In this sequence the 3rd bit from right is on 4 times from 16 to 19 and then off for 4 times from 20 to 23 and the pattern repeats. You are given l and r such that ith bit is off in both of them. Thus if the numbers between l and r is greater than or equal to 2^(i-1) then the bit must have flipped in the range otherwise not.

    You can check my submission I think it is clean

    https://codeforces.me/contest/1981/submission/265039262

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

Still haven't got why in D we should remove m/2 — 1, not m/2. Can somebody explain?

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

Hi! Thanks for the tasks. Does anyone has thoughts/any references on how the proof for F can be generalized beyond chains? As I understand, we have proved that optimal solutions for chains it's $$$O(\frac{n}{ln{n}})$$$, but that argument doesn't fit for trees (for example, full binary trees consisting of ones).

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

    We need some chains to cover a tree, and if for a single chain we need to consider MEX up to $$$O(\frac{n}{\ln n})$$$, then in the whole tree we also just need to consider MEX up to $$$O(\frac{n}{\ln n})$$$.

    → Reply
»
5 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

.

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

why in solution 1 of problem B x <= 2 ^ d — 1, and not x <= 2 ^ (d + 1) — 1?

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

There is not a single accepted submission for problem E in pypy3 till now, I wonder does the author checks out that the time limit is enough so that the correct algorithm can pass in different languages?

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

Nevermind, I understand now.

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

zltzlt can you explain this : Otherwise, if ⌊l2d+1⌋≠⌊r2d+1⌋, then the d-th bit has been flipped at least twice from l to r

i read your comment but stiil dont understand why is that true ?

thank you

→ Reply