PROBLEM LINK:
Tester: Kasra Mazaheri
Editorialist: Hussain Kara Fallah
PROBLEM EXPLANATION
There is a building with N floors (numbered 1 through N from bottom to top); on each floor, there are M windows (numbered 1 through M from left to right). Let’s denote the j-th window on the i-th floor by (i,j).
All windows in the building need to be cleaned one by one in a specific order. You are given this order as a matrix with N rows and M columns; for each valid i and j, the window (i,j) must be cleaned on the A_{i,j}-th turn.
Whenever we clean a window (i,j), it becomes clean, but the dirty water used for cleaning it flows down to windows (i−1,j−1), (i−1,j) and (i−1,j+1) (more precisely, to all of these windows which exist), so these windows become dirty again. Then, the water flows further down.
The next window is cleaned only after water flows down completely. Note that each window is cleaned only once and there may be dirty windows at the end.
For each window, determine whether it will be clean after the cleaning process ends.
PREREQUISITES:
Dp
DIFFICULTY:
Easy
CONSTRAINTS
1 \leq N,M \leq 10^3
EXPLANATION:
For each window (x,y) dirty water may reach it through windows (x-1,y-1) or (x-1,y) or (x-1,y+1).
For each window (x,y) let’s denote by dp_{x,y} = t the latest moment t such that some window (p,q) was cleaned at moment t and the dirty water reached (x,y) from (p,q).
We previously stated that dirty water may reach (x,y) only from its neighbors. Quite frankly:
t = dp_{x,y}=max( dp_{x-1,y-1},dp_{x-1,y},dp_{x-1,y+1})
Because these are the only possible ways such that the dirty water may reach (x,y).
Now that we have found t for our window (x,y). If t is later than A_{x,y} then it will be dirty by the end of the process, otherwise it will be clean.
After determining the answer for (x,y) (clean/dirty) we should update dp_{x,y}:
dp_{x,y}=max(dp_{x,y},A_{x,y})
Because dp_{x,y} denotes some moment where dirty water reaches (x,y) and it will be propagated to windows below (x,y). At the moment, A_{x,y} the window will be cleaned and dirty water will start flowing, so we must update dp_{x,y} such that A_{x,y} would be propagated as well.
Complexity: O(N*M)
Editorialist solution
#include<bits/stdc++.h>
using namespace std;
int T , n , m , dp[1003][1003] , timestamp[1003][1003] , ans[1003][1003];
int main(){
scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&m);
for(int j = 1 ; j <= n ; j++){
for(int i = 1 ; i <= m ; i++){
scanf("%d",×tamp[j][i]);
dp[j][i] = max(0 , max(dp[j-1][i-1] , max(dp[j-1][i] , dp[j-1][i+1])));
if(dp[j][i] > timestamp[j][i])
ans[j][i] = 0;
else ans[j][i] = 1;
dp[j][i] = max(dp[j][i] , timestamp[j][i]);
}
}
for(int j = 1 ; j <= n ; j++){
for(int i = 1 ; i <= m ; i++){
dp[j][i] = 0;
printf("%d",ans[j][i]);
}
puts("");
}
}
}
Tester Solution
// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 1009;
int n, m, q, A[N][N], dp[N][N], M[N * N];
char S[N][N];
int main()
{
scanf("%d", &q);
assert(1 <= q && q <= 1000);
for (; q; q --)
{
scanf("%d%d", &n, &m);
assert(1 <= n && n <= 1000);
assert(1 <= m && m <= 1000);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
scanf("%d", &A[i][j]), M[A[i][j]] = 1, dp[i][j] = 0;
for (int i = 1; i <= n * m; i ++)
assert(M[i]);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
if (dp[i][j] > A[i][j])
S[i][j] = '0';
else
S[i][j] = '1';
dp[i][j] = max(dp[i][j], A[i][j]);
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
dp[i + 1][j - 1] = max(dp[i + 1][j - 1], dp[i][j]);
dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j]);
}
for (int i = 1; i <= n; i ++)
printf("%s\n", S[i] + 1);
for (int i = 0; i <= n; i ++)
for (int j = 0; j <= m; j ++)
A[i][j] = dp[i][j] = S[i][j] = 0;
for (int i = 0; i <= n * m; i ++)
M[i] = 0;
}
return 0;
}
