APARTS Editorial

PROBLEM LINK:

Practice
Contest

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",&timestamp[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;
} 
1 Like

Why didn’t u use the A(n-i+1,j) for determining the (i,j) entry. The input format clearly mentions that (i,j) is A(i,j) and not A(n-i+1,j)

https://www.codechef.com/viewsolution/28019373
Any idea why this is failing.
Algorithm used.

  1. find the max of maxMatrix[i][j] = max of above three entries in the matrix.
  2. if maxMatrix and matrix differ (i.e max is greater than the matrix entry) it means that it was cleaned later than the above windows.
  3. therefore, that window will remain clean.

@qwerty29 Right idea, along the right track !!!. However, there is a case where all of the three entities above are smaller than the window being checked, but one of the three entities for those three entities, and so on (the windows 2 or 3 levels above the checked window) are larger than the window being checked. In this case the window is dirty. I’d suggest finding a way of tracking this somehow. Your get max function also does not return the largest of the three windows, but just the last value that is larger than val (e.g, if val = 0, i-1,j-1 = 5, i-1 j =4, i-1 j+1 = 3, your function would return 3).

2 Likes

@qwerty29
Your logic wouldn’t work for the below example.
1
3 4
1 12 7 10
9 2 4 3
8 11 5 6

By your logic window 11 would always be clean since the numbers above them are less then 11. But 11 would be dirty since 12 would be washed after it.

1 Like

Thank you for taking your time to look into this!

I checked getMax it is working fine. As you pointed out.
Error was while updating the maxMatrix i was looking at the previous row in the original matrix instead of the maxMatrix (dp matrix which will store the history of max elements).

It worked!! Thanks!

Yup! corrected that. Thx for the reply!

Just curious, did any one thought this was a Data structure problem and used map (like me)?

@minh2345 At 1st, I want to use unordered_map or gp_hash_table BUT at last, just array can to this job very efficiently without DP.

Here is my Solution
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define sz(a) a.size()
#define all(a) a.begin(), a.end()
#define w(a) std::cerr << #a << " : " << (a) << "\n";

char ans[1001][1001];
int n, m;

void left(int i, int j) {
  while (i <= n and j > 0) {
    if (ans[i][j] == '2')
      ans[i][j] = '0';
    else
      break;
    i++;
    j--;
  }
}

void right(int i, int j) {
  while (i <= n and j <= m) {
    if (ans[i][j] == '2')
      ans[i][j] = '0';
    else
      break;
    i++;
    j++;
  }
}

void down(int i, int j) {
  while (i <= n) {
    if (ans[i][j] == '2') {
      ans[i][j] = '0';
      left(i + 1, j - 1);
      right(i + 1, j + 1);
    } else
      break;
    i++;
  }
}

void solve() {
  memset(ans, '2', sizeof ans);
  cin >> n >> m;
  int tot = n * m;
  pair<int, int> a[tot + 1];
  for (register int i = 1, w; i <= n; i++)
    for (register int j = 1; j <= m; j++) {
      cin >> w;
      a[w] = make_pair(i, j);
    }

  for (register int w = tot, i, j; w > 0; w--) {
    i = a[w].first;
    j = a[w].second;
    if (ans[i][j] == '2') {
      ans[i][j] = '1';
      left(i + 1, j - 1);
      right(i + 1, j + 1);
      down(i + 1, j);
    }
  }

  for (register int i = 1; i <= n; i++) {
    for (register int j = 1; j <= m; j++) cout << ans[i][j];
    cout << "\n";
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
#ifndef ONLINE_JUDGE
  freopen("in.txt", "r", stdin);
#endif

  register int tc;
  cin >> tc;
  while (tc--) solve();
  return 0;
}

Can someone help me with this code:

https://www.codechef.com/viewsolution/28033582

i have used pair and recursion but i m getting tle . can u please share your solution

I tried the editorialist’s solution but it is giving WA on two test cases… can someone help me out?

Do we really need to use a seperate ‘dp’ array. Can we just maintain the max in the same i/p array.
e.g arr is my i/p array. of size n + 2 * m + 2
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
if (arr[i][j] < arr[i - 1][j] ||
arr[i][j] < arr[i - 1][j - 1] ||
arr[i][j] < arr[i - 1][j + 1]) {
ans[i - 1][j - 1] = 0;
} else {
ans[i - 1][j - 1] = 1;
}
arr[i][j] = max(arr[i][j], max(arr[i - 1][j],
max(arr[i - 1][j - 1],
arr[i - 1][j + 1])));
}
}
}

I spent an hour thinking your code was recursive :sweat_smile: