PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author:
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
None
PROBLEM:
There’s a hidden N\times N grid of characters, A.
You’re given two N\times N grids S and B: the first contains strings, the second contains boolean.
For each (i, j) with 1 \leq i, j \leq N,
- If B_{i, j} = 0, S_{i, j} is the smaller (lexicographic) string between the i-th row and j-th column of A.
- If B_{i, j} = 1, S_{i, j} is instead the larger of the two strings.
Given this information, reconstruct any valid A.
It’s guaranteed that a solution exists.
EXPLANATION:
For convenience, let r_i denote the string formed by the i-th row of A, and c_j denote the string formed by the j-th column.
The information we have is that S_{i, j} equals either \min(r_i, c_j) or \max(r_i, c_j), depending on what B_{i, j} is.
However, no matter what, S_{i, j} is either r_i or c_j which is useful to keep in mind.
It’s a bit hard to work with so much information, so let’s start small and look at just S_{1, 1}.
We know this is either r_1 or c_1, but not which one just yet.
However, observe that r_1 and c_1 share something in common: they both have the same first character! (That being A_{1, 1}).
This means that the first character of S_{1, 1} is also guaranteed to be A_{1, 1}, meaning we know A_{1, 1}.
It’s not hard to see that this can be extended to any i \gt 1 as well: r_i and c_i will have the same i-th character, so A_{i, i} will equal the i-th character of S_{i, i}.
Let’s now look at S_{1, 2}.
This is either r_1 or c_2.
A couple of trivial checks can be performed immediately:
- If S_{1, 2, 1} \neq A_{1, 1} then this can’t be r_1, and must be c_2.
- If S_{1, 2, 2} \neq A_{2, 2} then this can’t be c_2, and must be r_1.
So, the only interesting case is when S_{1, 2, 1} = A_{1, 1} and S_{1, 2, 2} = A_{2, 2}.
Note that once we reach this case, A_{1, 2} has to be either A_{1, 1} or A_{2, 2}.
This is because A_{1, 2} \neq A_{1, 1} \implies S_{1, 2} \neq r_1 \implies S_{1, 2} = c_2 \implies A_{1, 2} = c_{2, 2} = A_{2, 2}.
Now we obtain another trivial condition: if A_{1, 1} = A_{2, 2} we know that A_{1, 2} will also be equal to them, so we need to care about only A_{1, 1} \neq A_{2, 2}.
Notice that so far, we haven’t used any information about B at all — this is where we bring that in.
For convenience, let X = A_{1, 1} and Y = A_{2, 2}.
Then, looking at only the top-left 2\times 2 of A, we’re trying to decide between these two configurations:
Since we’re comparing lexicographically, the first case corresponds to comparing XX against XY, while the second is comparing XY against YY.
Both cases reduce to a simple comparison of X against Y.
In particular, it can be seen that:
- Suppose B_{1, 2} = 0. Then,
- If X \lt Y, the first case is invalid (since XX\lt XY but we know S_{1,2,2}=Y) so we must be in the second case; meaning A_{1, 2} = Y.
- If X \gt Y, the second case is invalid (since YY \lt XY), so we must have A_{1,2}=X.
- Note that both cases together can be combined to just A_{1, 2} = \max(X, Y).
- If B_{1, 2} = 1, similar analysis gives us exactly the opposite: A_{1, 2} = \min(X, Y).
Given that we know X, Y, B_{1, 2} it’s thus possible to determine A_{1, 2} uniquely.
We now attempt to generalize this idea to an arbitrary cell, going in row-major order.
Suppose we’re processing (i, j) now; meaning we’ve processed all cells (i', j') with i' \lt i, or i' = i and j' \lt j.
Given that we’re here, we definitely know the first j-1 characters of r_i (as well as r_{i, i}), and also the first i-1 characters of c_j (and c_{j, j}).
If S_{i, j} matches the conditions of only one of r_i and c_j, we immediately know which one it is and so A_{i, j} can be determined - so once again, we look at the case where it matches both.
The same reasoning as above tells us that A_{i, j} must now equal either A_{i, i} or A_{j, j}.
Just as we did with A_{1, 2}, this can now be determined by looking at B_{i, j}:
- If B_{i, j} = 0 then A_{i, j} must equal the larger of A_{i, i} and A_{j, j}.
- If B_{i, j} = 1 then A_{i, j} must equal the smaller of A_{i, i} and A_{j, j}.
Each character of A can thus be determined in linear time, which is fast enough for us.
Note that the way the answer was constructed also proves the answer is unique.
TIME COMPLEXITY:
\mathcal{O}(N^3) per testcase.
CODE:
Author's code (C++)
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=110;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T,n;
int b[N][N],a[N][N];
char s[N][N][N];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%s",s[i][j]);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&b[i][j]);
for(int i=0;i<n;i++) a[i][i]=s[i][i][i];
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++) //check a[j][i]
{
int flg1=1,flg2=1;
for(int k=0;k<i;k++) if(a[j][k]!=s[j][i][k]) flg1=0;
for(int k=0;k<j;k++) if(a[k][i]!=s[j][i][k]) flg2=0;
if(a[i][i]!=s[j][i][i]) flg2=0;
if(!flg1) a[j][i]=s[j][i][j];
else if(!flg2) a[j][i]=s[j][i][i];
else
{
if(a[j][j]==a[i][i]) a[j][i]=s[j][i][j];
else if(((!b[j][i])&&a[j][j]<a[i][i])||(b[j][i]&&a[j][j]>a[i][i])) a[j][i]=s[j][i][i];
else a[j][i]=s[j][i][j];
}
}
for(int j=0;j<i;j++) //check a[i][j]
{
int flg1=1,flg2=1;
for(int k=0;k<i;k++) if(a[k][j]!=s[i][j][k]) flg1=0;
for(int k=0;k<j;k++) if(a[i][k]!=s[i][j][k]) flg2=0;
if(a[i][i]!=s[i][j][i]) flg2=0;
if(!flg1) a[i][j]=s[i][j][j];
else if(!flg2) a[i][j]=s[i][j][i];
else
{
if(a[j][j]==a[i][i]) a[i][j]=s[i][j][j];
else if(((!b[i][j])&&a[j][j]<a[i][i])||(b[i][j]&&a[j][j]>a[i][i])) a[i][j]=s[i][j][i];
else a[i][j]=s[i][j][j];
}
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++) printf("%c",a[i][j]);
printf("\n");
}
}
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n; cin >> n;
vector<vector<string>> s(n, vector<string>(n));
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
cin >> s[i][j];
}
}
vector<vector<int>> b(n, vector<int>(n));
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
cin >> b[i][j];
}
}
vector<vector<char>> ans(n, vector<char>(n));
for (int i = 0; i < n; i++){
ans[i][i] = s[i][i][i];
}
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
if (i == j) continue;
// look at s[i][j]
auto t = s[i][j];
if (t[i] != ans[i][i]){
ans[i][j] = t[i];
continue;
}
if (t[j] != ans[j][j]){
ans[i][j] = t[j];
continue;
}
if (ans[i][i] == ans[j][j]){
ans[i][j] = ans[i][i];
continue;
}
bool got = false;
for (int k = 0; k < i; k++){
if (t[k] != ans[k][j]){
got = true;
ans[i][j] = t[j];
}
}
for (int k = 0; k < j; k++){
if (t[k] != ans[i][k]){
got = true;
ans[i][j] = t[i];
}
}
// cout << got << "\n";
if (!got){
// cout << i << " " << j << "\n";
if (b[i][j]){
ans[i][j] = min(ans[i][i], ans[j][j]);
} else {
ans[i][j] = max(ans[i][i], ans[j][j]);
}
}
}
}
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
cout << ans[i][j];
}
cout << "\n";
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}