ROWSOLD - Editorial

editorial
1

PROBLEM

There are n cells in a row. Some of these cells are empty, and the others are occupied by soldiers. You are provided this information in an array a of length n, where a_i is binary integer: a_0 = 0 denotes that the i-th cell is empty, whereas a_i = 1 says that the cell is occupied by a soldier.

You are playing a game in which you are allowed to make following kind of moves.

  • Choose a soldier (it takes exactly one second to choose a soldier) and ask him to keep moving in the right till he can, i.e. he stops only if he is on the last cell or the next cell to him has a soldier in it. Each soldier moves at a speed of one cell to the right per second.
  • You are allowed to choose a soldier only if he is able to move at least one cell to his right.

You want to play the game as long as possible. Find out the maximum possible time for which you can enjoy the game.

SOLUTION

Let us take examples and make observations from them.

00111: In this case it is not possible to choose any soldier for making a move. The answer will be zero. This tells us if all the soldiers have moved the to right of row, then we can’t make any move and answer will be zero.

01011: Here, we can only move the solider at cell 2 to cell 3. It takes one second to choose and one second to move 1 cell to the right. Answer will be 2. You can notice that the soldiers at position 4 and 5 were already to the right of row and can’t be moved, thus they don’t affect the answer.

1010: We have two soldiers that we can choose to move while making first move. Let us analyze both the cases.

  • Suppose we choose the soldier at first cell to move to the right, we get 0110 (it took 2 seconds). Now, we can only move the solider at 4th cell to the right, we get 0101 (2 seconds again). At last we move the soldier at second cell to the right and get 0011. Overall we took 2 + 2 + 2 = 6 seconds.
  • Suppose we choose to move the soldier at 3rd cell instead. We get 1001 and it took 2 seconds. Now, we move the soldier at first cell to 2 cells right (takes 3 seconds). The game lasted for 5 seconds.

This examples makes us to think that what was special about moving soldier at 1st cell first than moving the one at 3rd cell. Why did the first took longer?

Let us think about the choosing the soldier step and moving the soldier to the right step separately. In the first case, we had 3 soldier choosing steps, and overall we moved soldiers 3 cells to right. In the second case, the soldier choosing steps were only 2, where as the total number of cells moved to the right by the soldiers were 3. You see that total number of cells moved to the right by the soldiers are same in both the cases. In fact, if you think more over it, you realize that this fact is indeed true for any general case. We know that in the final configuration, all the soldiers will be on the right of the row. As the soldier can’t change their relative positions, you can uniquely identify the final positions of the soldiers. The number of cells that solider has to move will be the distance between his initial and final cells. As the initial and final positions of each soldier is unique, so the number of cells moved to the right will remain unique regardless of order of movements.

This means, in order to maximize the time taken, we should choose the soldiers as many times as possible. Let us understand what’s the maximum number of times we can possibly choose a soldier.

Let us say that we have following example row: 0010\textbf{1}0011000101. For the soldier shown in bold, we want to figure out what is the maximum number of times we can choose this soldier. We can see that there are three group of consecutive zeros that occur after the soldier’s cell 00101\textbf{00}11\textbf{000}1\textbf{0}1. You can notice that it is impossible to increase the number of these groups of consecutive zeros by our moves. Also, if you choose the soldier and decide to move him to the right, then you will be decreasing the number of these consecutive zeros by one (001010\textbf{1}11\textbf{000}1\textbf{0}1, 2 groups of zeros). Hence, you can only move the soldier only by the number of consecutive groups of zeros that are to the right of him.

So, here will be our strategy for achieving this maximum time. We pick the leftmost soldier that can be moved and move him. We keep on doing this till we move all the soldiers to the right of row. This will be optimal as in this case the soldiers will be chosen maximum number for the moves.

For solving the second subtask, you can directly simulate this observation in \mathcal{O}(n^2) time. We need to do something better for the last subtask.

For each soldier, we find the number of consecutive groups of zeros that lie to the right of him. Let cnt_i denote this for count for i-th soldier. We go from right to the left, we will say that a group of zeros has started only if the last encountered cell was 1 and the current cell is zero.

cnt[n] = a[i] == 0 ? 1 : 0;
for i = n - 1 to 1:
    cnt[i] = cnt[i + 1]
    if (a[i] == 0 && a[i + 1] == 1):
        cnt[i]++;

We will also need to final the total number of cells moved by the soldiers to find the total time.

final_cell[n] = n;
soldiers = 0;
for i = n to 1:
    final_cell[i] = n - soldiers;
    if (a[i] == 1):
        soldiers++;
total = 0
for i = 1 to n:
    if (a[i] == 1):
        total += final_cell[i] - i;

Finally, our answer will be total number of choose moves and the total number of cells moved

ans = total;
for i = 1 to n:
    if (a[i] == 1):
        ans += cnt[i];

Time complexity of this approach is \mathcal{O}(n) per test case.

1 Like