 # How to do Washing windows from Nov Lunchtime 2019?

How to do Washing windows from Nov Lunchtime 2019?

I just did bruteforce for 50 pts But I couldn’t find a good test case…

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]])

else 0

Do you think you can help me find a test case at which my solution fails? ``````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 = max (cache, cache)
where cache[x] contains the maximum window number above x.

If the Cache 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.

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

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;
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)