You are not logged in. Please login at www.codechef.com to post your questions!

×

INVENTRY - EDITORIAL

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.

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:

Setter's solution
Tester's solution
Editorialist'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

taran_1407's gravatar image

6★taran_1407
4.0k31103
accept rate: 22%

edited 06 Nov '18, 16:09


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.

link

answered 06 Nov '18, 09:12

nilmadhab1's gravatar image

5★nilmadhab1
312
accept rate: 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))
link

answered 05 Nov '18, 04:43

robertking's gravatar image

4★robertking
14816
accept rate: 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
link

answered 12 Nov '18, 17:05

ajaysaundeep's gravatar image

3★ajaysaundeep
01
accept rate: 0%

edited 12 Nov '18, 17:09

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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
×721
×264
×52
×7

question asked: 03 Nov '18, 18:57

question was seen: 871 times

last updated: 12 Nov '18, 17:09