PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Hasan Jaddouh
Tester: Joud Zouzou
Editorialist: Taranpreet Singh
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming, Pointers and Observations.
PROBLEM:
There are N piles of meals numbered from 1 to N where there are A_i meals in pile i. You can either move the meals at the current pile to its adjacent position incurring cost A_i or cook all the meals at the current pile, costing X (calling it COOK operation). Find the minimum cost to cook all the meals.
QUICK EXPLANATION
- Suppose for segment [L, R], we have to use COOK operation only once. Lets call position p, L \leq p \leq R as optimal position, if we perform COOK operation at position p.
- We can prove that if for segment [L, R], position p is optimal, then for segment [L, R+1] only any position q \geq p can be optimal.
- Using second observation, we can start from segment [L, L] and maintain a pointer to an optimal position in the current segment. We can keep extending the interval to the right and computing optimal position after each extension by keeping track of the number of meals from L to p and the number of meals from mid+1 to R if we are considering interval [L, R].
- Computing cost of each interval, we can run a basic DP to cover whole segment [1, N] in minimum cost.
EXPLANATION
FIrst of all, Let us assume that we can apply COOK operation at only one pile. This means, that firstly we move all the meals to a single position and then apply COOK operation. The cost of COOK operation is independent of the positon, so, in order to minimize the total cost, we just need to minimize the cost of moving meals from all piles to a single pile.
Let us say that we have computed the cost of cooking all meals in segment [L, R-1] and the optimal position is p. Now, extending this interval to [L, R], it shall add (R-p)*A_R to the cost. Now, If we try p+1 as the optimal position, we can see, that all piles in range [L, p] have to be moved one more step, increasing the cost by A_L+A_{L+1}+\ldots A_p. Also, all piles to the right of p have to be moved one less step, reducing the cost by A_{p+1}+A_{p+2}+\ldots +A_R.
We can see, that as p moves to the right, A_L+A_{L+1}+\ldots A_p increases and A_{p+1}+A_{p+2}+\ldots +A_R decreases. This means, that at a point, the reduction in overall cost by moving to next position would at one time, become less than the increase in cost due to piles on the left. It happens when we have reached the optimal position. It is the first position where moving one step to right increases the cost. This way, we have found the minimum cost for segment [L, R] from the cost for segment [L, R-1] if we know the optimal position for segment [L, R-1]. We also know, that for a segment [L, L], cost is zero and optimal position is L itself.
Above allows us to compute for each segment, the minimum cost to move all piles to a single pile, by trying left ends of the segments and extending intervals to the right.
Coming back to problem, we can see that for the original [1, N] segment of piles, we divide it into K subsegments where K is the number of times COOK operation is applied. Now it is a simple dynamic programming problem where given cost to cover various segments [l, r] find minimum cost to cover the whole segment [1, N]. If facing issue with recurrence, see the hidden text.
DP recurrence
dp(p) = min(dp(q-1) + cost(q, p)+ X) for q <= p where dp(p) denote minimum cost to cover first p positions and cost(l,r) denote cost of covering segment [l, r]. dp(0) = 0 and Required answer is dp(n).
Solution still getting WA? See the edge case.
Edge Case
All piles are empty. Total cost incurred should be zero.
TIME COMPLEXITY
Time complexity is O(N^2) per test case.
SOLUTIONS:
Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
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){
assert(cnt>0);
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 T;
int n,x;
int sm_n=0;
long long arr[5050];
long long best[5050][5050];
long long dp[5050];
int main(){
T=readIntLn(1,1000);
while(T--){
n=readIntSp(1,5000);
x=readIntLn(1,1000000000);
sm_n += n;
assert(sm_n<=20000);
bool chk=true;
for(int i=1;i<=n;i++){
if(i==n){
arr[i]=readIntLn(0,1000000000);
} else {
arr[i]=readIntSp(0,1000000000);
}
if(arr[i]>0)chk=false;
}
if(chk){
cout<<0<<endl;
continue;
}
for(int i=1;i<=n;i++){
long long cost =0;
long long left = arr[i];
long long right = 0;
best[i][i]=0;
int mid = i;
for(int j=i+1;j<=n;j++){
cost += (j- mid) * arr[j];
right += arr[j];
while(left < right ){
cost += left - right;
left += arr[mid+1];
right -= arr[mid+1];
mid ++ ;
}
best[i][j] = cost;
}
}
for(int i=1;i<=n;i++){
dp[i]= 1ll<<60;
for(int j=0;j<i;j++){
dp[i]= min(dp[i],dp[j] + best[j+1][i] + x);
}
}
cout<<dp[n]<<endl;
}
assert(getchar()==-1);
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
long long dp[5001];
long long a[5001];
long long pre[5001];
long long get(int l,int r)
{
if (l>r)return 0;
else return pre[r]-pre[l-1];
}
int main()
{
int t;
cin>>t;
while(t--)
{
long long X;
int n;
cin>>n>>X;
long long sum=0;
for (int i=1;i<=n;i++)
cin>>a[i],sum+=a[i],pre[i]=pre[i-1]+a[i];
dp[0] = 0;
for (int i=1;i<=n;i++)
{
long long cost = 0;
int id = i;
dp[i]=1e18;
for (int j=i;j>=1;j--)
{
cost += a[j]*(id-j+0LL);
while(id>j)
{
long long newCost = cost + get(id,i) - get(j,id-1);
if (newCost<cost) cost = newCost, id--;
else break;
}
dp[i] = min(dp[i],cost+X+dp[j-1]);
}
}
if (sum==0)dp[n]=0;
cout<<dp[n]<<endl;
}
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
public class Main{
//SOLUTION BEGIN
//This code is not meant for understanding, proceed with caution
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni();long x = nl();
long[] a = new long[1+n];
long sum = 0;
for(int i = 1; i<= n; i++){
a[i] = nl();
sum+=a[i];
}
if(sum==0){
pn(0);
return;
}
long[][] cost = new long[1+n][1+n];
for(int left = 1; left<= n; left++){
int mid = left;
long lsum = a[mid], rsum = 0;
cost[left][left] = 0;
long current = 0;
for(int right = left+1; right<= n; right++){
current+=(right-mid)*a[right];
rsum+=a[right];
while(lsum<rsum){
current+=lsum-rsum;
lsum+=a[mid+1];
rsum-=a[mid+1];
mid++;
}
cost[left][right] = current;
}
}
long[] ans = new long[1+n];
Arrays.fill(ans, IINF);
ans[0] = 0;
for(int right = 1; right <= n; right++)
for(int left = 1; left<= right; left++)
ans[right] = Math.min(ans[right], ans[left-1]+cost[left][right]+x);
pn(ans[n]);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
long mod = (long)1e9+7, IINF = (long)1e18;
final int INF = (int)1e9, MX = (int)2e5+1;
DecimalFormat df = new DecimalFormat("0.00000000000");
double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
static boolean multipleTC = true, memory = false;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
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{
if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
else new Main().run();
}
long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
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;
}
}
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 