Hello, how to solve INTERVAL problem of the long challenge?
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 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 (whichever is required), for the previous values using a deque.
6 Likes
@hemanth_1 's solution is right and it can also be done using only 1-D array. After calculating maximum result from ith turn, we can overwrite this array because we don’t need i th array once we have calculated i-1 th array.
2 Likes
@hemanth_1 your answer is a great explanation, but it would be very helpful if you could elaborate on the line '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.
@tkhurana96, lets take the sample test case given in the problem page:
1
8 3
3 7 5 4 9 6 1 3
6 3 1
Suppose that we want to find T[7][1] (1-based indexing), ie., the score that we can get if we make move 1 with index 7 as the right end, since b[1]=6, the chosen interval would be a[2] to a[7], which will contain the numbers:
7 5 4 9 6 1Now, you need to pick a subarray of size 3, within the above subarray, ie., you need to pick the right end for your next move. Which of the available positions can you pick ? the positions containing the numbers 9 (position 5) and 6 (position 6), those are the values that ‘k’ would take.
This geeksforgeeks link helped me solve the problem.
http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/
1 Like
@hemanth_1 could you please explain how you are applying sliding technique on your dequeue array in your code? Specifically, how is the dequeuearray getting filled?
Thanks in advance.
Can anyone provide the algorithm of the interval problem
I used priority queue instead of sliding window method which gave me an extra logn factor. The dequeue method is pretty good
Please someone explain the logic how, chef and chefu will maximise and minimise the score.Please.
#include<stdio.h>
int interval(long int a[],int b[],int n,int m,int score,int beg,int k)
{
int sum,maxsum=0,i,j,l,st,fn,end;
l=beg+n-1;
end=beg+b[k]-1;
//printf("end=%d l=%d\n",end,l);
while(end<=l)
{
j=beg;
sum=0;
for(i=0;i<b[k];i++)
{
sum=sum+a[j];
j++;
}
if(sum>maxsum)
{
maxsum=sum;
st=beg+1;
fn=end-1;
}
beg++;
end++;
}
n=fn-st+1;
if((k+1)%2==0)
score=score-maxsum;
else
score=score+maxsum;
// printf("%d\n",score);
k++;
if(k<m)
score=interval(a,b,n,m,score,st,k);
return score;
}
int main()
{
long int a[300001];
int score=0,n,m,j,i,strt,b[201],t;
scanf("%d",&t);
while(t-->0)
{
scanf("%d",&n);
scanf("%d",&m);
for(i=0;i<n;i++)
scanf("%ld",&a[i]);
for(i=0;i<m;i++)
scanf("%d",&b[i]);
strt=0;
score=interval(a,b,n,m,score,strt,0);
printf("%d",score);
}
return 0;
}
Its giving me the correct answer in my compiler but wrong in codechef ide. Where am i doing wrong? Is it about the constraints and the datatypes i have used? if it is plz help me understanding the constraints. i get this kind of error often in codechef.
I recommend using long long int for storing the sum. Your code works very nicely for n <=10, but for cases n ~30, your code does get overflow. Try changing data type to long or long long int and then get back to us 
Hi @mathecodician,
I finally managed to make a video editorial for this problem:
Your doubts and suggestions are welcome.
Cheers!
1 Like
if the third input line had been 7 3 1, and chef would have choosen 3 7 5 4 9 6 1 then what would chefu choose? If chefu chooses 5 4 9 (5+4+9=18)then chef would choose 4 in the next move and the answer would have been 21. But if chefu chooses 4 9 6(4+9+6=19) then chef would choose 4 in the next move and answer would have been 25.
What is the answer in this case.