INVENTRY - EDITORIAL

taran_1407 · November 3, 2018, 6:57pm

PROBLEM LINK:

Practice
Contest

Setter: Hasan Jaddouh
Tester: Misha Chorniy
Editorialist: Taranpreet Singh

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.

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.

Click to view

.####....
.###.#...
.###..#..
.##.#.#..
.##.#..#.
.##..#.#.
.#.#.#.#.
#..#.#.#.
#.#..#.#.
##...#.#.
##..#..#.
##.#...#.
###....#.
###...#..
###..#...
###.#....
####.....

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

Time Complexity

Time complexity is O(|S|) per test case.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

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

robertking · November 5, 2018, 4:43am

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))

nilmadhab1 · November 6, 2018, 9:12am

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.

ajaysaundeep · November 12, 2018, 5:05pm

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