MKIT - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Kasra Mazaheri

Tester: Arshia Soltani

Editorialist: Kasra Mazaheri

DIFFICULTY:

Medium

PREREQUISITES:

Dynamic Programming

PROBLEM:

You are given an array A of length N and an integer K. We call a subset of elements of A good, if their product is divisible by K. We define the cost of such subset to be the sum of all it’s elements. You are given Q queries of form (L_i,R_i), for each of which you should output the minimum cost of a good subset of the array A, if we deleted all the indices in the interval [L_i,R_i]. In case there’s no good subset for a given query, output -1.

QUICK EXPLANATION

  • Let K = \prod\limits_{i = 1}^m {p_i^{\alpha_i}} be the factorization of K where p_i are distinct prime numbers and 0 < \alpha_i. Then a number T is a multiple of K, if and only if for each p_i it has at least \alpha_i of them. So we’re only interested in these prime numbers and their relative count in the interval [0, \alpha_i].
  • Define a state to represent how many of each p_i we have. One can see that each important state corresponds to a divisor of K since we should only keep track of the primes that K has (p_i) and at most the amount that K has of each in it’s factorization (\alpha_i).
  • If our current subset’s state corresponds to d, a divisor of K, then after adding an element a to it, it would correspond to gcd(d \times a, K).
  • We can define dp_{i,d} to be the minimum cost of a subset of the first i elements that corresponds to d. Then dp_{i,d} = min(dp_{i-1,d}, dp_{i-1,j} + A_i) for all such j that gcd(j \times A_i, K) = d. Similarly define pd_{i,d} to be the minimum cost of a subset of the elements in the interval [i, N] that corresponds to d. Then we can retrieve the answer for a query (L_i,R_i) using the data we calculated in dp_{L_i-1} and pd_{R_i+1}.

EXPLANATION

For now we only focus on calculating the minimum cost of a good subset of the whole array.

It can be easily proven that a number T is divisible by K = \prod\limits_{i = 1}^m {p_i^{\alpha_i}} if and only if for all 1 \le i \le m, T has at least \alpha_i instances of p_i. Thus only these primes matter as other prime numbers won’t play a part in T being divisible by K. So we can ignore any prime number other than p_i in each of the A_i. Also if at some point we had more than \alpha_i of p_i, we can assume that we only have \alpha_i of it since adding more p_i is useless.

Define the state of a subset to be an array S of length m, meaning that we have picked S_i of p_i where 0 \le S_i \le \alpha_i for all 1 \le i \le m. One can easily see from the above observations that d = \prod\limits_{i = 1}^m {p_i^{S_i}} is always a divisor of K. So we can map each state to a divisor of K and vice versa. Now we can see that adding an element a to a subset with state of d, changes it’s state to gcd(d \times a, K). This is because of the fact that gcd gets rid of all the extra primes, those other than p_i and those p_i that we have more than \alpha_i of them. We can now solve this problem using a dynamic programming solution :
Define dp_{i,d} to be the minimum cost of a subset of the first i elements that their state equals d. Then we can write dp_{i,d} = min(dp_{i-1,d}, dp_{i-1,j} + A_i) for all such j that gcd(j \times A_i, K) = d. Then the minimum cost of a good subset of the whole array is dp_{N,K}. To do this efficiently, we can loop over j and calculate the value of d from it. This way we only loop over each divisor of K once for every element of A we add, so the time complexity of this part will be O(N \times D(K)) where D(K) is the number of divisors of K.

Now back to the original problem. In order to answer the queries, we need another helping function. Define pd_{i,d} to be the minimum cost of a subset of the elements in the interval [i, N] such that their state equals to d. pd can be updated similarly as dp. Now the answer to a query (L_i,R_i) is min(dp_{L_i-1,d_1} + pd_{R_i+1,d_2}) for all such d_1 and d_2 that d_1 \times d_2 is multiple of K. However, this would not fit in the time limit. We can improve this solution by modifying the definition of dp_{i,d} to be the minimum cost of a subset of the first i elements such that their state is a \textbf{multiple} of d. Now the answer to a query (L_i,R_i) is min(dp_{L_i-1,d} + pd_{R_i+1,\frac{K}{d}}) for all d. This improved version is now fast enough to fit in the limit. The only remaining problem is how to calculate the new value of dp_{i,d}. We can compute the array dp in the aforementioned way and then do dp_{i,d} = min(dp_{i,d}, dp_{i,gcd(d \times p_j, K)}) for 1 \le j \le m. It’s worth noting that we should do this in the decreasing order of d. This extra step costs us O(N \times D(K) \times P(K)) where P(K) is the number of distinct primes in factorization of K. And so we arrive at the final solution.

For implementation purposes, it’s recommended to precompute the value of gcd(d_1 \times d_2, K) for every d_1 and d_2 in order to avoid the extra O(log(K)) factor caused by gcd.

TIME COMPLEXITY

The time complexity is O(D(K) \times (N \times P(K) + Q)).

SOLUTIONS:

Setter's Solution
// In The Name Of The Queen
#include<bits/stdc++.h>
#pragma GCC optimzie("O3");
using namespace std;
const int N = 100005, K = 779;
int n, q, k, d, A[N], Id[K][K];
uint32_t dp[N][K], pd[N][K];
vector < int > D, P;
inline void SMin(uint32_t &a, uint32_t b) {a = min(a, b);}
int main()
{
	scanf("%d%d%d", &n, &q, &k);
	for (int i = 1; i <= n; i ++)
		scanf("%d", &A[i]);
	for (int i = 1; i * i <= k; i ++)
		if (k % i == 0)
		{
			D.push_back(i);
			if (i < k / i)
				D.push_back(k / i);
		}
	sort(D.begin(), D.end());
	d = (int)D.size();
	for (int i = 0; i < d; i ++)
		for (int j = 0; j < d; j ++)
			Id[i][j] = (int)(lower_bound(D.begin(), D.end(), __gcd(1LL * D[i] * D[j], 1LL * k)) - D.begin());
	for (int i = 1; i < d; i ++)
	{
		bool Fail = 0;
		for (int j = 1; j < i; j ++)
			if (D[i] % D[j] == 0)
				Fail = 1;
		if (!Fail)
			P.push_back(i);
	}
	for (int j = 1; j < d; j ++)
		dp[0][j] = (uint32_t)(3e9);
	for (int i = 1; i <= n; i ++)
	{
		int id = (int)(lower_bound(D.begin(), D.end(), __gcd(A[i], k)) - D.begin());
		for (int j = 0; j < d; j ++)
			dp[i][j] = dp[i - 1][j];
		for (int j = 0; j < d; j ++)
			SMin(dp[i][Id[j][id]], dp[i - 1][j] + A[i]);
	}
	for (int j = 1; j < d; j ++)
		pd[n + 1][j] = (uint32_t)(3e9);
	for (int i = n; i; i --)
	{
		int id = (int)(lower_bound(D.begin(), D.end(), __gcd(A[i], k)) - D.begin());
		for (int j = 0; j < d; j ++)
			pd[i][j] = pd[i + 1][j];
		for (int j = 0; j < d; j ++)
			SMin(pd[i][Id[j][id]], pd[i + 1][j] + A[i]);
	}
	for (int i = 1; i <= n; i ++)
		for (int j = d - 1; ~ j; j --)
			for (int p : P)
				SMin(dp[i][j], dp[i][Id[j][p]]),
				SMin(pd[i][j], pd[i][Id[j][p]]);
	for (; q; q --)
	{
		int l, r;
		long long Mn = dp[0][1];
		scanf("%d%d", &l, &r);
		for (int j = 0; j < d; j ++)
			Mn = min(Mn, (long long)dp[l - 1][j] + pd[r + 1][d - j - 1]);
		if (Mn >= (long long)(3e9))
			Mn = -1;
		printf("%lld\n", Mn);
	}
	return 0;
}
Tester's Solution
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
 
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
 
#define ll long long
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll> 
 
using namespace :: std;
 
const ll maxn=1e5+500;
const ll maxt=880;
const ll maxQ=1000;
const ll inf=1e10;
 
ll a[maxn];
bool useL[maxn];
bool useR[maxn];
ll Rv[maxn];
 
 
vector<ll> magh;
ll b[maxt][maxt];
ll dp[maxt];
 
ll ans[maxQ][maxQ];
ll t;
 
bool add(ll ind){
	ll x=a[ind];
	ll rv=Rv[ind];
 
	bool u=0;
	for(ll j=maxt-1;j>=0;j--){
		if(dp[b[x][j]]>dp[j]+rv){
			u=1;
			dp[b[j][x]]=dp[j]+rv;
		}
	}
	return u;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);	
	ll n,q,k;
	cin>>n>>q>>k;
	for(ll i=1;i*i<=k;i++){
		if(k%i==0){
			magh.pb(i);
			if(k/i!=i){
				magh.pb(k/i);
			}
		}		
	}
	sort(magh.begin(),magh.end());
	for(ll i=0;i<n;i++){
		cin>>a[i];
		Rv[i]=a[i];
		a[i]=gcd(a[i],k);
		a[i]=lower_bound(magh.begin(),magh.end(),a[i])-magh.begin();
	}
	t=magh.size();
	for(ll i=0;i<t;i++){
		for(ll j=0;j<t;j++){
			b[i][j]=lower_bound(magh.begin(),magh.end(),gcd(k,magh[i]*magh[j]))-magh.begin();
		}
	}
 
 
	memset(dp,30,sizeof dp);
	dp[0]=0;
	for(ll i=0;i<n;i++){
		useL[i]=add(i);
	}
	memset(dp,30,sizeof dp);
	dp[0]=0;
	for(ll i=n-1;i>=0;i--){
		useR[i]=add(i);
	}
 
	vector<ll> vecL,vecR;
	for(ll i=0;i<n;i++){
		if(useL[i])vecL.pb(i);
		if(useR[i])vecR.pb(i);
	}
 
	memset(ans,31,sizeof ans);
	for(ll i=-1;i<(ll)vecL.size();i++){
		memset(dp,30,sizeof dp);
		dp[0]=0;
		for(ll j=0;j<=i;j++){
			add(vecL[j]);
		}
		for(ll j=(ll)vecR.size();j>=-1;j--){
			// ans[i+1][j+1];
			if(j>=0 && j<(ll)vecR.size()){
				add(vecR[j]);
			}
			ans[i+1][j+1]=dp[t-1];
		}
	}
	for(ll i=0;i<maxQ;i++){
		for(ll j=0;j<maxQ;j++){
			if(ans[i][j]>inf)ans[i][j]=-1;
		}
	}
	for(ll i=0;i<q;i++){
		ll l,r;
		cin>>l>>r;
		l--;
		r--;
		l--;
		r++;
		l=upper_bound(vecL.begin(),vecL.end(),l)-vecL.begin()-1;
		r=lower_bound(vecR.begin(),vecR.end(),r)-vecR.begin();
		cout<<ans[l+1][r+1]<<endl;
	}
}

Feel free to share your approach. As usual, suggestions are warmly welcomed. :slight_smile:

1 Like

In the problem statement it says “Roger picks some non-empty group of citizens”. For K = 1, I read this as meaning we cannot take an empty group. However, to get accepted I needed to answer 0 whenever k = 1. I believe this is an error in the problem statement.
This cost me a lot of time and frustration during the contest, and gave a very bad first impression of the Codechef platform.

That extra log(N) factor due to gcd caused me TLE during contest. :frowning:

Sorry about that. The original statement didn’t have this sentence, the statement verifier added it in the verification process. I’m also clueless why. Anyway, I fixed the statement, thanks for pointing it out.

Hey, how do I know whether the solution would pass; I mean what is the max value of D(K) and P(K) for the given range of K from 1 to 10^8?

@kmaaszraa How does this work while computing the final answer (in your/setter’s solution)?
I can possible still compute the same maintaining a reverse map from divisors to index in D, but wanted to understand your approach here.

You can calculate it easily using dp. The maximum values for K \le 10^8 would be D(K) = 768 and P(K) = 8.

Well basically we’re looking for the id of \frac{K}{d} in the sorted array. You can see that as we increase d, the value of \frac{K}{d} decreases, for example (1, K), (2,\frac{K}{2}) and so on. So the i-th divisor of K (in sorted order) would match with the (D(K)-i-1)-th divisor of K in the sorted order.

1 Like

Hi, I’ve been trying for some time to get my submission to pass (it’s modeled after the Tester’s solution) but I keep getting Runtime Error, link to sol is here
Any idea why I’m failing tests?