ZCO13002 - Editorial

editorial
, ,
1

PROBLEM SETTER -
ZCO 2013

DIFFICULTY –
Easy-medium

PREREQUISITES –
Dynamic Programming, Implementation

PROBLEM IN SHORT –
Given a grid and the reachable coordinates or points, find the maximum value of sum of nodes/values in a path for all the paths from top left to bottom right in the grid. Also tell if there exists a path or not.

SOLUTION IN SHORT –
Find the points reachable and put their values equal to the corresponding values in the given 2-D array. The points not reachable are assigned a very high negative number. Then, the classic DP of maximum of sum of values in all paths from top left corner to bottom right corner is used to get the answer. If the answer is very negative, the answer is NO, else YES, and we also output the answer.

EXPLANATION –
Let us find the points which are reachable with a simple brute as shown below. We initialize an array A with a very high negative number. We brute out the reachable points as below and set those point’s values in A equal to the values of corresponding points in the given 2-D array V.

    while(m--)
	{
		cin>>x>>y>>z;
		for(ll i=x-z;i<=x+z;i++)
		{
			if(i<=x)
			for(ll j=y-(i-x+z);j<=y+(i-x+z);j++)
			{
				if(i>0 && i<=n && j>0 && j<=n)
					A[i][j] = V[i][j];
			}
			else
			for(ll j=y-(x-i+z);j<=y+(x-i+z);j++)
			{
				if(i>0 && i<=n && j>0 && j<=n)
					A[i][j] = V[i][j];
			}
		}
	}

A DP can be formulated to find the maximum value of sum of nodes in a path for all the paths from top left to bottom right. This is a classic DP.

dp(i,j) is the maximum of sum of values in all paths from coordinate (i,j) to bottom right corner (N,N).

Here is the recurrence code–

ll dp(ll i, ll j)
{
	if(i<1 || i>n || j<1 || j>n)
		return INT_MIN;
	if(memo[i][j] != LLONG_MIN)
		return memo[i][j];
	if(i==j && i==n)
	    memo[i][j] = a[i][j];
	else
	    memo[i][j] = a[i][j] + max(dp(i+1,j),dp(i,j+1));
	return memo[i][j];
}

Do not confuse with memo array as it is used to store the results. dp notation is used for recursion and memo[i][j] is used for actually storing result of dp(i,j).

This recurrence works because at each coordinate (i,j), we have only two choices: to move down or to move right. We recursively compute the maximum optimal value of both the sub-paths (from (i,j+1) and (i+1,j) to bottom right corner), take the maximum of both, and add it to the value of current coordinate to obtain the maximal sum of values in all paths from (i,j) to bottom right corner.

If dp(1,1) is less than (grid size) * (least number) that is -250000000, then the answer is NO, otherwise YES and output dp(1,1).

If you don’t understand the DP recurrence, don’t worry! You may refer here for a deeper explanation.

TIME COMPLEXITY -
O(M*K^2 + N^2)

2

Easy way to mark M points reachable.

    void ff(int x,int y,int z) {
    int c=0;
    FOR(i,x-z,x+z){
        FOR(j,y-z,y+z){
            if( (abs(x-i)+abs(y-j))<=z){
                if(i>0 && i<=N && j>0 && j<=N)
                    path[i][j]=1;
            }
        }
    } 
  }
3

In the recurrence, shouldn’t it be max(dp(i-1, j), dp(i, j-1))?
Because we’re ultimately computing dp(N, N), which will only end up calling the function with values of i and j greater than or equal to N?

4

Can somebody please help me debug this recurrence for the problem? It has some issues with the sample case. It’s not memoized yet, but even without that, the output should’ve been correct. reached is a global variable initialized as false.

int maxBerries(int r, int c)
{
	if (r == 0 and c == 0)
	{
		reached = true;
		return berries[0][0];
	}
	int ret = numeric_limits<int>::min();
	if (r != 0 and safe[r - 1][c])
	{
		ret = max(ret, berries[r][c] + maxBerries(r - 1, c));
	}
	if (c != 0 and safe[r][c - 1])
	{
		ret = max(ret, berries[r][c] + maxBerries(r, c - 1));
	}
	return ret;
}

(I’ve used 0-based indexing and the function looks for a path from (0, 0) to (N-1, N-1))

6

There’s overflow because you set ret to min value of int but it can go even lower because number of strawberries or whatever can be negative

7

Thanks! It worked. It turns out recursion was not the best way to mark cells safe as well (which makes sense because that would have something like O(4^n) complexity due to recursion), which further resulted in a TLE.

8

can anyone help me where my code is going wrong
https://www.codechef.com/viewsolution/30872701
Just getting failed in one testcase.
ans also in the given editorial isn’t it wrong of deciding NO because answer cant be less than 250000000 any way