6

Codeforces Round #815 (Div. 2) Editorial

 2 years ago
source link: http://codeforces.com/blog/entry/106136
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
By TeaTime, 4 hours ago, In English

4 hours ago, # |

We are sorry for statement of problem D being unclear :( We will do our best to write cleaner and easier to understand statements next time! We hope you enjoyed solving our problems though.

  • 4 hours ago, # ^ |

    But this problem is really good!

    • 4 hours ago, # ^ |

      Thank you!

  • 2 hours ago, # ^ |

    Hey, thanks for the round. The problems were definitely enjoyable!

    Just to clarify, the statement was not unclear, it was wrong. On top of trying to write cleaner and easier statements, please update statements during the contest if it is pointed out as wrong.

    Thanks, hoping to see more rounds from you!

4 hours ago, # |

Observation forces

  • 43 minutes ago, # ^ |

    very fitting handle for today's contest

4 hours ago, # |

thanks for fast editorial)

4 hours ago, # |

A was a bit too tedious for a task in such a place, and I think many contestants today gave up completely because they cannot finish A.

All of the other problems are really nice, though.

  • 4 hours ago, # ^ |

    Didn't gave up. Tried till last minute. Yet couldn't manage to solve A :V

    • 113 minutes ago, # ^ |

      I just quit A, and thankfully I solved C, which I usually dont do in a div 2

  • 3 hours ago, # ^ |

    Deciding to quit before submitting A is not giving up, it is strategy.

4 hours ago, # |

I'm confused. In D1 Wouldn't i-256 also work, since it toggles the 9'th bit (which cannot be toggled by any number in the array).

  • 4 hours ago, # ^ |

    I think it does, but 500 works as well and might be easier to see why.

  • 3 hours ago, # ^ |

    i tought "xor 200 will add or subtract at most 200". So i went with 402 just to be sure. It feels like the most intuitive lower bound to me, but i didn't think about it too much

  • 98 minutes ago, # ^ |

    The best bound I could think of is i-2*max+1 (and it does not need to be the maximum of the entire array, just of the elements before and including the current one, from 0 to i):

    If j < i-2*max+1, then j <= i-2*max and j^ai <= i-max <= i^aj. So, if j < i-2*max+1 we do not need to check this j.

    But maybe this is not the best possible bound: I just manually binary-searched the problem and i-255 is accepted, i-254 is not.

  • 83 minutes ago, # ^ |

    This is correct. Technically, i−256i−256 and below are guaranteed to fail the condition (since the prefix before the last 8 bits cannot be XOR'd out), so you can start checking from i−255i−255 onwards.

4 hours ago, # |

In the solution of D2, an 'equal' is wrong spelled.

and if it's equels 1).

  • 4 hours ago, # ^ |

    We will fix it quickly. Thank you)

4 hours ago, # |

C was a nice problem

4 hours ago, # |

d1 and d2 are two good problem!

3 hours ago, # |

I can't get the editorial of Problem E. Is it too simple or poorly explained? Can somebody please explain the solution ?

3 hours ago, # |

In Problem-B it's mentioned that you cannot take subsegment of length = n (r — l — 1 < n) but it is taking subsegment of length=n as a correct solution, please let me know if I am wrong.

  • 3 hours ago, # ^ |

    In which test case ?

    • 3 hours ago, # ^ |

      I don't know in which test case, but i am getting it wrong considering max length=n-1, and i have seen some correct solutions considering max length=n

      • 3 hours ago, # ^ |

        u didn't take n size and the logic is simple behind it u just have to maximized last answer so for that reason u need only 4 index of sorted array first second last second last

        then i will just select any of two index which doesn't have n size actually i can make it using r-l+1<=n-1 just think

        • 3 hours ago, # ^ |

          1 6 2 1 3 6 10 9 In this case, to satisfy your condition we have to take subsegment with l=1 and r=6 which is not satisfying r-l+1<n. Please tell me where am i getting it wrong? Thanks

          • 3 hours ago, # ^ |

            we also take l=4,r=7, so we end with max(al....ar)=10 and min(al....ar)=1(1 base index)

            then we will get ans 9-1+10-1

          • 2 hours ago, # ^ |

            Oh sorry, got it I misunderstood problem statement

          • 2 hours ago, # ^ |

            also an answer in this case (n=8) is l=3,r=7, 7-3+1<8

3 hours ago, # |

The code for problem E in the Editorial is incorrect. Countertest:

3 5
1 2 3
4 5 6
7 8 9

  • 3 hours ago, # ^ |

    Thanks for noticing! I posted correct solution.

3 hours ago, # |

← Rev. 2 →  

+4

Here we go, Thanks for the lightning fast editorial:)

3 hours ago, # |

kirill.kligunov bring a new word for our: subsequence, mean for index of some array.

Learn a lot from statement of problem D.

3 hours ago, # |

can anyone explain why we dont have to go beyond 256 for checking for a particular i... i am not able to get this by editorial

  • 3 hours ago, # ^ |

    It's because when xoring a[i] with j, you will get j modified by maximum 8 bits (because a[i] <= 200), therefore you need to check only the last 256 to make it bigger than a[i] ^ j

  • 2 hours ago, # ^ |

    Maybe it's due to the floating-point error.

    Try to compare a * c and b * d to compare a / b and c / d.

    Don't forget to use bigger data type such as long long!

    • 111 minutes ago, # ^ |

      yeah I think I too made this error

  • 2 hours ago, # ^ |

    Never use doubles and floats if you can avoid it.

  • 113 minutes ago, # ^ |

    ← Rev. 3 →  

    0

    Floating Point precision error. Try this test case:

    It should return 1, since you need to multiply the first numerator by 0, but your code seems to print 0, because it incorrectly calculated the first fraction as 0 due to precision errors.

3 hours ago, # |

B — Interesting Sum Proposed solution O(nlog(n)) fails with time limit on test 15 when it's implemented in Java (not sure about other languages).

  • 2 hours ago, # ^ |

    I suppose you can steal SecondThread's template and use his custom sort and input? It might be good enough.

  • 27 minutes ago, # ^ |

    Arrays.sort on primitives can degrade to O(n^2). Either make an array of the wrapper class, or use/ convert to Collections

2 hours ago, # |

Didn't get the 'C' problem. Can anyone explain?

  • 2 hours ago, # ^ |

    ← Rev. 3 →  

    +3

    Suppose you have two 0s that are next to each other, either horizontally, vertically, or diagonally. Then either the entire matrix is filled with 0s, or there exists a 1 that can be covered by an L-piece that also covers 2 zeros. The nice thing is that even after covering this 1, the property must continue to hold, so there is another 1 that can be covered by a single L-piece that also covers 2 zeros, and so on. As a result, if there are kk 1s in the matrix, then we can perform kk operations to zero them all, covering exactly one 1 with each operation. Try this out with Sample Input #2.

    But if you don't have two 0s aligned (horizontally, vertically or diagonally) at first, then you have to place the first piece in an area with two 1s (if a 0 exists), or in an area with three 1s (if there is no 0 at all initially). After that, however, the remaining 1s can be covered one at a time.

    Basically: if there exists two 0s aligned horizontally/vertically/diagonally, then the answer is the number of 1s initially. Otherwise, if there exists at least one 0, then the answer is (number of 1s) minus 1. Otherwise, if there is no 0, then the answer is (number of 1s) minus 2.

2 hours ago, # |

← Rev. 5 →  

+1

Weak pretest for A, there wasn't even a test case in pretest with b==d and a and c being coprime, (or variant of it) and many answers got failed in system test due to that. I guess it is easy to have all such simple combinations for pretest., Especially for current A question.

  • 2 hours ago, # ^ |

    I actually think this is a good thing for Problem A when the logic is actually simple, since it punishes those who try to speedsolve it without actually thinking properly about whether their answer is correct, while also rewarding the careful solvers with an opportunity to hack them.

    I can understand the annoyance if it was a really tricky edge case, but for this one, the system tests that are destroying A submissions are stuff that the solver really should have considered before submitting, instead of being so impatient.

    • 2 hours ago, # ^ |

      The point is pretest should represent minimum possible validation of correctness. And if the solution wrong, then penalty would do the job for wrong submission.

2 hours ago, # |

A and B harder than C ngl

2 hours ago, # |

I hate to say this but I believe the statement for B isn't clear enough. When I read the equation to determine beauty of subsegment, I thought it's max(a) — min(a) + max(a[l:r]) — min(a[l:r]). So my intuition to that problem is we want the subsegment to be as long as possible since we can include more elements for the max of the subsegment to be bigger and min to be smaller. So what I thought was that the answer max of max(a) — min(a) + max(a[1:n-1]) — min(a[1:n-1]) and max(a) — min(a) + max(a[2:n]) — min(a[2:n]). (Here [l:r] both sides are inclusive) But it turned out to be different and I still can't turn my head around that. Only reason why I got to the answer was deducing from the sample explanation.

2 hours ago, # |

I succeeded to solve D2 using bit tree on two values: 168855514. I struggle to evaluate the complexity of this solution. Can somebody explain it to me? I guess there is some countertest for getting TLE

2 hours ago, # |

← Rev. 2 →  

0

Cool... problem set was good.

111 minutes ago, # |

Didn't get the logic of i-512 in question D. Can anyone explain it in detail.

107 minutes ago, # |

Could anyone explain what mistake I made for A? 168826645

  • 102 minutes ago, # ^ |

    Float division is inaccurate. Minimize the use of that.

93 minutes ago, # |

Really liked the idea of calculating the the count of 1 in L shape in C.

92 minutes ago, # |

I do not understand the solution to D2. Are we solving for each prefix in order ? Is i the index of the last element of the prefix ? Is j the index of the element before it ? Are the k bits the k most significant bits or least significant bits ? Are the "answers" the length of the subsequences for each prefix ?

58 minutes ago, # |

could someone explain c . editorial is not at all clear

    • 50 minutes ago, # ^ |

      but in the question they mentioned that take L shape such that one square at corner is left .

      • 21 minute(s) ago, # ^ |

        I do not understand your remark.

        If there are two zeroes in a 2 by 2 submatrix and at least a one is still present in the grid, you are certain to be able to remove a single one in a single step, by including two zeroes in the L shape. Thus the answer will be the number of one in the grid.

        Otherwise, if there is at least one zero in the grid, you will be able to remove only two one in one step, by including a zero in the L shape. Then, you are left with the first case, so you just removed an extra one in the first step. The answer is the number of one in the grid, minus one.

        Finally, if there are no zeroes in the grid, your first step will remove two extra ones. The answer will be the number of one in the grid, minus two.

40 minutes ago, # | 

If the tut of Problem D1 is not clear. Have a look here : 
observe the inequality a[j] ^ i < a[i] ^ j.
notice that a[i] < 200 so, we can observe that : 
        1. by doing a[j] ^ i , we can reduce i by atmost 256
        2. by doing a[i] ^ j, we can increase j by atmost 256
Hence and after reducing i to i' and increasing j to j', we need to check if j' > i'.
So to find the max length ending at index i, we have to look only 512 indexes left to it.

35 minutes ago, # |

Really Clean and Concise Editorial.Although problems were intersting specially First one

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK