You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFSUBA help!

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

asked 03 Jul '17, 11:53

viraniaman's gravatar image

2★viraniaman
1
accept rate: 0%


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

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

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.

link

answered 03 Jul '17, 12:34

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

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.

link

answered 03 Jul '17, 15:47

viraniaman's gravatar image

2★viraniaman
1
accept rate: 0%

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??

(03 Jul '17, 15:54) vijju123 ♦♦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;
link

answered 03 Jul '17, 16:22

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

@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

link

answered 03 Jul '17, 16:24

sonu_628's gravatar image

4★sonu_628
4208
accept rate: 10%

edited 03 Jul '17, 16:30

Sharp eyes dear. Nicely spotted ^^

(03 Jul '17, 16:26) vijju123 ♦♦5★

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

link

answered 04 Jul '17, 11:26

viraniaman's gravatar image

2★viraniaman
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,738
×1,768
×16

question asked: 03 Jul '17, 11:53

question was seen: 496 times

last updated: 04 Jul '17, 11:26