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

×

[closed] Need help understanding editorial

Problem link
Editorial

I need help with BIT version of the solution. I get it how update is done. But divide part is causing problem for me.

We will find the sum of the values stored till l-1 for Binary Indexed tree of p. We will find the index of the next value which is just greater than the sum found. We will divide that index of the array by p. We will update our sum to this new sum. We will continue to do this till our index just exceeds r.

Here are my doubts : (consider the BIT storing index divisible by 2)

1) Finding sum upto l-1. Isn't it the number of elements in array divisible by 2 occurring before l-1 (inclusive)? If so, what is the purpose of it?

2) How is the next index greater than present sum found? If we search each and every elements won't it be linear?

3) Is the approach by tester and setter different than the one described in the editorial?

4) At the end there is another approach that uses prefix sum to find number of times a given element will be divisible by p. Won't this affect the updation query? I mean suppose at index i value in array is 50. Let's say there are 3 division operations for this index. Then let the value changes to 16. If we compute the division at the end, (after finding the prefix sum), there are three divisions for 50, not 16. Dividing 16 by 2 three times will result in incorrect answer. How is this problem handled?

asked 21 Aug '15, 16:02

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

closed 22 Aug '15, 09:09

The question has been closed for the following reason "The question is answered, right answer was accepted" by dragonemperor 22 Aug '15, 09:09


I don't understand it either, but I can tell you how I solved it using a BIT. Frankly I don't even see if thats the solution proposed by the editorial.

With 3 BITs you keep track on how often you have to divide the number in the array by 2,3 and 5. The division doesn't happen till after all queries.
How to handle the two types of queries:

  1. 1 l r p add 1 at position l in the corresponding BIT and add -1 at r+1 (if $r\lt n$)
  2. 2 l d update the array a at position l. For the BIT: The fresh number doesn't need to be divided. So get the current value at position l and subtract it from position l. To get the correct values for higher positions add the value to position l+1 (if $l\lt n$).

After the queries the BITs contain exactly how often each number has to be divided. So divide until you reach this limit or the number is not divisible any more.

My code.

link

answered 22 Aug '15, 04:56

ceilks's gravatar image

7★ceilks
1.8k9
accept rate: 36%

Thank you bro. I tried your method (before seeing your solution :) ) and got AC with 100 points. Then I saw your approach and learned how to do it in C++.

Thank you for your help

My code

(22 Aug '15, 09:08) dragonemperor3★

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:

×371

question asked: 21 Aug '15, 16:02

question was seen: 367 times

last updated: 22 Aug '15, 09:09