Problem: valet_parking_ch1 (2021 round2)

**Note: This problem shares similarities with [Chapter 2](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-2/problems/C2/). The solution to either chapter may help with solving the other, so please consider reading both first.**

When not out fighting crime, Shaun works valet at the Fairmont hotel. Recently, he has been using his new weapon – the ten rings – to secretly help him park cars among \(T\) valet-designated garages.

The layout of a garage is a grid \(G\) of \(R\) rows (numbered from \(1\) to \(R\) from top to bottom) and \(C\) columns (numbered from \(1\) to \(C\) from left to right) of parking spaces. Initially, each space in row \(i\) and column \(j\) contains a car if \(G_{i,j} =\) "X", or is otherwise empty (if \(G_{i,j} =\) ".").

Shaun has been tasked to clear out a path for easy garage access, requiring cars to be rearranged such that a certain row \(K\) contains no cars in any of its \(C\) spaces. To that end, the magic of the ten rings supports the following \(3\) types of moves:

1. Levitate any car out of the garage and onto the street, leaving its space empty (and the position of all other cars unchanged).
2. Shift all the cars in the garage upwards. For each car in the garage, it moves from its current parking space to the space just above it, unless there's either no such space (due to the car being in row \(1\)) or that space is occupied by a car which is remaining stationary, in which case this car itself remains stationary.
3. Shift all the cars in the garage downwards (similarly to #2).

For example, a sequence of two moves of type #2 is illustrated below:

```
  X..   XXX   XXX
  .XX   ..X   XXX
  ..X   XXX   ..X
  XXX   ...   ...
```

Please help Shaun determine the minimum number of moves required to clear all the spaces in row \(K\).


# Constraints

\(1 \le T \le 55\)
\(1 \le R, C \le 2{,}000{,}000\)
\(R * C \le 2{,}000{,}000\)
\(1 \le K \le R\)
\(G_{i,j} \in \{\)".", "X"\(\}\)

The sum of \(R*C\) across all garages is at most \(10{,}000{,}000\).


# Input

Input begins with an integer \(T\), the number of garages in which Shaun must clear a path. For each garage, there is first a line containing \(3\) space-separated integers \(R\), \(C\), and \(K\). Then, \(R\) lines follow, the \(i\)th of which contains the \(C\) characters \(G_{i,1..C}\).


# Output

For the \(i\)th garage, print a line containing *"Case #i: "* followed by a single integer, the minimum number of moves required to clear row \(K\).


# Sample Explanation

In the first garage, there is a single occupied space which must be cleared. Shaun can simply execute a move of type #1 to clear it.

In the second garage, row \(2\) is already cleared as required, so no moves are needed.

In the third garage, one optimal strategy is for Shaun to use a move of type #1 to remove the car in row \(1\) and column \(2\), followed by a move of type #3 to shift all cars downwards, resulting in the following valid arrangement:

```
  ...
  XXX
  XXX
```

In the fourth garage, one optimal strategy is for Shaun to use a single move of type #2, resulting in the following valid arrangement:

```
  XXX
  ..X
  XXX
  ...
```



Sample input:
6
1 1 1
X
3 3 2
XXX
...
XXX
3 3 1
XXX
.X.
XXX
4 3 4
X..
.XX
..X
XXX
4 5 3
.X.X.
.X.X.
X.X.X
X.X.X
7 8 4
..XX.X.X
X..X.X..
XX....XX
.XXX.XX.
X...XX.X
..X.....
.X..X.X.


Sample output:
Case #1: 1
Case #2: 0
Case #3: 2
Case #4: 1
Case #5: 2
Case #6: 4


Solution: There always exists an optimal solution involving either \(0\) or more upward shifts or \(0\) or more downward shifts, followed by \(0\) or more car removals. It cannot be better to combine both upward and downward shifts, nor to perform car removals before the desired shifts are done.

Assuming for the moment that the grid has no bottom and top edges (i.e. that every car has somewhere to move when a shift is performed), performing \(x\) upward shifts results in the contents of row \(K+x\) being moved into row \(K\), while performing \(x\) downward shifts similarly results in row \(K-x\) being moved into row \(K\). We'll refer to this row which would end up in row \(K\) as the *target row*. We can choose any target row \(i\) at the cost of \(|i-K|\) shift moves. \(i\) may even be chosen to be outside the regular grid (with such rows implicitly considered to contain no blocks) – so, possible relevant choices for \(i\) include all rows between \(0\) and \(R+1\), inclusive.

For a given target row \(i\), after performing the necessary \(|i-K|\) shifts, we would also need to remove every car ultimately present in row \(K\), which may be independently determined per column \(j\). If \(G_{i,j} =\) "X", then row \(K\) will certainly end up with a car in column \(j\) (either that car originally from row \(i\), or another car blocking that one). Otherwise, if \(G_{i,j} =\) ".", then row \(K\) will end up with a car in column \(j\) if and only if there are more than \(K-1\) cars in cells \(G_{1..i,j}\) and/or more than \(R-K\) cars in cells \(G_{i..R,j}\).

These observations can then be turned into a solution. We'll consider each column independently, iterating over its cells from top to bottom while maintaining how many cars are above/below the current cell in that column. This allows us to determine whether or not each column would contribute \(1\) car for each possible choice of target row \(i\). These values can then be added up per row \(i\) and added to \(|i-K|\) to find the best choice of target row. This process takes \(O(RC)\) time.

It can also be observed that only target rows within \(C\) rows of row \(K\) need to be considered, as shifting to further target rows must take longer than sticking with a target row of \(K\) and removing all cars in it, though this insight does not help improve the time complexity of this solution.

[See David Harmeyer (SecondThread)'s solution video here.](https://youtu.be/o9PqijKhax0)


Code: #include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int INF = 1000000000;
const int LIM = 2000005;

int R, C, K;
string G[LIM];

int solve() {
  cin >> R >> C >> K;
  for (int i = 1; i <= R; i++) {
    cin >> G[i];
  }
  vector<int> nb(LIM);
  for (int j = 0; j < C; j++) {
    int tot = 0;
    for (int i = 1; i <= R; i++) {
      tot += G[i][j] == 'X';
    }
    int curr = 0;
    for (int i = 0; i <= R + 1; i++) {
      bool isX = 1 <= i && i <= R && G[i][j] == 'X';
      curr += isX;
      if (isX || curr > K - 1 || tot - curr > R - K) {
        nb[i]++;
      }
    }
  }
  int ans = INF;
  for (int i = 0; i <= R + 1; i++) {
    ans = min(ans, abs(i - K) + nb[i]);
  }
  return ans;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}