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