Monogon's blog

By Monogon, history, 5 months ago, In English

I hope you enjoyed the contest!

1615A - Closing The Gap

Author: PurpleCrayon

Tutorial

1615B - And It's Non-Zero

Author: PurpleCrayon

Tutorial

1615C - Menorah

Author: Monogon

Tutorial

1615D - X(or)-mas Tree

Author: PurpleCrayon

Tutorial

1615E - Purple Crayon

Author: PurpleCrayon

Tutorial

1615F - LEGOndary Grandmaster

Author: PurpleCrayon

Tutorial

1615G - Maximum Adjacent Pairs

Author: BledDest

Tutorial

1615H - Reindeer Games

Author: Monogon

Tutorial
 
 
 
 
  • Vote: I like it
  • +178
  • Vote: I do not like it

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

As someone who got WA pretest 8, was G doable with flows?

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

    By making a test case like $$$(a_i$$$ $$$0$$$ $$$0$$$ $$$b_i$$$ $$$n)$$$ repeated $$$m$$$ times the answer is quite clearly $$$m+($$$size of maximum matching where edges are $$$a_i-b_i)$$$, so unless you can solve maximum matching with flows the answer is no.

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

why f*cking tight time??????????????????????????

»
5 months ago, # |
Rev. 2   Vote: I like it -29 Vote: I do not like it

fastest editorial ¿?

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

I solved upto E in the contest and have ready code for F to submit now lol. Amazing problems.

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

How to solve problem b for l and r less than equal to 10^9.

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

    Maths

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

    solve by doing pre-computation... and in this precomputation use prefix sum method to store no. of zeros bitwise ... so at the end you can get answer of each testcase in o(1) time

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

      This works only for l, r <= 2 * 10^5 no ? Correct me if i'm wrong.

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

        Yes Bcoz test case is up to 10^4

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

          But ... "How to solve problem b for l and r less than equal to 10^9.

          "

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

            Do you literally think , Test case<= 10^4 And then l and r <= 10^9 Will this work bro?

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

              Correct me if I'm wrong, but you said : solve by doing pre-computation... and in this precomputation use prefix sum method to store no. of zeros bitwise ... so at the end you can get answer of each testcase in o(1) time

              Have I misinterpreted something ?

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

                Then it'll work... Definately i guess... What you say according to your opinion?

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

                  IMO, your algorithm works only for l,r <= 2*10^5 no ?

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

                  Yes...

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

                  so your algorithm doesn't work for 2*10^5 <= l, r <= 10^9

                  UPD : sorry everyone for the long conversation

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

                  Yes Yes.... And thanks for clearing my confusion

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

            we can calculate the number of set bits at jth position in [1,n] in O(log n)

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

              Yeaa... Sigma( 2^(i-1)) ;i = pos of set bits greater than Or equal to j in n. Correct?

              Edit- with some modifications for the equality thing

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

                count of numbers in [1,x] having jth bit set is floor(x/(2^(j+1))) + max(0,x%(2^(j+1))-2^j).

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

                  Can you please explain the purpose of max() func here? Because IMO x%(2^(j+1) — 2^j) would always result in +ve number which ultimately will be the maximum.

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

                  look closely i have written [x%(2^(j+1))]-2^j which can be negative

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

                  Sorry, my bad!

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

    It can be easily done in O(log2(r))

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

      Congrats for being the Legendary Grandmaster : )

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

        Thanks ^-^, You too for becoming International Master. Merry Christmas Everyone :)

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

      O(log(r))*

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

      Can you explain how your code for finding total numbers having Kth bit set is working

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

      What is the logic for count function?

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

      Bro, I did not understand how does your getcount function work. Could you please explain how does it work?

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

        For all the bits greater than kth bit, he shifted them right by 1 , and deleted all the smaller bits. Second expression is to add more stuff if kth bit itself is set in n.

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

      Thanks a lot. that's a great solution.

      Merry Christmas everyone

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

      Can you please explain why you used l and r+1 in calculating x and y? I think it should be l-1 and r+1, but got WA using this.

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

        Actually, this getcount(int N, int K) function returns the no of Kth set bits in [1, N-1]. So we have to give arguments getcount(N + 1, K) to get no of Kth set bits in [1, N]. You may find clear explanation here

        So to get the no of Kth set bits in [L, R] we can have x = getcount(L, K) that gives No of Kth set bits in [1, L-1] and y = getcount(R + 1, K) that gives No of Kth set bits in [1, R]

        so by substracting x from y we can get no of Kth set bits in [L, R].

        Hope you got it :)

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

      Can you explain a bit your solution? Thanks!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
  • »
    »
    5 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Finally, I find a solution I can't find a solution on the contest

    this function return number of combination of 0 for given number n and given bit position i


    int count0(int n, int i) { int q = std::pow(2, i); int m = (n + 1) - (n + 1) % q; int r = n + 1 - m; int mx = m / q; int count0; count0 = odd(mx) ? q * (mx + 1) /2 : m/2 + r; // int count1 = n - count0; return count0; }

    combination of l to r will be

            int min =  count0(r,0) - count0(l - 1,0);
    
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i had same problem you can find ans for 1 to 2*1e5 and use it as ref to find 1e4 queries its that simple Here is my solution link for refrence

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

    Check my solution its O(1) time complexity. I didnt precompute anything.

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

Thanks for the fast editorial and merry Christmas

»
5 months ago, # |
Rev. 5   Vote: I like it +20 Vote: I do not like it

Hey! I actually found some different solution for problem C and I guess it's supposed to work? I started with the same observation than the editorial: we will consider the count of different types of candles.

The four types are: $$$10, 00, 01, 11$$$

We can apply operations on types: $$$10$$$ and $$$11$$$ because these types are the only ones having the candle of string $$$a$$$ setted to $$$1$$$ (and we can only to operations on $$$1$$$ candles)

Now, what will happen if we apply an operation on a char of type $$$10$$$ ? Let's call $$$[a_ib_i]_{old}$$$ the count of the type $$$a_ib_i$$$ before the operation and $$$[a_ib_i]_{new}$$$ the count of the type $$$a_ib_i$$$ after the operation.

So if we apply an operation on a char of type $$$10$$$ we'll have:

$$$[10]_{new} = 1 + [00]_{old}$$$

$$$[01]_{new} = [11]_{old}$$$

$$$[11]_{new} = [01]_{old}$$$

$$$[00]_{new} = [10]_{old} - 1$$$

In a similar way we can find how $$$[a_ib_i]$$$ will change if make an operation on a char of type $$$11$$$.

Furthermore, doing the same operation twice is useless as we will comeback to the same string.

As an operation only do a small local change (+/- 1) and let two counts invariant (it just swaps them) we may think there is not that much reachable strings.

So one could implement a BFS where the nodes contains the count of each type and the transitions are: apply operation on $$$10$$$ or apply operation on $$$11$$$.

It appears that it works quite fast. Here is my AC code (~90ms): 140494838

I have some intuitive ideas of why it's fast. I'll try to think a bit more and I'll update this comment if I found something :)

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

    The total number of nodes and edges is $$$O(n)$$$ due to the observations. Basically, we always have that $$$c(10)+c(00)$$$ and $$$c(01)+c(11)$$$ are fixed because the string $$$b$$$ doesn't change, and after an even number of operations we also have $$$c(10)+c(11)$$$ is fixed because two operations is just a swap. From these three equations, the count $$$c(10)$$$ uniquely determines the other counts.

    The nodes that correspond to an odd number of operations are just one step away from an even number of operations, so we conclude the size of the graph overall is $$$O(n)$$$.

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

    I got the same idea, but without BFS part: https://codeforces.com/contest/1615/submission/140485290 so the idea is that it is enough to check only one action on each type

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

How to do B??? :(((( Can someone give an easy explanation plzzz!

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

    This is how I solved B.

    Notice that the maximum value you can have in all test cases is 2 * 10^5, so let's precompute a prefix sum arrays ps[i][j], i is from 0 to 200000, j is from 0 to 19. ps[i][j] is the total count of bit 1 in bit position j for all numbers from 0 to i.

    Then each test case becomes checking the prefix sum in range [L, R] for all bit positions. In order to use minimum deletions, we want to take a bit position that has the most 1s.

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

      Sorry if this is a stupid question but can you tell me why j is from 0 to 19. An int is represented by 32 bits shouldn't it be 0 to 31

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

        As 2^19 > 2 * 10^5 therefore if we check for larger values of j the count is always zero.

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

          ohh ok thank you for the help

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

        because our max constraint is 2*10^5 , and most significant bit we wiil found upto 18 or 19.

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

I'm not sure, but I think that it's possible to solve H using slope trick.

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

Just wanted to say, D was brilliant

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

since im not able to solve problems (just solved A nd B today) in contest and also not understanding the solutions from editorial what must i do to see myself solving these problems in contest like if i keep doing this how would i improve ? advice needed!!

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

Tasks are good but time to think about them no so much :(

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

can somebody please recommend some blogs or references to read about bitmask? it'll be great help.

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

Can anyone give the proof of bonus in problem C?

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

    Take a look at the submission: 140511019. If we do operation on 10, we end up scoring (#00 + 1) * 2 + 1. If we do operation on 11, we end up scoring #00 * 2 + 1.

    And if #11 is 0, then doing operation on 10 won't work either, since #00 + 1 should be equal to #11, which is impossible.

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

      Beautiful solution thanks for sharing.

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

      could you please elaborate how you concluded #00 + 1 should be equal to #11

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

        Here's a chunk of code that explains it:

        if (type[1][0] > 0){
                int newType01 = type[1][1];
                int newType10 = type[0][0] + 1;
                if (newType01 == newType10) {
                    result = min(result, newType10 * 2 + 1);
                }
            }
        

        For result to be updated, newType01 should be equal to newType10, thus #00 + 1 is equal to #11.

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

Problem D was very nice imho.

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

Hey !

I actually solved $$$C$$$ quite differently. First check if two strings are equal if yes answer is $$$0$$$. Otherwise, Consider two pairs: $$$E$$$ = (count of equal $$$0s$$$, count of equal $$$1s$$$) and $$$NE$$$ = (count of not equal $$$0s$$$, count of not equal $$$1s$$$). Consider these two pairs as starting state. Now, we can simply run $$$BFS/DFS$$$ to check if we can reach to goal state which is $$$E$$$ = ($$$0$$$, $$$1$$$) and $$$NE$$$ = ($$$x$$$, $$$y$$$) where $$$x + y = N - 1$$$. This is the goal state because last move we do will have this kind of form. At each step, we can either take $$$1$$$ from $$$E$$$ or $$$NE$$$ and then we swap $$$N$$$ and $$$NE$$$ (we also swap number of $$$0$$$s and $$$1$$$s in each pair while handling picked $$$1$$$ separately). If we can't reach goal state answer is obviously $$$-1$$$ otherwise we can simply output current level of $$$BFS/DFS$$$. I had an intuition that this process will not continue forever and will end in after some small number of steps (I didn't prove correctness do reply if you can prove it).

My Submission

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

Another way to solve $$$C$$$:

First of all, selecting the same candle twice will not change anything, so each candle will either be selected once or not at all.

If we select $$$x$$$ candles, the number of ones in them must be $$$\lceil\frac{x}{2}\rceil$$$, because the sequence of selected candles must be those with initial values 1010101...

If $$$x$$$ is even, at the end the selected candles will be inverted and the others will not. If $$$x$$$ is odd, the selected candles will not change and others will be inverted.

As we know the invalid candles that need to be inverted having count $$$cnt$$$, if $$$cnt$$$ is even we can try to select the invalid candles, and if $$$n-cnt$$$ is odd, we can try to select the correct candles.

At the end take the minimum answer found or -1 if both trials failed. If a trial succeeds, its answer is the count of selected candles.

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

    $$$\lceil{\frac{n}{2}}\rceil$$$ should be $$$\lceil{\frac{x}{2}}\rceil$$$.

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

    had very much same logic ...got 3 WA during contest bcz i made count of 1 >=ceil(x/2) istead of ==ceil(x/2) (sob)

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

I have solved so many problems similar to problem D and yet again during the contest struggles to do it

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

    It will be helpful if you send the link to those similar ones. And also some good resources I should go through before solving them.

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

Problem E has an N*sqrtN*logN solution which is good enough to pass system tests but can be hacked. I hacked 1 and 2

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

    The solution constructs some sort of a longest-path decomposition.

    A sketch of a proof why that's the complexity, as discussed with kostia244:

    There can be at most $$$O(\sqrt{n})$$$ paths of length $$$> \sqrt{n}$$$, so the dfs works $$$O(n \sqrt{n})$$$ times. For the shorter paths, consider the forest at some time instant. If you give a potential equal to the depth of a tree to each node in that tree, doing a dfs and taking away 1 from the potential of each affected node reduces the potential of each affected node to at least the actual potential of the affected node after the tree has been split into a forest by removing the longest path. So the total change in the potential is at most the initial potential, which is $$$O(n \sqrt{n})$$$, since only the short paths remain.

    The extra log comes from the usage of std::set.

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

Does anyone know the ratings for each of the problems?

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

i went to youtube to see the explanation of problem C and i saw it

youtube.com/watch?v=B9Xr3tm5_K4

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

In the editorial for problem F, $$$p_{ij}$$$ is defined as the number of ways to get $$$\sum_{i=1}^{k} |a_i-b_i| = j$$$. I think the $$$\sum_{i=1}^{k}$$$ shouldn't be there.

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

In problem B

What I did is count the number of 0s of every array element at every bit position and the ans will be the minimum of all those counts

My solution

Its complexity is O(32*n) which should pass the given constraints, isn't it?

since the maximum constraints is 2*10^5.

Am I wrong?

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

    It's $$$O(32\times \sum (r - l))$$$, and the sum of (r-l) will be $$$10^4 \times 2\times 10^5 = 2\times 10^9$$$, so you will get TLE.

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

      Thank you for the reply but why is this summation sign is coming. The 1st loop runs for 32 times and the second loop runs for (r-l) time times so all together it will be 32*(r-l) isn't it?

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

        t test cases.

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

          That I was meaning to ask you in competitive programming do we have to consider the constraints of t(the number of test cases) also? Sorry, if its a stupid question I don't know about it.

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

            Always consider it unless there's a constraint of $$$\sum (r-l)$$$.

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

              ohhhhhhhhhhhh ok thank you for the help.

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

The Problem H is well-known in China...

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

Hello Monogon, I think there is a typo in your editorial.

In problem H's editorial,

If there is any node u such that $$$s \rightarrow u$$$ and $$$u \rightarrow v$$$ both have flow, make them both have 0 flow, and this won't change the cost.

I think it's supposed to be $$$s \rightarrow u$$$ and $$$u \rightarrow t$$$, right?

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

which problem was interactive ?

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

    Every problem is interactive when you talk about it with friends.

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

https://codeforces.com/contest/1615/submission/140504399 problem B. I dont know why i got a time limit error at pretest 3 .

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

    you are doing 2e9 operations in 2 second which will surely give you TLE. note that in problem there is no limit on sum of all test cases.

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

      but for each test case the time limit is 2s right. i dont think my code takes more than that(for each test case) even in the worst case. or am i wrong?

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

        you have 2s for t test cases not for each test case

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

          DAAAAMNNN!! Lol I made all my submissionns for the past 2 months without knowing this. Thanks man

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

Done A, B in 15 min. Took ~1.50 to solve C.

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

Is there anyone can use DP to solve problem E? Thank you in advance.

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

[ignore, sorted] i was returning without taking complete input on a multi — test.

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

Problem D was not original. I think a similar problem appeared once on codechef PARITREE

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

time limit in test 2 in B how can i solve https://codeforces.com/contest/1615/submission/140474193

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

Could you show any reference to potential method O(nm log n) to calculate min cost flow in problem H?

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

Can someone explain why we only check bits 1-30 at problem B? Shouldnt we also include the 0th bit?

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

    I think in explanation , 1-based indexing is considers.

    so 1 here is LSB- least significant bit

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

      You're still considering 30 bits, when an int has 31 bits (excluding the sign bit). Shouldnt it only make sense to check all 31 bits?

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

        check constraint, 2*10^5, I only checked 20 bits, checking more bits than that is not required

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

could someone elaborate the bonus statement of problem C

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

I only want to know how to find the Key observation of 'F'? It is too difficult for me.

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

    The most sensible way to reach the key observation is by noticing the invariant of the problem.

    An invariant is some property of the string which doesn't change under the operations available to you. For example, one possible invariant in this problem is the parity of the number of ones in the string: If we started with an even/odd amount, every operation will add/subtract two ones, therefore keeping its parity.

    However, we want to find a tighter invariant. We want to be able to say that if $$$s_1$$$ and $$$s_2$$$ have that property, then we can reach $$$s_2$$$ from $$$s_1$$$ (or vice versa, of course). It is not possible with the previous invariant, as $$$0101$$$ is not reachable from $$$1010$$$.

    The correct invariant to look at is the number of zeros on even positions plus the number of ones in odd positions. It is indeed an invariant (check). Now we construct $$$s\prime$$$ which will act as a "dual" problem: for every bit $$$i$$$, if $$$s_i$$$ adds to the score of the string (so either $$$i$$$ is odd and $$$s_i$$$ is 1 or $$$i$$$ is even and $$$s_i$$$ is 0), we choose $$$s\prime_i = 1$$$, otherwise $$$s\prime_i = 0$$$. Also, every operation on $$$s\prime$$$ would be to flip two adjacent different bits (check that it indeed corresponds to a basic operation on $$$s$$$).

    Notice that:

    1. $$$s_2$$$ is reachable from $$$s_1$$$ if and only if $$$s\prime_2$$$ is reachable from $$$s\prime_1$$$, if and only if the bitcount of $$$s\prime_2$$$ equals the bitcount of $$$s\prime_1$$$
    2. The way we constructed $$$s\prime$$$ from $$$s$$$ is exactly the key observation!
»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

where is D problem standard code?

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

Problem C : Menorah

My Code with explanation : click here

// we will change 1-1 and 1-0 alternatively because
//  if we changes same pair twice or more times consecutively than it will nullify the previous change
//  for ex. changing 1-1 (odd number of times consecutively) is equivalent to changing 1-1 (only once).
//         same for changing even no. of times which is equivalent to changing 0 times;

int go(int a, int b, int c, int d, bool flag) {

    // if flag == 1 : it's time to choose 1-0 else 1-1
    // c1 : 1-1
    // c0 : 0-0
    // w1 : 1-0
    // w0 : 0-1
    // x-y : x is the ith character of first string and y is the ith character of second(destination) string
    // a = c0, b = c1, c = w0, d = w1;

    if(c == 0 && d == 0) return 0; // no wrongs, only corrects

    if(flag) {
        // change 1-0 pair
        if(d == 0) return 1e9; // no more 1-0 left to change
    
        int c1 = c;
        int c0 = d - 1;
        int w1 = a + 1;
        int w0 = b;

        return 1 + go(c0, c1, w0, w1, 0);
    }
    else {
        // change 1-1 pair
        if(b==0) return 1e9; // no more 1-1 left to change

        int c1 = c + 1;
        int c0 = d;
        int w1 = a;
        int w0 = b - 1;

        return 1 + go(c0, c1, w0, w1, 1);
    }

} 


void solve() 
{
    string a, b;
    cin >> n >> a >> b;
    if(a==b) {
        cout << 0 << endl;
        return;
    }
    int mn = 1e9;

    int c1 = 0, c0 = 0, w1 = 0, w0 = 0;

    fr(i,0,n) {
        if(a[i] == '1') {
            if(b[i] == '1') c1++; // 1-1
            else w1++; // 1-0
        } else {
            if(b[i] == '1') w0++; // 0-1
            else c0++; // 0-0
        }
    }

    mn = go(c0, c1, w0, w1, 0);
    mn = min(mn, go(c0, c1, w0, w1, 1));

    if(mn > n) mn = -1;

    cout << mn << endl;

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

I'm not sure whether the proof in E is called contradiction or exchange argument. Can somebody elaborate?

Edit: Oh, the editorial is updated! There was the word "contradiction" sometime and I commented on that. I also had too many doubts about the first revision of the proof but everything is now clear to me. Thanks!

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

In problem D,how can I find out the final r_i for each node? Could anyone please show me a sample of the code to problem D?Thank you!

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

Nice contest!!

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

why am getting wrong ans? filling prefix array:-

for (int i = 0; i < 32; ++i) {

for (int j = 1; j < N; ++j) {

if ((j << i) & 1) {

prefix[j][i] = 1;

}

prefix[j][i] += prefix[j — 1][I] ;

} }

solve() function

void solve() { ll l, r; cin >> l >> r; ll ans = INT_MAX;

for (int i = 0; i < 32; ++i) {
    ans = min(ans, ((r - l + 1) - (prefix[r][i] - prefix[l - 1][i])));
}

put(ans);

} '

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

    bruh ! You are calling solve function in each test case :| just calculate it once !

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

      this is not the final code i am precalculating it but not getting correct ans

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

The tutorial for problem A was not very clear to me. For one thing, I did not understand how the observation in the first sentence implies that the answer is always $$$\le 1$$$. And besides, it does not explain why the sum being divisible by $$$n$$$ is sufficient for the answer to be 0. So I came up with my own proof.

Let $$$m$$$ be the mean value of the elements of the array. Note that $$$m$$$ is integer when the sum of the elements is divisible by $$$n$$$.

If $$$m$$$ is integer, and not all the elements are equal to $$$m$$$ then there is an element that is less than $$$m$$$ and an element that is greater than $$$m$$$. We can apply the operation to these two elements and repeat until all the elements are equal to $$$m$$$.

If $$$m$$$ is fractional we can use a similar approach to make all the elements equal to either $$$\lfloor m \rfloor$$$ or $$$\lceil m \rceil$$$. This is the general case that is also applicable to integer values of $$$m$$$ when $$$\lfloor m \rfloor = m = \lceil m \rceil$$$.

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

    If the downvotes are because of what I wrote about the tutorial — I got it. $$$max(a) - min(a)$$$ eventually decreases even if initially there are multiple values of both $$$min(a)$$$ and $$$max(a)$$$, and the sum cannot be divisible by $$$n$$$ if $$$max(a) - min(a) = 1$$$. Still, what I wrote after that is valid.

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

Nice Explanation

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

resolved

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

Am I the only one, or you guys too think that problem C is a pain?

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

Can anyone share their code for C that worked? Thanks in advance

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

Why are we able to add a direct edge between nodes $$$a$$$ and $$$b$$$? Or more precisely, how is a path relationship converted into a parent-child relationship?

Also if we add direct edges, won't we be creating a graph rather than a tree? PurpleCrayon

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +48 Vote: I do not like it
    1. An edge between $$$(a, b)$$$ is just a path of length $$$1$$$ between $$$a$$$ and $$$b$$$, so you can just treat it the same way as you do for any other path.
    2. Yes, you are creating an undirected graph, not a tree. However the graph you create isn't what you output. The graph is used to establish relationships between the different $$$r_i$$$ values. This information can be used to figure out all of the $$$r_i$$$ values, which you can then use to find the original values of each edge.
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve the Challenge Problem given in Editorial in Problem B Challenge: solve the problem with 1≤l≤r≤109.

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

    You can count the number of bits set as $$$1$$$ in the $$$i-$$$th bit from $$$[0,n]$$$ inclusive by noticing that the number of set bits alternates every $$$2^i$$$ numbers. For example for $$$i=1$$$, and the range $$$[0,7]$$$, the numbers are $$$000,001,010,011,100,101,110,111$$$. Notice that $$$i=1$$$ (the second bit from right) changes like this: $$$0,0,1,1,0,0,1,1$$$, it alternates between $$$0$$$ and $$$1$$$ every $$$2^i=2$$$ numbers. So you can use this pattern to count the number of ones in the range $$$[0,n]$$$ by dividing $$$\lfloor (n+1)/(2^{i+1}) \rfloor $$$ and handling the remainder separately.

    See submission here: https://codeforces.com/contest/1615/submission/151272206