GRIDPA - Editorial

PROBLEM LINK:

Contest - Division 3

Contest - Division 2

Contest - Division 1

DIFFICULTY:

EASY

PREREQUISITES:

Dynamic Programming

PROBLEM:

Given a grid of size N*N, some of whose cells are impassable. You are in the top left cell and want to reach the bottom right cell, moving only one step to the right or downwards, in each move. Each cell also has a certain number of coins you collect on passing through it.

You may choose a sequence of at most K adjacent cells and make them passable. Determine if it is possible to reach the bottom right cell, and the maximum amount of coins you can collect.

EXPLANATION:

Note: We use 0 based row and column indexing in the editorial.

When K=0, the problem is a slight modification of a classical grid DP problem. We build our solution directly atop it (readers are requested to get acquainted with the DP solution of the above problem).

Intuition for the DP states

Let’s try visualising our path through the grid. If we denoted passable cells as P and the cells made passable using the special ability as S, our path would look something like:

PP\dots P|\underbrace{SS\dots S}_\text{$\le K$ times}|PP\dots P

Small point of contention - we can make the number of S exactly equal to K by using the special ability continuously on the adjacent P cells (while still keeping the path valid).

Therefore, apart from tracking our current position, we also need to keep count of our position w.r.t. the special ability. More precisely, we keep another state k, such that:

  • k=0 implies we are in the first section of the above path (that is, we haven’t yet used the special ability).
  • 1\le k\le K implies we are in the middle section (and have used the special ability on the last k cells).
  • k = K+1 implies we are in the last section (having used our special ability completely).

Let dp[i][j][k] be the maximum number of coins we can collect if we move till cell (i,j) and have already made k adjacent cells on our path passable. Initially, all values are -INF.

The only base case - dp[0][0][0] = A_{i,j} is obvious.
The transition states of the DP are (out-of-bounds states are -INF):

  • dp[i][j][k] = \max(dp[i-1][j][k-1], dp[i][j-1][k-1])+A_{i,j}

    We use the special ability and make cell (i,j) passable, irrespective of whether it is already passable or not.

  • dp[i][j][0] = \max(dp[i-1][j][0], dp[i][j-1][0])+A_{i,j}

    Only when cell (i,j) is passable by default. We walk through the cell normally, without having travelled on any special cells before.

  • dp[i][j][K+1] = \max(dp[i-1][j][K], dp[i-1][j][K+1], dp[i][j-1][K], dp[i][j-1][K+1])+A_{i,j}

    Only when cell (i,j) is passable by default. We walk through the cell normally, having already used the special ability on cells before this cell.

The final answer is then \max(dp[N-1][N-1][0], dp[N-1][N-1][1], \dots) or -1 if the answer is negative (implying no valid path exists).

TIME COMPLEXITY:

Since computing each state of the DP takes O(1), and computing the final answer takes O(K), the total time to compute the DP table is:

O(N*N*K+K) \approx O(N^2K)

SOLUTIONS:

Editorialist’s solution can be found here


Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

3 Likes

I am unable to understand how the tags are assigned .is it really an easy problem??

9 Likes

For them maybe

This problem is easy because our proposed solution is a simple extension of the classical grid DP problem.

is there any bfs solution possible.i am working on one .if anyone can help??

“We use the special ability and make cell (i,j) passable, irrespective of whether it is already passable or not.”
Can anyone tell me why we want to start a path if the cell is already open given that we haven’t started the path yet ?
I did get this, that if there is an open cell and if we have started the path then it does make sense though.

Yes, it was simply for the ease of implementation. You could make a special path of length less than K, but then, you’d have to define your DP state as:

dp[i][j][K+1] = max(dp[i-1][j][x], dp[i][j-1][x])+A[i][j] where x takes on all values from 0 to K+1.

Thinking back, it sounds like a better way to describe the states (the steps that look redundant to me, don’t seem the same way to beginners in dp). Will see what I can do!

The final answer is then max(dp[N-1][N-1][0], dp[N-1][N-1][1], …) …

Shouldn’t dp[N-1][N-1][K+1] be already max?

can anyone tell why this is showing runtime error.

int main()
{
    int t;
    cin >> t;
    while (t--)
    {

        int n, k;
        cin >> n >> k;
        string str[n];
        for0(i, n)cin >> str[i];
        vector<vector<int>>mat(n, vector<int>(n, 0));
        for0(i, n) {
            for0(j, n) {
                cin >> mat[i][j];

            }
        }

        int dp[n][n][k + 2];
        for0(i, n) {
            for0(j, n) {
                for0(l, k + 1)dp[i][j][l] = -1e9;

            }
        }

        dp[0][0][0] = mat[0][0];
        for0(i, n) {
            for0(j, n) {
                if (i > 0 && str[i][j] == '.')dp[i][j][0] = max(dp[i][j][0], mat[i][j] + dp[i - 1][j][0]);

                if (j > 0 && str[i][j] == '.')dp[i][j][0] = max(dp[i][j][0], mat[i][j] + dp[i][j - 1][0]);
                for1(l, k) {
                    if (i > 0)dp[i][j][l] = max(dp[i][j][l], mat[i][j] + dp[i - 1][j][l - 1]);
                    if (j > 0)dp[i][j][l] = max(dp[i][j][l], mat[i][j] + dp[i][j - 1][l - 1]);
                }
                if (i > 0 && str[i][j] == '.')dp[i][j][k] = max(dp[i][j][k], mat[i][j] + dp[i - 1][j][k]);

                if (j > 0 && str[i][j] == '.')dp[i][j][k] = max(dp[i][j][k], mat[i][j] + dp[i][j - 1][k]);
            }
        }

        cout << max(dp[n - 1][n - 1][k], (int) - 1) << endl;
        // int res = recurse(0, 0, K, str, mat, ans);
        //  cout << res << endl;

    }
    return 0;
}

Yes, I overlooked that. Thanks!

can someone provide me memoized dp code? since Top down approach are more intuitive.

I am getting TLE on subtask 4 with time 1.01 s.
Was O(N^2*K) really the intended solution or does the number of test cases doesnot match the strict time limit?

PS:- If somebody can suggest some optimization, it would be very helpful.
It’s memoized solution.

#include <iostream>
#include <functional>
#include <cstdio>
#include <vector>
using namespace std;

using ll = long long;
constexpr ll OO = (ll)1e14;

int main () {
	int tt; scanf ("%d", &tt);
	while (tt--) {
		int n, K;
		scanf ("%d %d", &n, &K);
		using vi = vector<ll>;
		using vvi = vector<vi>;
		using vvvi = vector<vvi>;

		vvi cost(n, vi(n));
		vector<string> mat(n + 1);
		for (int i = 0 ; i < n; ++i) {
			cin >> mat[i];
		}
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				scanf ("%lld", &cost[i][j]);
			}
		}
		
		vvvi dp(n, vvi(n, vi(K + 2, -1)));
		function < int (int, int, int) > solve = [&] (int i, int j, int k) {
			if (i == n - 1 && j == n - 1) {
				return cost[i][j];
			}
			ll & ans = dp[i][j][k];
			if (ans != -1)
				return ans;
			ans = -OO;
			if (i + 1 < n) {
				if ((k == 0 || k == K) && mat[i + 1][j] != '#')
					ans = max(ans, solve(i + 1, j, k) + cost[i][j]);
				if (k < K) ans = max(ans, solve(i + 1, j, k + 1) + cost[i][j]);
			}
			if(j + 1 < n) {
				if ((k == 0 || k == K) && mat[i][j + 1] != '#')
					ans = max(ans, solve(i, j + 1, k) + cost[i][j]);
				if (k < K) ans = max(ans, solve(i, j + 1, k + 1) + cost[i][j]);
			}
			return ans;
		};
		ll ans = solve(0, 0, 0);
		if (ans < 0) puts("-1");
		else printf ("%lld\n", ans);
	}
}

I think the bfs solution is just as the same as the dp solution.Because DP is doing recursion on a DAG.And when changed to BFS this DAG is just the same.:face_with_monocle:

Why 3D DP array gives SIGSEGV for last two test cases and 3D vector passes all test cases ?

Array solution: Link
Vector solution: Link

1 Like

The answer is in the question itself.

Ya, in my case too all the testcases failed for 3d array but passed for 3d vector… dunno whyyy :disappointed: :disappointed:

The memory for global variables is allocated on the heap. Similarly, memory for a vector is also allocated on the heap. But, memory for local variables (other than STL data structures) is allocated on the stack. If this exceeds the stack size of the program, it results in a Segmentation fault or simply RTE.

1 Like

I also tried to use memoization but got stuck on the same test case 4, then optimized it and now worked, you should also remove vector and use int[] array .
Have a look at my solution if you want Link

Yes, I also used memoization, and thinking in memoization is pretty easy, right :smiley:
Here is my solution Link