How to do Washing windows from Nov Lunchtime 2019?

general
1

How to do Washing windows from Nov Lunchtime 2019?

I just did bruteforce for 50 pts :stuck_out_tongue:

2

Simple DP: CodeChef: Practical coding for everyone

But I couldn’t find a good test case…

3

Use dynamic programming : maximum_dirty_time[i][j] = max(maximum_dirty_time(above neighbours), washing time (above neighbours))

Then a window ends up clean iff cleaning_time[i][j]>maximum_dirty_time[i][j]

1 Like
4

dp[i][j]=max([a[i][j],dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1]])

if dp[i][j]==a[i][j]:answer is 1
else 0

5

Do you think you can help me find a test case at which my solution fails? :slight_smile:

6

Lets follow sample test case.

1
3 4
1 3 7 10
9 2 4 11
8 12 5 6

If you are in cell ( 2, 0), Window = 9

We can observe,

cache[9] = max (cache[5], cache[6])
where cache[x] contains the maximum window number above x.

If the Cache[9] is greater than the window, It cannot be washed, else it can be.

We use the top down approach to get the cache of each window to get the result.

solution : CodeChef: Practical coding for everyone

7

CodeChef: Practical coding for everyone. My super easy solution. Used dynamic programming only.

9

It would be really helpful if someone provides a testcase or mark out the error in this solution.
I used BFS for order of cleaning of window in reverse.
Link- CodeChef: Practical coding for everyone

10

What are the states exactly?

11

> dp[i][j] = max(dp[i - 1][j - 1], max(dp[i - 1][j], dp[i - 1][j + 1]));

Provided, all of them are in bounds.

P.S: dp[i][j] --> maximum time when dirty water comes.

1 Like
12

No need to use DP. Here is my solution

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;
}
13

Brute force works, but with traversing windows in reverse order and not visiting any window twice once you visit a window make lower windows dirty using recursion (floodfill)

Complexity O(rows*cols)

Implementation Click here