Oggy and Cockkroaches

Hard
0/120
Average time to solve is 45m
profile
Contributed by
6 upvotes

Problem statement

Oggy and Cockroaches are playing a game. 'N' cockroaches are hidden inside the holes in a straight line numbered from 1, 2,.., 'N'(i.e. 'i'th cockroach is present at coordinate 'i' where 0 < 'i' <= 'N'). At the time 't', the cockroach at position 'X[t]' comes out of the hole with 'A[t]' coins where 0 < 't' <= 'N'. Initially, at time 't' = 0, Oggy is at coordinate 0 and has 0 coins. Each second, he can remain idle or move only to its adjacent coordinates.

Oggy can collect the coins from 'i'th cockroach only if he is at the coordinate 'i' exactly when it appears.

You can assume that no time is taken to collect the coins.

Return a number 'C' denoting the maximum number of coins Oggy can collect.

Note: Assume 1-based indexing.

For example: 
Let 'N' = 5, 'X' = [1, 2, 4, 3, 5] and 'A' = [20, 0, 10, 0, 1]. 
Oggy moves to position 1 and collects 'A[1]' coins at time t = 1. Then, Oggy will move to position 5, which takes 4 seconds. So, at time t = 5, he will collect 1 coin. In total, he will be able to collect 21 coins. 
Hence, the answer will be 21.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:- 
The first line contains an integer 'T', which denotes the number of test cases.
For every test case:-
The first line contains one integer, 'N',  denoting the total number of cockroaches.   
The second line contains the array 'X' having 'N' space-separated integers, denoting the position of the cockroach that comes out of the hole at some time.
The third line contains the array 'A' having 'N' space-separated integers, denoting the number of coins each cockroach has when they come out of the hole.
Output Format:- 
For each test case, Return a number 'C' denoting the maximum number of coins Oggy can collect.
Note:- 
You don’t need to print anything. Just implement the given function.
Constraints:- 
1 <= 'T' <= 10
1 <= 'N' <= 10^3
1 <= 'X[i]' <= 'N'
0 <= 'A[i]' <= 10^4
Time Limit: 1-sec
Sample Input 1:-
2
4
4 2 2 3
8 3 0 2
3
3 2 1
0 0 0
Sample Output 1:-
5
0
Explanation of sample input 1:-
First test case:- 
'N' = 4, Oggy moves to position 2 in 2 seconds and collects 'A[2]' coins at time t = 2. He will remain idle for 1 second. Then, Oggy will move to position 3, which takes 1 second. So, at time t = 4, he will collect 2 coins. In total, he will be able to collect 5 coins. Hence, the answer will be 5.

Second test case:-
'N' = 3, All the cockroaches came out with 0 coins. Hence, the answer is 0.
Sample Input 2:-
2
4
4 4 4 4
1 2 3 0
2
1 2
2 3
Sample Output 2:-
0
5
Hint

Can we recursively check for each possible case?

Approaches (3)
Recursion

Approach:- 
 

Oggy will always go to point 1, at t = 1, as there is no benefit in remaining at point 0. Let's say he is at coordinate 'y' at the time 't', then he will have the following three possible options 

  • He can either remain at point 'y'.
  • He can move to point 'y'+1.
  • He can move to point 'y'+1.

    We can recursively check for all three above-mentioned cases and find the answer for all of these cases, and will select the option which will return the maximum answer. 

If at any instant, Oggy's position 'y' and 'X[t - 1]' are the same then we can add 'A[t - 1]' to our answer.
 

 Algorithm:-

 

  • Declare a function 'maxCoinHelper(int pos, int time, vector<int> &x, vector<int> &y, int n)' to find the maximum number of coins Oggy can collect if he is at 'pos' at the time 't'.
    • If  'time' is 'n+1' or 'pos' is 0 or 'pos' is 'n+1', return 0.
    • Define a variable 'ans' with 0 to store the maximum number of coins when Bob is at position 'pos' at time 'time'.
    • If 'x[time-1]' is equal to position of 'Bob'.
      • Add the number of coins i.e., 'A[time-1]' in 'ans'.
    • In 'ans' Add the maximum of values return by calling functions 'maxCoinHelper(pos-1, time+1, x, a, n)', 'maxCoinHelper(pos, time+1, x, a, n)' and 'maxCoinHelper(pos+1, time+1, x, a, n)'.
    • Return 'ans'.
  • Return the function 'maxCoinHelper(1, 1, x, a, n)'.
Time Complexity

O(3^N), where 'N' is the total number of cockroaches.

Since at each unit of time from 1 to 'N', we are making three recursion call so the time complexity will be O(3^N).

Space Complexity

O(N), where 'N' is the total number of cockroaches..

since we are using a recursion stack of size 'N', which will take O(N) space. so, the space complexity is O(N).

Code Solution
(100% EXP penalty)
Oggy and Cockkroaches
Full screen
Console