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

×

How to solve GTREE - "TREE GCD" ?

2
5

Problem Link (Contest) - https://www.codechef.com/LOCAUG17/problems/GTREE

I tried to solve the above problem from LoC AUG 2017 and wrote a brute force solution (by doing a DFS from each node in its subtree) that fetched 30 pts but couldn't come up with an approach to solve this problem completely.

Can someone explain how to solve this problem?

asked 29 Aug '17, 02:14

c_utkarsh's gravatar image

5★c_utkarsh
1.1k5
accept rate: 17%

edited 29 Aug '17, 10:16

2

I checked a few solutions and they seem to be using the Möbius function, which I don't know about. I'm reading up on it and if I am able to understand the solution I'll explain it here.

(29 Aug '17, 22:46) meooow ♦6★

I have a better approach.

The key problem is that: Given several integers, with integer $x$ appears $c_x$ times, and some fixed integer $m$. It is asked that how many integers that are co-prime to $m$, i.e. $$ \sum_{i=1}^n c_i [ \gcd (i, m) = 1 ]. $$

By Mobius inversion, we can get that $$ \sum_{i=1}^n c_i [ \gcd (i, m) = 1 ] = \sum_{d|m} \mu(d) \sum_{i=1}^{\lfloor n/d \rfloor} c_{id}. $$

Here we use some technique when we DFS the tree, for each vertex $v$, and every $val_v$'s divisor $d$, maintain $$ s(d) = \sum_{i=1}^{\lfloor n/d \rfloor} c_{id}, $$ and thus we can get $s(d)$ in $O(1)$ each time.

As above, an $O(n \max_{k} \sigma(k))$ algorithm is exhibited, where $\sigma(k)$ means the number of $k$'s divisors.

For more details, please see my code.

link

answered 09 Sep '17, 07:39

liouzhou_101's gravatar image

7★liouzhou_101 ♦♦
6822313
accept rate: 12%

edited 09 Sep '17, 21:42

1

@liouzhou_101 $s(d)$ appears to be cnt[d] in your code, but $s(d)$ is the number of times any multiple of $d$ occurs whereas cnt[d] is just the number of times $d$ appears. Am I getting something wrong?

(15 Sep '17, 20:21) meooow ♦6★

@skyhavoc

$$ \begin{aligned} & \quad \sum_{i=1}^n c_i [ \gcd(i, m) = 1 ] \\ & = \sum_{i=1}^n c_i \epsilon(\gcd(i, m)) \\ & = \sum_{i=1}^n c_i \sum_{d|\gcd(i, m)} \mu(d) \\ & = \sum_{i=1}^n c_i \sum_{d|m} \mu(d) [d|i] \\ & = \sum_{d|m} \mu(d) \sum_{i=1}^n c_i [d|i] \\ & = \sum_{d|m} \mu(d) \sum_{i=1}^{\lfloor n/d \rfloor} c_{id} \\ \end{aligned} $$

link

answered 15 Sep '17, 08:39

liouzhou_101's gravatar image

7★liouzhou_101 ♦♦
6822313
accept rate: 12%

@liouzhou_101 How did you convert

∑d|mμ(d)∑i=1⌊n/d⌋cid

I have already this and this but not able to figure out how you converted to mobius inversion. Can you please explain that formula

link

answered 15 Sep '17, 00:11

skyhavoc's gravatar image

4★skyhavoc
1616
accept rate: 0%

edited 15 Sep '17, 00:28

@meooow

cnt[d] is to calculate the number of times any multiples of $d$ occurs, however, it is not that itself. In my code:

void dfs(int x, int pre) { size[x] = 1; ans[x] = 0; for (auto d : divisor[a[x]]) { ++ cnt[d]; ans[x] -= u[d]*cnt[d]; } for (auto y : v[x]) { if (y == pre) continue; dfs(y, x); size[x] += size[y]; } for (auto d : divisor[a[x]]) ans[x] += u[d]*cnt[d]; ans[x] = size[x]-1-ans[x]; }

Note that ans[x] = ∑ u[d]*( (cnt[d] after dfs the subtree of x) - (cnt[d] before dfs the subtree of x) ), which implies that ( (cnt[d] after dfs the subtree of x) - (cnt[d] before dfs the subtree of x) ) is to calculate s(d).

Note that when we run dfs(x, pre), before looping "for (auto y : v[x])", for each a[x]'s divisor d, what we do is "cnt[d] ++". And the difference of cnt[d] before and after the loop is exactly what we want to calculate, i.e. s(d). If still confused, think of the DFS order of a tree and implement it by hand in order to understand what the procedure exactly does.

link

answered 16 Sep '17, 09:38

liouzhou_101's gravatar image

7★liouzhou_101 ♦♦
6822313
accept rate: 12%

edited 16 Sep '17, 09:40

1

I did understand why you were subtracting first and adding up after the children were visited, because of the DFS order, but I guess I didn't fully grasp what was happening. I thought about it a bit more and it's clear to me now, thanks!

(16 Sep '17, 13:28) meooow ♦6★

I didnt give any submissions on the problem... but I can write what i think is a correct solution.

So, first... flatten the tree into an array. So now the problem is to solve range queries where each query returns the number of non co-prime numbers. First, compress the numbers so that they contain its prime factors only once. for example, 72 = 2 * 2 * 2 * 3 * 3

Write it as 2 * 3 -- meaning that every unique prime factor is taken only once. So you can easily show that a number will contain at most 6 factors in this form. for that just take the product of the first 7 unique prime numbers and that will exceed 1e5, the max size of the number.

Now, maintain list of all the possible factors and their multiples that are present. Now this may seem to be N^2 as you are maintaining 1e5 sized array of vectors, but each number can have atmost 2^6 factors, so in all there can be at most 2^6 * N elements.

Now given a range, basically do a principle of inclusion and exclusion type thing, and binary search for the numbers present in the range, using the aforementioned lists that have been made. The whole factorization can be done in NlogN time using the smallest prime factor seiving technique, and the overall complexity should be about 2^6 * log^2 N per query approx.( this may be actually logN, i forgot :p ). This should work within the given time limit.

I hope this was a correct solution.

link

answered 29 Aug '17, 17:28

rajarshi_basu's gravatar image

6★rajarshi_basu
6288
accept rate: 10%

i had similar idea but stuck at the inclusion and exclusion thing..(:

(29 Aug '17, 21:42) srikanth_161★

@rajashri_basu can you please explain the last paragraph a little more?

link

answered 29 Aug '17, 22:40

pk301's gravatar image

2★pk301
62710
accept rate: 16%

How do we apply binary search in your last part , like what is the property that is monotonic here , I understood the property of inclusion and exclusion like suppose if our curr_subtree node has {2,3,5} as it's unique prime divisor's then we will use inclusion and exclusion principle to find like how many numbers are divisible in that range by atleast one of the numbers from our given list like we will find how_many_divisible_by(2)+how_many_divisible_by(3)+how_many_divisible_by(5)-how_many_divisible_by(2 3)-how_many_divisible_by(2 5)-how_many_divisible_by(3 5)+how_many_divisible_by(2 3* 5) in that range and u are saying that we can find the value of a how_many_divisible_by(x) by using binary search in that range but i don't understand how to apply binary search .

link

answered 05 Sep '17, 23:14

stringray's gravatar image

4★stringray
11
accept rate: 0%

edited 05 Sep '17, 23:18

There are do not need array and binary search. Simple dfs and use array with number of multiples present in upper nodes.

link

answered 08 Sep '17, 20:20

batura_dima's gravatar image

5★batura_dima
1264
accept rate: 5%

@liouzhou_101 ♦♦ Can you explain how you converted the problem to: "Given several integers, with integer x appears cx times, and some fixed integer m. It is asked that how many integers that are co-prime to m"

link

answered 09 Sep '17, 16:26

taraprasad73's gravatar image

4★taraprasad73
0
accept rate: 0%

@taraprasad73

For every vertex $x$ in the tree, it is asked that how many vertices $y$ in the subtree of $x$ such that $\gcd (val_y, val_x) > 1$.

It can be converted to that how many vertices $y$ in the subtree of $x$ such that $\gcd (val_y, val_x) = 1$ (The original problem's complement.), where $val_x$ is the $m$, and $val_y$ are the integers $x$.

link

answered 09 Sep '17, 21:41

liouzhou_101's gravatar image

7★liouzhou_101 ♦♦
6822313
accept rate: 12%

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:

×2,738
×2,657
×711
×321
×65

question asked: 29 Aug '17, 02:14

question was seen: 1,545 times

last updated: 16 Sep '17, 13:28