PROBLEM LINK:
Author: agarwal_keshav
Tester: dragno99, mr_cchef, valiant_vidit
Editorialist: agarwal_keshav
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
DP
PROBLEM:
Keshav has an array of n integers [a_1,a_2,a_3,.. a_n]. He can perform the following operation on the given array any number of times.
(i) if the leftmost or rightmost element is zero remove this element from the array at cost 0
(ii) he can replace the leftmost element a_l to D(a_l) at the cost of F(a_l)*a_l
(iii) he can replace the rightmost element a_r to D(a_r) at the cost of F(a_r)*ar
(iv) if the rightmost and leftmost element both are the same and not equal to zero then he can replace the leftmost element a_l to D(a_l) and the rightmost element a_r to D(a_r) at the cost of F(a_l)*a_r
where F(x) = number of distinct prime factors of x for e.g. F(1)=0, F(12)=2 and D(x) = floor value of x/2
Keshav wants to find the minimum cost to make the array completely empty but he is busy somehwere else and asking for your help to calculate the minimum cost.
EXPLANATION:
we can precompute the value of function F(x) for x\leq 10^5 using sieve of eratosthenes
Now to make array empty let’s consider the array from index i to j, we want to find the minimum cost to make array empty from index i to j, we can perform the following three operation
(i) make a_i to 0 at
Cost
long int cost =0;
while(a[i]){
cost += a[i]*F(a[i]);
a[i] /=2;
}
and find the answer for array from index i+1 to j
(ii) make a_j to 0 at
Cost
long int cost =0;
while(a[j]){
cost += a[j]*F(a[j]);
a[i] /=2;
}
and find the answer for array from index i to j-1
(iii) make a_i and a_j to 0 at
Cost
long int cost =0;
while(a[i] || a[j]){
if(a[i] > a[j]){
cost += a[i]*F(a[i]);
a[i] /=2;
} else if(a[i] < a[j]){
cost += a[j]*F(a[j]);
a[j] /=2;
} else{
//using operation 4 acc. to question
cost += a[j]*F(a[j]);
a[j] /=2;
a[i] /=2;
}
}
and find the answer from index i+1 to j-1
and finally, take the minimum of all three values.
SOLUTIONS:
Setter's Solution in C++
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define nl cout<<"\n";
ll minv(ll a,ll b){ return a<b?a:b;}
ll maxv(ll a,ll b){ return a>b?a:b;}
const ll mn = 100001;
vector<int> a;
vector<vector<int>> dp;
ll prime[mn];
ll Cost(int val){
ll cost =0;
while(val){
cost += val*prime[val];
val = val/2;
}
return cost;
}
ll find(int l,int r){
if(l>r) return 0;
if(dp[l][r]!=-1) return dp[l][r];
if(l==r){
return dp[l][r] = Cost(a[l]);
}
ll v1 = Cost(a[l]) + find(l+1,r);
ll v2 = Cost(a[r]) + find(l,r-1);
ll tem_cost =0;
int a1 = a[l],a2 = a[r];
while(a1){
if(a1 < a2){
tem_cost += a2*prime[a2];
a2 = a2/2;
}else if(a1 > a2){
tem_cost += a1*prime[a1];
a1 = a1/2;
}else{
tem_cost += a1*prime[a1];
a1 = a1/2;
a2 = a2/2;
}
}
ll v3 = tem_cost + find(l+1,r-1);
return dp[l][r] = minv(v1,minv(v2,v3));
}
ll spf[mn];
void sieve(){
spf[1] = 1;
for(int i=3;i<mn;i+=2){
spf[i] =i;
}
for(int i=2;i<mn;i+=2) spf[i] = 2;
for(int i=2;i*i<mn;i++){
if(spf[i]==i){
for(int j=i*i;j<mn;j+=i){
if(spf[j]==j)
spf[j] = i;
}
}
}
}
int fac(ll x){
int ans =0;
while(x>1){
int tem = spf[x];
while(spf[x]==tem)
x = x/spf[x];
ans++;
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt","w",stderr);
#endif
sieve();
for(int i=1;i<mn;i++){
prime[i] = fac(i);
}
int n;cin>>n;
dp.resize(n);
for(int i=0;i<n;i++){
dp[i].resize(n);
fill(dp[i].begin(),dp[i].end(),-1);
}
a.resize(n);
for(int i=0;i<n;i++)cin>>a[i];
cout<<find(0,n-1);
return 0;
}
Tester's Solution in C++
#include "bits/stdc++.h"
#define ll long long int
#define oo 1000000000000000000
#define forr(i,n) for(int i=0;i<n;i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define unique(v) sort(all(v)); v.resize(distance(v.begin(),unique(all(v))))
#define eb emplace_back
#define FF first
#define SS second
#define mem(a,v) memset(a,v,sizeof(a))
#define pb push_back
#define popcount(x) __builtin_popcount(x)
using namespace std;
template<typename T>
ostream &operator<<(ostream &output,const vector<T> &v){
if(v.empty()) return output;
for(int i=0;i<v.size()-1;i++) output << v[i] <<" ";
output << v.back();
return output;
}
template<typename T>
istream &operator>>(istream &input,vector<T> &v){
for(auto &i: v) cin >> i;
return input;
}
void __sol(){
int n; cin >> n;
vector<int> a(n); cin >> a;
int sz = *max_element(all(a))+2;
vector<int> f(sz);
for(int i=2;i<sz;i++){
if(!f[i]){
for(int j=i;j<sz;j+=i) f[j]++;
}
}
auto get = [&](int x){
int sum = 0;
while(x>0){
sum += x * f[x];
x/=2;
}
return sum;
};
vector<vector<int>> dp(n,vector<int>(n,INT_MAX/2));
for(int i=0;i<n;i++) dp[i][i] = get(a[i]);
for(int len=2;len<=n;len++){
for(int i=0,j=len-1;j<n;i++,j++){
if(a[i] == a[j]) dp[i][j] = min(dp[i][j] , dp[i][i] + ( i+1<=j-1 ? dp[i+1][j-1] : 0 ));
dp[i][j] = min({dp[i][j] , dp[i][i] + dp[i+1][j], dp[i][j-1] + dp[j][j]});
int x = a[i] , y = a[j];
int cost = 0;
while(x && y){
if( x == y ){
dp[i][j] = min(dp[i][j] , cost + get(x) + ( i+1<=j-1 ? dp[i+1][j-1] : 0 ));
break;
}
else if(x > y) cost += x * f[x] , x/=2;
else cost += y * f[y] , y/=2;
}
}
}
cout << dp[0][n-1];
return;
}
int main(){
fastio;
int tc=1; // cin >> tc;
while(tc--) __sol();
return 0;
}