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

×

PRMDIV - Editorial

Problem Link

Practice

Contest

Author: Ivan Fekete

Tester: Misha Chorniy

Editorialist: Bhuvnesh Jain

Difficulty

EASY

Prerequisites

Sieving Techniques

Problem

Let $S(x)$ denote the sum of distinct prime divisors of $x$. Find the number of pairs $(i, j)$ in array $A$ such that if $A[i]$ divides $A[j]$ then $S(A[i])$ also divides $S(A[j])$.

Explanation

Let us first calculate the function $S$ for all integers efficiently. This is a simple modification of the prime sieve where we add the contribution each prime divisor to the numbers as well.


    S[1] = 0
    for i in [2, 1000000]:
        if S[i] == 0:
            # number is prime
            j = i
            while j <= 1000000:
                S[j] += i
                j += i

The time complexity of the above approach will be $O(\sum_{p = prime} X/p) = O(X \log{\log{X}})$, where $X = 1000000$.

Let us also calculate the good pairs of numbers. Below is a pseudo-code for it:


    # good[i] stores the "j" such that
    # "i" and "S[i]" divide "j" and "S[j]" respectively.
    for i in [2, 1000000]:
        j = i
        while j <= 1000000:
            # Ensured that "i" divides "j". See the loop conditions.
            if S[j] % S[i]:
                good[i].append(j)
            j += i

The time complexity of the above approach is $O(\sum_{i=2}^{i=N} X/i) = O(X \log{X})$, where $X = 1000000$. If you have any doubts regarding the above 2 precomputations, I suggest you to learn and read Sieve of Eratosthenes and try to understand how the code is modified here.

Now, coming back to the problem. We need to find the number of pair of $(i, j)$ in array $A$ such that if $A[i]$ divides $A[j]$ then $S(A[i])$ also divides $S(A[j])$. For this, if we do it naively for every pair using the help of above pre-computation to check if $A[i]$ and $A[j]$ is good, then it will inefficient and only pass subtask 1.

The important thing to note that even if we iterate over all "good" arrays, the total size of all arrays is bounded by $O(X \log{X})$, considering all the numbers are appended. Actually, this bound is lower, but it doesn't matter.

So, let say if we have the frequency of all elements in the array $A$. When iterating over the "good" array, if $2$ numbers have frequency $x$ and $y$ then they contribute $(x * y)$ to the answer. The only caveat is that pair $(i, i)$ i.e. same pair of indices is also counted in it. So, we need to subtract $N$ from the final answer as well.

Thus, the below psuedo-code can easily solve our complete problem:


    for i in [1, n]:
        freq[a[i]] += 1
    ans = 0
    for i in [2, 1000000]:
        if freq[i] > 0:
            # Element is present
            for j in good[i]:
                ans += freq[i] * freq[j]
    # Account for i == j
    ans -= n
    print ans
    # Clear freq array for next test case.
    for i in [1, n]:
        freq[a[i]] -= 1

Once, you are clear with the above idea, you can see the editorialist implementation below for help.

Feel free to share your approach, if it was somewhat different.

Some Thoughts

There exist a linear sieve for prime numbers as well. Can you modify the first algorithm for pre-computation of $S$ to work in linear time? If yes, how? If no, what is your counter argument?

Time Complexity

$O(X \log{X} + N)$ per test case.

Space Complexity

$O(X \log{X})$

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.

Tester's solution can be found here.

Editorialist's solution can be found here.

This question is marked "community wiki".

asked 28 Jul '18, 17:31

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

edited 31 Jul '18, 18:57

aryanc403's gravatar image

5★aryanc403
2.7k1618

1

Author's solution link is wrong. It should be for the tester. Correct one is : https://ideone.com/b1dJXm

(29 Jul '18, 01:16) likecs6★

I was so close to a full AC in this one. I didn't realize we could precompute the good pairs and store them to speed up each test case. TLE on the absolute last test case :-(

(29 Jul '18, 01:31) rashomon4★

# Clear freq array for next test case.
for i in [1, n]:
    freq[a[i]] += 1

This should be freq[a[i]] -= 1. Correct it

link

answered 29 Jul '18, 02:02

deepak_d14's gravatar image

4★deepak_d14
313
accept rate: 0%

Correct. Check again.

(29 Jul '18, 02:03) likecs6★

@likecs could you please clear the linear sieve and an additional O(n) array approach?

link

answered 29 Jul '18, 12:33

titin_'s gravatar image

3★titin_
133
accept rate: 0%

Hint 2: Linear sieve stores smallest prime factor for every number. In the second loop, we will use a DP solution. Say we have computed answer till some point, how can handle transition for "x", say using the answer from "x / lp[x]" where lp[x] denotes lowest prime factor of "x"

(29 Jul '18, 13:05) likecs6★

We cannot use linear sieve for pre-computation of $S$. Because linear sieve makes sure that each n is visited by it's lower prime no. And is only visited once. But For computation of we have to visit each distinct prime factor of no. And there are atmost 6 distinct factors for nos upto 1e6.

link

answered 29 Jul '18, 01:46

aryanc403's gravatar image

5★aryanc403
2.7k1618
accept rate: 10%

@aryanc403, think you. Hint: The answer is yes and instead of using only the linear sieve, we can use an additional $O(N)$ loop again. Do you get some hint or more is required?

(29 Jul '18, 02:05) likecs6★

I am sure I did the same, but still wasn't able to pass subtask 6. Could someone provide some pointers:

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

Thanks.

link

answered 29 Jul '18, 02:01

fr4nkesti3n's gravatar image

4★fr4nkesti3n
864
accept rate: 12%

2

Overflow error. Your soln https://www.codechef.com/viewsolution/19384172 .

Changes made - pairs += a[i] * ((long long)a[k]); and pairs += a[i] * (a[i] - 1L);

E.g. - Test case T=1; n=1000000; a[i]=3; ans ~ 1e12 > INT_MAX

(29 Jul '18, 02:34) aryanc4035★

Congrats man you again proved that we should not use \% until and unless it is absolutely necessary. Your soln with removed if(a[k]) results in TLE.
https://www.codechef.com/viewsolution/19384237

With this correct my soln (which I used in contest) similar to your now passes.

(29 Jul '18, 02:40) aryanc4035★

@vijju123 I think there is some problem with counting upvotes on this answer. I upvoted but it is showing 0 upvotes. And his profile does not show any downvote. And If I un upvote this answer then it is showing -1 votes.

(29 Jul '18, 02:43) aryanc4035★

Its always stuff like this! Thanks @aryanc403, I hope this will make me remember about overflow during int arithmatic.

(29 Jul '18, 19:14) fr4nkesti3n4★

Does it EASY? :)

link

answered 29 Jul '18, 02:20

batura_dima's gravatar image

5★batura_dima
1264
accept rate: 5%

Thanks @fr4nkesti3n ,
My AC approach here - I was just trying luck along with double sieve. Hence I used a variable named $lucky$. xD. In case I get AC this is reason behind it.

Approach -

Sieve to find $S[i]$
Maintain Counter Array.
Used Map. Although Set is more appropriate then Map ;)
Brute force for $1<=a[i]<=lucky$. With $lucky<=100$ Atmost 100 iterations.
For $a[i]>lucky$. One loop for $1<=i<=lucky$ and rest sieve. Atmost 200 iterations.
But still in TL .
Unfortunately it failed on last test case. And I made 15 submissions with different values of $lucky$ with hope of getting AC.
Finally I got AC after seeing @fr4nkesti3n soln.
And bingo it resulted in A.C. Soln.
Never use % until and unless it is absolutely necessary.
I repeat Never use % until and unless it is absolutely necessary.
It can take you from $100 pts$ to $20 pts$ And you will never realise reason behind it.
He added condition if(cnt[j]) then only compute $s[j]\%s[i]$

Editorials soln can be optimised further by using set/map for outer loop. By in that case insertion complexity will be $O(logn)$ And overall complexity will be again $O(NlogN)$ .

link

answered 29 Jul '18, 04:54

aryanc403's gravatar image

5★aryanc403
2.7k1618
accept rate: 10%

@likecs in the pseudocode to calculate the final answer

for i in [2, 1000000]: if freq[a[i]] > 0: # Element is present

Should'nt it be freq[i] instead of freq[a[i]] ?

link

answered 29 Jul '18, 11:40

radon12's gravatar image

4★radon12
361
accept rate: 50%

Correct. Please check again.

(29 Jul '18, 13:02) likecs6★

Hello everyone,I m getting TLE in last test cases and i m not able to figure out the reason..please help me out.
Here is the link to my solution:- https://ideone.com/XUhDs1

link

answered 29 Jul '18, 15:14

rtrajat's gravatar image

2★rtrajat
11
accept rate: 0%

edited 29 Jul '18, 15:15

Reason is already answered. Check this page again.

(29 Jul '18, 16:47) aryanc4035★

Can someone point out what was wrong with my code (I was targeting for subtask 1) https://www.codechef.com/viewsolution/19376505

link

answered 30 Jul '18, 11:11

harbeersamra's gravatar image

4★harbeersamra
112
accept rate: 0%

1

for(int i=2;i<=sqrt(MAX);i++) => Mistake is here, this is enough to compute if a number is prime is or not but not enough to calculate S[x]. Think about counter examples.

(30 Jul '18, 23:22) tamiliit3★

After trying to understand it for 10hrs and after doing nearly 15 submissions, I am still struggling to get AC.

please check my PA Solution here and tell me what I am missing.

link

answered 30 Jul '18, 21:19

thesmartguy's gravatar image

4★thesmartguy
786
accept rate: 7%

ans += freq[i]*(freq[i] - 1) ;
ans += freq[i]*freq[good[i][j]] ;

Either use ans += 1LL*freq[i]*(freq[i] - 1) ; etc or use long long.

(30 Jul '18, 21:29) vijju123 ♦♦5★

okay got it...looks like someone already asked this question before thanks :))

(31 Jul '18, 18:52) thesmartguy4★

I tried the way as mentioned in the editorial, but am getting TLE on the 1st, 2nd and last Test Cases. I find my and ediorialist's codes almost similar but couldn't figure out why I am getting TLE. Is the O(MAX^2) complexity in every precalculation is causing TLE.

Secondly, I tried to sieve only up to the maximum element in the input array. It decreased the time of execution but all tasks gave WA.(Some still gave TLE)

My code _ TLE One

My code _ WA One

link

answered 31 Jul '18, 00:36

kshitij_07's gravatar image

4★kshitij_07
364
accept rate: 6%

https://www.codechef.com/submit/complete/19404615

Your AC code. A judicious and appropriate use of data structures is a must. Your map gave a heavy, extra $logN$ factor. Also, use arrays wherever possible.

(31 Jul '18, 01:00) vijju123 ♦♦5★

Okay, got it, Thanks :)

(31 Jul '18, 14:18) kshitij_074★

Time Complexity:- O(XlogX+N) per test case, where X=1000000
On Computing time, it is similar to 2*10^7 and there can be 100 test cases at maximum, when i am assuming N=10^4 then total time will be over >10^9 still no TLE according to editorial.. why? please SomeOne Explain where I am wrong

link

answered 31 Jul '18, 02:15

hemant_dhanuka's gravatar image

5★hemant_dhanuka
533112
accept rate: 3%

waiting for reply... plz someOne help

(31 Jul '18, 21:31) hemant_dhanuka5★

Because at any instance, only ${10}^{4}$ of the ${10}^{6}$ elements will be present in an array. This reduces time complexity. Further, if operations are basic,such as addition etc. then its easy to get ${10}^{8}-{10}^{9}$ operations done in a second.

(01 Aug '18, 12:29) vijju123 ♦♦5★

In the last section psuedo-code line no. 5 if freq[a[i]] > 0: should it not be changed to freq[i] > 0: here is the AC Code.

link

answered 31 Jul '18, 08:54

chandyshot's gravatar image

4★chandyshot
35010
accept rate: 13%

Its typo. Corrected it.

(31 Jul '18, 18:56) aryanc4035★

https://ideone.com/LskyCZ

I have been trying to solve for subtask 1 but not getting an AC. Please someone help.

link

answered 01 Aug '18, 05:39

shekhrishabh18's gravatar image

1★shekhrishabh18
1
accept rate: 0%

@likecs It will have 10^9 (approx) computations.How will it be completed in 1 sec?

link

answered 02 Aug '18, 01:02

utchinu's gravatar image

3★utchinu
01
accept rate: 0%

edited 02 Aug '18, 01:04

Can someone please explain, why the author is

ensuring that "i" divides "j" ?

when he is calculating good[i] array,

does he mean if "i" doesn't divide "j" => "s[i]" doesn't divide "s[j]" ?

link

answered 02 Aug '18, 10:18

lilvisionlil's gravatar image

4★lilvisionlil
213
accept rate: 0%

edited 02 Aug '18, 10:29

Need Help !!! Since I am a beginner I don't understand How Counting is performed to clear subtask 2. I try to do the dry run in my rough copy but was not able to solve due to the huge size of the array. Can u plz tell me where I am lacking and which concept should I study to understand this. You can also share some link.

link

answered 02 Aug '18, 19:19

osho_garg's gravatar image

2★osho_garg
737
accept rate: 4%

Can someone help me out ? I can't find reason why it still TLE Here is my code https://www.codechef.com/viewsolution/19452525 Thank you!!

link

answered 04 Aug '18, 09:46

napatnicky's gravatar image

3★napatnicky
1
accept rate: 0%

I tried implementing the solution in the editorial in Java. Its giving me TLE. Can someone please tell me why? Solution Link: https://www.codechef.com/viewsolution/19435752

link

answered 13 Aug '18, 10:10

svr8's gravatar image

2★svr8
1
accept rate: 0%

In java you can implement editorial's method like this:
https://www.codechef.com/viewsolution/19737889

(I was getting TLE if I pre-processed using Lists of Java)

link

answered 16 Aug '18, 00:42

vjvjain0's gravatar image

5★vjvjain0
91210
accept rate: 6%

edited 16 Aug '18, 01:04

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:

×15,852
×3,820
×593
×303
×81
×51

question asked: 28 Jul '18, 17:31

question was seen: 2,346 times

last updated: 16 Aug '18, 01:04