According to me , this is the logic for above program :-

First we are finding the basic case in which we have just added the number with its index and obtained the array, this will be the scenario in round1.

Now iterating through the array we have found the greatest sum upto the index j, notice he has done it two times , one forward iteration and one backward iteration

Now at any particular index j, we have got the maximum value upto j by forward iteration and maximum value at j by backward iteration, and these two are the only values that we have to focus on as all the sums will be incremented and decremented by the same amount at any round if we can notice the change in the jth index value it will be the maximum

Now we start from the last index i.e. N and we have very smartly used N-A as this will be the number added to the given index at a round 1, notice that all the values at index less than A will also be incremented by the same amount and we know that upto Ath index we have the maximum value already stored so we just have to focus on Ath index.

The other value that can change is the number just next to the Ath index as new value will be put below the upper value thus decrementing its value (as the number placed is 1), so if we can find the max of both the changed value , then that will be the answer for that round

Hope that helps :-)

I used the memoization technique and got AC of 0.02s

// Algo for round tab

    #include<iostream>
    using namespace std;
    int findmin(int A[], int i, int sz, int sel, int D[][2]){
     if(i >= sz)
      return 0;
    else{
        if(sel == -1){
            if(D[i][0] == -1)
            D[i][0] = A[i] + findmin(A, i+1, sz, 0, D);
       return D[i][0];
      }else{
        if(D[i][0] == -1)
          D[i][0] = A[i] + findmin(A, i+1, sz, 0, D);
        if(D[i][1] == -1) 
         D[i][1] = findmin(A, i+1, sz, -1, D);
       return min(D[i][0], D[i][1]);
 }
  }
}
 

can`t understand how this algorithm will give the correct answer i.e. the greatest sum up to index k .

suppose if have

A[] = {1,19,29,2,3}; B[]={1,2,1,2,1}

Now we will start the calculation from dpf(1), which will be dpf(1) = A[0]+A[1] = 20 , now dpf(2) = max(A[2]+A[1], dpf(1)-A[1]+B[1]+A[2]]) => max(48, 32) = 48 dpf(3) = max(A[3]+A[2], dpf(2)-A[2]+B[2]+A[3]) => max(31, 22) = 31 dpf(4) = max(A[4]+A[3], dpf(3)-A[3]+B[3]+A[4]) => max(5, 34) = 34

hence the max value up to k = 4 that we are getting is 34 while it must be 48 as the sum of A[1] and A[2].

Please tell me where i am wrong??

If we take into account that the size of the set is also being reduced with each recursive call, we will find that on reaching the last position we have just one option i.e to put 1 , in second last position we have 2 options i.e 1 and 2 which are arranged in 2 ways, In third last position we will have three numbers i.e. 1,2,3 which are arranged in 6 ways. so going this way, the total elements in P will be n!.

Can anyone tell me how the memory complexity in Q.3 is coming out to be n^2 . I understood that as the depth of the recursion tree is n we have the memory complexity of O(n).

This is how i approched the problem-

As the total time spent is dependent on the time of apperance and dissappearance of the wormhole i calculated the minimum time b/w the appearance and dissapperance of the wormhole, as it is guaranteed that there will be atleast one contest for every wormhole set the duration i calculated should have atleast one contest in it and as it is minimum , it should be the required answer.

But on submission i got mixed result, 5[3 from subtask 1 and 2 from subtask 2] tests were passed, can someone tell me what is wrong with my this approch , below is my code :-

#include<bits/stdc++.h>
using namespace std;
 
int main(){
	int n,v,w,i,j;
	cin>>n>>v>>w;
	int S[n], E[n];
	for( i = 0; i < n;i++){

In my opinion

1. Getting the value of first operand
2. Getting the value of second operand
3. Adding them
4. Storing their result in the result 2d array

Can someone please clarify me about how the time complexity for matrix multiplication was calculated ? I understood the due to three for loops we got n^3 time but how we deduced 4*10^3