×

# INVENTRY - EDITORIAL

Tester: Misha Chorniy
Editorialist: Taranpreet Singh

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$.

Rewriting it as $P_I-P_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 .##.#.#... 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.

View Content

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:

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

4.0k31104
accept rate: 22%

 1 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 31●2 accept rate: 0%
 0 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.  class Box: def __init__(self, i, prev): self.prev = prev self.i = i self.order = 0 self.rightPos = i if self.prev is not None: self.order = prev.order + 1 self.rightPos = max(self.rightPos, self.prev.rightPos + self.prev.spaceNeeded + 1) self.spaceNeeded = 0 if self.order < self.i: self.spaceNeeded = 1 #needs push if self.rightPos > self.i: self.spaceNeeded = 1 #needs pull def canFit(self, a): return self.rightPos + self.spaceNeeded < len(a) def distance(self): right = self.rightPos - self.i left = self.rightPos - self.order return right + left def f(a): ans = 0 prevBox = None for i, v in enumerate(a): if v == '#': box = Box(i, prevBox) if not box.canFit(a): return -1 ans += box.distance() prevBox = box return ans def test(): tests = """##.#.. 1 .#.#.#. 6 ##.## -1 ##.#.. 1 .#.#.#. 6 ###.# -1 .##. -1 .##.. 4 #.##.. 4 ##.##.. 4 .#.#..#.... 7 .###.. -1 .###... 9 .###..#.. 14""" for line in tests.splitlines(): a, ans = line.split() if f(a) != int(ans): print(a, f(a), ans) test() for _ in range(int(input())): n = int(input()) a = input().strip() print(f(a))  answered 05 Nov '18, 04:43 148●1●6 accept rate: 0%
 0 strong text i tried every testcases but my code is giving wrong answer. my solution:https://www.codechef.com/viewsolution/21613166 @taran_1407 pls help  answered 12 Nov '18, 17:05 0●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×3,820
×1,024
×727
×267
×52
×7

question asked: 03 Nov '18, 18:57

question was seen: 874 times

last updated: 12 Nov '18, 17:09