Busy Ninja for coding interview round

New update is available. Click here to update.

Last Updated: 19 Mar, 2021

Busy Ninja

Moderate

Solve now

Problem statement

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.

Solve now

Approaches

01Approach

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.

Solve now

02Approach

Let ‘directExp’ be the experience gained without requiring any focus (non-busy days), and ‘focusExp’ be the maximum experience gained on busy days from a window of ‘K’ consecutive days. So, the maximum experience that ninja can gain is equal to ‘directExp + focusExp’. Calculate ‘directExp’ and after that for all non-busy days set ‘EXP[i] = 0’.

As ‘EXP[i] = 0’ for non-busy days, the experience gained on busy days from:

Day 0 to ‘K - 1’ = ‘curExp’ = ‘summation of EXP[i]’ where ‘i’ ranges from 0 to ‘K - 1’.

Day 1 to ‘K’ = ‘curExp - EXP[0] + EXP[k]’

Update ‘curExp = curExp - EXP[0] + EXP[k]’.

Day 2 to ‘K + 1’ = ‘curExp - EXP[1] + EXP[K + 1]’, and so on.

Similarly, move this window of ‘K’ days until the last ‘K’ days and store the maximum value of ‘curExp’ in ‘focusExp’.

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]’
  - ‘EXP[i] = 0’
Initialize ‘focusExp’ to ‘0’. Use it to store the maximum experience gained on busy days from a window of ‘K’ consecutive days.
‘curExp = summation of EXP[i]’ where ‘i’ ranges from 0 to ‘K - 1’.
‘focusExp = curExp’.
Run a loop where ‘i’ ranges from ‘1’ to ‘N - K’:
- ‘curExp = curExp - EXP[i -1] + EXP[i + K - 1]’
- If ‘curExp’ is greater than ‘focusExp’, then:
  - ‘focusExp = curExp’.
Return ‘directExp + focusExp’ as the answer.

Solve now

Busy Ninja

Example :

Input Format :

Output Format :

Note :

Constraints :

01Approach

02Approach

Interested in Coding Ninjas Flagship Courses?