Busy Ninja

Posted: 19 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Ninja is doing an offline course that has a duration of ‘N’ days. After attending the course, the ninja gains some experience ‘EXP[i]’ (for the day ‘i’). On some days, the ninja is busy and will not be able to attend the course, hence not gaining any experience on that day. If ‘BUSY[i] = 1’, then the ninja is busy on day ‘i’. Otherwise, if ‘BUSY[i] = 0’, the ninja attends the course on day ‘i’. To get the most out of the course, the ninja can focus for ‘K’ days straight (only once during the course), attending the course every day for these ‘K’ consecutive days. You are given two arrays, ‘EXP’ and ‘BUSY’, each of size ‘N’. You are also given an integer ‘K’. The task is to find the maximum experience that the ninja can gain from this course.

Example :
‘N’ = 6, ‘K’ = 3
‘EXP’ = [1, 4, 2, 2, 3, 6]
‘BUSY’ = [0, 1, 1, 0, 0, 1]
To get the maximum experience ninja has to focus on the last ‘3’ days. The maximum experience gained will be = 1 + 2 + 3 + 6 = 12. So, the answer is 12.
Input Format :
The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

The first line of each test case contains two space-integer ‘N’ and ‘K’ denoting the course duration and the number of days ninja can focus on the course.

The second line of each test case contains ‘N’ space-separated integers representing the array ‘EXP’.

The third line of each test case contains ‘N’ space-separated integers representing the array ‘BUSY’.
Output Format :
For every test case, print a single line containing a single integer denoting the maximum experience that the ninja can gain from this course.

The output of each test case will be printed in a separate line.
Note :
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 100
1 <= N <= 1000
0 <= K <= N
0 <= EXP[i] <= 10 ^ 6
BUSY[i] = {0, 1}

Time limit: 1 second.
Approach 1

Use ‘res’ to store the maximum experience that ninja can gain. Initially, ninja focuses on attending the first ‘K’ days starting from day ‘0’ (to ‘K - 1’). Calculate the total experience gained and store it in ‘res’. Now, focus on the next ‘K’ days starting from day ‘1’ (to ‘K’), and if the total experience gained is more than ‘res’, then update ‘res’. Similarly, find the experience gained for each such combination until the last ‘K’ days, each time updating the value of ‘res’. 

 

Find the experience gained without requiring any focus(non-busy days) and store it in ‘directExp’.To find the experience gained after focusing on any ‘K’ days, iterate through the ‘K’ days and only add experiences of those days when ninja was busy to ‘directExp’ (as ‘directExp’ already stores the experience gained on non-busy days).

 

  • Initialize ‘res’ to ‘INT_MIN’. Use ‘res’ to store the answer. ‘INT_MIN’  is the lowest possible integer value.
  • Initialize ‘directExp = 0’. Use to store the experience gained on non-busy days.
  • Run a loop where ‘i’ ranges from ‘0’ to ‘n - 1’:
    • If ‘BUSY[i]’ is equal to 0, then:
      • ‘directExp += EXP[i]’
  • Run a loop where ‘i’ ranges from ‘0’ to ‘N - K’:
    • ‘curExp = directExp’. Use to find the experience gained from busy days if ninja focusses from the day ‘i’ to ‘i + K - 1’.
    • Run a loop where ‘j’ ranges from ‘i’ to ‘i + K - 1’:
      • If ‘BUSY[j]’ is equal to 1, then:
        • ‘curExp += EXP[j]’
    • If ‘curExp’ is greater than ‘res’, then:
      • ‘res = curExp’.
  • Return ‘res’ as the answer.
Try Problem