Chocolate Pickup

Hard
0/120
Average time to solve is 29m
profile
Contributed by
614 upvotes
Asked in companies
Chegg Inc.AppleOracle

Problem statement

Ninja has a 'GRID' of size 'R' X 'C'. Each cell of the grid contains some chocolates. Ninja has two friends Alice and Bob, and he wants to collect as many chocolates as possible with the help of his friends.

Initially, Alice is in the top-left position i.e. (0, 0), and Bob is in the top-right place i.e. (0, ‘C’ - 1) in the grid. Each of them can move from their current cell to the cells just below them. When anyone passes from any cell, he will pick all chocolates in it, and then the number of chocolates in that cell will become zero. If both stay in the same cell, only one of them will pick the chocolates in it.

If Alice or Bob is at (i, j) then they can move to (i + 1, j), (i + 1, j - 1) or (i + 1, j + 1). They will always stay inside the ‘GRID’.

Your task is to find the maximum number of chocolates Ninja can collect with the help of his friends by following the above rules.

Example: 
Input: ‘R’ = 3, ‘C’ = 4
       ‘GRID’ = [[2, 3, 1, 2], [3, 4, 2, 2], [5, 6, 3, 5]]
Output: 21

Initially Alice is at the position (0,0) he can follow the path (0,0) -> (1,1) -> (2,1) and will collect 2 + 4 + 6 = 12 chocolates.

Initially Bob is at the position (0, 3) and he can follow the path (0, 3) -> (1,3) -> (2, 3) and will colllect 2 + 2 + 5 = 9 chocolates.

Hence the total number of chocolates collected will be 12 + 9 = 21. there is no other possible way to collect a greater number of chocolates than 21.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer 'T', denoting the number of test cases. 

For each test case, the first line contains two integers' R' and 'C' denoting the number of rows and number of columns in the grid. 

Next 'R' lines will contain 'C' integers each the value of each cell in the grid.
Output format : 
For each test case, print the maximum number of chocolates that can be collected.

Output for each test case will be printed in a separate line.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= ‘T’ <= 10
2 <= 'R', 'C' <= 50
0 <= 'GRID[i][j]'<= 10^2
Time Limit: 1sec
Sample Input 1 :
2
3 4
2 3 1 2
3 4 2 2
5 6 3 5
2 2
1 1
1 2
Sample Output 1 :
21
5
Explanation Of Sample Input 1 :
For the first test case, Initially Alice is at the position (0, 0) he can follow the path (0, 0) -> (1, 1) -> (2, 1) and will collect 2 + 4 + 6 = 12 chocolates.

Initially Bob is at the position (0, 3) and he can follow the path (0, 3) -> (1, 3) -> (2, 3) and will collect 2 + 2 + 5 = 9 chocolates.

Hence the total number of chocolates collected will be 12 + 9 = 21.

For the second test case, Alice will follow the path (0, 0) -> (1, 0) and Bob will follow the path (0, 1) -> (1, 1). total number of chocolates collected will be 1 + 1 + 1 + 2 = 5
Sample Input 2 :
2
2 2
3 7
7 6
3 2
4 5
3 7
4 2
Sample Output 2 :
23
25
Hint

Try to think recursively to explore all possible paths.

Approaches (3)
Brute Force Solution

Approach: Say Alice is at column 'C1' and Bob is at column 'C2' of row 'R'. We will try all possible ways of moving both of them to the next row 'R' + 1 under the given conditions.

 

Each person has three choices in the next row, so combined, they have 3 * 3 = 9 choices. Among these nine choices, we will consider the path which gives us the maximum score. In case both of them land on the same cell in a row, we will add that cell's value only once.

 

We will implement the above logic recursively.

 

Algorithm : 

  1. We will pass the ‘currRow’ as 0 as both are on the starting point and ‘C1’ as 0 and ‘C2’ as ‘C’ - 1 as coordinates of Alice and Bob respectively.
  2. Return 'getMaximumChocolates(0, 0, C - 1, grid)’.

 

maximumChocolatesHelper(currRow, C1, C2, GRID):

  1. Check if current coordinates 'currRow', 'C1', and 'C2' are valid or not. If they are not valid, then return 0.
  2. Declare and Initialize variable 'maximumChocolates' with 0.
  3. Run a loop from -1 to 1 with variable 'i' and another nested loop from -1 to 1 with variable 'j'.
  4. Update 'maximumChocolates' with the maximum of it and 'maximumChocolatesHelper(currRow + 1, C1 + i, C2 + j, GRID)'
  5. If ‘C1!=C2’ then add ‘grid[r][c2]’ to the ‘maximumChocolates’.
  6. Return '(maximumChocolates + grid[r][c1])’.
Time Complexity

O(3^(R*C)), where 'R' is the number of rows, and 'C' is the number of columns in the grid.

 

As we are using the recursive solution, there can be at max three calls per coordinates in the recursion, and there are N*M possible coordinates for the grid. Hence there will be a maximum 3^(R*C) calls. Thus asymptotically, the time complexity will be O(3^(R*C)

Space Complexity

O(R*C), where 'R' is the number of rows, and 'C' is the number of columns in the grid.

 

As we are using the recursion, the recursion stack's maximum depth will be the 'R*C'; hence, the space complexity will be the O(R*C).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Chocolate Pickup
Full screen
Console