CHEFSUBA help!

help
, ,
1

Hello. I am new to codechef, and I am not able to solve the question CHEFSUBA. I followed the editorial, learned about segment trees, and implemented the solution. I am getting wrong answer. Can anyone please tell me where I went wrong? I have commented the code so it is easier to understand.

https://www.codechef.com/viewsolution/14397067

2

if(idx_last < first || idx_first > last)
{
return -1;
}

Can you explain returning -1 here? I thought you wanted to return 0 here :confused:

BTW, your code fails on this type of test case-

Input
5 3 5
1 0 0 1 1
?!?!?
Your Output
2
3
3
Expected Output
2
2
3

This error is mostly caused by incorrect rotation of array. Perhaps you are rotating it in opposite direction of what is given in question.

1 Like
3

I have updated the code to make the -1 to be 0. Essentially it would only appear in a max function, so it wouldnt matter if it is 0 or -1 as we are dealing with only nonzero numbers here.

My new code is still giving WA. I fixed the frame calculation logic, with sum[i] now denoting number of 1s in a frame of size k starting from i

https://www.codechef.com/viewsolution/14398977

It works on the two test cases, one in the question and the on you gave me.

4

Umm, what fixing did you do? I mean, are you sure that you correctly fixed it, and that its not just co-incidence that it passed my test case??

5

One of the type of test cases failing are-

Input
5 9 7
1 0 0 1 1
?!?!?!?
Your Output
0
3
3
3
Correct Output
3
3
3
3

Also, can you have a re-look at the limits? Since effectively, size of sum array (upto which we are storing things/upto which its useful) is (n-k+1). But you are still building tree upto entire sum array. I think this is one of the things leading to SIGSEV error in one of the larger test cases. Have a look at your corrections.

for(int i=1;i<arr1.size()-k;i++)//Effectively only elements before arr1.size-k index are useful



build_tree(segvec, sum, 0, sum.size()-1, 0);//using whole of sum to query?
 cout<<maximal(segvec, beg_index, beg_index+n-1, 0, sum.size()-1, 0)<<endl;
6

@viraniaman if length of array is n and frame size is k then number of possible frames will be n-k+1 (you can try with example).so
in your code vector sum should of size n-k+1.

sum[0] contains first frame result after that look that line

for(int i=1;i<arr1.size()-k;i++)
{
    sum[i] = sum[i-1] + arr1[i+k-1] - arr[i-1];
}

I goes from 1 to n-k-1 and hence fills (n-k-1)+1 = n-k frames hence you are missing the last frame.See the I is going till n-k-1 hence arr1[n-k-1+k-1] i.e arr1[n-2] is added and the last element ,arr1[n-1] is not added .So,just correct the code

for(int i=1;i<=arr1.size()-k;i++)
{
    sum[i] = sum[i-1] + arr1[i+k-1] - arr[i-1];
}

Also as size sum vector should be n-k+1 because you passing arr.size() in build_tree

7

Sharp eyes dear. Nicely spotted ^^

8

Thank you so much everyone! This was much appreciated! I love codechef and you people so far!