HUGE_GRID_EZ - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: wuhudsm
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given a binary array A.
Construct an N\times N grid B such that B_{i, j} = \sum_{k = \min(i, j)}^{\max(i, j)} A_k.

Find the minimum cost of a right-down path from (1, 1) to (N, N) in this grid.

EXPLANATION:

First, note that since B is symmetric, we can always remain in only the “upper triangular” region - that is, only move through cells (i, j) such that i \leq j.

Since the costs of B are determined in terms of subarrays of A, it’s helpful to analyze how the moves we make change the subarrays under consideration.

We start off at cell (1, 1), corresponding to the subarray [1, 1]; and our goal is (N, N), representing the subarray [N, N].
Thereafter, if we’re at (i, j), we can move to either (i+1, j) or (i, j+1).
These correspond to shrinking the left border of the subarray b one element, or extending its right border by one element; however, since we’re staying in the upper triangular region, the move to (i+1, j) is only possible when i \lt j, not when i = j.

Since the aim is to minimize the overall sum of the subarrays we visit, and all values are \ge 0, the natural greedy choice here is to move to (i+1, j) whenever possible, i.e. shrink the subarray rather than extend it.

And indeed, this greedy algorithm does give us the optimal solution.

Proof

Consider some index i. What’s the minimum number of times the value A_i must be added to the answer?

Since the right endpoint of the subarray under consideration can increase by only 1 at a time, the first time i is included in a subarray will be in one of the form [L, i] where L \lt i.
Thereafter, i will only be excluded once the left endpoint of the subarray crosses i.
Since the left endpoint also can only increase by 1 at a time, this will surely take at least two more moves: at minimum, the left endpoint must move from i-1 to i, and the right endpoint must move beyond i as well (since the left endpoint cannot be beyond the right endpoint).

That is, the “best” path here is to go along the subarrays [i-1, i] \to [i, i] \to [i, i+1] \to [i+1, i+1].

All in all, the value A_i must be added to the answer at least three times.
The only exceptions are the values A_1 and A_N at the endpoint, which must be added at least two times instead.

We thus obtain a lower bound on the answer: we surely can’t do better than

2A_1 + 2A_N + \sum_{j=2}^{N-1}3A_j

(unless N = 1, in which case the answer is just A_1).

It’s not hard to see that the greedy path of “always move left endpoint when possible” does attain the above lower bound, and so it is optimal as claimed.

So, quite simply, one optimal path is

(1, 1) \to (1, 2) \to (2,2)\to (2, 3) \to (3, 3) \to (3, 4) \to\ldots\to (N-1, N) \to (N, N)

Simulating this path and computing its cost can be done in \mathcal{O}(N) time, which solves the problem.

As noted in the proof above, this cost turns out to be exactly

2A_1 + 2A_N + \sum_{j=2}^{N-1}3A_j

with N = 1 being an edge case having answer A_1.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = '1' + input()
    if n == 1: print(a[n])
    else:
        ans = 0
        for i in range(1, n+1):
            if 1 < i < n: ans += 3*(ord(a[i]) - ord('0'))
            else: ans += 2*(ord(a[i]) - ord('0'))
        print(ans)
2

include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector vi;
typedef vector vl;
define PB push_back
define REP(i, a, b) for (int i = a; i <= b; i++)
#pragma GCC optimize(“Ofast,unroll-loops”)
#pragma GCC target(“avx,avx2,fma”)

int getSum(int i, int j, vi &arr)
{
int sum = 0;
if(j == arr.size()) return INT_MAX;
if(i == arr.size()) return INT_MAX;
if (i > j) swap(i,j);
sum = arr[j];
if (i > 0)
sum = sum - arr[i - 1];
return sum;
}

auto solve()
{
int n;
cin >> n;
string s;
cin >> s;
vi arr;
int count = 0;
for (int i = 0; i < n; i++)
{
if (s[i] == ‘1’)
count++;
arr.push_back(count);
}
ll sum = 0;
int i = 0, j = 0;
sum = arr[0];
while (i < n and j < n) //i = 2 j = 2 s = 5
{
int num1 = getSum(i + 1, j, arr);
int num2 = getSum(i, j + 1, arr);
if (num1 <= num2)
{
i++;
sum = sum + num1;
}
else
{
j++;
sum = sum + num2;
}
}
return sum - INT_MAX;
}

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen(“in.txt”, “r”, stdin);
freopen(“out.txt”, “w”, stdout);
#endif
ll t;
cin >> t;
while (t–)
{
cout << solve();
cout << endl;
}
}

is this code wrong? why is it failing?