How to do Washing windows from Nov Lunchtime 2019?

I just did bruteforce for 50 pts

How to do Washing windows from Nov Lunchtime 2019?

I just did bruteforce for 50 pts

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

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

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

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.

https://www.codechef.com/viewsolution/28010984. My super easy solution. Used dynamic programming only.

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- https://www.codechef.com/viewsolution/28019907

What are the states exactly?

`> 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

No need to use 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;
}
```

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