What was the logic in this question . I could solve it only for m=2 . Please explain the logic in simple way , I am a mere beginner.
2 Likes
Logic was simply to find interval which can maximize final score. Now that you scored for m=2, most probably you used recursion which blows up the time due to repeated computation.
Thus we can use something called Dynamic programming to solve this problem efficiently.
I would like to know if you are familiar with DP or not so that I can craft my answer accordingly so that you can understand and be able to solve these types of questions in future
1 Like
Sorry , I am unfamiliar with DP . Thanks for help .
Please if you could tell me what was the approach of chef and chefu to max or min final score .
I’ve read the INTERVAL GAME about a hundred times but I ain’t familiar with the DP, can you explain this problem using DP and not using DP if it’s possible.
If you;re a mere beginner, i would suggest you to not to worry much.
DP or Dynamic Programming isn’t a cakewalk thing. First make sure you’re quite familiar with things like loops, if-else, input-output etc. That’s a basic.
After that, slowly advance yourself. Problems on hackerrank.com in algorithm sectiona re sorted by category, and are good practice (you can get test cases by using their currency - “hackos” , it is earned by solving questions and logging in daily) .
To learn advance things, you also need theory, so I suggest geekforgeeks for this. MAKE SURE TO WATCH THEIR VIDEO LECTURES!! After reading the stuff, the video explanation makes things crystal clear.
And remember one thing- It doesn’t matter what pace you set for yourself, make sure you ENJOY every bit of it, because coding is something which I find very beautiful, interesting and elegant.
Once you reach the basics of dp, give a try to this Q, and if the doubt persists, we are here. Hope this helps you progress further dear! 
1 Like
How final score is maximised or minimised in this question , I want to know that only . Please explain logic of question.
Please tell me what do you mean by how finals core is maximised or minimised? Do you mean you are not able to predict the moves or did you not understand the logic in which they both move?
I will try to be as elaborate as possible.
Firstly, we are given a 2 sequences A and B. Now it is said that at any turn, k, player will choose a interval in A of length Bk. Meaning, in the sequences given in sample test, i.e.
Let A= 3 7 5 4 9 6 1 3
Let B = 6 3 1
In the first turn, 1st element of B is 6. This means Chef can choose a interval of length 6. Now, this means he can choose 6 continuous values of A. We must remember, the sum of all elements in interval adds to the score AND he wants to make score AS LARGE AS possible.
Meaning, if he choses from element 1 to element 6, i.e. 3,7,5,4,9,6 then score is sum of all these elements
Meaning, score = 3+7+5+4+9+6 = 34
Now, he wants to make the score AS LARGE as possible? How will this happen?
The score will be as large as possible if the sum of elements in it are as large as possible. And the sum would be greater if the value of elements in it are greater.
This means, he will chose an interval whose elements have maximum sum.
Lets see the choices of interval Chef has-
1. 3,7,5,4,6,9. Sum =34
2. 7 5 4 9 6 1 Sum = 32
3. 5 4 9 6 1 3 Sum = 28
No more 6 element interval is possible. Out of all the interval, interval “3 7 5 4 9 6” has maximum sum, hence Chef chooses it.
Score =34.
Now its Chefu’s turn. He wants to make score AS SMALL AS POSSIBLE, and we all know that the sum of elements of his interval would be SUBTRACTED from score. Also, he is restricted to choose his interval INSIDE Chef’s interval, as the problem clearly says that the interval of succeeding term should be completely inside the interval of preceding term.
So, interval for Chefu is “3 7 5 4 9 6” and he wants to minimize the score. For this, again, he needs an interval with highest sum. Upon inspection, we see that the interval “5 4 9” has highest sum among all the 3 element intervals possible. So Chefu chooses “5 4 9”
Score = 34-18=16.
Now it is Chefs turn. Remember, the problem said the chosen interval should be COMPLETELY inside the preceeding interval, so among “5 4 9” he cannot choose 5 and 9 since they are not “insides” but “at boundary”. It is clearly mentioned in problem statement that
l < u ≤ v < r,`
So he cannot choose 5 and 9, and he is only left with 4.So he chooses 4 and the game comes to end with score of -
Score=16+4=20
That being said, the entire problem is NOT limited to this. Finding maximum interval will perhaps clear only 1 subtask or two. Why? Because see here-
Let A= 3 7 5 4 9 6 1 3
Let B = 3 1
Now, the maximum sum interval is 4 9 6, which makes score 19. But in next turn Chefu chooses 9, reducing the score to mere 10.
However, if we choose 5 4 9, then final score would be 5+4+9-4 = 14, which is higher. I think dp is needed here for full score, which I sadly don’t know much atm.
However, I can give you a link to correct code-
That’s all I can help dear, and yeah, thanks for correction.
Thanks for help ,but I don’t think that taking maximum sum in every turn will help.I was trying that way but I got only 5 sub tasks right . I think logic is somewhat different.
Thanks for correction, yeah. I missed the part that Chefu is also playing optimally, so my test cases had Chefu taking the worst choice. Anyway, this problem would then require things that I don’t know yet, but I can give you a link to correct code. I have added it in answer, so please have a look. I hope that this helps
Ok so lets try DP solution here. Before I start DP, I will give you a slight motivation for DP. DP stands for Dynamic Programming and is used to solve optimization problem by storing the results of solution of smaller sub-tasks.
For ex: Lets take example of factorial. If we write naive factorial program
ll fac(ll n)
{
(n==1)?return 1:return n*fac(n-1);
}
Now you can check recurence T(n)=n*T(n-1) which is O(2^n)
So now question arises can we do something better.
So what if we store previous values of fac and get next value from it.
Ex :dp[i] means fac(i)
dp[0]=dp[1]=1
dp[i]=i*dp[i-1]
Now for finding fac(5), we start from dp[0],dp[1] to dp[5]. This is called bottom-up approach (solving smaller sub-tasks first)
Now lets try to formulate DP version of this problem
Create a table T[N][M] where,
T[i][j] is the score you can get if the right end of the interval for move ‘j’ is index ‘i’,
T[i][j] = min/max(T[k][j+1]), min/max(Chef’s or CHefu’s chance) depends on whether ‘j’ is odd or even, ‘k’ takes the values of all indices, which lie in the interval for T[i][j] such that it is valid to make move j+1 with ‘k’ as the right end of the chosen interval. There will be b[j]-b[j+1]-1 valid values for ‘k’, you can maintain a sliding maximum/minimum window(whichever is required), for the previous values using a deque or use simple array or a priority queue.
Hope it helps
1 Like
Please someone answer this question , I just want to know how did chef and chefu approach to maximise and minimise the final score.
They approached by choosing the best combination possible. They will always choose the best possible (i.e. most optimal) choice they have.
How do we find the optimal one which they will choose?
Naïve Solution-
By going through all the possible intervals and choosing which one possible is best.
Eg-
Let A= 3 7 5 4 9 6 1
Let B= 6 3 1
- Lets say, Chef chooses 3 7 5 4 9 6
Score= 34
a. Now chefu can choose 7,5,4 or 5,4,9.
Lets say he chooses 7 5 4, then Score now is-
Score= 34-16 = 18.
a1 .Now Chef can only choose 5, which he does, making the final score 23.
This, if chefu chooses 7 5 4.
But would he? He would choose it only if this was the best possible choice for him. To test if its the best or not, we will have to go through all choices and their impact on score and final result and pick out the best.
b. If Chefu would had choosed 5 4 9
Score = 34 - 18 =16.
b1. Chef can only choose 4, making final score 20.
Since this leads to lower final score, Chefu will pick this one, IF AVAILABLE.
When will this be available? If chef picks 3 7 5 4 9 6 as his choice.
2 .What if Chef would had choosen 7 5 4 9 6 1 -
Score= 32.
Chefu could choose 5 4 9, 4 9 6.
a. Had chefu taken 5 4 9,-
Score= 32- 18 =14.
a1. Chef would had to choose 4 now as its only choice available, making final score 14+4=18.
b. Had Chefu choose 4 9 6, Score would be 32-19 = 13. But problem here is-
b1. Chef has (one and only) ‘choice’ of 9. He can only take 9 and this would make score 13+9 = 22.
Since final score in earlier choice was less, Chef would NOT take this alternative. Meaning, Chefu will pick 5 4 9.
BUT! Chefu will have these two choices if chef chooses 7 5 4 9 6 1. Recall that Chef’s goal is to MAXIMISE the score, so he will pick that interval, where after Chefu’s moves and his moves, final score is greater.
One thing MUST be clarified here, we have to look for the greatest score from among the “possible” scores. Because if Chefu would get a chance, he will try to minimise it as much as he can.
Remember this one observation-
A score is NOT possible if it involves either Chef or Chefu making an non-optimal choice. OR A score is possible IF AND ONLY IF, all choices made to reach the score are optimal, for Chef AND Chefu.
(If you look closely, only one score is possible and that’s the score we are looking for. Refer to the image below)
In the image, I have shown in tree diagram which scores are possible and which are now-
(Note- For proper understanding of possible and not possible scores, read the ‘possible’ or ‘not possible’ from bottom to top.)
3 Likes
Thanks brother , thanks a lot . You made my day. I was looking for answer desperately.
I am glad the explanation came across you clearly dear.
Try this solution : https://www.codechef.com/viewsolution/12915345
and this : https://www.codechef.com/viewsolution/13073576
-
calculate Prefix Sum [To get the sum of range in O(1) ].
-
Calculate dp[] for base Cases ( for last move i.e k = m-1) (i.e if b[m-1] = 2 then dp[i] = a[i] + a[i+1] )
-
proceed from last to first [for all moves from m-2 to 0]
3. Maintain a Queue to store the Maximum value for the range
3. Main Idea dp[i] = (summ[i+range] - summ[i]) - dp[Q[front]]; // Range_Sum - Previous_Maximum -
ans = maximum in dp[]
1 Like
Hi Ayush,
I have made a video editorial on this problem:
Cheers!
Thank you…
@vijju123 @gkcs please have a look at my solution, I am not getting it where is it going wrong.
#include<stdio.h>
#include<math.h>
int main(){
int t,i,j,x,y,ans,p,max,sum,k,b,aa,bb,pos1,pos2;
scanf("%d",&t);
while(t--){scanf("%d %d",&x,&y);ans=0;p=1;pos1=-1;pos2=x;
int a[x];
for(i=0;i<x;i++){scanf("%d",&a[i]);}
for(i=0;i<y;i++){scanf("%d",&b);p++;max=0;
for(j=0;j<=(x-b);j++){sum=0;
if(pos1<j && (j+b-1)<pos2){for(k=j;k<(j+b);k++){sum=sum+a[k];}
if(sum>max){max=sum;aa=k-b;bb=k-1;}}
}if(p%2==0)ans=ans+max;else ans=ans-max;
pos1=aa;pos2=bb;
}
printf("%d\n",ans);}
return 0;
}
Link:https://www.codechef.com/viewsolution/13145640
@rj25 Your code fails on this test case-
Compilation Successful
Input (stdin)
1
5 2
10 10 1 10 10
3 1
Your Output
11
Expected Output
20
Your code outputs 11, while I feel correct output is 20, as Chef can choose interval [10,1,10], and Chefu would be only able to choose [1], making final score as 1.
Make sure you are EXCLUDING the corner values of intervals (Eg, if interval of Chef is [1,2,3,4,5], then Chefu can only choose interval from among [2,3,4], 1 and 5 are excluded from his choice, as problem clearly states-
In the i-th turn, the corresponding player should select an interval (continuous subsegment) of sequence A of length Bi that is strictly inside the interval selected in previous turn, i.e. if the interval in previous turn was [l,r] then if the interval in current turn is [u,v] then it should satisfy **l < u ≤ v < r,** except in the first turn where the player can select any interval of length B1.
High stress on-
if the interval in previous turn was [l,r] then if the interval in current turn is [u,v] then it should satisfy l < u ≤ v < r,