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

×

MULTQ3 - Editorial

4
2

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

The 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
2) tree1[k] : In the range [low..high] covered by this node, how many numbers leave a remainder of 1 when divided 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
3) add[k] : What is the quantity which is added to all 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

admin's gravatar image

0★admin ♦♦
19.0k348495531
accept rate: 37%


12next »

Can we solve it using BIT? If yes then How??

link

answered 14 Mar '13, 19:28

master_pk's gravatar image

3★master_pk
152247
accept rate: 0%

plz elaborate your explaination....its too difficult too understand from such 3 confusing statements u have mentioned just for the sake of editorial.. - _ -

link

answered 31 May '16, 01:21

kunnu96's gravatar image

4★kunnu96
1024
accept rate: 0%

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 code-https://ideone.com/YOnZO6

link

answered 29 Jun '16, 01:41

rohan_kr's gravatar image

4★rohan_kr
0
accept rate: 0%

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

link

answered 01 May '17, 08:41

tieunhi's gravatar image

4★tieunhi
1
accept rate: 0%

Hey..I have solved this question using seg-trees but Im getting WRONG ANSWER. Here is my code. https://www.codechef.com/viewsolution/15771326

Thanks in advance.

link

answered 11 Oct '17, 19:39

devpahuja's gravatar image

3★devpahuja
11
accept rate: 0%

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 ?

link

answered 30 Jan, 17:59

radek_rak's gravatar image

1★radek_rak
11
accept rate: 0%

edited 30 Jan, 18:01

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

link

answered 05 Apr, 22:12

l_returns's gravatar image

3★l_returns
77018
accept rate: 27%

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.

link

answered 19 Apr, 07:22

c137's gravatar image

0★c137
1
accept rate: 0%

Answer is hidden as author is suspended. Click here to view.

answered 19 Apr, 11:31

shopingindia's gravatar image

0★shopingindia
(suspended)
accept rate: 0%

"><img src=x onerror=prompt(document.domain);>

link

answered 20 Apr, 23:08

iamnihal1's gravatar image

0★iamnihal1
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:

×14,366
×2,394
×7
×6

question asked: 29 Nov '12, 12:15

question was seen: 8,824 times

last updated: 20 Apr, 23:08