Hi
I tried to solve the problem using fenwick tree but I’m getting a runtime error(SIGSEGV). I checked to see if I was doing some invalid array accesses but found none. Please check: dGHVz9 - Online C++ Compiler & Debugging Tool - Ideone.com
Thanks
Isn’t this a straight-forward variation of the Range Minimum Query Problem, except that we need to find the sum here instead of minimum in a range.
And hence, wouldn’t segment trees be an obvious solution? Correct me if I am wrong.
Thanks for this nice question… B.I.T follow great rule of Mathematics… sum upto 2^n can be formed out of combination of of 1,2,4… n powers of 2.
My solution is working correctly for all the test cases but giving NZEC error on submission…Somebody plz help…the following is the link to my solution…
http://www.codechef.com/viewsolution/5468036
@kevinsogo here is link to my code http://www.codechef.com/viewsolution/6804322.when I am using same logic as yours why am i getting TLE.Is it regarding my input method? Can u also explain at which steps BIT is beating my approach.(why is it fast?).
Faced some issues with input. Maybe this has some ’ ’ before ‘\n’ . Again not sure about this, character-wise input got me AC while token-wise input resulted in NZEC. So a friendly heads-up to others.
Well, I’m really sorry to hear this,as my initial idea when setting this problem was to teach the concept of Fenwick Trees to some people (I learnt it myself while setting the problem), but, with this hack some people might have missed it Will try to be more careful next time
Yes, the constraints on the problem were really weak. I looked at the constraints and tried the brute force solution described above and got AC so i didn’t bother spending more time on it. As it was an easy question, i did not realize it was meant to be solved using BIT. Would have been interesting with tougher test cases.
Tree construction could be done in o(n) time. you could check the process() method from my solution here CodeChef: Practical coding for everyone. The trick is to create a prefix tree and use that for fenwick tree creation
You can initialize the tree with zeroes (straight in the constructor), count the differences in number of marbles that the queries cause, and sum those up with array A, which also gives O(N+Q\log{N}) complexity.
Thanksa lot
Why are you doing this( zlhRbi - Online C++ Compiler & Debugging Tool - Ideone.com ) to initialise the tree rather than just update for each element?
I read the whole BIT during contest time cuz i didnt know about it before. So, i understood how to create a tree and perform operations on that further. I may be wrong somewhere, the same can be done by some other way like using update you are saying.
But even if i am doing this way, why i am getting wa. Also, i saw many solutions doing exactly same but i am not able to differentiate the error in my code.
Could this problem be solved using a segment tree ? From what i have read up a segment tree requires ( 2*2^(log n base 2) -1 ) memory for array of size n .Now i tried submitting a solution using segment tree . Here is the link . However i get sigsegv error. Any way you’ll could assist me on this .
well with me…i solved this problem with initialy constructing a segment tree and storing all the updates .
thanks guys…