PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Yuriy Fedorov
Tester: Aryan
Editorialist: Taranpreet Singh
DIFFICULTY
Easy-Medium
PREREQUISITES
Binary search and Dynamic Programming
PROBLEM
Complicated problem description, refer problem statement.
QUICK EXPLANATION
- We can binary search on the minimum time needed to distribute dakimakuras. Now, we have to check if we can distribute dakimakuras in time T or not.
- The whole city shall be partitioned into segments [L_1,R_1], [L_2, R_2], \ldots [L_K, R_K] where all cities in segment [L_i, R_i] are served by a branch at city R_i. Each segment operates independent of other.
- Let’s compute f(L, R, T) as the minimum productivity needed at a branch at city R to serve all cities from L to R within time T.
- We can use dynamic programming within each iteration of binary search. Specifically, DP_i = min_j(DP_{j-1} + f(j, i, T))
EXPLANATION
We can see in this problem that there’s no immediate way to approach the problem, no equations, no parameters within range to brute force.
Binary Search on Minimum Time Needed
But we can notice the fact that there exists some time T such that it is possible to distribute dakimakuras in time T' \geq T with cost up to X and it is not possible to distribute in time T' \lt T. We need to compute this T with a cost up to X.
As the conditions for binary search are satisfied, we can run a binary search.
Now, the problem becomes, given time T, compute the minimum cost of opening branches to distribute dakimakuras in time T.
Minimum Cost to distribute dakimakuras in time T
Let’s focus on the distribution system now. Let’s assume branches are open at cities c_1, c_2 \ldots c_k.
We can see that these branches divide the whole city into segments [1, c_1], [c_1+1, c_2] \ldots [c_{k-1}+1, c_k], where cities in segment [c_{i-1}+1, c_i] are served by branch in city c_i.
Let us compute F(x) as the minimum cost of opening branches such that all people are served in the first x cities within time T and there’s a branch in the city x. We are looking to compute F(N). Also, we have F(0) = 0
Now, if we open a branch in city x, and the previous branch was opened in city y, then the cost to serve people in the first x cities can be written as F(y) + f(x+1, y, T) where f(l, r, T) denotes the minimum productivity needed at the branch at city r to serve all people in cities [l, r] within time T
Hence, we have the DP transition \displaystyle F(x) = \min_y (F(y-1) + f(y, x, T))
The problem now reduces to computing f(l, r, T)
Minimum cost to serve a range of cities
Now, we have an interval [l, r], only one branch at city r, and time T, we want to find minimum productivity to serve all people in these cities within time T.
One decent way to proceed is to binary search on productivity, which is a valid idea, but the time complexity goes too high in that case.
We can see that now we have pair (C_1, T_1), (C_2, T_2) \ldots (C_K, T_K) where K = r-l+1 and T_i \lt T_{i+1} denoting that C_i people reach city r at time T_i, and we need to find minimum productivity to serve them in time T.
Now, it is possible that sometimes branch may serve some people, then have to wait for people to arrive, and then again serve people and so on. Whenever the queue is non-empty, it is optimal to serve rather than not.
Let’s assume we need to process X people in time T, which imply that productivity must be at least \displaystyle \left\lceil \frac{X}{T} \right\rceil .
Let’s suppose, tuple (C_x, T_x) is the last tuple, before which branch had to wait for the people to arrive. Calling such tuple as the special tuple.
All people in tuples before are already served. Current time is T_x, so the minimum productivity at which all would be served within time T, would be \displaystyle \frac{\sum_{j = x}^K C_i}{T - T_x}. Intuitively, you can think of it as wait for T_i time, and then you have to serve \displaystyle \sum_{j = i}^K C_j people in time T - T_i time.
Hence, let’s consider each tuple (C_i, T_i) as the special tuple and compute compute \displaystyle \left\lceil \frac{\displaystyle\sum_{j = i} C_j}{T - T_i}\right\rceil. We can now simply take maximum value of productivity needed.
Conclusion
Hence, we do a binary search on time, compute a minimum number of coins needed to serve in time T, Divide the cities into segments where each segment is processed by the rightmost city of the segment, and computed the minimum cost needed to set up a branch at the right end of the segment.
TIME COMPLEXITY
Initial binary search takes O(log(MAX)) time. There are O(N^2) transitions, leading to N^2 calls to f(l, r, T) function. Function f works in O(N) time, leading to overall time complexity O(N^3 * log(MAX)) per test case. disten
SOLUTIONS
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18 + 228;
long long calc(int i, int j, vector<long long> &sum_c, vector<long long> &sum_t, long long val) {
long long tmp_val = 0;
if (sum_c[i + 1] - sum_c[j] == 0)
return 0;
if (sum_t[i] - sum_t[j] >= val)
return inf;
for (int k = j; k <= i; ++k) {
long long s1 = sum_c[k + 1] - sum_c[j], s2 = sum_t[i] - sum_t[k];
tmp_val = max(tmp_val, (s1 + val - s2 - 1) / (val - s2));
}
return tmp_val;
}
bool check(int n, int x, vector<int> &c, vector<int> &t, long long val) {
vector<long long> dp(n + 1, inf);
vector<long long> sum_c(n + 1);
vector<long long> sum_t(n);
for (int i = 0; i < n; ++i) {
sum_c[i + 1] = c[i] + sum_c[i];
if (i != n - 1)
sum_t[i + 1] = t[i] + sum_t[i];
}
dp[0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= i; ++j) {
dp[i + 1] = min(dp[i + 1], dp[j] + calc(i, j, sum_c, sum_t, val));
}
}
return dp.back() <= x;
}
void solve() {
int n, x;
cin >> n >> x;
vector<int> c(n), t(n - 1);
for (int i = 0; i < n; ++i)
cin >> c[i];
for (int i = 0; i < n - 1; ++i)
cin >> t[i];
long long l = -1, r = inf;
while (r - l > 1) {
long long mid = (l + r) / 2;
if (check(n, x, c, t, mid))
r = mid;
else
l = mid;
}
cout << r << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
int t;
cin >> t;
while (t--)
solve();
}
Tester's Solution
/* in the name of Anton */
/*
Compete against Yourself.
Author - Aryan (@aryanc403)
Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/
#ifdef ARYANC403
#include <header.h>
#else
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize ("-ffloat-store")
#include<bits/stdc++.h>
#define dbg(args...) 42;
#endif
using namespace std;
#define fo(i,n) for(i=0;i<(n);++i)
#define repA(i,j,n) for(i=(j);i<=(n);++i)
#define repD(i,j,n) for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"
typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;
const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
cerr<<"Time Taken : "<<diff.count()<<"\n";
#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;
}
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,' ');
}
void readEOF(){
assert(getchar()==EOF);
}
vi readVectorInt(int n,lli l,lli r){
if(n==0){
readStringLn(0,0);
return {};
}
vi a(n);
for(int i=0;i<n-1;++i)
a[i]=readIntSp(l,r);
a[n-1]=readIntLn(l,r);
return a;
}
const lli INF = 1e12;
lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}
class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{ return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y )); }};
void add( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt==m.end()) m.insert({x,cnt});
else jt->Y+=cnt;
}
void del( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt->Y<=cnt) m.erase(jt);
else jt->Y-=cnt;
}
bool cmp(const ii &a,const ii &b)
{
return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}
const lli mod = 1000000007L;
// const lli maxN = 1000000007L;
int main(void) {
ios_base::sync_with_stdio(false);cin.tie(NULL);
// freopen("txt.in", "r", stdin);
// freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
lli T=readIntLn(1,5);
while(T--)
{
const lli n=readIntSp(2,100);
const lli maxTugriks=readIntLn(1,1e9);
auto a=readVectorInt(n,0,1e9);
const auto e=readVectorInt(n-1,1,1e9);
// reverse(all(a));a.pb(0);reverse(all(a));
vi tt(n+1),a_sum(n+1);
for(lli i=0;i+1<n;++i){
tt[i+2]=e[i]+tt[i+1];
}
for(lli i=0;i<n;++i)
a_sum[i+1]=a_sum[i]+a[i];
dbg(a,e,tt,a_sum);
auto checkCostRange = [&](lli l,lli r,lli tugriks){
for(lli i=r;i>=l;--i){
if(a[i]&&tugriks==0)
return INF;
}
if(tugriks==0)
return 0LL;
lli ans=0;
lli c=0,t=0;
for(lli i=r;i>=l;--i)
{
const lli delta = min((c+tugriks-1)/tugriks,tt[r]-tt[i]-t);
if(c)
ans=max(ans,t+delta);
c=max(0LL,c-delta*tugriks);
t=tt[r]-tt[i];
c+=a[i];
dbg(c,t);
}
if(c)
{
const lli delta = (c+tugriks-1)/tugriks;
ans=max(ans,t+delta);
t+=delta;
}
return ans;
};
auto findCost=[&](lli l,lli r,lli maxTime){
if(checkCostRange(l,r,INF)>maxTime)
return INF;
lli LT = -1, RT = INF;
while(RT-LT>1){
const lli MT = (LT+RT)/2;
if(checkCostRange(l,r,MT)<=maxTime)
RT=MT;
else
LT=MT;
}
return RT;
};
auto findCost2=[&](lli l,lli r,lli maxTime){
if(a_sum[r]==a_sum[l-1])
return 0LL;
if(tt[r]-tt[l]>=maxTime)
return INF;
lli ans=0;
for(lli i=l;i<=r;++i){
const lli c=a_sum[i]-a_sum[l-1],t= maxTime - (tt[r]-tt[i]);
ans=max(ans,(c+t-1)/t);
}
return ans;
};
auto chkTime=[&](lli maxTime){
vi dp(n+1,INF);
dp[0]=0;
for(lli r=1;r<=n;++r)
for(lli l=1;l<=r;++l)
dp[r]=min(dp[r],dp[l-1]+findCost2(l,r,maxTime));
return dp[n]<=maxTugriks;
};
{
lli L=-1,R=INF;
while(R-L>1){
const lli M = (L+R)/2;
if(chkTime(M))
R=M;
else
L=M;
}
cout<<R<<endl;
}
} aryanc403();
readEOF();
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class DAKIMAKU{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni();
long X = nl();
long[] C = new long[1+N], T = new long[1+N];
for(int i = 1; i<= N; i++)C[i] = nl();
for(int i = 1; i<= N-1; i++)T[i] = nl();
long lo = 1, hi = (long)1e18;
while(lo < hi){
long mid = lo+(hi-lo)/2;
if(cost(N, C, T, mid) <= X)hi = mid;
else lo = mid+1;
}
pn(hi);
}
//Minimum cost to ensure delivery in time X
long cost(int N, long[] C, long[] T, long ti){
long[] DP = new long[1+N];//DP[i] = Minimum coins needed for first i cities, if there's a branch at city i
Arrays.fill(DP, Long.MAX_VALUE/2);
DP[0] = 0;
for(int i = 1; i<= N; i++){
List<long[]> list = new ArrayList<>();
long dist = 0;//, sum = 0;
for(int j = i; j> 0; j--){
//[j, i] are dealt by a branch at city i
if(C[j] > 0)list.add(new long[]{C[j], dist+1});
dist += T[j-1];
DP[i] = Math.min(DP[i], DP[j-1] + minProductivityNeeded(list, ti));
}
}
return DP[N];
}
//finding the minimum productivity needed to serve all people upto maxTime
long minProductivityNeeded(List<long[]> people, long maxTime){
long minProd = 0;
long sum = 0;
for(int i = people.size()-1; i >= 0; i--){
sum += people.get(i)[0];
long ti = people.get(i)[1];
if(ti > maxTime)return Long.MAX_VALUE/2;//T <= Ti
long di = (maxTime-ti+1);
//sum = sum C[k] for i <= k <= j
minProd = Math.max(minProd, (sum+di-1)/di);
}
return minProd;
}
//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 DAKIMAKU().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;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 