Shaastra Contest editorial?

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.

  1. Keep an array for storing number of prime of factors of each number in the range [L,R]
  2. Find all prime numbers till \sqrt{R}
  3. 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.
  4. 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)
  5. 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}
  6. 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?