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

×

GCDCNT - Editorial

1
3

PROBLEM LINK:

Contest
Practice

Author: Vipul Sharma
Tester: Triveni Mahatha
Editorialist: Adarsh Kumar

DIFFICULTY:

Medium

PREREQUISITES:

Inclusion exclusion, Ordered Set

PROBLEM:

You are given an array with $N$ elements. You need to support two types of operations on this array. First one is point update. For the second operation, you will be given query range $l,r$ and an another number $G$ as input, you need to find number of elements that are co-prime to $G$ in the given range.

EXPLANATION:

Let's try to find the number of integers co-prime to $G$ in the given query range, represented by $ANS(G,L,R)$. Say,

$G = p_1^{a_1} . p_2^{a_2} . ..... p_q^{a_q}$

We will be using inclusion-exclusion principle to find the required expression. Lets represent number of integers divisible by $x$ from the range $L,R$ as $F(x,L,R)$. Then, we can write:

$$ANS(G,L,R) = F(1,L,R) - \sum \limits_{i=1}^q F(p_i,L,R) \\ + \sum \limits_{i=1}^q \sum \limits_{j=i+1}^q F(p_i.p_j,L,R) \\ - (\text{3 at a time}) \\ + (\text{4 at a time}) \\ - ... + (-1)^q.F(\prod \limits_{i=1}^q p_i,L,R) $$

Number of terms in expansion of $ANS(G,L,R)$ is $2^q$, where $q$ is number of distinct prime factors of $G$. Also, notice that first argument to function $F$ is always a square free divisor of $G$. If we can answer $F(x,L,R)$ in logarithmic complexity, we can have a solution that will work in $O(2^q.logN)$ for each query.

We will maintain an ordered set for each of the number $1 \le x \le 10^5$. For all $A[i]$ $(1 \le i \le N)$, we will iterate over its square free divisors and insert this index $i$ in the ordered set of corresponding divisors. Since, a number upto $10^5$ can have at-max 64 square free divisors, this will take a time of $O(K.N.logN)$ where $K=64$. You can answer $F(x,L,R)$ in $O(logN)$ time by querying over ordered set corresponding to $x$. We can also support the update in similar fashion. Say, current update operation is to change $A[x]$ to $y$. First, we will iterate over square free divisors of $A[x]$ and erase index $x$ from the ordered set of corresponding divisors. Then, we will iterate over square free divisors of $y$ and insert index $x$ into the ordered set of corresponding divisors. Finally, make $A[x]=y$.

ALTERNATE SOLUTION

This solution requires knowledge of mobius inversion. You can refer to some of these awesome links(L1, L2), in case you are not familiar with the same. Lets represent unit function by $e(n)$. Then, we can write:

$$ANS(G,L,R) = \sum \limits_{i=L}^R e(gcd(G,A[i]))$$ $$\Rightarrow ANS(G,L,R) = \sum \limits_{i=L}^R \text{ } \sum \limits_{d|G,d|A[i]} \mu (d)$$ $$\Rightarrow ANS(G,L,R) = \sum \limits_{d|G} \mu (d).F(d,L,R)$$$

Notice that above formula is same as the one which is derived using inclusion-exclusion principle. Another informal way of looking at this is, mobius function is the sign in the inclusion-exclusion principle.

Later part of the problem can be solved in similar fashion as above. There can be many different approach for this part too. Feel free to discuss them in comments if you find them interesting.

Time Complexity:

$O((Q+N).K.logN)$

AUTHOR'S AND TESTER'S SOLUTIONS

Setter's solution
Tester's solution

This question is marked "community wiki".

asked 06 Mar, 15:15

adkroxx's gravatar image

7★adkroxx
306718
accept rate: 7%

edited 13 Mar, 15:05

admin's gravatar image

0★admin ♦♦
19.0k348495531

setter's solution is showing 'Access Denied' please fix it.

(12 Mar, 21:01) pk3011★

Great question but it was totally similar to the one in codeforces discussion which result in so many AC's. http://codeforces.com/blog/entry/54419

See this link here everything was explained how to get AC including link to policy based data structures.

(13 Mar, 16:59) rj254★

how to find F(x,L,R) in O(logN) time by querying over ordered set corresponding to x ? If I am using ordered_map , I can get iterator corresponding to L and R in O(logN) . But getting their difference will take linear time .

(16 Mar, 10:29) animeshp_19934★

12next »

I have used the fact that any number <=1e5 can have at most 6 prime divisors.

I have found out all prime numbers <=1e5 (~10000) using sieve, used a Java BitSet array to mask each prime number. Each array element has its respective array index position marked in their respective prime divisor BitSet.

For example, if the 3rd element has prime factors (2, 5 & 13), the 3rd index of the BitSet at index (0, 2, 5) are marked true [1st prime = 2, 6th prime = 13].

For update it takes at most 12 operations - unmark existing marked positions (6 operations), mark new positions (another 6). The prime factor decomposition takes hardly log n time.

For query operation, the input 'g' is prime factorised (log n time operation), and the corresponding BitSets are 'or'ed. From the resulting BitSet the required range is extracted and then some easy calculations follow...

To be honest, I did not expect Java BitSet to be so efficient and fast. I tried segment trees with BitSet, but got TLE. Suddenly this algo clicked in my mind and I got an AC in a single shot... :)

My solution: https://www.codechef.com/viewsolution/17593545

link

answered 17 Mar, 23:42

sarthakmanna's gravatar image

5★sarthakmanna
606112
accept rate: 39%

edited 23 Mar, 21:08

nice approach sir :) +1

(23 Mar, 01:10) sumitjha43213★

I am still a student. Anyway, thanks @sumitjha4321

And thanks @teruel98 for pointing out the error.

(23 Mar, 21:18) sarthakmanna5★

For calculating F(x,L,R) we can use sqrt decomposition also. Complexity would be $O(n*sqrt(n)*64)$

link

answered 12 Mar, 16:23

mathecodician's gravatar image

5★mathecodician
2.6k629
accept rate: 7%

can you please explain your approach.

(12 Mar, 21:05) pk3011★

Great Question on Mobius! I have used sqrt decompostion for calculating F(x,L,R). If anyone used segment trees,do explain!

link

answered 12 Mar, 21:34

ripulvohra8's gravatar image

5★ripulvohra8
1
accept rate: 0%

I used dynamic segment trees, here's my code https://www.codechef.com/viewsolution/17818958. Though this is really overkill! :D

(12 Mar, 21:43) dhruvsomani4★

Hello Community, Can anyone please help me optimize my solution....I am getting TLE in a single Test Case...code
I tried a lot but couldn't convert single TLE test case to AC.

link

answered 12 Mar, 23:45

vivek_shah98's gravatar image

5★vivek_shah98
203
accept rate: 0%

@vivek_shah98

I tried to solve it using map, but map is too slow, even unordered map, because of rehashing or other overheads. I tried for several days using map, no result. Use an array for O(1) look up and use square root decomposition.

(13 Mar, 09:01) nilmadhab15★
2

Hello Community, I would like to share something with you all....I had been using vector<unordered_map<int,int> > bit; for my fenwick tree...And probably I had made more than 30 submissions since yesterday...But I was getting TLE in single Test Case (code in above comment)...Then I used Hash Map from Mike Mirzayanov's github repo... https://github.com/MikeMirzayanov/open_addressing_hash_table Not only was it time efficient but also memory efficient and It passed with 0.44s with suprise memory usage of just 18.2 MB. Here is my code: https://www.codechef.com/viewsolution/17821553

(13 Mar, 10:16) vivek_shah985★

I used AVL trees for this. Explanation is given in this solution:

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

link

answered 13 Mar, 00:10

avcbcoder's gravatar image

5★avcbcoder
1
accept rate: 0%

Dynamic Segment Trees Solution :D

Here is the link
https://www.codechef.com/viewsolution/17813833

link

answered 13 Mar, 00:12

coolreshab's gravatar image

5★coolreshab
1
accept rate: 0%

Could u explain your solution?

(13 Mar, 03:39) beginner_11113★

I have used inclusion and exclusion that uses frequency of the factor of G between L to R. Since maximum value in an array can be 10^5 so we will be building 10^5 segment trees where segment tree i can tell u the frequency of a no i between L and R. Of course this will lead to MLE.

(13 Mar, 23:08) coolreshab5★

So we can use dynamic segment trees to solve this problem HOW? For each factor x among 2^6 factors(in worst case) of A[i] we will update segment tree x on its ith index.And this can be done by allocating log2(50000) nodes in the worst case and during this process if the node is already created we will be using it else create a new one.

(13 Mar, 23:08) coolreshab5★

In worst case there are a total of 2*50000 nos (including updates) that will be needing 10^5 * 2^6 * log2(50000) = 99901699 nodes that is well within the Memory Limit.

We have solved the problem in O( 2^6 * Q * log2(N) ) time and O( 9*10^7 ) memory

(13 Mar, 23:09) coolreshab5★

My Square root decomposition solution. Some observations, as N=50,000, so square root (N) = 225 (approx) So No. of blocks = Block Size = 225 In each block, I am storing all the frequencies of square free divisors, by an array of size 100,000

Total space used = 225100,000 = 2.2510^7. This much memory can be allocated easily, by declaring a global 2D array.

Lets see query and Update Time

Update takes O(1) i.e constant time because you have to remove frequencies of old number and add frequencies of new number.

For example, suppose the earlier number of 10 and it is updated to 30.

10--> [ 2, 5, 10] remove freq of these numbers by 1

30-->[ 2, 3, 5, 6, 15, 10, 30] add freq of these numbers by 1.

If anyone has doubt about square free divisor please feel free to ask.

Now go come back to query

We find all square free divisor of G, maximum 64 numbers. Search all the blocks which contain L, R for these divisors.

Complexity: O(sqrt(N)*64)

Total complexity of queries O(Nsqrt(N)64) ~ 10^7.

My first question of Square root decomposition, it was great when I got all ACs.

Here is link to my solution

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

I tried to solve it by Map, unordered_map and segment tree. Took me 75 TLES to solve but at the end, it was worth it.

link

answered 13 Mar, 08:53

nilmadhab1's gravatar image

5★nilmadhab1
112
accept rate: 0%

edited 13 Mar, 08:54

@nilmadhab1 what is square free divisor?

(14 Mar, 13:57) beginner_11113★

I used policy based data structure in c++.. and i think that will do in logn.... link to my soln is... https://www.codechef.com/viewsolution/17764565 ask any questions if u want....

link

answered 13 Mar, 10:43

l_returns's gravatar image

3★l_returns
77018
accept rate: 27%

edited 13 Mar, 10:49

@l_returns i also used the policy-based data structure still, i keep getting WA. Can you please help me out?

code

link

answered 14 Mar, 19:30

helloman's gravatar image

4★helloman
1
accept rate: 0%

@sarthakmanna: I think that number of different divisors is actually 6, for number: 30030 = 235711*13

link

answered 19 Mar, 19:36

teruel98's gravatar image

3★teruel98
11
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,396
×264
×44
×24
×20

question asked: 06 Mar, 15:15

question was seen: 4,523 times

last updated: 23 Mar, 21:19