PROBLEM LINK:Setter: Hasan Jaddouh DIFFICULTY:Easy PREREQUISITES:Greedy and Observations. PROBLEM:Given $N$ positions numbered from 1 to $N$, which each cell either empty or containing a box, we need to move each box such that if the total number of boxes is $K$, the boxes end at leftmost $K$ positions. The chef can move boxes in two ways, as follows, each being considered as a separate move.
Determine the minimum number of moves to achieve the task, or determine if its impossible to achieve the task. SUPER QUICK EXPLANATION
EXPLANATIONSee, if we have some boxes already at leftmost positions, something like After this, number the boxes. Considering the above example, Each PUSH operation moves box one position to the left, while each PULL operation moves the box one position. We know the Initial position, say $P_I$, as well as the final intended position of the box, call if $P_F$, so, if we apply $x$ PULL operations and $y$ PUSH operations, then the relation will always satisfy. $P_F = P_I+xy$. Rewriting it as $P_IP_F + x = y$. We need to minimize the number of operations, so, we will try to choose the minimum value of x, that is, Minimum number of PULL operations. We can easily find the Total number of operations (x+y) if we know $x$. Now, Let's see, how we can move boxes to the left. We can prove, that we can apply all PULL operations first, followed by PUSH operations. The proof is left as an exercise. For proof, try to solve the case To apply PUSH operation on the box at position p, we need both positions $p1, p+1$ to be empty. Position $p1$ will be automatically empty if we start considering boxes from the left. Now, to empty position $p+1$ we have to apply PULL operation at the box at position p+1. To achieve that, we need to push box immediately to the right of p+1 at position p+3. This procedure repeats, each time, we need to move boxes till we have all boxes in form probably
Gaps may occur, do not worry about them, The important thing is, that no two stones are adjacent. This form is necessary because we cannot apply PUSH operation at a box at position p unless position p+1 is empty, and that never happens, if there are two boxes adjacent to each other (unless these boxes are already at leftmost position, already ignored) Hence, we can find the position where the current box shall reach, if we know the position previous box will reach. If both positions p and p+1 are not empty, the box at p+1 will reach p+2 and so on. Consider example We can simulate, that We will arrive at position Consider example Again, we can see, that we will arrive at the same position with 2 PULL operations. Now, knowing total pull operations, we can count the total number of moves too. The idea is, that if we intend to move the previous box at position pos, the current box will be moved to position $max(P, pos+2)$ because we need the box beyond pos+1. This becomes the intended position for the current box. This way, we try to get the boxes at gaps of at least 1 by applying the minimum number of PULL operations. After that, we can apply PUSH operation at all stones and count the number of PUSH operations required which is just the distance between leftmost position it can reach and its current position after PULL operations. Now, If still doubtful, try to simulate the whole process, for example, See the secret box. Impossible case Suppose, the Intended position of any box we calculate as above, is above $N$, or its the last position, then the answer is impossible. Because, we cannot move any box outside the range, and secondly, if we move a box to last position (how will you??), we cannot apply either PUSH as well as PULL operation, Hence, we can never move that box to its intended position, making answer impossible. That's all for this problem. Challenge Determine the minimum number of boxes for a given $N$, such that it is impossible to move them to correct positions. Determine the maximum number of boxes for a given $N$, such that it is possible to move them to correct positions. Enjoy :P Time ComplexityTime complexity is $O(S)$ per test case. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 03 Nov '18, 18:57

if we apply x PULL operations and y PUSH operations, then the relation will always satisfy. PF=PI−x+y. I think it should be PF = PI + x  y as while pull PI will go right and after that apply y push and it goes at PF position. answered 06 Nov '18, 09:12

access denied for the testers solution. I decided to use OO for this solution just to make the box logic easier. I worked out the position of a box based on its previous box.
answered 05 Nov '18, 04:43

strong text
answered 12 Nov '18, 17:05
