INVENTRY - EDITORIAL
#PROBLEM LINK:
[Practice][1]
[Contest][2]
**Setter:** [Hasan Jaddouh][3]
**Tester:** [Misha Chorniy][4]
**Editorialist:** [Taranpreet Singh][5]
#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.
- If positions $i$ and $i+2$ are empty, and position $i+1$ contain a box, we can move box to position $i$. Call it PUSH operation OR
- If positions $i+1$ and $i+2$ are empty, and position $i$ contains a box, we can move box to position $i+1$. Call it PULL operation.
Determine the minimum number of moves to achieve the task, or determine if its impossible to achieve the task.
#SUPER QUICK EXPLANATION
* First of all, the boxes already lying to the border do not affect answer at all, since they will never be moved. Ignore them, along with their positions.
* Secondly, if we number the boxes from 1 to $K$ from left, we can know that we need to apply PUSH operation exactly $P_i-x$ where box numbered $x$ is present at $P_i$ position.
* After ignoring boxes as well as their positions as mentioned in point 1, if we can, using PULL operation, can place stones at the gap of 1, without reaching the last cell, the answer is possible. Otherwise, it's impossible to move all boxes.
* Now, After getting all stones at gaps of 1, we can move them to leftmost positions using PUSH operations. See, if P is the current position, and There are $X-1$ stones to the left of current stone, The final position of current stone will be $X$, which we'll reach by applying PUSH operation $P-X$ times.
* The crux of the idea is, to apply the minimum number of PULL operations to ensure that we can apply PUSH operation on every stone not already at its intended position and then apply required number of PUSH operations to get the stone at its leftmost position.
#EXPLANATION
See, if we have some boxes already at leftmost positions, something like `###.#...#..`, we can simply ignore the first three boxes, and solve the problem for 1.#...#..1 The answer will remain the same.
After this, number the boxes. Considering the above example, `.1...2..` is the configuration. We also know, that box numbered will move to the first position, box numbered 2 will move to the second position, requiring minimum $(pos-number)$ operations for each box, if we apply no PULL operation.
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-x+y$.
P_I+x-y$.
Rewriting it as $P_I-P_F + y x = 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 PULL operations. We can easily find the Total number of operations (x+y) if we know $y$.
$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 `.##.#.#...` Everything will be clear.
To apply PUSH operation on the box at position p, we need both positions $p-1, p+1$ to be empty. Position $p-1$ 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 `.#.#.#.`, moving the second box by 1 and third box by 2 pull operations.
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, `.####......` step by step.
See the secret box.
[hide]
`.####....`
`.###.#...`
`.###..#..`
`.##.#.#..`
`.##.#..#.`
`.##..#.#.`
`.#.#.#.#.`
`#..#.#.#.`
`#.#..#.#.`
`##...#.#.`
`##..#..#.`
`##.#...#.`
`###....#.`
`###...#..`
`###..#...`
`###.#....`
`####.....`
[/hide]
**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 Complexity
Time complexity is $O(|S|)$ per test case.
#AUTHOR'S AND TESTER'S SOLUTIONS:
[Setter's solution][6]
[Tester's solution][7]
[Editorialist's solution][8]
Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
[1]: http://www.codechef.com/problems/INVENTRY
[2]: https://www.codechef.com/SNCKPE19/problems/INVENTRY
[3]: https://www.codechef.com/users/kingofnumbers
[4]: https://www.codechef.com/users/mgch
[5]: http://www.codechef.com/users/taran_1407
[6]: http://www.codechef.com/download/Solutions/SNCKPE19/setter/INVENTRY.cpp
[7]: http://www.codechef.com/download/Solutions/SNCKPE19/tester/INVENTRY.cpp
[8]: http://www.codechef.com/download/Solutions/SNCKPE19/editorialist/INVENTRY.java