GRIDPATHEZ - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: sushil2006
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Prefix sums

PROBLEM:

There’s a 2\times N binary grid.
On one operation, you can swap two adjacent elements within the same row.

Find the minimum number of operations needed to obtain a path from (1, 1) to (2, N) consisting of only ones, that only moves right or down at every step.

EXPLANATION:

A path that only moves right and down on a 2\times N grid has a simple form: it must start at (1, 1), move several steps right, then move one step down, and then only move right till (2, N) is reached.

If the single down move is performed in the k-th column, it means the first k elements of the first row should all be ones, and the last N-k+1 elements of the second row should all be ones.
We don’t care about the values at the other positions.

Let’s fix the value of k and try to compute the minimum cost.
If we can do this quickly enough, we can try all k and take the minimum among them.

Consider the top row.
Suppose it has m ones, initially at positions i_1, i_2, \ldots, i_m in ascending order.
If m \lt k then obviously there’s no way to make the first k elements all 1, so we assume m \geq k.

Since there should be ones in the first k positions, and we’re performing adjacent swaps only, it’s optimal to move the leftmost one to position 1, the second one to position 2, and so on.
That is, for each 1 \leq j \leq k, the 1 initially at position i_j must end up at position j.
This of course takes i_j - j operations.
So, the total number of operations is \sum_{j=1}^k (i_j - j).

The same applies to the second row, just in reverse: the last one ends up at position N, the second-last at position N-1, and so on.

The quantity we’re interested in for the first row is \sum_{j=1}^k (i_j - j)
This is of course easy to compute in linear time for a fixed k, but our aim is to check all k so we need to do better.

It’s not hard to see how: if we attach a cost of i_j - j to the j-th occurrence of 1, then we’re just summing up the first k costs; so to answer this for multiple k quickly we can just build the prefix sum array of the costs.

Do the same for the second row (with appropriate costs), and now each k can be processed in \mathcal{O}(1) time.
This allows us to check all of them and take the best.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, q = map(int, input().split())
    a = input()
    b = input()
    
    acost, bcost = [], []
    j = 0
    for i in range(n):
        if a[i] == '1':
            acost.append(i - j)
            j += 1
    j = n-1
    for i in reversed(range(n)):
        if b[i] == '1':
            bcost.append(j - i)
            j -= 1
    
    for i in range(1, len(acost)): acost[i] += acost[i-1]
    for i in range(1, len(bcost)): bcost[i] += bcost[i-1]
    
    ans = 10**14
    for k in range(1, n+1):
        if len(acost) < k: break
        if len(bcost) < n-k+1: continue
        ans = min(ans, acost[k-1] + bcost[n-k])
    if ans == 10**14: ans = -1
    print(ans)
3 Likes
2

include <bits/stdc++.h>

using namespace std;

void solve() {
int n;
cin >> n;

int cnt = 0;
int k;
cin >> k;
string a;
string b;
cin >> a >> b;
for(int i = 0; i < n; i++){
    if(a[i] == '1'){
        cnt++;
    }
}
for(int i = 0; i < n; i++){
    if(b[i] == '1'){
        cnt++;
    }
}

if(cnt < n + 1){
    cout << -1 << endl;
    return;
}

vector<int> preSum(n + 1, 1e9);
vector<int> postSum(n + 1, 1e9);

int prev = 0;
for(int i = 0; i < n; i++){
    if(a[i] == '1'){
        int last = 0;
        if(prev != 0){
            last = preSum[prev - 1];
        }
        preSum[prev] = last + i - prev;
        prev++;
    }
}



prev = n - 1;
postSum[n] = 0;
for(int i = n - 1; i >= 0; i--){
    if(b[i] == '1'){
        int last = postSum[prev + 1];
        
        postSum[prev] = last + prev - i;
        prev--;
    }
}


int ans = 1e9;
for(int i = 0; i < n; i++){
    ans = min(ans, preSum[i] + postSum[i]);
}

if(ans == 1e9){
    cout << -1 << endl;
    return;
}

cout << ans << endl;

}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int tc = 1;
cin >> tc;
for (int t = 1; t <= tc; t++) {
// cout << “Case #” << t << ": ";
solve();
}
return 0;
}, This solution of mine is being rejected on test case 4 for WA, can someone help me in figuring out the edge case I’m missing

3

It’s because of int overflow so use long long instead.