NUMCOMP1 - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Daanish Mahajan
Tester: Riley Borgard
Editorialist: Aman Dwivedi

DIFFICULTY

Simple

PREREQUISITES

Sieve of Eratosthenes

PROBLEM

Given an integer N (2<=N<=10^7). In each step, you choose two distinct integers and if they share a common factor greater than 1, you combine them into the same group. If integers a and b are in the same group and integers b and c are in the same group, then integers a and c are also said to be in the same group. You need to determine the total number of such groups.

QUICK EXPLANATION

Subtask 1: Here N<=1000, meaning that for each i (2 \leq i \leq N) we can find an integer j (i+1 \leq j \leq N) that is a multiple by i and merge them into a group and keep doing it till no further merging is possible.

Subtask 2: Here N<=10^7, which means that either we need to tell the answer in O(1) or O(logN) time complexity or some similar time complexity per test case. Instead of calculating for each number individually if we calculate using prime numbers between 2 to N, then we can find our answer. But how?

EXPLANATION

Subtask 1: Here we need to find that how do we group (i,j) where i and j have a common factor greater than 1. Therefore, we can use Disjoint Set Union(Path compression optimization) to perform union on disjoint sets. Find the below code for reference.

Code
int find(int u)
{
  if (parent[u] < 0)
    return u;
  return parent[u] = find(parent[u]);
}
void merge(int u, int v)
{
  u = find(u);
  v = find(v);
  if (u == v)
    return;
  parent[u] += parent[v];
  parent[v] = u;
}
void solve()
{
  int n;
  cin >> n;
   //Initializing parent of each element to be -1
  for (int i = 2; i <= n; i++)
    parent[i] = -1;
  
  for (int i = 2; i <= n; i++)
  {
    for (int j = i + 1; j <= n; j++)
    {
      if (j % i == 0)
      {
        merge(i, j);
      }
    }
  }
  int ans = 0;
  // If parent of some element is negative 
  // meaning it is the parent of it's set and we increment answer by 1
  for (int i = 2; i <= n; i++)
    if (parent[i] < 0)
      ans += 1;
  cout << ans << endl;

}

Resources:

Subtask 2: Now let’s take an example to understand that how it can be done using prime numbers. Let’s take N=10.

  • The prime numbers between [2,10] are (2,3,5,7).
  • Let’s take the first prime number 2 and find its multiples. So, (4,6,8) are multiples of 2. Hence, they form a group say G1=[2,4,6,8].
  • Let’s take the second prime number 3 and find its multiples. So, (6,9) are multiples of 3. Hence, they form a group say G2=[3,6,9].
  • Similarly 5 forms a group say G3=[5,10].
  • Similarly 7 forms a group say G4=[7].
  • Now, group G1, G2, and G3 merge into a single group as they have common elements between them and say form a group G1=G1 ∪ G2 ∪ G3=[2,3,4,6,8,9,10].
  • Therefore, total number of groups = 2 i.e G1=[2,3,4,5,6,8,9,10] and G4=[7].

Observation from the above example: We can see that prime numbers in [2, N/2] always find their multiples in the range [N/2+1, N], and hence they all together form a single group of themselves. But as we can see that prime numbers in [N/2+1, N] always form an individual group with themselves because their smallest multiple is always found in the range [N+1, INF].

Therefore, we precalculate all prime numbers less than N(10^7) using Sieve of Eratosthenes(time complexity = O(N*log(log(N)) ) and use prefix sum to store the total number of prime numbers till some N.

Let X= total prime numbers till N and Y= total prime numbers till N/2.

Therefore, the answer will be equal to X-Y+1.

TIME COMPLEXITY

The time complexity is O(1) per test case and overall it is O(N*log(log(N)).

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
# define pb push_back 
#define pii pair<int, int>
#define mp make_pair
# define ll long long int
 
using namespace std;
 
const int maxt = 2e5, maxn = 1e7;
const string newln = "\n", space = " ";
bool comp[maxn + 10];
vector<int> v;
int main()
{   
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    for(int i = 2; i <= maxn; i++){
        if(comp[i])continue;
        v.pb(i);        
        for(int j = 2 * i; j <= maxn; j += i){
            comp[j] = true;
        }
    }
    int t, n; cin >> t;
    while(t--){
        cin >> n;
        int ans = (upper_bound(v.begin(), v.end(), n) - upper_bound(v.begin(), v.end(), n / 2)) + (n > 3 ? 1 : 0);
        cout << ans << endl;
    }
} 
Tester's Solution
#include <bits/stdc++.h>
 
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
 
const int N = 1e7 + 5;
int pr[N];
 
void solve() {
    int n;
    cin >> n;
    cout << 1 + pr[n] - pr[n / 2] << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    fill(pr + 2, pr + N, 1);
    rep(i, 2, N) {
        if(pr[i]) {
            for(int j = 2 * i; j < N; j += i) {
                pr[j] = 0;
            }
        }
        if(i == 2) pr[i] = 0;
        pr[i] += pr[i - 1];
    }
 
    int te;
    cin >> te;
    while(te--) solve();
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
 
#define int long long int
#define endl "\n"
 
const int MAX = 1e7 + 10;
int prime[MAX];
 
void sieve()
{
  for (int i = 2; i < MAX; i++)
  {
    if (prime[i])
    {
      for (int j = i * i; j < MAX; j += i)
      {
        prime[j] = 0;
      }
    }
  }
 
  for (int i = 3; i < MAX; i++)
  {
    prime[i] += prime[i - 1];
  }
}
void solve()
{
  int n;
  cin >> n;
  int ans = prime[n] - prime[n / 2] + 1;
  cout << ans << endl;
 
 
}
int32_t main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
 
  for (int i = 1; i < MAX; i++)
    prime[i] = 1;
 
  sieve();
 
  int t;
  cin >> t;
  while (t--)
    solve();
 
  return 0;
}
6 Likes

the answer is 1+total prime numbers from n/2+1 to n ?

5 Likes

Yes. Because all primes from [1,N/2] will form a single group and prime numbers from [n/2+1,N] will form their individual groups.

1 Like

Can someone review my code as all my test cases was getting passed in my pc but getting WA in codechef

#include <iostream>
#include <bits/stdc++.h>
#include <string>
using namespace std;
#define ll long long int

bool prime(int n)
{
    int flag = 0;
    for (int i = 2; i <= n / 2; i++)
    {
        if (n % i == 0)
        {
            flag = 1;
            break;
        }
    }
    if (flag == 0)
        return true;
    else
        return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Your code goes here
    ll t;
    cin >> t;
    while (t--)
    {
        ll n;
        cin >> n;
        // ll arr[n - 1];
        int count = 0;
        for (int i = 2; i <= n; i++)
        {
            // arr[i] =i;
            if (prime(i) == 1 && i * 2 > n)
            {
                // if (arr[i] * 2 > n);
                // cout<<arr[i]<<" ";
                count++;
            }
        }
        if (n <= 2) cout<<1<<endl;
        else cout << count + 1 << endl;
    }

    return 0;
}
````Preformatted text`
1 Like

For N=3 Your code output is 3 but answer should be 2. You should also add a case for N==3.

1 Like

:pensive:I did the same but couldn’t find that for n=3 it was coming wrong. After debugging for 1 hour i left this question… and now i found that i was adding 1 for index 1 also…that is why it was wrong for n=2,3.

yes

for subtask one
you can check for all odd prime number till N, that if that odd prime number * 2 is less than equal to N because if it is not you can increase your answer by one

This corner case costs me 100 point :frowning: but anyways my approach was right.
and thank you for pointing my mistake.

lol. leaving DSU aside I got the fact very clear that all the primes from N/2+1 will form their individual groups but somehow I kept failing didn’t knew I was This close to answer, costed 100 points!!

Done by Sieve and Binary Search. Got AC in second go. :slight_smile:
Link

1 Like

1 is added only when n \gt 3 because otherwise there are no numbers remain to form a group.

1 Like

And a star too I guess
ps- I lost one

this did coz 100 points ,lol nice question

how should i try and avoid such corner cases, is there something to help

Can someone explain what’s wrong here, it is giving wa despite having the same idea
https://www.codechef.com/viewsolution/47233681

Same here. Just because of n = 3. LOL

I managed to get 100 points with UFDS and linear Sieve of Eratosthenes.

Code For Reference

Hey @cherry0697 it seems the desired time complexity is O(N \times \log({\log{N}})). But my solution, if I am not wrong, has an overall time complexity of O(N\times(\log{N})^2).

In my approach, I calculated Smallest Prime Factor using the Sieve of Eratosthenes. Initialised a Union Find Data Structure with Path compression. Now, iterating from 3 to max(N), I merge all prime factors of N with N. This should be O(N\times log(N)^2), if I am not wrong.
(It was a kind of Let me try this approach).

But unfortunately, it was giving me SIGFPE error. After debugging for some time, the program executed in 0.92 second(s) for sample test cases. I couldn’t optimise the approach further so I decided to optimise the runtime of the program. One of the finest optimisations was not calling solve() function for every test case, instead, the main() function reads input and prints the corresponding output.

Luckily, the submission was accepted by the Judge. I am still in a dilemma - why did my code pass, shouldn’t it take more time?

Can you explain why it was accepted? :slightly_smiling_face:

I am also attaching a link to my submission.

PS: The code may not seem to reflect my approach, feel free to ask if anything in my code is ambiguous. Thanks is advance.

Your solution isn’t O(N.log(N)^2). With two heuristics, UFDS becomes almost linear for practical cp purposes. It should pass.

2 Likes