Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Ninja’s Training

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
807 upvotes
Asked in companies
AmazonDunzoGroww

Problem statement

Ninja is planing this ‘N’ days-long training schedule. Each day, he can perform any one of these three activities. (Running, Fighting Practice or Learning New Moves). Each activity has some merit points on each day. As Ninja has to improve all his skills, he can’t do the same activity in two consecutive days. Can you help Ninja find out the maximum merit points Ninja can earn?

You are given a 2D array of size N*3 ‘POINTS’ with the points corresponding to each day and activity. Your task is to calculate the maximum number of merit points that Ninja can earn.

For Example
If the given ‘POINTS’ array is [[1,2,5], [3 ,1 ,1] ,[3,3,3] ],the answer will be 11 as 5 + 3 + 3.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer,' N’, denoting the number of days.

The next ‘N’ lines of each test case have 3 integers corresponding to POINTS[i].
Output Format:
For each test case, return an integer corresponding to the maximum coins  Ninja can collect.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 100000.
1 <= values of POINTS arrays <= 100 .

Time limit: 1 sec
Sample Input 1:
2
3
1 2 5 
3 1 1
3 3 3
3
10 40 70
20 50 80
30 60 90
Sample Output 1:
11
210
Explanation of sample input 1:
For the first test case,
One of the answers can be:
On the first day, Ninja will learn new moves and earn 5 merit points. 
On the second day, Ninja will do running and earn 3 merit points. 
On the third day, Ninja will do fighting and earn 3 merit points. 
The total merit point is 11 which is the maximum. 
Hence, the answer is 11.

For the second test case:
One of the answers can be:
On the first day, Ninja will learn new moves and earn 70 merit points. 
On the second day, Ninja will do fighting and earn 50 merit points. 
On the third day, Ninja will learn new moves and earn 90 merit points. 
The total merit point is 210 which is the maximum. 
Hence, the answer is 210.
Sample Input 2:
2
3
18 11 19
4 13 7
1 8 13
2
10 50 1
5 100 11
Sample Output 2:
45
110
Hint

Try out each combination and find the maximum sum.

Approaches (3)
Recursion

As given in the question, if we do the jth activity on day i, then Ninja cant repeat the activity on day i+1. So, we will define a recursive function REC(N,i, POINTS) that will return the maximum merit points till the Nth day, and he did the ith activity on the Nth day.

We can recursively find the value of REC(N,i, POINTS)  as  POINTS[N-1][i] + maximum among REC(N-1,i-1, POINTS) and REC(N-1,i-1, POINTS) for i different from the current choice of activity.

The final answer will be the maximum of REC(N,i, POINTS) among all three values of i.

 

Algorithm:

  • Defining 'REC'(N, i,’ POINTS’) function :
    • If N is 0:
      • No days left.
      • Return 0.
    • Set ‘ANS’ as POINTS[N-1][i-1].
    • If i == 1:
      • Set MX as maximum as REC(N-1,2,POINTS) and REC(N-1,3,POINTS).
    • If i == 2:
      • Set MX as maximum as REC(N-1,1,POINTS) and REC(N-1,3,POINTS).
    • If i == 3:
      • Set MX as maximum as REC(N-1,1,POINTS) and REC(N-1,2,POINTS).
    • Return ‘ANS’ + ‘MX’.
  • Set ‘ANS’ as 0.
  • Set ‘ANS’ as the maximum of ‘ANS’ and REC(N,1, POINTS).
  • Set ‘ANS’ as the maximum of ‘ANS’ and REC(N,2, POINTS).
  • Set ‘ANS’ as the maximum of ‘ANS’ and REC(N,3, POINTS).
  • Return ‘ANS’.
Time Complexity

O(2^N), where ‘N’ is the number of days.

 

In this approach, in the worst case, we will run the 'REC' function for all possible combinations. Each day has two choices. So the total number of combinations is 2^N. Hence the overall time complexity is O(2^N).

Space Complexity

O( 2^N), where ‘N’ is the number of days.

 

In this approach, in the worst case, we are making 2^N calls of the 'REC'() function. It will consume stack memory. Hence the overall space complexity is O(2^N).     

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Ninja’s Training
All tags
Sort by
Search icon

Interview problems

Best solution with two states of dp

#include <bits/stdc++.h>

long long solve(vector<vector<int>>&arr,int i,int prev,int n,int m,vector<vector<long long>>&dp){

        if(i>=n)return 0;

        

        if(dp[i][prev]!=-1)return dp[i][prev];

        

        long long ans = 0;

        for(int col=0;col<m;col++){

            if(prev!=col){

                long long val = arr[i][col] + solve(arr,i+1,col,n,m,dp);

                ans = max(ans , val);

            }

            

        }

        return dp[i][prev] = ans;

}

int ninjaTraining(int n, vector<vector<int>> &arr)

{

    // Write your code here.

        int m = arr[0].size();

        vector<vector<long long>>dp(n,vector<long long>(m,-1));

        long long ans = -1e9;

        for(int i=0;i<m;i++){

            ans = max(ans , arr[0][i] + solve(arr,1,i,n,m,dp));

        }

        return ans;

}

56 views
0 replies
0 upvotes

Interview problems

BestSpaceOptimisedApproach 🔥| Beats 99.63%🚀 | Most Efficient💯💯

  • We can also apply dynamic programming which can take 3 dp arrays !!
  • But it's not necessarily required !!!
  • We can build up solution without any DP Arrays.

The Approach

  1. Initialize three pointers last_a, last_b, last_c that stores the values of the 1st row in points matrix.
  2. Run a for loop starting at 1 to n.
  3. Since the ninja cannot perform  the same task for 2 consecutive days, we take the remaining tasks of previous days which are having the maximum points !!(i.e., for A1 = Math.max(B0, C0) ,similarly for B and C also).
  4. We then update the last_a, last_b, and last_c values with the calculated ones !!.
  5. We will return the max of all these three values. 

And you're Done !!✅✅💯💯😉

public class Solution {
    public static int ninjaTraining(int n, int points[][]) {
        // Write your code here..                
        int last_a = points[0][0], last_b = points[0][1], last_c = points[0][2];
        for(int i=1;i<n;i++){
            int curr_a = Math.max(last_b, last_c)+points[i][0];
            int curr_b = Math.max(last_a, last_c)+points[i][1];
            int curr_c = Math.max(last_a, last_b)+points[i][2];
            last_a = curr_a;
            last_b = curr_b;
            last_c = curr_c;
        }
        return Math.max(last_c, Math.max(last_a, last_b));
    }

java

algorithms

beginners

84 views
0 replies
2 upvotes

Interview problems

easy cpp || DP + Memoization

 

int MPE(vector<vector<int>> &points,int days,int last, vector<vector<int>> &dp){

    if(days==0){

        int maxi=0;

        for(int i=0;i<=2;i++){

            if(i!=last)

            maxi=max(maxi,points[0][i]);

        }

        return maxi;

    }

    if(dp[days][last]!=-1) return dp[days][last];

    int maxi=0;

    for(int i=0;i<=2;i++){

        if (i != last) {

            int point = points[days][i] + MPE(points, days - 1, i,dp);

            maxi = max(maxi, point);

        }

    }

    return dp[days][last]=maxi;

}

 

int ninjaTraining(int n, vector<vector<int>> &points)

{

    // Write your code here.

    vector<vector<int>> dp(n,vector<int>(4,-1));

    return MPE(points,n-1,3,dp);

}

143 views
0 replies
0 upvotes

Interview problems

Tabulation DP

#include <bits/stdc++.h>

int ninjaTraining(int n, vector<vector<int>> &points) 

{

  //dp[i] -> maximum merit points earned till i'th day

  vector<vector<int>> dp(n,vector<int>(3,0));

  dp[0][0] = points[0][0];

  dp[0][1] = points[0][1];

  dp[0][2] = points[0][2];

 

  for(int i=1; i<n; i++) 

  {

    int run = points[i][0];

    int fight = points[i][1];

    int learn = points[i][2];

 

    //I want to run today

    dp[i][0] = run + max(dp[i-1][1],dp[i-1][2]);

    //I want to fight today

    dp[i][1] = fight + max(dp[i-1][0],dp[i-1][2]);

    //I want to learn today

    dp[i][2] = learn + max(dp[i-1][0],dp[i-1][1]);

  }

    return max({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]});

}

112 views
1 reply
1 upvote

Interview problems

JAVA BEST SOLUTION || Ninja’s Training ||

import java.util.*; 

public class Solution {

        public static int ninjaTraining(int n, int points[][]) { 

       int[][] dp = new int[n][3];  

      for (int[] i: dp) {  

          Arrays.fill(i,-1); 

       }    

    for (int i=0;i<3;i++) {   

         dp[0][i] = points[0][i]; 

       }  

      for (int i=1;i<n;i++) {  

          for (int j=0;j<3;j++) {   

             int maxi=0;   

             for (int k=0;k<3;k++) {   

                 if (j==k)    

                    continue;     

               maxi = Math.max(maxi,dp[i-1][k]);  

              }         

       dp[i][j] = points[i][j] + maxi;    

        }  

      }    

    int maxi = 0;  

      for (int i=0;i<3;i++) {   

         maxi = Math.max(maxi,dp[n-1][i]); 

       }  

      return maxi; 

   }

 }

114 views
0 replies
0 upvotes

Interview problems

best solution using dp

int ninjaTraining(int n, vector<vector<int>> &points)

{

    vector<vector<int>> dp(n,vector<int>(3,-1));

    dp[0][0]=points[0][0];

    dp[0][1]=points[0][1];

    dp[0][2]=points[0][2];

    for(int i=1;i<n;++i){

        dp[i][0]=points[i][0]+max(dp[i-1][1],dp[i-1][2]);

        dp[i][1]=points[i][1]+max(dp[i-1][0],dp[i-1][2]);

        dp[i][2]=points[i][2]+max(dp[i-1][1],dp[i-1][0]);

    }

   return max({dp[n-1][0],dp[n-1][1],dp[n-1][2]});

}

105 views
0 replies
0 upvotes

Interview problems

C++ | DP| MOST OPTIMISED| SC: O(4)| STRIVER'S APPROACH| 100% ACCEPTED

int ninjaTraining(int n, vector<vector<int>> &points){
    // Write your code here.
    vector<int>prev(4,0);
    prev[0]=max(points[0][1], points[0][2]);
    prev[1]=max(points[0][0], points[0][2]);
    prev[2]=max(points[0][0], points[0][1]);
    prev[3]=max(points[0][0], max(points[0][1], points[0][2]));
    for(int day=1;day<n;day++){
        vector<int>temp(4,0);
        for(int last=0;last<4;last++){
            temp[last]=0;
            for(int task=0;task<=2;task++){
                if(task!=last){
                    temp[last]=max(temp[last], points[day][task]+prev[task]);
                }
            }
        }
        prev=temp;
    }
    return prev[3];
}
329 views
0 replies
0 upvotes

Interview problems

My solution in GO

package main


import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)


func solve(day, last int, points [][]int, dp [][]int) int {
if day == 0 {
maxi := 0
for i := 0; i < 3; i++ {
if i != last {
if points[0][i] > maxi {
maxi = points[0][i]
}
}
}
return maxi
}


if dp[day][last] != -1 {
return dp[day][last]
}


maxi := 0
for i := 0; i < 3; i++ {
if i != last {
point := points[day][i] + solve(day-1, i, points, dp)
if point > maxi {
maxi = point
}
}
}
dp[day][last] = maxi
return maxi
}


func ninjaTraining(n int, points [][]int) int {
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, 4)
for j := range dp[i] {
dp[i][j] = -1
}
}
return solve(n-1, 3, points, dp)
}


func main() {
reader := bufio.NewReader(os.Stdin)
input, _ := reader.ReadString('\n')
t, _ := strconv.Atoi(strings.TrimSpace(input))


for t > 0 {
t--


input, _ := reader.ReadString('\n')
n, _ := strconv.Atoi(strings.TrimSpace(input))


points := make([][]int, n)
for i := 0; i < n; i++ {
input, _ := reader.ReadString('\n')
numStrs := strings.Fields(input)
points[i] = make([]int, 3)
for j := 0; j < 3; j++ {
points[i][j], _ = strconv.Atoi(numStrs[j])
}
}


result := ninjaTraining(n, points)
fmt.Println(result)
}
}

 

35 views
0 replies
0 upvotes

Interview problems

C++ DP Bottom Approach for the Problem

#include<bits/stdc++.h>

 

int ninjaTraining(int n, vector<vector<int>> &points)

{

    // Write your code here.

    vector<vector<int>> dp(n,vector<int>(4,-1));

 

    dp[0][0] =  max(points[0][1],points[0][2]);

    dp[0][1] =  max(points[0][0],points[0][2]);

    dp[0][2] =  max(points[0][0],points[0][1]);

    dp[0][3] =  max(points[0][0],max(points[0]      [1],points[0][2]));

 

    for(int day=1;day<n;day++){

        

        for(int last=0;last<4;last++){

            dp[day][last] = 0;

 

            for(int task=0;task<3;task++){

 

                if(task != last){

                    int point = points[day][task] + dp[day-1][task];

                    dp[day][last] = max(dp[day][last],point); 

                }

            }

        }

 

    }

   return dp[n-1][3];

}

229 views
0 replies
0 upvotes

Interview problems

Recursive code

int fun(int day,int last,vector<vector<int>> &points){

if(day==0){

int maxi=0;

for(int i=0;i<3;i++){

if(i!=last){

maxi=max(maxi,points[day][i]);

}

}

return maxi;

}

 

int maxi=0;

for(int i=0;i<3;i++){

if(i!=last){

int totalPoint=points[day][last]+fun(day-1,last,points);

maxi=max(maxi,totalPoint);

}

}

return maxi;

}

int ninjaTraining(int n, vector<vector<int>> &points)

{

// Write your code here.

return fun(n-1,3,points);

 

}

154 views
0 replies
1 upvote
Full screen
Console