PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
None
PROBLEM:
Given an N\times M boolean grid, you must split it into four parts by drawing two paths: one from the top-left to the bottom-right corner, and one from the bottom-left to the top-right corner.
Find a way to split the grid such that all four parts have distinct sums.
The sum of an empty part is 0.
EXPLANATION:
We want to end up with four parts, each with a sum that’s different from all the others.
Since each sum must be non-negative, the absolute smallest possible values of the sums that can satisfy this condition are (0, 1, 2, 3).
So, if there are less than 0+1+2+3=6 ones in the grid, it’s always impossible to find a valid partition.
It turns out that in every other case, a solution always exists!
We’ll prove this by explicit construction.
Let S denote the number of ones in the grid.
We’re working with S \ge 6.
The sums we’re aiming to achieve are (0, 1, 2, S-3).
As long as S \ge 6 these are all distinct.
Using the first path, let’s try to split the grid into two parts: one with a sum of 1, and the second with a sum of S-1.
This can always be done - one method is as follows.
Let r_1 be the smallest row containing a 1.
Among all the 1's in row r_1, let c_1 denote the largest column such that A_{r_1, c_1} = 1.
Then, consider the following path:
(Parts of this path are compressed for brevity where only one move is possible: for example (0, 0) \to (0, c_1-1) represents the sequence (0, 0) \to (0, 1) \to (0, 2) \to\ldots\to (0, c_1-1).)
Observe that this path will exactly isolate the 1 at cell (r_1, c_1) of the grid into its own component (the “right” part), while everything else will be in the remaining component (the “left” part).
This gives us the desired split into 1 and S-1.
Now, observe that no matter what we do with the second path, the “right” part will always split into two with one having sum 0 and the other having sum 1; after all that’s the only possible way two non-negative integers can sum to 1.
Thus, independent of our choice of second path, we have obtained the values 0 and 1.
We now only need to obtain 2 and S-3 from the part with sum S-1.
It’s not hard to see that a similar idea to the first part works here.
More precisely, let r_2 be the largest row such that among rows r_2, r_2+1, \ldots, N, there are at least 2 ones (in the “left” component.)
We can then isolate the “last two” occurrences of 1 into their own component, as follows:
- If there are no ones at all among rows \gt r_2, then row r_2 itself must contain \ge 2 ones.
Let c_2 be the second-largest column such that A_{r_2, c_2} = 1 (again, considering only the “left” part.) - Otherwise, there can be exactly one occurrence of 1 at a row \gt r_2.
In that case, let c_2 be the largest column such that A_{r_2, c_2} = 1.
With (r_2, c_2) known, we can isolate two ones using the path
This will split out 2 ones, giving us one part with a weight of 2.
Since we already have parts with weights 0 and 1 as noted earlier, the remainder must be S-3, and as long as S \ge 6 we’re done!
TIME COMPLEXITY:
\mathcal{O}(N\cdot M) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
void solve(int test_case){
ll n,m; cin >> n >> m;
ll a[n+5][m+5];
memset(a,0,sizeof a);
rep1(i,n) rep1(j,m){
char ch; cin >> ch;
a[i][j] = ch-'0';
}
ll sum = 0;
rep1(i,n) rep1(j,m) sum += a[i][j];
if(sum < 6){
no;
return;
}
// scoop the right-most guy in the top-most row
string ans1 = "", ans2 = "";
auto trace_path = [&](vector<pll> v){
string res = "";
rep(i,sz(v)-1){
auto p1 = v[i], p2 = v[i+1];
char ch = '?';
ll times = 0;
if(p1.ff == p2.ff){
times = abs(p1.ss-p2.ss);
if(p1.ss < p2.ss){
ch = 'R';
}
else{
ch = 'L';
}
}
else{
times = abs(p1.ff-p2.ff);
if(p1.ff < p2.ff){
ch = 'D';
}
else{
ch = 'U';
}
}
rep1(j,times){
res.pb(ch);
}
}
assert(sz(res) == n+m);
return res;
};
rep1(i,n){
ll p = -1;
rep1(j,m){
if(a[i][j]){
p = j;
}
}
if(p == -1) conts;
vector<pll> v = {{0,0},{0,p-1},{i,p-1},{i,m},{n,m}};
ans1 = trace_path(v);
a[i][p] = 0;
break;
}
// left-most col has at least 2 guys --> scoop top-most 2
// else --> scoop top guy from the next col
ll seen = 0;
rep1(j,m){
vector<ll> guys;
rev(i,n,1){
if(a[i][j]){
guys.pb(i);
}
}
if(guys.empty()) conts;
ll siz = sz(guys);
ll p = -1;
if(seen){
// scoop guys.back()
p = guys.back();
}
else{
seen = siz;
if(siz >= 2){
// scoop guys[siz-2]
p = guys[siz-2];
}
}
if(p == -1) conts;
vector<pll> v = {{n,0},{n,j-1},{p,j-1},{p,j},{0,j},{0,m}};
ans2 = trace_path(v);
break;
}
yes;
cout << ans1 << endl << ans2 << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
cerr << "RUN SUCCESSFUL" << endl;
return 0;
}