Weird Game

Moderate
0/80
Average time to solve is 32m
profile
Contributed by
1 upvote

Problem statement

Ninja and his friends are playing a weird game. The game consists of ‘N’ levels, and each level can be played in ‘M’ different difficulty modes.

For the first level you can start the game with any difficulty mode and for the subsequent levels, you can either play it with one mode lower or one mode above or equal to the previous difficulty mode, i.e. If you played the ith level in jth mode, then you can play i+1th level in either j+1th (j < M) or j-1th (j > 1) or jth mode.

On completion of each level player is awarded some points based on the difficulty mode he played the level.

Points awarded in the ith level played in jth difficulty mode will be ‘POINTS[i][j]’.

Score of the game is defined as the sum of points obtained after completion of each level.

Determine the maximum score a player can get if he optimally plays the game.

You can start the game with any difficulty mode.

Note: In the Problem Statement 1-based indexing is used and in the code 0-based indexing is used.

Example: 
Input: ‘N’ = 3  ‘M’ = 3  ‘POINTS’ = [ [ 1, 4, 3 ], [ 2, 9, 11 ], [ 6, 1, 1 ] ]  

Output: 19

The optimal strategy would be:-
Playing the first level in 2nd difficulty mode with 4 points.
Playing the second level in 2nd difficulty mode with 9 points.
Playing the third level in 1st difficulty mode with 6 points.
So we get a total score of 19 points.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
First line contains ‘T’, denoting the number of test cases.    

The first line of each test case contains two integers, ‘N’ and ‘M’, denoting the number of       levels and the number of difficulty modes respectively.

Each of the next ‘N’ lines contains ‘M’ single space-separated integers, elements of 2D array ‘POINTS’.
Output format : 
Return the maximum score that can be obtained on completion of the game.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 100   
1 <= N, M <= 100
1 <= POINTS[i][j] <= 100

Time Limit: 1 sec
Sample Input 1 :
2
4 4
1 3 1 2   
1 2 5 4  
10 7 6 9  
2 1 7 5
2 2
1 1
1 1

##### Sample Output 1 :

24
2
Explanation Of Sample Input 1 :
For the first test case:-
The optimal strategy would be:-
Plating the first level in second difficulty mode with points 3.
Plating the second level in third difficulty mode with points 5.
Plating the third level in fourth difficulty mode with points 9.
Plating the fourth level in third difficulty mode with points 7.
So total score will be 3 + 5 + 9 + 7 = 24.  

For the second test case:-
Playing in any order will land you with a score of 2.
Sample Input 2 :
2 
5 4
1 3 1 2  
10 2 5 4  
10 9 6 7  
2 7 1 5  
8 2 6 1
3 3
2 9 1
7 5 5
4 4 10
Sample Output 2 :
38
24
Hint

Think of trying out all possibilities in which the game can be played and choose the one with the maximum score.

Approaches (3)
Recursion

In this approach, we will recursively try out all possible combinations of levels and difficulty modes. A recursive function is called with every difficulty mode for the first level and for the subsequent levels we will try all possible difficulty modes and will choose the one with the maximum score.


 

At max we will be having three choices at each level which are playing the next level on the same difficulty mode, one mode above, or one mode lower than the current one.


 

When the ‘LEVEL’ parameter of the recursive function (denoting the current level of the game) crosses the last level we will return zero.


 

The steps are as follows:-

// Recursive function to find maximum score

function getMaxScoreUtil(int level, int difficulty, int n, int m, [ [ int ] ]  points):

  1. If ‘LEVEL’ is equal to N.
    • Return 0.
  2. Initialize the variable ‘ANS’.
  3. Call the function getMaxScoreUtil with LEVEL = LEVEL+1 and the same ‘DIFFICULTY’ and store the returned value in ANS.
  4. If the value of ‘DIFFICULTY’ > 0.
    • Call the function getMinIngredirentsUtil with LEVEL = LEVEL +1 and DIFFICULTY = DIFFICULTY -1.
    • Update the value of ANS with the maximum of ANS and the value returned by the above function call.
  5. If the value of ‘DIFFICULTY’ < ‘M-1’.
    • Call the function getMinIngredirentsUtil with LEVEL = LEVEL +1 and DIFFICULTY = DIFFICULTY +1.
    • Update the value of ANS with the maximum of ANS and the value returned by the above function call.
  6. Return the value ANS + POINTS[ ‘LEVEL’ ][ ‘DIFFICULTY’ ].


 

function getMaxScore(int n, int m, [ [ int ] ] points):

  1. Initialize a variable ‘ANS’ with 0, denoting the maximum score a player can get.
  2. Run a for loop from i = 0…M-1
    • Call the function getMaxScoreUtil with ‘LEVEL’ = 0 and ‘DIFFICULTY’ = i.
    • Update the value of ANS with the maximum of ANS and the value returned by the above function call.
  3. Return the value of the variable 'ANS'.
Time Complexity

O( M * 3N ), Where ‘N’ is the number of levels, ‘M’ is the number of difficulty modes each level has. 
 

We are trying all possible choices for difficulty modes which will be at max 3 at each level so its time complexity will be exponential and we are doing this for ‘M’ difficulty modes for the first level.

 

Hence the time complexity is O( M * 3N ).

Space Complexity

O( N ), Where ‘N’ is the number of levels.

 

Extra auxiliary space will be needed for the recursion call stack.

 

Hence space complexity is O( N ).

Code Solution
(100% EXP penalty)
Weird Game
Full screen
Console