HIRINGWO - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter:
Tester: Rahul Dugar
Editorialist: Taranpreet Singh

DIFFICULTY

Easy-Medium

PREREQUISITES

Basic Maths, Implementation

PROBLEM

Given K tasks, where each task takes x days if x people are working on that task. The tasks are accepted if and only if all tasks are submitted on the same day. You have to decide the number of people for each task (at least 1), such that tasks are accepted on day X and the total number of people is minimized.

QUICK EXPLANATION

  • We need to find K integers such that their sum is minimized and their LCM is X.
  • Divide X into product of prime powers, now we need to distribute these prime powers over K tasks.
  • Since there are atmost 7 prime powers, we can either generate all partitions or even run Partition DP to find optimal partitioning, which gives minimum number of people.

EXPLANATION

Firstly, a group of x people submits tasks only on days y such that x | y (x divides y). Since all tasks are accepted on day X, the number of person in each tasks divides X.

One naive idea would be to assign X people in first task and 1 in other, leading to LCM X. Which works, except for the minimizing people condition.

Let’s assume A_i denote the number of people assigned on task i.

Lemma: GCD(A_i, A_j) = 1 for i \neq j

Proof

Let’s assume in optimal A, p^x divides both A_i and A_j for x \geq 1. Let’s assume p^y divides A_i and y is maximum possible, and p^z divides A_j and z is maximum possible.

We have x \leq min(y, z). WLOG assume y \leq z
Ignoring all other values in A, we can see that LCM is divisible by p^z. So even if we divide A_i by p^y, the LCM remains unaffected, while the sum of A is reduced.

Hence, our assumption is wrong.

After this, dividing X into product of prime powers, we need to distribute these powers into K tasks, minimizing the sum of people over each task. It is important to note that for X \leq 10^6, the number of prime powers cannot exceed 7. (Try finding smallest number with 8 distinct prime factors)

For example, X = 360 = 2^3 * 3^2*5 = 8*9*5.

Let’s say \displaystyle X = \prod_{i = 1}^N A_i, where each A_i is a prime power and GCD(A_i, A_j) = 1 for i \neq j We also know that N \leq 7

If we have N \leq K, we can simply assign each A_i to a different task to minimize sum.
Say K = 4 and X = 360, we can assign A = [1,5,8,9], minimizing sum.

Now what happens if K < N. In this case, we need to divide A into K partitions, minimizing sum of product of values in each partition.

It can be done by generating all partitions of N values (setter solution below), or using Partition DP (Tester and Editorialist solution).

Giving an overview of Partition DP, We maintain state (mask, count) which determines the minimum sum of products of each partition, if all set bits in mask are divided into exactly count partitions.

We can write f(mask, count) = min_{sub \sube mask}( f(sub, count-1)+P[mask \oplus sub]) where P[mask] denotes the product of all values included in mask. Also, we have f(mask, 1) = P[mask]

Practice problem for Partition DP: here

TIME COMPLEXITY

For factorisation, we can use O(\sqrt X). Generating all paritions takes P(N) time where P(N) denotes partition function. Partition DP takes O(K*3^N) time.

So depending upon implementation, it’s O(\sqrt X + P(N)) or O(\sqrt X + K*3^N)

SOLUTIONS

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#define ld long double

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<", "<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	for(int i = 0;i < (int)v.size(); i++){
		if(i)os<<", ";
		os<<v[i];
	}
	os<<"}";
	return os;
}

#ifdef LOCAL
#define cerr cout
#else
#endif

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			if(!(l<=x && x<=r))cerr<<l<<"<="<<x<<"<="<<r<<endl;
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
template<class T>
vector<T> readVector(int n, long long l, long long r){
    vector<T> ret(n);
    for(int i = 0; i < n; i++){
	ret[i] = i == n - 1 ? readIntLn(l, r) : readIntSp(l, r);
    }
    return ret;
}

map<vector<int>, vector<vector<vector<int>>>> mp;
vector<vector<vector<int>>> gen_partitions(vector<int> v){
	if(mp.find(v) != mp.end()) return mp[v];
	int n = sz(v);
	if(n == 1) return {{{v[0]}}};
	vector<vector<vector<int>>> ret;
	for(int mask = 0; mask < (1 << (n - 1)); mask++){
		vector<int> curr;
		vector<int> V = v; V.pop_back();
		for(int j = 0; j < (n - 1); j++) if(mask >> j & 1){
			curr.push_back(v[j]);
			V.erase(find(all(V), v[j]));
		}
		curr.push_back(v.back());
		if(V.empty()){
			ret.push_back({curr});
			continue;
		}
		vector<vector<vector<int>>> parts = gen_partitions(V);
		for(auto & it : parts){
			it.push_back(curr);
		}
		copy(all(parts), back_inserter(ret));
	}
	return mp[v] = ret;
}
const int N = 1000006;
int factor[N];

int get(int n, int k){
    vector<int> PE;
    while(n != 1){
	int p = factor[n];
	int pe = 1;
	while(n % p == 0) n /= p, pe *= p;
	PE.push_back(pe);
    }
    vector<int> v(PE.size());
    iota(all(v), 0);
    mp.clear();
    vector<vector<vector<int>>> P = gen_partitions(PE);
    int ans = INT_MAX;
    for(auto it : P){
	int l = it.size();
	if(l > k) continue;
	int here = k - l;
	for(auto H : it){
	    int prod = 1;
	    for(int u : H){
	        prod *= u;
	    }
	    here += prod;
	}
	ans = min(ans, here);
    }
    return ans;
}
int main(){
    int t = readIntLn(1, 40);
    for(int i = 2; i < N; i++) if(!factor[i]){
	for(int j = i; j < N; j += i) factor[j] = i;
    }
    while(t--){
	int k = readIntSp(1, 1000000), n = readIntLn(1, 1000000);
	cout << get(n, k) << endl;
    }
}
Tester's Solution
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}

long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);

			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}


int sum_n=0;
int dp[11][1<<10];
void solve() {
	int k=readIntSp(2,1000000),x=readIntLn(2,1000000);
	vi facs;
	for(int i=2; i*i<=x; i++)
		if(x%i==0) {
			facs.pb(i);
			x/=i;
			while(x%i==0) {
				x/=i;
				facs.back()*=i;
			}
		}
	if(x!=1)
		facs.pb(x);
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	int kk=min(k,sz(facs));
	for(int p=0; p<kk; p++) {
		for(int i=0; i<(1<<sz(facs)); i++) {
			int te=((1<<sz(facs))-1)^i;
			for(int j=te; j>0; j=(j-1)&te) {
				int cs=1;
				for(int k=0; k<sz(facs); k++) {
					if((j>>k)&1)
						cs*=facs[k];
				}
				dp[p+1][i^j]=min(dp[p+1][i^j],dp[p][i]+cs-1);
			}
		}
	}
	cout<<dp[kk][(1<<sz(facs))-1]+k<<endl;
}

signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(7);
	int t=readIntLn(1,100000);
//	cin>>t;
	fr(i,1,t)
		solve();
	assert(getchar()==EOF);
#ifdef rd
//	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class HIRING2{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
	int K = ni(), X = ni();
	int[] values = new int[7];
	int count = 0;
	for(int p = 2; p <= X; p++){
	    if(X%p == 0){
	        int c = 1;
	        while(X%p == 0){
	            c *= p;
	            X /= p;
	        }
	        values[count++] = c;
	    }
	}
	values = Arrays.copyOf(values, count);
	if(count <= K){
	    int ans = K-count;
	    for(int val:values)ans += val;
	    pn(ans);
	}else{
	    int[] prod = new int[1<<count];
	    for(int i = 0; i< 1<<count; i++){
	        prod[i] = 1;
	        for(int j = 0; j< count; j++)
	            if((i&(1<<j)) > 0)
	                prod[i] *= values[j];
	    }
	    int[][] DP = new int[1+K][1<<count];
	    DP[1] = prod;
	    for(int layer = 2; layer <= K; layer++){
	        Arrays.fill(DP[layer], (int)1e8);
	        for(int mask = 0; mask < 1<<count; mask++){
	            for(int sub = mask; sub > 0; sub = (sub-1)&mask){
	                DP[layer][mask] = Math.min(DP[layer][mask], DP[layer-1][sub]+prod[mask^sub]);
	            }
	        }
	    }
	    pn(DP[K][(1<<count)-1]);
	}
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
	in = new FastReader();
	out = new PrintWriter(System.out);
	//Solution Credits: Taranpreet Singh
	int T = (multipleTC)?ni():1;
	pre();for(int t = 1; t<= T; t++)solve(t);
	out.flush();
	out.close();
    }
    public static void main(String[] args) throws Exception{
	new HIRING2().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
	BufferedReader br;
	StringTokenizer st;
	public FastReader(){
	    br = new BufferedReader(new InputStreamReader(System.in));
	}

	public FastReader(String s) throws Exception{
	    br = new BufferedReader(new FileReader(s));
	}

	String next() throws Exception{
	    while (st == null || !st.hasMoreElements()){
	        try{
	            st = new StringTokenizer(br.readLine());
	        }catch (IOException  e){
	            throw new Exception(e.toString());
	        }
	    }
	    return st.nextToken();
	}

	String nextLine() throws Exception{
	    String str = "";
	    try{   
	        str = br.readLine();
	    }catch (IOException e){
	        throw new Exception(e.toString());
	    }  
	    return str;
	}
    }
}

VIDEO EDITORIAL:

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

20 Likes

Everything was fine in my solution except one thing. If I would have seen the maximum limit of X (10**6), then I would have achieved a Global rank 76 or even better than that. Saddddd…

5 Likes

I tried one different approach and was unable to get AC . My approach was to find smallest
co prime pair of factors (i, X/i) of X such that the ( i + ( X / i ) ) < ( 1+ X)

if any such pair is present then I got my members of 2 teams out of K teams
now I fill other ( K-2) with 1 member.

else
The total value will be ( ( X ) + ( K - 1 ) )

Link to my solution :- https://www.codechef.com/viewsolution/39771898
which test case am I failing and what is wrong with my approach ? Please guide me .

4 Likes

My logic for it is to get prime factors of x and multiply similar prime factors make a team for every one of it and if k is greater than it then all other team sizes will be 1
It is totally satisfying all constraints but not accepted. Please Help!
As mainly we have to find LCM(All the teams)=x
where sum of people of all teams should be minimum

ll HIRINGWO(ll k,ll x){
    vector<ll> factors = getFactorization(x);
    vector<int> f;
    int similar=factors[0];
    f.push_back(factors[0]);
    for(int i=1;i<factors.size();i++){
        ll num=factors[i];
        while(similar==factors[i]){
            num*=factors[i];
            i++;
        }
        f.push_back(num);
        similar=factors[i];
    }
    //for(int i=0;i<f.size();i++)cout << f[i] << " ";
    //cout << "\n";
    ll teamSize=0;
    if(f.size()==k){
        for(ll i=0;i<k;i++){
            teamSize+=f[i];
        }
    }
    else if(f.size()>k){
        ll mult=1;
        ll remain = f.size()-(k-1);
        for(ll i=0;i<remain;i++){
            mult*=f[i];
        }
        for(ll i=0;i<k-1;i++){
            teamSize+=f[remain+i];
        }
        teamSize+=mult;
    }
    else{
        for(int i=0;i<f.size();i++){
            //cout << f[i] << " ";
            teamSize+=f[i];
        }
        teamSize+=(k-f.size());
    }
    return teamSize;
}
2 Likes

Same solution as mine . Couldnt figure out why.

My solution was the same for N \leq K. For K > N, I added them to a set and merged the two smallest numbers and hoped for it to work.
Can I please have a test case for which my code fails or an explanation for why it’s wrong?
My code

1 Like

try this test case
3 30
ans=10

3 Likes

if anyone needs , complete step by step detailed explanation in hindi

https://youtu.be/paRvarNQ8AQ

5 Likes

I understand I was doing the same thing from a start, but choosing just two teams and assigning others 1 is not optimal, you have to assign multiple teams.

2 Likes

How is it 10?

try
2 210
ans = 29

8 Likes

for the 3 boxes, insert 2,3,5 which gives sum 10

2 Likes

Thanks, got it.

1 Like

I was also stucked in same approach. Your solution is trying to assign single worker to every task except two tasks with worker a and b such that lcm(a,b) = no of days. And total no of workers = a+b+ no of days -2. But think of a solution in which lcm(a,b,c)= no. of days such that total number of workers a+b+c + no of days - 3 is smaller.

1 Like

Thanks Got it.

it is 6 => 2+3+1

Can anyone please explain how to brute force partition?

2 Likes

Never thought dp would be used to minimize the sum. I just had the observation of lcm and all pairwise gcd’s as 1 and here is a beautiful solution :slight_smile:

As everytime, I love your editorials Taran bhaiyya!

3 Likes

For brute force partition run two nested loops and remove a[i] and a[j] from the array and insert (a[i] * a[j] ) into the array. Repeat the process until you get the desired size.

Spoiler
// left is number of times we need to compress the array

 void partition(int left, vector <ll> v1){
  if(left==0){
    ll temp=0;

    for(auto itr: v1){
      temp+=itr;
    }

    sum=min(sum,temp);
    return;
  }

  for(ll i=0;i<v1.size();i++){
    for(ll j=i+1;j<v1.size();j++){
      vector <ll> v2;

      v2.pb(v1[i]*v1[j]);
      for(ll k=0;k<v1.size();k++){
        if(k!=i && k!=j){
          v2.pb(v1[k]);
        }
      }

      partition(left-1,v2);
    }
  }
}
10 Likes

14 and 15

1 Like