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

×

Editorial for O2CTST03

Sandeep and his Magical buckets

If a query is of type 0,we need to calculate (A[i] + 1) mod 4 and if the query is of type 1,we need to perform

    giant += A[i]
    A[i] = 0

but the most difficult part about the question is its constraints. The number of queries is 10^7 and 1 <= index <= 10^9 under the time limit of 2.5s. So we need to find some way to handle the queries such that complexity of each operation is better than O(logn) but can be a little above O(1).

Here comes the power of C++ bit arrays,we can use a vector<bool> (10^9,0) and can work on it. But again the thing is that a bool can contain only 2 data either 0 or 1,then how we will store 2 and 3. If we will take short int then again the memory limit of the program will exhaust and moreover initialising a vector<short int=""> (10^9,0) will also take considerable amount of time as each entry here is 1 bytes(8 bits). So the best thing to do here is to use multiple(In this case,3) vector<bool> arrays say A,B,C... If for an index i,A is set we conclude that count is atleast 1,and then check for B,if it is also set we conclude that count is atleast 2 and similarily for C.

Thus the Possible combinations for A,B and C can be

    0 0 0
    1 0 0       indicates count as 1
    1 1 0           indicates count as 2
    1 1 1       indicates count as 3

Thus we have managed a way to keep track of the count of each index, Now a query of type 1 can be easily handled by adding the count of that index into the giant bucket and then setting each bucket(A,B,C) to 0.

asked 18 Oct '16, 03:00

diptanshu's gravatar image

4★diptanshu
4
accept rate: 0%


link
This answer is marked "community wiki".

answered 20 Oct '16, 23:36

vinayaksangar's gravatar image

3★vinayaksangar
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:

×1,404
×278
×39

question asked: 18 Oct '16, 03:00

question was seen: 562 times

last updated: 20 Oct '16, 23:36