[OFFICIAL] Live DSA Learning Session 6 - Contest 5

Hi everyone,

This is a continuation of the Live DSA learning sessions being conducted as part of the DSA Learning series.

A session would generally be conducted by CodeChef volunteers and would be a live discussion (via text + video). The main purpose of these sessions would be to discuss the theory topics and then move on how to go about solving the problems of the contest.

For Contest 5, the 1st session is as follows:

  • Topic: Theory discussion + Live problem solving of 1 - 2 problems of the contest 5 + QnA

  • Brief Description:
    Which theory topics would you prefer (Pick at most 3 out of the 4 options)
    (Update - The voting will close by 14th May evening)

  • Fast matrix exponentiation (to solve recurrences) and generic techniques to tackle fibonacci related questions using this
  • Problem solving tricks relevant to questions involving factors, gcd questions, etc.
  • Using modulo arithmetic for classical + non-classical uses (Example: Find if a bigint is a multiple of a small number or not? Is a number y a root of a polynomial p(x), where p(x) is of degree 10^5 and has big coefficients)
  • Derivation of formula for number of factors of N and sum of factors of N and how to obtain all factors from the prime factorisation of a given number

0 voters

From problem solving aspect which problems would you want to be discussed (Pick at most 3):
(Update - The voting will close by 14th May evening)

  • Pre-requisite:
    Recommended having gone through the reading material of this week here

  • Session volunteer:
    Sidhant Bansal

  • Date-Time:
    5:00 PM IST, 15th May 2020 (Friday)

  • Duration:
    1.5 - 2 hours

  • Platform for video conferencing:
    Zoom Meetings limited 100 seats. Entry to the session on Zoom will be on a first come first serve basis.
    Rest of the participants can join live on CodeChef’s YouTube channel .

  • To register:
    If you are interested just register by clicking on the Going button below the topic title at the top and Add it to your calendar for a reminder so that you don’t miss it :slight_smile:

  • Note from CodeChef:
    — These sessions are hosted by our volunteers. Kindly respect their efforts and time.
    — In case of any doubts, please post in the comments.

[Update1] Zoom meeting details

[Update2] Catch the session live on YouTube here: https://www.youtube.com/watch?v=iXfY7Urt28I

[Update3] Kindly share your valuable feedback on the session here: https://forms.gle/JZznX7nsKfJn66bs6

[Update4]
During the session we had discussion about number of factors of a given number N
Here are the facts:

  1. Let F(n) denote the number of factors of N. Then F(N) \leq 1344 for N \leq 10^9. You can see here that people in CP often assume F(N) = O(N^{\frac{1}{3}}) in worst case.

  2. \sum_{i = 1}^{N}F(i) = O(N\log{N}). Proof is from this pseudocode:

vector<int> factors[N];
for(int i = 2; i <= N; i++) {
  for(int j = i; j <= N; j += i) {
     factors[j].push_back(i)
  }
}
// How slow is this? O(N/2 + N/3 + N/4 + ...) = O(NlogN)

This shows that \sum_{i = 1}^{N}F(i) is better than O(N*\sqrt{N}) and even better than O(N * N^{\frac{1}{3}})

  1. Let P(N) denote the number of prime factors of N, then P(N) = O(\log_2{N}), proof is left as HW.
  2. \sum_{i = 1}^{N}P(i) = O(N\log{\log{N}}). Proof is from the analysis of Sieve of Eratosthenes. This shows that \sum_{i = 1}^{N}P(i) is better than O(N\log{N}) that you might be thinking naively.

Matrix expo resources:1, 2, 3, 4
Relevant to matrix expo is binary exponentiation. Read it up here

We also used Sieve of Eratosthenes and fast prime factorisation method to implement the solution for KPRIME. Find the implementation below.

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int A[N];
int prefix[N][6];

int prime_factor[N];

vector<pair<int, int> > prime_factors[N];

bool square_free(int x) {
  for(auto v : prime_factors[x]) {
    if(v.second > 1)  return 0;
  }
  return 1; // return true
}

int main() {
  ios_base::sync_with_stdio(false);
  // when you have a lot of input
  cin.tie(NULL);
  cout.tie(NULL);

  for(int i = 2; i < N; i++) {
    if(prime_factor[i] != 0)  continue;
    prime_factor[i] = i; //IMPORTANT
    for(int j = 2*i; j < N; j += i) {
      prime_factor[j] = i;
    }
  }
  for(int i = 2; i < N; i++) {
    int x = i;
    map<int, int> M; //HW - use vector instead of map here
    while(x != 1) {
      M[prime_factor[x]]++;
      x /= prime_factor[x];
    }
    for(auto v : M) {
      prime_factors[i].push_back(v);
    }
  }

  // A[] and prefix[][]

  // A[1] = dont care
  for(int i = 1; i < N; i++)  A[i] = prime_factors[i].size();

  for(int i = 1; i < N; i++) {
    for(int k = 1; k <= 5; k++) {
      prefix[i][k] = prefix[i - 1][k] + (A[i] == k);
    }
  }

  int t;
  cin>>t;
  while(t--) {
    // t = 10^5
    int l, r, k;
    cin>>l>>r>>k;
    cout<<prefix[r][k] - prefix[l - 1][k]<<'\n';
    // printing a lot of lines --> \n instead of endl
  }
}
3 Likes

It would be quite good if the Webinars are conducted over weekend because most of the coders are either Working Professionals or Students. It becomes quite not possible to attend the webinar due to work and also for student

it become quite hectic to attend in working day due to assignments and home work.

@admin I would like to suggest if it can be hosted in weekend but with longer duration that will really help.
Thanks

Update: The session is supposed to be conducted on 15th May (i.e Friday), NOT 16th May (there was a typo before)

Zoom meeting details and YouTube link updated.

Added [Update4] to the post above containing the following discussed during the session:

  1. Upper bound on number of factors and number of prime factors
  2. Matrix expo resources
  3. KPRIME code (also consists of fast prime factorisation method we discussed)

In [update4] of the discussion in finding factors of number i and factor[i] stores the all factors of the number , I think the statement in innner for loop should be factors[j].push_back(i)

1 Like

Can anybody tell whats wrong with this ?

#include<bits/stdc++.h>
using namespace std;
const int N= 100005;
int prime_factors[N]={0};
int count[N]={0};

void sieve() // an array is made with highest prime factorisation for a number …for example- for 10 it is 5…and for 5 it is 5…
{
for(int i=2;i<=N;i++) //for optimization ii<=n
{
if(prime_factors[i]!=0)continue;
prime_factors[i]=i;
//result.push_back(i);
for(int j=2
i;j<=N;j+=i)
{
prime_factors[j]=i;
}
}
}

int main()
{
#ifndef ONLINE_JUDGE
// for getting input from input.txt
freopen(“input.txt”, “r”, stdin);
// for writing output to output.txt
freopen(“output.txt”, “w”, stdout);
#endif
int t;
cin>>t;
sieve();
while(t–)
{
int a,b,x;
cin>>a>>b>>x;
int cnt=0;
int count[N]={0};
for(int i=a;i<=b;i++)
{
int temp=i;
while(temp!=1)
{
count[i]++;
temp/=prime_factors[temp];
}
}
for(int i=a;i<=b;i++)
{
if(count[i]==x)cnt++;
}
cout<<cnt<<endl;
}
return 0;
}