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. asked 03 Jul '17, 11:53

Can you explain returning 1 here? I thought you wanted to return 0 here :/ BTW, your code fails on this type of test case
This error is mostly caused by incorrect rotation of array. Perhaps you are rotating it in opposite direction of what is given in question. answered 03 Jul '17, 12:34

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. answered 03 Jul '17, 15:47
Umm, what fixing did you do? I mean, are you sure that you correctly fixed it, and that its not just coincidence that it passed my test case??
(03 Jul '17, 15:54)

One of the type of test cases failing are
Also, can you have a relook at the limits? Since effectively, size of sum array (upto which we are storing things/upto which its useful) is (nk+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.
answered 03 Jul '17, 16:22

@viraniaman if length of array is n and frame size is k then number of possible frames will be nk+1 (you can try with example).so in your code vector sum should of size nk+1. sum[0] contains first frame result after that look that line
I goes from 1 to nk1 and hence fills (nk1)+1 = nk frames hence you are missing the last frame.See the I is going till nk1 hence arr1[nk1+k1] i.e arr1[n2] is added and the last element ,arr1[n1] is not added .So,just correct the code
Also as size sum vector should be nk+1 because you passing arr.size() in build_tree answered 03 Jul '17, 16:24

Thank you so much everyone! This was much appreciated! I love codechef and you people so far! answered 04 Jul '17, 11:26
