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. 
