shishyando's blog

By shishyando, 8 months ago, In English

Again, I hope that you liked all the problems. Share your ideas and solutions in the comments, because there are always different ones! So, the editorial:

A: GCD vs LCM
B: Array Cloning Technique
C: Tree Infection
D: GCD Guess
E: MinimizOR
Who did what?
 
 
 
 
  • Vote: I like it
  • +143
  • Vote: I do not like it

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

Thanks for the fast editorial!

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

Thanks for the fastest editorial.

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

Seems like fast editorials are being the trend recently. A welcoming trend, for sure.

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

Wow, Fast editorial
Thank you very much

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

Thanks for the fast editorial! And problems are so nice :)

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

can someone explain D with more details

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

    Here was my reasoning (same as first approach):

    • 30 Queries to differentiate about 2^30 candidate numbers implies each query must learn 1 bit
    • hence looked for way to first learn LSB, then 2nd LSB etc.
    • Use fact 1 that gcd(x+a,x+b) = gcd(x+a,b-a) if a<b from property that gcd(x,y) = gcd(x,y-x) if x<y
    • Use fact 2 that if x = ?????000 (i.e ends with n zeros), then gcd(x,2^n)=2^n. (notice x is divisible by 2^n and there cannot be any larger number than this that divides 2^n).
    • Say we have learned that x = ?????01. Then, removing the last two bits (by subtracting 1) to get x', and then doing gcd with 2^2 will tell us 3rd bit.
    • In other words, if we know X starts with x in the first n bits, then doing gcd(X-x, 2^n) tells us next bit
    • This gives us a good strategy, but how do we translate to a suitable a and b?

    Answer? Use fact 1 ,gcd(X+ (2^(n) — x), X + (2^(n+1)-x)) = gcd(X + (2^n -x),2^n) = gcd(X-x,2^n), which is used as an indicator for next bit.

    At step n+1, we know the first n bits of X, i.e. x. Propose a= 2^(n)-x; b = 2^(n+1)-x; If gcd is 2^n, then next bit is 1, else 0

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

      still don't get it..

      "Say we have learned that x = ?????01. Then, removing the last two bits (by subtracting 1) to get x', and then doing gcd with 2^2 will tell us 3rd bit."

      If we remove last two bits in x, then gcd with 2^2 will be 2^2.. doesn't matter what 3rd bit is. How do we get whether 3rd bit is 0 or 1?

      "if we know X starts with x in the first n bits, then doing gcd(X-x, 2^n) tells us next bit."

      won't the gcd always be 2^n if you remove first n bits from X ?

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

        You are right. To check bit n, you need gcd with 2^(n+1).

        I meant to say that you need to check with gcd 2^3. If the next bit is a zero, then the gcd will give you 2^3, otherwise next bit is a one.

        The rest needs a little tweaking but the idea is the same.

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

      Thanks for the great explanation. But, I think this would need some workaround as 2^(n + 1) would exceed 2*10^9 (if n = 30).

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

        Yes, if you scroll down, there are some comments about that case.

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

      why If gcd is 2^n, then next bit is 1, else 0

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

        Because if the next bit was 0, it would imply that the number has another 2 as a factor. This would mean that there exists a greater divisor than 2^n, i.e. gcd >= 2^(n+1). Since this is not true, if gcd is 2^n then next bit must be 1

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

    Basically, you should visualize the number in the binary form. Now you can check what is the kth bit if you have Y, with the propriety: X + Y has the first (k — 1) bits set. Now you can check if the kth bit is set by querying (Y + 1 , Y + 1 + 2^(bit + 1) , if this is 2 ^ (bit), then you add it to the answer, otherwise you update Y.

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

    You can check my comment dowm, I tried to explain D clearly

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

Thanks for this rubbish trash boring disgusting fucking meaningless Problem C that I didn't have enough time to write E

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

    That's because you are not good enough noob

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

    Problem C was nice

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

    Totally agreed, Also the question statement is still wrong. He has written ancestor in "where pi is the ancestor of the i-th vertex in the tree". By ancestor, he is meaning parent. He has not even defined this definition of ancestor.

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

Sonic Speed Editorial

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

Is there any other solution for A other than [1,n-3,1,1]||[n-3,1,1,1]??

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

    I'm not exactly sure, but in n%4=0 case you can make a=b=c=d=n/4

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

    Yeah, check mine. Looks like I always overlook easy solutions and complicate it more :/.. 153033103

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it
    • n is odd :
    • (n-2)/2 (n-1)/2 1 1
    • n is even :
    • 1 1 1 1 (n == 4)
    • 1 3 1 1 (n == 6)
    • n-6 2 2 2 (when n >= 8)
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    n = odd -> x, x + 1, 1, 1 -> (x = (n — 3) / 2) n % 4 = (0) -> x / 4 each n % 4 = 2 -> x, x + 2, 1, 1 -> (x = (n — 4) / 2)

    n % 4 == 2 works because (n -> 4y + 2) -> x = (4y — 2) / 2 = 2y — 1

    we get => a = 2y — 1, b = 2y + 1 (2 consecutive odd numbers are co-prime)

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

    lol.

    I thought there were 4 situations when $$$n = 4k$$$, $$$n = 4k + 1$$$, $$$n = 4k + 2$$$ and $$$n = 4k + 3$$$.

    • When $$$n = 4k$$$ the answer can be k k k k;
    • When $$$n = 4k + 1$$$ the answer can be 2k 2k-2 1 2;
    • When $$$n = 4k + 3$$$ the answer can be 2k 2k+1 1 1 or 3k k-1 1 3.

    Then I realized the correct solution and gave up thinking of the $$$n = 4k + 2$$$ situation.

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

why so tight constraint(a,b<2000000000) for d? that forced to think exactly like you which is not always possible;

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

Can someone please explain why my C solution doesn't work? 153069119

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

C is nice . Thanks for the round.

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

Editorial's D implementation (1st) seems a bit off. It is not working for x=999999937; Can someone verify?

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

A very educational round with a fast editorial!!! I really like it, especially for the nice E, extremely educational.

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

In Editorial 1 for D, shouldn't it be $$$x \pmod{2^{k+1}} = r + 2^k$$$ ?

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

    yes

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

    Can you please prove this? I am getting it as x%(2^(k+1)) = r — 2^k

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

      $$$x \mod 2^{k + 1} = \left(r - 2^k \right) \mod 2^{k + 1} = \left(r - 2^k + 2^{k+1} \right) \mod 2^{k + 1} = r + 2^k $$$

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

It seems like my solution for C is different from the editoral, I used binary search

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

    How do you determine if the tree can be infected in say x seconds (I understand if we can infect it in x then we can infect it in X+1,X+2,...N)? Or can you explain your approach?

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

      In my solution I don't work on a tree, just all nodes of the same parent are put in a set (and node $$$1$$$ is alone in a set) and I make an array for the sizes of those sets, when I infect a set, it decreases by one every second, and for a set to decrease I need to inject it, so I will inject all $$$m$$$ sets first (lets say we have $$$m$$$ sets), it is obvious I want the biggest set to be injected first, so it decrease more early than the other sets, since I inject the $$$m$$$ sets I will use $$$m$$$ seconds, if I sort all sets by size, for each $$$i$$$ $$$(1 <= i <= m)$$$ set number $$$i$$$ size is decreased by $$$i$$$ elements (the size of the set is the number of non-infected nodes), so I already made the optimal move for the first $$$m$$$ sets, I already know now that for every second all sets decrease by one, so I can binary search on the number of extra second $$$x$$$, I decrease every set size by $$$x$$$, and then I get the summation of the remaining positive sizes of sets, if it is smaller than or equal to $$$x$$$ then x is valid (because I have $$$x$$$ injections) otherwise $$$x$$$ is not valid, and the answer is the $$$minimum$$$ $$$valid$$$ $$$x + m$$$

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

Thank you for the fast editorial and a nice round!

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

In my opinion,D is much easier than C,since it takes me almost an hour to solve C and WA 5 times,and it takes me half on hour to solve D.

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

Thousands of people learned today not to use stl::unordered__map in competitive programming.

Yeah I used to know about it, but I've been out of the game for so long that I completely forgot lol.

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

    Same, it sucks that the time limits are that tight when asymptotically, one is $$$O(1)$$$ and the other is $$$O(log n)$$$

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

      Well, personally I don't think that sucks, just something need to know for participating competitive programming. I'm competing again after three years and it's like a welcome back lmao.

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

        I mean u could resort to gp_hash_table if u really need to use some sort of hash map

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

    For which question? I'm new to CP and used unordered_map but didn't get any problems? What are the alternatives?

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

    My solution took 46ms which is also using unordered map. Maybe your problem got TLE because of some other reason! (not sure though!)

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

      The reason your solution passes is because you are using a slightly newer implementation (C++20 instead of C++17). Try it with C++17 compiler.

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it -20 Vote: I do not like it

    I liked the problem, I didn't like the TL constraints. I mean, it's an algorithmic contest, so when you write O(N) solution instead of the "intended" O(N*logN) you are supposed to pass. But no — since you are using the standard library of a specific implementation of specific language you fail, even though your solution is correct (and will pass, if the system used another implementation of the same language, or even if you selected another version from the drop-down).

    Let's give problems that exploit specific bugs in the language implementations, yey, so smart, amazing! Too bad the Timsort bug required too large inputs to be viable for a programming contest, it would make an AWESOME problem where you need to sort numbers, but fail if you use the built-in sort.

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

C was interesting, but I wasn't able to solve it. Thanks for the round!

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

Thanks for the fast editorial!The problems are nice but I only solved AB T_T.

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

Problem B giving tle on unordered_map code while got ac using map code. I know unordered_map time complexity is O(n) in worst case and O(1) in best case so should we only use map for safer side? and how to determine where should we use unordered_map or map? thanks in advance.

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

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

I've also added 2 new features: Near real-time log streaming and Compressed Parameter editing without using tables.

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

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

    Hi! It says that I'm violating constraints, even though I'm pretty sure I'm not: https://cfstress.com/status/3708

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

      Oh, my bad.

      Actually, constraint violation is a catch all phrase for when input file is not present. It could be either due to the fact that the generator crashed (i,e. actual constraint violation) or the submission didn't compile (with c++17). (Of course, I could write a better error message, and I'll make that improvement in future).

      This was the error that occurred while compiling your submission:

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

      Bobrosoft I fixed the compilation error and ran it on the parameters that you had selected. Here's the counter example I received.

      Input
      Expected Output
      Your Output
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks a lot, I was able to fix my code! Although it did make me pretty miserable, knowing how close I was to getting 5/5, but that's definitely not a flaw in the service. :D

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

    Hi, I tried some parameters but it seems no counter example is found. Problem 1665-C, submission 153078042

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

    153071478

    https://cfstress.com/status/3803

    For problem C, I couldn't find a counter test case.

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

    Contest ID = 1665 Problem Index = C Submission ID = 153057004

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

    Contest id: 1665 Problem index: C Submission id: 153157370

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

Why unordered map is giving TLE in problem B, but map works?? My solution was basically the same as the one in the editorial, only difference was it used unordered map instead of map.

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

This old blog for people asking about unordered_map

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

I have a solution E that catches ML.

Let's build a merge sort tree from tries. Then when we respond to the request, we make a descent over <= log n trues. We go from the highest bit to the smallest. Now let's say there are cnt numbers by which we can go left. Then if cnt >= 2, then we'll just go left. And if cnt < 1, then if cnt = 1, then we add this number to some array b on the left, and we ourselves go to the right. After that, the answer will be found as some b[i] | b[j]

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

failed maine test on problem C , WA on test 20 can someone tell what's wrong in this code ?

Solution link

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

Did anyone AC problem D using the CRT solution?

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

    153047261

    I used the CRT implementation from this blog.

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

      I'm sorry, but can you please explain the CRT solution in detail ?

      Mostly i cannot understand 2 things -

      1. Why we are using gcd(x+i, x+lcm+i)

      2. How can we be sure that 30 queries are enough to fill all the a[i] values. Isn't it possible that the gcd we got in response isn't divisible by any of them ?

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 2   Vote: I like it +7 Vote: I do not like it
        1. If $$$gcd(x+i, x+i+lcm)$$$ is divisible by some integer $$$y$$$, then $$$x+i \equiv 0 \mod y$$$, in other words $$$x \equiv -i \mod y$$$.

        2. All the prime integers I’m using as modulos for the CRT (2, 3, 7, 11, 13, 17, 19, 23, 29) are less than 30, so it’s certain that for each of them, at least one integer in $$$[x, x+30)$$$ divides it.

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

Can someone please check why this solution is giving tle for problem C. https://codeforces.com/contest/1665/submission/153076888

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

I had a slightly different approach to D.

At every step, I would add padding to the number and make sure that it is divisible by 2, 4, 8, ... .

For example, if the hidden number is 5, I would first check if it is even by asking (+2, +4).

Since it is not even, I must pad the number by +1.

Then, I make sure it is divisible by 4. I ask (padding, padding+4), which is (+1, +1+4). This returns 2, which means that I must further add 2 to the padding to get +3 padding.

Then, I make sure it is divisible by 8. I ask (padding, padding+8), which is (+3, +3+8). This returns 8, which means that I must further add 8 to the padding to get +11 padding.

I repeat this process until 2^30 and I can finally subtract the padding from 2^30 to get the original number.

Edge Case 1
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used similar solution except with +1 and +3. This way the padding is -1 for odd number and 0 for even.

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

unordered_map gave TLE in problem B.. (T T)

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

Can someone please explain me that what is wrong in my solution to problem c?153064535

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

In C

You do two operations every second

Doesn't that mean you do at most 2 operations each second?

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

    You do two operations : then he specified the two operations, meaning you have to do them both (the two types)

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

Can't able to figure out the logic of the B problem. When I have used an unordered map it was a TLE at tc 13, but for the same logic when I have used a map it is Accepted. Can anyone help me clear this doubt, I appreciate that.

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

Can someone please explain why my C solution doesn't work? Solution

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

Check out this solution to problem b : 153043206

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

The 2nd solution for problem D is neat! Thanks!

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

For problem C what is wrong with my approach can someone please help me? 153060505

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

    Failing testcase: Ticket 3780

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

      for this test case how can answer be 4 because in first operation we can infect 1 node only and remaining value would be 7 now we can't take more than 2 nodes at at a time still that means we need 4 operation here + 1 for start so total should be 5?

      Sorry for negative like on your reply by mistake happened

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

        Each second, you are allowed to spread the infection in all nodes if they satisfy the condition (and not just one node).

        Hence, you can have a lot more than 2 vertices being infected every second.

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

          Yeah, I misunderstood the problem Thanks for the clarification.

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

            In the conditions, it's saying if at least one child of v is infected, you can spread the disease by infecting at most one other child of v of your choice. that means we can infect one more child and according to that, it will take 5 seconds as we have to infect the root as well. Can you explain how 4 seconds will be the answer? my solution it's giving wrong answer: https://codeforces.com/contest/1665/submission/153433189

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

              You can spread the infection in each at most child of all parents whose one more child are infected already parallaly. So let's say you have child 2, 3, 4 for parent 1 and child 5, 6, 7 for parent 2 then if child 2 and child 6 infected in each group then each time other child of 1 and one other child of 2 will be infected too because of spread. Long story short it can happen for more than 1 parent at a time that's why it's possible in 4 seconds.

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

So many fsts for test case 20 in problem C. Can anyone explain why I got fst on test 20 ? 153064962

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

In editorial of Problem D [Solution 1], the value of x mod 2^(k+1) should be r + 2^k and not r+2^(k-1).

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

I have another approach for E.Let we will solve all queries together.We will go from greater bit to lowest.If we have at least two zeros in a greater bit we have 0 in it in the answer,and we can push the query to the array of numbers,which have zeros at our bit.Otherwise,we push the query to the array of all numbers we have now.This solution works in O(nlog^2) memory and O(nlog^3) time.The every query was in 30 layers one time.Let we will count sum of the lengths of the arrays we process.It is the sum for each element of it's total count.It is at most 30*(count of nodes where element goes to both sons).But if in some node element goes to both sons,then is has 0 in this bit,and it was a query when it is the only zero.But then the sum of (count of nodes where element goes to both sons) by elements is at most number of queries at all layers(each query gives us at most 1)<=30*q,so our soluiton runs in (n+q)*30^2 memory and (n+q)*30^2*log time. (The main moment is that in each node i eliminate all elements,which are not used in queries).So we have much slower solution,but without and ideas:)

link: https://codeforces.com/contest/1665/submission/153052760

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

In editorial of problem D(Solution 1), the condition

if gcd = 2^(k+1), then x mod 2^(k+1) = r + 2^(k-1)

is wrong and should be

if gcd = 2^(k+1), then x mod 2^(k+1) = r + 2^(k)

We can verify this since when k=0 (base case), the value of x mod 2 would be r + 0.5 which is wrong.

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

I can't find a counterexample for my solution even using cfstress.com for problem C. Here's a link to my solution can someone find a counterexample or the error I made — Submission

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

    I didn't find my original mistake but instead of finding the final solution using a formula i simulated it manually at the end and it got accepted. During the contest i thought the solution would TLE if i manually did it but sadly turns out it was the right answer — Solution

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

Can anyone tell me why this solution for C doesn't work? Link

Code explanation

Thanks in advance for your help

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

    Even I Tried the similar approach still not getting why it didn't work? 153060505

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Input
    Expected Output
    Your Output
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you.

      I've figured out that I misunderstood the problem. The spread can go in parallel for more than one node for different parents at the same time.

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

In problem c, After updating the atleat one child of a parent as infect we use ans++ and cnt-1 to queue i think in one time we (spread+inject) so ans+=2 and cnt-2 will be inserted can anyone clarify https://codeforces.com/contest/1665/submission/153080174 link to my sol

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

my solution link I know now that the problem was signed and unsigned comparison. Is this supposed to happen? corrected solution link

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

I think my solution for 1665E - MinimizOR is hackable: 153083146 In short, I split queries bit by bit, and when I set bit to 0 I also filter the numbers.

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

Can anyone explain why my C solution is not working? Edited: My submission I'm getting WA in test 20. I already tried cfstress, but I didn't find any counterexample .-.

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

Here's a screencast of me doing todays codeforces round:))

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

I really cannot figure out where my solution actually fails? I tried cfstress.com as well with n = 20 to n = 200000, but nothing found

Submission ID: 153074382

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

ENG: D could be done even simpler in my opinion!

Idea

RU: На мой взгляд, D можно было решить даже проще!

Идея:
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So that x+a=2^k for some k. Why is this true?

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

      'a' is initially 1. Each step we verify if in picked number 'x' i-th digit is 1 or 0, so if it is 1 we add 2^i to ans, otherwise we add 2^i to 'a'.

      So, for example for some x=100110101, 'a' will be = 011001010 + 1 (initial value)

      So, x+a will be 111111111 + 1, which is 1000000000 == 2^some k

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

    When i=30, the value of b would be a + 2^30. But b should be <= 10^9.

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

      Constraints: "a, b <= 2*10^9"

      Be more attentive when you read constraints ;)

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

I’m feeling so dumb right now, I just come up with this exactly solution to the problem B, and I did not submitted because I was thinking that it was not a good implementation, ever you guys felt like this?

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

This editorial is very fast!!!

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

If $$$\gcd=2^{k+1}$$$, then $$$x \mod 2^{k+1}=r+2^{k−1}$$$ Shouldn't it be $$$2^k$$$ in the end?

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

How can I get the key idea for the solution is that the answer always lies among no more than 31 minimal numbers? why?

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

I love problem E because it has so many different ways to solve it!

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

    Can you please explain one thing about E, i.e. why keeping track of 31 min values is required ? why not just 2 most minimums ? answer would be their OR then, because they have lowest max significant bits.

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

Thanks for many different solutions!

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

Could someone please explain me the "Other solutions" of problem E?I think I don't really understand that.

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

Tyyyyyy will be crooked

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

Thanks for giving the editorial fast!

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

Can anyone help me, why is my solution for A giving WA?

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

Can anyone help why my submission for problem C has FST WA on testcase 20. 153086129 I calculated the time required for injecting one sibling, then tried to spread and inject other.

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

Can anyone tell why in problem C the answer to the following test case should be 4 and not 5? 8 4 8 8 1 8 1

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    • (1 = spread : nothing | infect : vertex 2)
    • (2 = spread : vertex 4 from vertex 2 | infect : vertex 6)
    • (3 = spread : vertex 5 from vertex 2 and vertex 8 from vertex 6 | infect : vertex 3)
    • (4 = spread : vertex 7 from vertex 2 | infect : vertex 1)
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why my C solution is not working? submission

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

while (am < n) { int d = min(n — am, am); ans += 1 + d; am += d; } Can anyone Please Explain this in Problem B Not able to understand why he choose min.Also even though we take wouldn't there be a chance we end up counting more than required elements

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

Problem D, we asked $$$\gcd(x+2^k-r,2^{k+1})$$$. If the result is $$$2^{k+1}$$$, shouldn't $$$x\bmod 2^{k+1}=r+2^k$$$?

Or am I mistaken?

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

What brief problems there are! Just like math!

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

I really don't understand why my solution for Problem B got TLE on test case 13 when I used hash map. And after the contest when I submitted same solution just by using simple map, it got accepted.

TLE

Accepted

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

average CRT D solver

1d5826c6-7399-40a9-8f9f-e0662ab6fef0

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

I'm having some trouble figuring out my error for problem C. I tried printing the test case I got wrong (test 6 case 246) and got:

10
3 8 3 1 1 3 1 1 3 5

Am I missing something or shouldn't this test case be n=11 since there are 10 inputs on the second line? Original submission: https://codeforces.com/contest/1665/submission/153081192

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

I dont understand why i get wrong-ans in problem C test case 20. I try so hard but can't fix it.Plz help me anyone to fix.

https://codeforces.com/contest/1665/submission/153127622

Thanks.

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

Getting TLE on test case 5 in Java O(nlogn) solution, can someone tell what's wrong? link

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

can someone explain C ques TREEINFECETION

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

For C:
in this input, what should be the output

INPUT:

1
8
4 4 1 2 7 4 7

should it be 4 or 5 ? if 5 then how ?

my code https://codeforces.com/contest/1665/submission/153068424

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

Problem C was so good, Thanks :)

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

If gcd=2^k+1, then x mod 2^k+1=r+2^k−1 else x mod 2^k+1=r.

Can anyone explain why this line is true?

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

spookywooky can you explain this part of your code for problem C..!

    while(cnt<q.top()) {
        int v=q.top();
        q.pop();
        cnt++;
        q.push(v-1);
    }
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    This is simulating the process. The idea is to maintain that priority_queue, where we store foreach vertex the day that all children of that vertex are finished. $$$cnt$$$ is the number of days.

    Initially we put all vertex into the queue. Then, when each vertex has at least one infected child, we infect every day another child of the vertex with the most uninfected childs, and put that decremented number on the q.

    Note that in the beginning, we have to add an artificial vertex, which is the parent of the root vertex. We need this, because the root vertex also needs to become infected.

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

Can someone please tell me where I'm making error for Problem (C)? I have implemented exactly what's the tutorial says. I had figured out the solution but failed to implement it. I have looked at my solution multiple times but don't know what I'm missing. Please help me out.

You can look at my submission: https://codeforces.com/contest/1665/submission/153271339

I have added comments for better code readability.

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

Thanks for fast editorial

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

Thanks for your editorial

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

For problem D, wouldn't $$$x \mod {2^{k + 1}} = r + 2^k$$$ if the gcd is equal to $$$2^{k + 1}$$$? (not k — 1 as written)?

My reasoning is as follows: let $$$x = y\cdot 2^k + r$$$. Thus, the gcd becomes $$$\gcd((y + 1)\cdot 2^k, (y + 3)\cdot 2^k)$$$. If the gcd is $$$2^{k + 1}$$$, that means $$$y$$$ is odd. Thus $$$x = (y - 1)\cdot 2^k + 2^k + r$$$. Since $$$y - 1$$$ is even, $$$(y-1)\cdot2^k$$$ can be written as a multiple of $$$2^{k + 1},$$$ making $$$x \equiv 2^k + r \pmod {2^{k + 1}}.$$$

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

I want to know if the problem A ask you print all solution about n, how can I solve it?

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

I solved Problem E differently: maintain a trie of all elements of the array: also each node of the trie should store the indices which correspond to the node in the trie: so each index corresponds to $$$log(A_{max})$$$ nodes in the trie, one for each bit of the element.

Now for a query, we are initially in the root node of the trie. We want to find out the set of numbers which result in the minimum OR. If the left son ($$$0$$$ bit) of the current node has $$$\geq 2$$$ nodes in the query range, we go to that node, otherwise if it has exactly $$$1$$$ node in the query range, we add that value to our set of possibilities and go to the right son. If it has $$$0$$$ nodes we just go to the right son.

Formally, the invariant maintained is that the union of set of possibilities and the subtree of the current node stores two values which give the minimum OR. Easy to prove, that this invariant is maintained in every step.

153497046

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

    Thanks for sharing your solution. One question though, I think the below code-snippet isn't correct without checking how many of those positions (ie. tr[curr].pos) fall between $$$[l, r]$$$. I kind of understand why this works, because if none falls between the given range, regardless of how many of them added, they'll not be part of the answer. Therefore, my point is rather on the correctness of the algorithm. I think the correct way would be using your cnt function to find how many falls in the range. What do you think?

    if (is_num)
    {
    	for (int z = 0; z < min(2ll, (int)tr[curr].pos.size()); z++)
    	{
    		possible.push_back(num);
    	}
    }
    
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank you sooo much. you are absolutely right. the algorithm is obviously correct, but this implementation detail was wrong, the correct snippet, as you pointed out, is

      if (is_num)
      {
              int count=cnt(tr[curr].pos, l, r);
      	for (int z = 0; z < min(2ll, count); z++)
      	{
      		possible.push_back(num);
      	}
      }
      
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have a similar solution, but I use Wavelet tree instead of Trie: 153497046

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

Contest ID = 1665 Problem Index = C Submission ID = 153959804

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

https://codeforces.com/contest/1665/submission/154231870

problem : C why im getting wa for 20'th case ?

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

Why does this TLE? I think it is O(n*(log n)), as the priority queue loop runs only while pq.top()>t, and t is being incremented in each iteration.
Edit: it is O(n^2) actually. Changed.

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

Can any one explain why i get tle in this solution

void solved(){ int n; cin>>n; unordered_map<int,int> mp; int ans =0; for(int i=0;i<n;i++){ int x; cin>>x; ++mp[x]; ans = max(ans,mp[x]); } ll equal=ans; if(ans==n ) { cout<<"0\n"; return; } int op=0; int unequal=n-ans; while(equal<n){ op += 1+min(n-equal,equal); equal += min(n-equal,equal); } cout<<op<<"\n"; } int main(){ int t; cin>>t; while(t--) solved(); return 0; }

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

can anyone tell me where i am getting wrong answer I cant figure it out 160814737

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

Can someone please help me out what is the error in my submission for C? Although I am writing the brute force approach though?However where is the error? Link:Your text to link here...

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

B:why considering most freq element gives optimal answer? mathematical proof pls

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

Short Solution for B.

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

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

    int t;
    cin >> t;

    while(t--)
    {
        int n;
        cin >> n;

        vector<int> v(n);

        map<int, int> f;

        int maxi = 0;

        for(int i=0; i<n; i++)
        {
            cin >> v[i];

            if(!f.count(v[i]))
            {
                f[v[i]] = 1;
            }
            else
            {
                f[v[i]]++;
            }

            maxi = max(maxi, f[v[i]]);
        }

        if(maxi == n)
        {
            cout << 0 << "\n";
            continue;
        }

        int cpyOp = ceil(log2((double) n / maxi));

        int swapOp = n - maxi;

        cout << cpyOp + swapOp << "\n";
    }

    return 0;
}