When we can see editorials for the problems or when we can see the code of other contestants?
1 Like
Please move the problems to practice section
1 Like
how can I do such like that? is it todo list?
How did you solve the prime factorization problem
Hi,
I will share my approach.
The prime factorization problem can be solved using a segmented sieve.
- Keep an array for storing number of prime of factors of each number in the range [L,R]
- Find all prime numbers till \sqrt{R}
- Mark all their multiples in the interval [L,R]. For each multiple, get the count and add to the array. (Example if you are looking at a number X which is a multiple of prime P and the number has a factor of P^K, you add K to the corresponding number in the array.
- Lastly, note that some numbers may also have a factor larger than \sqrt{R}. However, note that at most one such factor will be there. (proof is left as an exercise to the reader)
- To find if a number has a prime factor larger than \sqrt{R}, you can divide the original number by all the factors less than \sqrt{R}, if a number that is not 1 remains, then we have a prime factor larger than \sqrt{R}
- Once we have the count of all prime factors of each number, we just need to count which all are prime. Observe that any number smaller than 10^9 has at most 30 prime factors. (Why?). So we keep a set of prime numbers upto 30, and we compare if the number of factors of each number is in the set or not.
The complexity of a segmented sieve is O((R−L+1)log(R)+\sqrt{R})
4 Likes
Nice. Could you get the Derived string problem?
Wowww!!! God level solution
Here is my implementation for anyone interested.
AC_CODE
#include "bits/stdc++.h"
using namespace std ;
const int mxN =31622+2;
bool sieve[mxN] ;
vector<int>P ;
void solve(){
int l,r,ans=0;
cin >>l>>r ;
vector<int>c(r-l+1),A(r-l+1) ;
iota(A.begin(),A.end(),l) ;
for(int p:P){
int l1 = (l%p==0?(l/p)*p:(l/p+1)*p) ;
for(int i=l1;i<=r;i+=p)
while(A[i-l]%p==0)
A[i-l]/=p,c[i-l]++ ;
}
for(int i=l;i<r+1;i++)
c[i-l]+=A[i-l]!=1 ;
for(int i=l;i<r+1;i++)
ans+=sieve[c[i-l]] ;
cout<<ans<<'\n' ;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
for(int i=0;i<mxN;i++)
sieve[i]=1 ;
sieve[0]=sieve[1]=0 ;
for(int i=2;i<mxN;i++){
if(!sieve[i])
continue ;
P.push_back(i) ;
for(int j=i*2;j<mxN;j+=i)
sieve[j]=0 ;
}
int TC=1;
cin>>TC;
while(TC--)
solve();
}
Sure,
I’ll share my approach.
Here, Just count the number of 1s and 0s in the binary string. So by this, you can derive this following equation:
a*x + b*y = n
Where,
a = no. of zeroes
b = no. of ones
n = size of the derived string
Now, find all the values of x & y which satisfy the above equation.
Then for every value of x & y try to fit in the derived equation and whenever it fits perfectly that’s the desired answer.
Here is my implementation if anyone interested.
Accepted Solution
#include "bits/stdc++.h"
#define int long long
using namespace std;
void solve(){
string s1,s2;
cin >> s1 >> s2;
int n = s1.size();
int a = 0, b = 0;
for(int i = 0; i < s2.size(); ++i){
if(s2[i] == '0') a++;
else b++;
}
if(a == n || b == n){
int k = n/s2.size();
cout << s1.substr(0,k) << "\n";
return;
}
// ax + by = n
vector<pair<int,int>> vec;
for (int i = 0; i * a <= n; i++) {
if ((n - (i * a)) % b == 0) {
if(i != 0 && (n - (i * a)) / b != 0)
vec.push_back({i,(n - (i * a)) / b});
}
}
for(auto x : vec){
string ch1 = "", ch2 = "";
bool ok = 1;
int j = 0;
for(int i = 0; i < s2.size(); i++){
if(s2[i] == '0'){
if(ch1 != ""){
string temp = s1.substr(j,x.first);
if(temp != ch1){
ok = 0;
break;
}
}
else{
ch1 = s1.substr(j,x.first);
}
j += x.first;
}
else{
if(ch2 != ""){
string temp = s1.substr(j,x.second);
if(temp != ch2){
ok = 0;
break;
}
}
else{
ch2 = s1.substr(j,x.second);
}
j += x.second;
}
}
if(ok == 1){
cout << ch1 << "\n";
cout << ch2 << "\n";
return;
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
solve();
return 0;
}
2 Likes
Thanks.
thanks so much, I appreciate it!
1 Like
What’s the time complexity of this solution?