CHEFD - Editorial

bit
editorial
ltime16
medium
sets

#1

Problem link:

[contest][1]
[practice][2]

Difficulty :

Medium

Pre-requisites :

Binary Indexed Tree or Sets in C++[Balanced Binary Search Trees]

Problem:

You are given an array of N integers. You have to make M queries. Each query has one of the two types:

  • (1, l, r, p) - choose all numbers with indexes between l to r. Divide all numbers by p, that are divisible by p.
  • (2, l, d) - assign l-th number in array to d

Also p is in [ 2 3 5]

Explanation

Let us assume that we have a data structure which can give us the next number divisible by p in the range [l r] in O(t) time, t is what we will find out later.

Can you give an estimate of total amortised cost on the total time complexity using the above data structure ?

If we forget that there is any query of type 2, then what will be the total amortised cost ?
As each number is less than 109, in the worst case a number can be divided by p by at most 30 times (when p is 2 and number is 109).
So total time complexity would be O(t) * 30 * N

Now Let us add queries of type 2.
Each number which is replaced will require at most 30 steps to reach 1. So at most M numbers are added.
So total time complexity is O(t) * 30 * (M + N) + Time required to change the data structure for query 2.

Now, if t = O(log N), then we are done.

The Data Structure

We will make 3 balanced binary search trees [ one for p = 2, other for p=3 and the last one for p=5 ].
Balanced Binary search trees to keep numbers in the sorted is implemented in C++ as [“set”][5] and in Java as HashSet or TreeSet.

In our set , we will keep index of the numbers which are divisible by p.

Let us solve for p = 2, rest primes are analogous to this case.

Query of First Type : l r p
Find in the balanced binary search tree [i.e. set ] for index which is just greater than or equal to l and less than or equal to r. Divide the number on that index with p.
If after division it is no longer divisible by p then remove that index from the binary search tree and proceed to find another index which is greater than this index and less than or equal to r. We will continue this again and again till it terminates.

Query of Second Type : l d
We first remove index l from all 3 set if it is present in them.
Then we’ll add index l in the set if d is divisible by p.

Pseudo Code


//Declaring the Data Structure
set myset[6]

//Building the Data Structure
for(int i=1;i<=N;i++)
Read( arr* )
if( arr*%2 == 0 ) myset[ 2 ].insert(i);
if( arr*%3 == 0 ) myset[ 3 ].insert(i);
if(arr*%5 == 0 ) myset[ 5 ].insert(i);

//Report Query
scanf("%d%d%d",&l,&r,&p); //taking the input.
a = lower_bound(myset[p].begin(),myset[p].end(),l);//finding the first index
vector del; //to store the index which are needed to be deleted
for(set::iterator it = a;it!=myset[p].end();it++) //iterating the set from the found index
if( *it > r) break; //breaking the loop when you encounter index greater than r
arr[*it]/=p; //dividing the number by p
if ( arr[*it] %p )
del.push_back(*it); //if number is no more divisible by p, then we need to remove this from the set
for(vector::iterator it = del.begin();it!=del.end();it++)
myset[p].erase(*it); //deleting the numbers


//Update Query
scanf("%d%d",&l,&d);
//Delete them if already in set.
if( arr[l] %2 == 0 ) myset[ 2 ].erase(l);
if( arr[l] %3 == 0 ) myset[ 3 ].erase(l);
if( arr[l] %5 == 0 ) myset[ 5 ].erase(l);
//Add them
if ( d%2 == 0 ) myset[ 2 ].insert(l);
if ( d%3 == 0 ) myset[ 3 ].insert(l);
if ( d%5 == 0 ) myset[ 5 ].insert(l);
arr[l] = d;

Other Data Structure

We can use Binary Indexed trees to solve this problem.
We will make 3 binary indexed trees[p=2 ,3 and 5] of size N . We will keep 1 at index i if number in that index is divisible by p.

Updating in Binary Indexed Tree
If a[l] is divisible by p=2 , then we will add -1 in Binary Indexed tree for p=2.
If d is divisible by 2 , we will add +1 in Binary Indexed tree for p=2.
We will do it similarly for other Binary Indexed Tree.

Reporting in Binary Indexed Tree
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. We will keep track of the numbers which are no more divisible by p. We will add -1 there at the end.

Thus Overall time complexity of querying from both the structure is O(log N)

Subtask

subtask 1:
Brute Force algorithm will pass.

Subtask 2:
Find for all index , number of times it is divided by p= [2 3 5] .
How can this be done ?

Maintain 3 arrays for the counter and as soon as a Divide query comes for prime p, you can simply do Add 1 at position l and -1 to Position r+1 in array made for prime p.
After all queries, find prefix sum of all 3 arrays.

This will give you the power of p which is proposed to be divided for each index.

Some Important Links to Read

[Sets in Cplusplus][5]
[Binary Indexed Tree in Topcoder][6]
[Binary Indexed Tree in Editorialist’s blog][7]

Setter and Tester Solutions:

[setter][3]
[tester][4]
[1]: http://www.codechef.com/LTIME16/problems/CHEFD
[2]: http://www.codechef.com/problems/CHEFD
[3]: http://www.codechef.com/download/Solutions/LTIME16/Setter/CHEFD.cpp
[4]: http://www.codechef.com/download/Solutions/LTIME16/Tester/CHEFD.cpp
[5]: http://www.cplusplus.com/reference/set/set/
[7]: http://bitdevu.blogspot.in/
[6]: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees


#2

Segment Trees with lazy update were also possible for 100p. ( http://www.codechef.com/viewsolution/4919355 )


#3

Well I also used segment tree but I wouldn’t call it lazy propagation.I just stored the count of each primes i.e no of times all the numbers are to be divided by a particular prime,if they are divisible.
My solution : http://www.codechef.com/viewsolution/4916671


#4

This problem can also be done by sqrt decomposition.


#5

I used almost the same approach but got WA throughout the contest. I found the bug in the last few minutes which was that “a single number can be present in more than one set”.

In the pseudo code above, the author is taking care of this situation while reading the input, and in update query, but I cannot see it in “report query”.

And while posting my doubt here, I was trying to give examples of such number (ex- 30, 10) but then I realized that we don’t need this check there! :smiley:

Hence, I got the answer while posting the question itself… :slight_smile:


#6

I have followed the same algorithm as described above. I have used set in c++.

But I am getting WA.

Kindly advise me where i am going wrong?

Thank you.

Code Link : http://ideone.com/NIa8Ai


#7

@kshitij94

check out:
http://www.codechef.com/viewsolution/5033745


#8

@neo1tech9_7 can u please explain me your sqrt root decomposition solution ?


#9

only a lazy tree serves the purpose … :slight_smile:

https://www.codechef.com/viewsolution/15011370


#10

i just used segment tree without lazy updates and it passed. not that data is weak or something, but there is a 100 point soln without lazy prop too


#11

I just thought that this solution was also worth mentioning.


#12

@alexvaleanu, can you please explain what to store in a node? I am not clear how can we perform the operation of dividing only the the elements which are divisible by p.


#13

Check my solution : http://www.codechef.com/viewsolution/4919355