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

×

MARBLEGF - Editorial

PROBLEM LINK

Contest

AUTHOR

@kuruma

TESTER

@white_king

SOLUTION

This is a trivial application of Fenwick tree. Those not familiar with Fenwick tree may look at the topcoder editorial available here.

All this is asking you to do is to online update of a single element in the array and the sum in a range. Note that the sum of elements of an array from indices i through j can be written as cum_sum[j]-cum_sum[i] where cum_sum[i] is the cumulative sum of all elements in 1 through i.

Seeking the cumulative sum at any point in an array after multiple updates can be done efficiently in O(log n) using the Fenwick tree. You may use the update and read function (available here) in order to do this efficiently.

This question is marked "community wiki".

asked 18 Dec '13, 12:51

balakrishnan_v's gravatar image

5★balakrishnan_v
7651013
accept rate: 0%

edited 12 Feb '14, 04:17

admin's gravatar image

0★admin ♦♦
19.8k350498541

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 .

(22 Dec '13, 15:47) prahaladp82★

It seems the constraints of the problem doesn't really force us to find a subquadratic solution.

I found a few solutions that run in O(Q2) in the worst case, and to hide their identities, I tried to replicate their solution. I got AC with this code (this submission) ! I simply kept track of all updates so far in a list, and during queries I simply determined which of those updates are relevant, using a linear scan!

This is a bit saddening, because some solvers who did this didn't get the chance to learn Fenwick/Binary-indexed/segment tree.

It might have been better to have Q ≤ 200000 instead of just Q ≤ 50000 .

link

answered 18 Dec '13, 16:14

kevinsogo's gravatar image

7★kevinsogo
1.7k586142
accept rate: 11%

6

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 :(

(18 Dec '13, 16:25) kuruma3★
1

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.

(18 Dec '13, 16:31) kcahdog3★

well with me..i solved this problem with initialy constructing a segment tree and storing all the updates .

(22 Dec '13, 18:08) princerk3★

@symphonyiitg, N can be up to 10^6, your code only works with N<=10^5.

link

answered 20 Dec '13, 18:47

junior94's gravatar image

4★junior94
3.2k143058
accept rate: 15%

Thanksa lot :)

(20 Dec '13, 18:57) symphonyiitg2★

is there any efficient method to construct the fenwick tree ..i saw many of the sols construct the tree by reading the data and updating the tree. in worst case if we have to construct the tree of n node it will take O(nlogn) time. and if there are Q query hence the total time complexity will be O(n logn+Qlogn).

link

answered 18 Dec '13, 13:19

princerk's gravatar image

3★princerk
73871123
accept rate: 5%

1

Tree construction could be done in o(n) time. you could check the process() method from my solution here http://www.codechef.com/viewsolution/3049621. The trick is to create a prefix tree and use that for fenwick tree creation

(18 Dec '13, 17:51) newbie4563★
1

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.

(18 Dec '13, 23:35) xellos07★

thanks guys..

(22 Dec '13, 18:11) princerk3★

@xellos0 as i can understand ur code ur code also taking O(nlogn+Qlogn) since ur put() function taking logN time and u r calling this function after taking the N input and of query type "T" & "G". BTW ur code is really amaZing :D

(22 Dec '13, 18:47) princerk3★

@newbie456 although im going through ur code i coudnt understand ur code how the prefix sum is working .can u give some reference to it.

(22 Dec '13, 19:02) princerk3★

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: http://ideone.com/dGHVz9 Thanks

link

answered 20 Dec '13, 17:05

symphonyiitg's gravatar image

2★symphonyiitg
151
accept rate: 0%

whats the mistake in this code http://ideone.com/EqIXgj

link

answered 21 Dec '13, 17:36

damn_me's gravatar image

3★damn_me
2.6k21336
accept rate: 24%

Why are you doing this( http://ideone.com/zlhRbi ) to initialise the tree rather than just update for each element?

(21 Dec '13, 17:57) symphonyiitg2★

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.

(22 Dec '13, 01:10) damn_me3★

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.

link

answered 23 Dec '13, 15:47

ankesh_iitkgp's gravatar image

4★ankesh_iitkgp
16226
accept rate: 0%

edited 23 Dec '13, 15:48

segment tree or BIT, more or less the same thing

(23 Dec '13, 16:13) yashkumar185★

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.

link

answered 16 Feb '14, 09:27

abcdexter24's gravatar image

2★abcdexter24
309212
accept rate: 3%

why am i getting runtime error??link text please help...

link

answered 03 Apr '14, 18:34

abeyaar's gravatar image

1★abeyaar
33422140
accept rate: 30%

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

link

answered 29 Nov '14, 21:48

nidhisingh779's gravatar image

2★nidhisingh779
314
accept rate: 0%

@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?).

link

answered 21 Apr '15, 19:03

sravy_171's gravatar image

2★sravy_171
1
accept rate: 0%

edited 21 Apr '15, 19:41

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.

link

answered 17 Apr '16, 10:06

debverine's gravatar image

2★debverine
112
accept rate: 0%

edited 17 Apr '16, 10:08

Solved using square root decomposition .Worked fine for me:-https://www.codechef.com/viewsolution/17104195

link

answered 21 Jan '18, 13:55

prateek0310's gravatar image

4★prateek0310
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:

×15,680
×3,766
×16

question asked: 18 Dec '13, 12:51

question was seen: 6,587 times

last updated: 21 Jan '18, 13:55