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
-
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
-
Zoom Meeting URL
Launch Meeting - Zoom -
Meeting ID: 816 6432 1560
-
Password: 126419
[Update2] Catch the session live on YouTube here: [OFFICIAL] Live DSA Learning Session 6 - Contest 5 - YouTube
[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:
-
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.
-
\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}})
- Let P(N) denote the number of prime factors of N, then P(N) = O(\log_2{N}), proof is left as HW.
- \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
}
}