PROBLEM LINKSDIFFICULTYMEDIUM EXPLANATIONThe problem can be solved using segment trees. Every node of the tree stores the following data : 1) tree0[k] : In the range [low..high] covered by this node, how many numbers are divisible by 3 considering just additions performed on numbers totally inside this range and not considering additions performed on ranges which are a subrange of the range covered at node k/2
This question is marked "community wiki".
asked 29 Nov '12, 12:15

Can we solve it using BIT? If yes then How?? answered 14 Mar '13, 19:28

plz elaborate your explaination....its too difficult too understand from such 3 confusing statements u have mentioned just for the sake of editorial..  _  answered 31 May '16, 01:21

my code passes sample test cases and few more cases but gives WA,can some one figure it out what am i missing. here's my codehttps://ideone.com/YOnZO6 answered 29 Jun '16, 01:41

Can anyone help me, pls ?? I use Segment Tree but I got Wrong Answer and I don't know why. This is my submission, help me, please. https://www.codechef.com/viewsolution/13414560 answered 01 May '17, 08:41

Hey..I have solved this question using segtrees but Im getting WRONG ANSWER. Here is my code. https://www.codechef.com/viewsolution/15771326 Thanks in advance. answered 11 Oct '17, 19:39

How can one identify that this should be solved through segment tree ? are there any ways to identify such problems (related to segment etc) ? also is there any other way to solve this ? answered 30 Jan, 17:59

@piyusjain1555 its a question of "lazy propagation" in "segment tree"... looks like you were a beginner for coding... so you can google and learn how to do this type of questions... u have have a look at FLIPCOIN which is similar to this question.. answered 05 Apr, 22:12

The following is the idea. Initially, all the numbers are divisible by 3. tree[node][0] = hi  lo + 1 Now, let's say we are updating range [lo .. hi] and hi  lo + 1 = 4. Each update to range [lo .. hi] of tree node moves the count in the following fashion. Update number 1 > all 0's will be 1. 0000 > 1111 and we save these numbers in tree[node][1] Update 1: tree[node][1] = tree[node][0]. Update number 2 > all 1's will be 2. 1111 > 2222. So we save these numbers in tree[node][2] Update 2: tree[node][2] = tree[node][1]. Update number 3 > all 2's will be 3. 2222 > 3333. They are now divisible by 3, so we save these numbers in tree[node][0] Update 3: tree[node][0] = tree[node][2] and so on. answered 19 Apr, 07:22

Answer is hidden as author is suspended. Click here to view.
answered 19 Apr, 11:31
