Educational Codeforces Round 151 Editorial

Educational Codeforces Round 151 Editorial

4 weeks ago, # | Maybe you shoule've set n,k <= 2500 or sth for problem E, because this way many were able to make the n^2k pass while others (myself included) didn't even try it even with the idea in mind

• 4 weeks ago, # ^ | I think the problem is that even with the current constraints, solutions that run in O(N×K^1.5) aren't guaranteed to pass. During the contest I submitted a O(N×K^1.5) solution that used a std::unordered_set which was too slow (admittedly, std::unordered_set is known for having a high constant factor). After the contest I rewrote it to use only arrays, but even then it still takes 4.773 seconds, which is quite close to the 5 second time limit: 211663856. Honestly there isn't a lot of fat to trim there. So I don't think they could have increased the bounds by much without failing reasonable solutions. Is the problem in its current form even solvable in a language other than C++? Maybe Java?

  • 3 weeks ago, # ^ | ← Rev. 6 →   +8 I tried submitting your code. Submission 2, 5 use #define int int64_t while submission 1, 3, 4 don't. I am not very sure as to which compiler should be used for which cases but from my past experience it feels like using 64-bit compiler for 64-bit maths is better.

    • 3 weeks ago, # ^ | Oh interesting! I had no idea that the “G++17” compiler ran in 32-bit mode, and I had been avoiding the “G++20” compiler because it mentioned ”winlibs” and I don't know what it meant so I was afraid it was Windows-specific somehow. It sounds like I should switch to using G++20 for all my submissions from now on! Thanks for the tip!

      • 3 weeks ago, # ^ | I am not able to understand anything about E the statement seemed simple but I am not able to understand anything about E can you please help ?

        • 3 weeks ago, # ^ | Take a look at 211973366. This solution won't pass because it's too slow, but that's not the point. It is intended to show how to enumerate all the possible sequences that can be constructed with at most K moves, recursively. Once you understand this principle, the challenge is to rewrite the recursive solution as an iterative dynamic programming solution that runs within the time and space limits. This is fairly mechanical. If you don't know how to do this, you should read a dynamic programming tutorial first.

          • 3 weeks ago, # ^ | I still don't understand. Can you help? So you say that the sum of excess must be 0 at the end, but even in the example you've given at the start of your submission the sum is -1 + -2 + -1 + 0 + 0 + 1 + 0 = -3 which is not 0, although the numbers of balls in goal and in A are equal. Do I miss something?

            • 3 weeks ago, # ^ | ← Rev. 2 →   +5 It's the final value of excess that must be zero, not the sum of the values. excess represents the number of balls pushed to the right (if positive) or borrowed from the right (if negative). I'll give you two detailed examples to explain the logic of the recursive solution (and them I'm giving up!) Let's say we want to transform A=[1,1,0,0] into B=[0,0,1,1]. Imagine the boxes are lined up in a row and I'm physically moving from the left to the right of the array, trying to make things right, keeping track of how many balls I have to carry from left to right (which is the minimum number of swaps I can do, since a swap moves a ball from bin i to i+1 or vice versa). Initially, I'm at index 0. A[0] = 1 but I want it to be B[0] = 0, so I pick up the ball (I now have 1 ball), and then I move to the right (moving 1 ball with me). I'm at index 1. A[1] = 1 but I want it to be B[1] = 0, so I pick up that ball too (I now have two balls), and then I move to the right (moving 2 balls with me). I'm at index 2. A[2] = 0 but I want it to be B[2] = 1. Luckily I have two balls, so I put one of them down here, and then I move to the right (moving 1 ball with me). I'm at index 3. A[3] = 0 but I want it to be B[3] = 1. I still have 1 ball left so I put it down, and then I move to the right, and I'm at the end of the array with no balls left. excess represents the number of balls I move to the right at each step, so excess = [1,2,1,0] and the total number of times I had to move a ball one space was 1 + 2 + 1 = 4. In that example, I only had to move balls to the right. What if I need to move balls left, let's say by transforming A=[0,0,1,1] to B=[1,1,0,0]? It's clear the optimal solution is to move the balls at A[2] and A[3] two spaces to the left each. I can use the same algorithm as above if I introduce the idea that I can borrow balls from the right. It looks like this: Initially, I'm at index 0 and A[0] = 0 but I want it to be B[0] = 1. Since I don't have a ball, I remember that I need one and move the right (I'm 1 ball short that I need to move from box 1 to 0). I'm at index 1 and A[1] = 0 but I want it to be B[1] = 1. Since I still don't have any balls, I remember that I need another one and move the right (I'm 2 balls short that I need to move from box 2 to 1). I'm at index 2 and A[2] = 1 but I want it to be B[2] = 0, so I pick up the ball. That's one of the balls I can pass to the left (throwing it in box 0), but I'm still 1 ball short as I move to the right. I'm at index 3 and A[3] = 1 but I want it to be B[3] = 0, so I pick up that ball. That's the last ball I needed to pass to the left (throwing it in box 1). So now I can move to the right (at the end of the array) and I have no balls left nor am I short any balls, so I've found a solution. In this example, excess = [-1,-2,-1,0], the negative numbers representing the number of balls I was short. Just like before, the total number of times I had to move a ball one space was |-1| + |-2| + |-1| = 4, except the balls moved to the left instead of to the right. (I didn't prove that this algorithm is optimal, but it's not too difficult to convince yourself that it is.) If the above explanation isn't enough to understand the problem, I suggest you let it go for now, practice on other problems, and come back to it later.

              • 3 weeks ago, # ^ | Thank you very much for such a detailed explanation. Now I get it