CHVSDO - Editorial

editorial
, , ,
1

PROBLEM LINK:

Cheems VS Doge

Authors: Parth Dhorajiya and Rituj Aryan
Tester: Rohit Doshi

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

Number Theory, Dynamic Programming

PROBLEM:

You are given three integers L, R, and S. Find the total number of subsets wherein the summation of the total number of prime factors of distinct numbers (lying between L and R, both inclusive) is equal to S.

The prime factor of a number is that divisor which has a factor as 1 and that number itself only. Can you help Cheems to solve this question?

EXPLANATION:

Idea behind the problem is :-

  1. Make a list v_1 in which i^{th} element stores the number of prime factors of the (L+i)^{th} element.
  2. This is classic subset sum problem in which we have to count the number of subsets having sum = S.

For 1) – A number N can be represented in prime factorization as
N = a^p * b^q * c^r * d^s * e^t ...
where (a,b,c,d,e, ... are prime factors in increasing order)

For every number lying in range [L,R]:

Suppose current number is N.
count = 0; // Number of prime factors

for i = 2 to sqrt(N) { 

    if (N%i == 0) {
        count++; 
        N = N/i;
    }

    while(N%i == 0) {
        N = N/i;
    }

    if (N > 1) {
        count++;
    }

    Store the count in list v1
    (This denotes the number of prime factor of given number N)
}

Then sort v_1 in non-decreasing order.

For 2) –

  • We make dp[(R-L+1)+1][S+1] in which dp[i][j] denotes the number of subsets (considering first i elements of v_1) having sum j.

  • Initialize dp[i][0]=1 (1st column of dp[ ][ ]) for valid 0 \leq i \leq (R-L+1), since there is always an empty subset { } having sum 0.

  • For every particular element we have 2 options, to include it in the contribution of the sum or not.

    • If v_1[i-1] > j, i.e. if the i^{th} element is greater than j (current sum).
      Then its impossible to include it so the total number of subset would be same as of considering (first i-1 elements) having sum j.

    • If v_1[i-1] \leq j, i.e we have option to include it.
      So we add dp[i-1][j] + dp[i-1][j-v_1[i-1]],
      first term means we consider first (i-1) elements that sums upto j, and
      second term means we consider i^{th} element of v_1 and the sum remaining is (j-v_1[i-1]). So we would consider first (i-1) elements that sums to (j-v_1[i-1]).

  • dp[n][s] would give our required answer.

CORNER CASE: (L = 1)

Now since our first element in v_1 would be 0
So we can initialize dp[0][0]=1 and dp[i][0] = 2, 1 \leq i \leq (R-L+1)
Since we have 2 subsets having sum 0: ({ }, 0).

OR

Initialize 1st column in dp [ ] [ ] =1 as did before and multiply the answer we would get by 2. (because for every subset we can get a new subset by adding 0 to it.)

SOLUTIONS:

Setter's Solution - CPP 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define A first
#define B second
#define lb long double
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fo(i,n) for(i=0;i<n;i++)
#define mpp map<ll,ll>m;
#define vec vector<ll>v;
#define mod (ll)(1e9+7)
ll a[1005][1005];

void solve() 
{
	ll l,r,s,i,j,c=0,n,count=0;
	cin>>l>>r>>s;
	vector<ll> v,v1;

	for(i=l;i<=r;i++)
		v.pb(i);

	for (auto e:v) {
		ll a=e;
		c=0;
		for(i=2;i*i<=a;i++)
		{
			if(a%i==0)
			{
				c++;
				a=a/i;
			}
			while(a%i==0)
			{
				a=a/i;
			}
		}
		if(a>1)
		c++;
		v1.pb(c);
	}
	sort(v1.begin(),v1.end());
	n=v1.size();
	ll dp[n+1][s+1];
	for(i=0;i<=n;i++)
	dp[i][0]=1;
	for(j=1;j<=s;j++)
	dp[0][j]=0;
	for(i=1;i<=n;i++){
		for(j=1;j<=s;j++){
			if(v1[i-1]<=j){
				dp[i][j]=(dp[i-1][j]%mod+dp[i-1][j-v1[i-1]]%mod)%mod;
				dp[i][j]%=mod;
			}
			else{
				dp[i][j]=dp[i-1][j]%mod;
				dp[i][j]%=mod;
			}
		}
	}
	if(l>1)
	cout<<dp[n][s]%mod<<endl;
	else{
		cout<<((dp[n][s]%mod*2)%mod)<<endl;
	}
}
int main()
{
	fast
	solve();
}
Tester's Solution - Python 
from math import sqrt

mod = 10**9 + 7
MAXN = 1000001
SPF = [i for i in range(MAXN)]

# Calculating SPF (Smallest Prime Factor) for every number till MAXN.
# Time Complexity : O(n log(logn))
def manipulated_seive(): 
	for i in range(4, MAXN, 2):
		SPF[i] = 2

	i = 3
	while(i*i < MAXN):
		if SPF[i] == i:
			for j in range(i*i, MAXN, i):
				if SPF[j] == j:
					SPF[j] = i

		i += 1


# A O(log n) function returning primefactorization by dividing by smallest prime factor at every step
def getFactorization(x):
	ret = []
	while (x != 1):
		ret.append(SPF[x])
		x = x // SPF[x]
	
	return len(set(ret))


def subsetSum(numbers, sum):
	array = [1] + [0] * (sum)
	for current_number in numbers:
		for num in range(sum - current_number, -1, -1):
			if array[num]:
				array[num + current_number] = (array[num + current_number]%mod + array[num]%mod)%mod
	
	return array[sum]%mod


manipulated_seive()
l, r, s = map(int, input().split())

primeDiv = []
for i in range(l, r+1):
	primeDiv.append(getFactorization(i))

ans = subsetSum(primeDiv, s)%mod
print(ans)

Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. :smile: