Division#5545
Sign in

Division (Editorial)

Written by vlomaczk

Let’s say is the sum of all elements in the grid.

First, check if S \equiv 0 \mod 2. If not, print IMPOSSIBLE and return.

Now set target_sum = S / 2 and proceed with the solution.

The maximum path length on the border is , which means we're restricted to using only "S" (South) and "E" (East) moves.

If the grid only contained 0s and 1s, we could apply a greedy algorithm directly.

However, with 0s, 1s, and 2s, this approach may leave us at target_sum - 1 because we might lack a 1 on the border to complete the total sum.

(!!! If you don't know how to implement the greedy algorithm, there’s a C++ example at the end !!!)

Now consider a case where there's a 1 positioned like this:

Grid Example

This 1 can be part of the upper border if sum(B) < target_sum, because otherwise including the 1 would force us to take the entire "B" section, overshooting the target sum due to only using "S", "E" moves.

Similarly, it can be part of the lower border if sum(D) < target_sum.

If we find a 1 that satisfies both conditions — that is, it can belong to either side — we know a solution must exist. Why?

From:

We derive:

sum(D) < target_sum
⇒ -sum(D) > -target_sum
⇒ S - sum(D) > S - target_sum
⇒ sum(A) + sum(B) + sum(C) + 1 > target_sum

So:

Now we construct a solution. Let sum = sum(B). Use a greedy algorithm on section A to get ans1, and on section C to get ans2.

Based on the above conditions, we're guaranteed either:

So:

What if no such 1 exists — i.e., no 1 can be part of both regions?

Examples:

3
0 1 0
0 2 0
0 1 0

or

3
2 0 2
0 0 2
0 0 2

In the second case, there are no 1s at all.

In this case, just run the greedy algorithm across the entire grid.If it gives you target_sum, print the answer. Otherwise, print IMPOSSIBLE.

(I don’t have a formal proof for this fallback case, but it works. If anyone finds one, feel free to post it in the discussion tab.)

Example: C++ Greedy Algorithm

vector<ll> h(n+1, 0);
ll sum = 0;
ll lasth = n+2;

for (ll j = n; j >= 1; --j) {
    for (ll i = 1; i <= n; ++i) {
        if (i > lasth) break;
        if (sum + grid[i][j] <= target_sum) {
            sum += grid[i][j];
            h[j] = i;
        } else break;
    }
    lasth = h[j];
}

if (sum != target_sum) {
    cout << "IMPOSSIBLE\n";
    return;
}

string ans = "";
ll wys = 0;

for (ll i = 1; i <= n; ++i) {
    while (wys < h[i]) {
        ans += 'S';
        wys++;
    }
    ans += 'E';
}

while (ans.size() != 2 * n) ans += 'S';
cout << ans << "\n";
C++