PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: nirbhaypaliwal
Tester: wasd2401
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Dynamic programming
PROBLEM:
There are N dominoes arranged in a circle. The i-th has weight W_i and absorption factor K_i.
When domino i is pushed with force F,
- If F \lt W_i, nothing happens.
- Otherwise, domino i falls, and pushes the next domino with a force of W_i + \max(0, F - K_i).
Find the minimum force needed so that pushing a single domino is enough to make all of them fall.
EXPLANATION:
Dealing with circles is a bit annoying, so let’s work on a simpler version first.
Assume all the dominoes are arranged in a line, and we want to find the minimum force with which to push domino 1 so that all N of them fall.
Of course, this can be done by binary searching for the answer and simulating the process for a fixed force in linear time; however, there’s also a way to solve this in \mathcal{O}(N) time with the help of dynamic programming - which we’ll look at because it generalizes to the circular version.
Let dp[u] denote the minimum force that needs to be applied on domino u, so that all the dominoes u, u+1, \ldots, N fall.
Then, we have the following:
- dp[u] should be at least W_u, to cause domino u to fall.
- After domino u falls, the extra force should be enough to cause domino u+1 to fall (meaning the extra force should be at least dp[u+1].
- If W_u \geq dp[u+1], this is automatically satisfied; so dp[u] = W_u
- Otherwise, we need a force F such that F - K_u + W_u \geq dp[u+1] which gives us a lower bound on F.
- So, we get dp[u] = \max(W_u, dp[u+1] + K_u - W_u) in this case.
The answer we’re looking for is, of course, dp[1].
Now, let’s move to a circle.
Let’s fix a domino u, and try to figure out the minimum force we need to make everything fall.
- First, certainly everything from u to N must fall.
We already know how much force this needs: it’s exactly dp[u]. - Next, when domino N falls, it will transfer some force to domino 1.
This must then be enough to cause all the dominoes 1, 2, 3, \ldots, u-1 to fall.
The latter requires us to know information about a prefix, rather than a suffix.
So, let’s attempt to compute that (once again, using DP).
Let dp_2[u] denote the minimum force that needs to be applied on domino 1 so that all the dominoes 1, 2, 3, \ldots, u fall.
Computing this is a bit tricker than the simple suffix DP we had earlier.
How do I do it?
dp_2[1] = W_1, as a base case.
Then, for u \gt 1,
- dp_2[u] should be \geq dp_2[u-1], since making the first u fall must surely make the first u-1 fall.
- Apart from that, enough ‘extra force’ should reach domino u to make it fall.
- In particular, if W_{u-1} \geq W_u, this is automatically satisfied, so dp_2[u] = dp_2[u-1] here.
- More generally, if a force of dp_2[u-1] is applied to domino 1 and u-1 falls with enough to make u also fall, we’ll have dp_2[u] = dp_2[u-1].
However, we need to be able to recognize this (and also decide what to do if this force isn’t enough).
This motivates us to store a bit more information.
So, let E_u denote the force with with domino u pushes u+1, if a force of dp_2[u] is applied on domino 1.
Then,
- If E_{u-1} \geq W_u, we simply have dp_2[u] = dp_2[u-1] and E_u = W_u + \max(0, E_{u-1} - K_u).
- Otherwise, we need to increase the force applied to domino 1.
Notice that the only way this increased force can ever affect domino u is if it never gets ‘zeroed out’ in the middle.
That is, for an applied force F, all of the following inequalities must be true:
If and only if all these inequalities are satisfied, will domino u be pushed with a force of
Note that each constraint is of the form F - C_i \geq 0, where C_i is a constant that depends on indices 1, 2, 3, \ldots, i-1.
All of these C_i can be precomputed in \mathcal{O}(N) using prefix sums.
Now, we need to ensure that F - C_i \geq 0 for all relevant constants C_i; so F should be at least the maximum among them, for it to affect domino u at all.
Apart from that, the force reaching domino u should be \geq W_u; which gives us another lower bound on F.
Together, these give us the minimum possible value of F that will allow domino u to fall.
Further, since F is known, computing E_u is also quite simple (since we know the exact force with which domino u will be pushed).
In this way, we can compute dp_2[u] and E_u for all u from 1 to N in linear time.
We’re now ready to solve the original problem.
If the first domino u is fixed, we know dp[u]: the minimum force needed to make everything till N fall.
We also know dp_2[u-1], the minimum force with which domino 1 needs to be pushed so that everything from 1 to u-1 fall.
The only part remaining is to ensure that when domino N falls, it pushes 1 with a force of at least dp_2[u-1].
This is not too hard to figure out, and indeed similar to how we computed the dp_2 array.
For each u, also store the force with which domino N will fall if u is pushed with a force of dp[u] (which can be computed in similar fashion to how we computed E_u).
If this extra force is at least dp_2[u-1], nothing needs to be done; otherwise, increasing the force applied on u will increase the force with which N falls only if it doesn’t get ‘zeroed out’ before that — which will give you a similar system of inequalities that the force needs to satisfy, this time on a suffix.
If all the arrays dp, dp_2, and the extra forces are precomputed (which takes linear time), a single index can be processed in constant time; so just try them all and take the minimum.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
#define int long long int
signed main()
{
int T;
cin >> T;
while(T--)
{
int n;
cin >> n;
vector<int> a(n+1),k(n+1);
for(int i=0;i<n;i++) cin >> a[i+1];
for(int i=0;i<n;i++) cin >> k[i+1];
vector<int> dp1(n+1);
dp1[n]=a[n];
int suma=a[n];
int sumk=0;
for(int i=n-1;i>=1;i--)
{
if(a[i]>=dp1[i+1]) dp1[i]=a[i];
else dp1[i]=max(dp1[i+1]+k[i]-a[i],a[i]);
}
vector<int> suff(n+1);
suma=a[n];
sumk=0;
suff[n]=a[n];
for(int i=n-1;i>=1;i--)
{
suma+=a[i];
sumk+=k[i+1];
suff[i]=suma-sumk;
suff[i]=max(suff[i],suff[i+1]);
}
vector<int> pref(n+1);
pref[1]=a[1];
for(int i=2;i<=n;i++)
{
pref[i]=max(a[i],pref[i-1]+a[i]-k[i]);
}
// pref[i] denotes this force will surely be applied if 1 to i falls
vector<int> dp2(n+1);
dp2[1]=a[1];
suma=a[1];
sumk=k[1];
for(int i=2;i<=n;i++)
{
if(pref[i-1]>=a[i]){dp2[i]=dp2[i-1];}
else
{
dp2[i]=max(dp2[i-1],a[i]-suma+sumk);
}
suma+=a[i]; // a[i] has fallen
sumk+=k[i];
}
int ans=1e18;
suma=0;
sumk=0;
for(int i=1;i<=n;i++){suma+=a[i];sumk+=k[i];}
for(int i=1;i<=n;i++)
{
int force=1e18;
if(suff[i]>=dp2[i-1])
{
force=dp1[i];
}
else
{
force=dp2[i-1]-suma+sumk;
force=max(force,dp1[i]);
}
suma-=a[i];
sumk-=k[i];
ans=min(ans,force);
// cout << force << ' ';
}
// cout << endl;
cout << ans <<endl;
}
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n; cin >> n;
// n^2 idea :
// do over all starts
// dp[i] = pair of minimum force on 1 to fall 1...i and the resultant force exerted by i then
// if force is greater than weight of (i + 1) good
// otherwise we need to exert extra force to make sure that (i + 1) topples
// extra force only influences when it never goes below 0, i.e F - k[1] >= 0,
// F - k[1] + A[1] - k[2] >= 0, ....
// so F = max(pk[j] - pa[j - 1]) for all k < i
// if current F is already this value, good
// otherwise make it this value
// Optimizations :
// every setup contains a suffix and a prefix
// calculate dps in both suffix and prefix
// then do the same thing
// suffix dp should be possible to calculate as well
vector <int> w(n), k(n);
for (auto &x : w) cin >> x;
for (auto &x : k) cin >> x;
vector <pair<int, int>> dp(n);
{
dp[0] = {w[0], w[0] + max(0LL, w[0] - k[0])};
int mx = 0, ok = 0;
int add = 0;
// cout << dp[0].first << " " << dp[0].second << "\n";
for (int i = 1; i < n; i++){
ok += k[i - 1];
if (i != 1) ok -= w[i - 2];
mx = max(mx, ok);
add += w[i - 1] - k[i - 1];
if (dp[i - 1].second >= w[i]){
dp[i].first = dp[i - 1].first;
dp[i].second = w[i] + max(0LL, dp[i - 1].second - k[i]);
} else {
int need = w[i] - dp[i - 1].second;
dp[i].first = max(dp[i - 1].first, mx) + need;
// never dipped below 0 till date => force on i can be written as
// F - k[1] + w[1] - k[2] + w[2]
dp[i].second = w[i] + max(0LL, dp[i].first + add - k[i]);
}
}
}
int ans = dp[n - 1].first;
// cout << ans << "\n";
vector <int> sufdp(n), eff(n);
// sufdp[i] = minimum force to fall i.. n - 1, and resulting effect
vector <int> holy(n);
// minimum force such that its effects act on 1
{
sufdp[n - 1] = w[n - 1];
eff[n - 1] = w[n - 1] + max(0LL, w[n - 1] - k[n - 1]);
holy[n - 1] = k[n - 1];
int sum = w[n - 1] - k[n - 1];
for (int i = n - 2; i >= 0; i--){
// need to create sufdp[i + 1] at i + 1
holy[i] = max(holy[i + 1] + k[i] - w[i], k[i]);
if (w[i] >= sufdp[i + 1]){
sufdp[i] = w[i];
} else {
sufdp[i] = max(w[i], k[i] + sufdp[i + 1] - w[i]);
}
int force = w[i] + max(0LL, sufdp[i] - k[i]);
// cout << force << " " << sufdp[i] << " " << sum << "\n";
if (force < holy[i + 1]){
// cant create any extra effects
eff[i] = eff[i + 1];
} else {
// eff[i] = force - sumk[i] + sumw[i]
eff[i] = force + sum;
}
sum += w[i];
sum -= k[i];
}
}
// for (int i = 0; i < n; i++){
// cout << sufdp[i] << " " << eff[i] << " " << holy[i] << "\n";
// }
for (int i = n - 1; i >= 1; i--){
// solve i...n - 1 suffix and then 0...i - 1 prefix
int force = sufdp[i];
int effect = eff[i];
// cout << sufdp[i] << " " << eff[i] << "\n";
if (effect >= dp[i - 1].first){
} else {
force = max(force, holy[i]);
force += dp[i - 1].first - effect;
}
// cout << force << "\n";
ans = min(ans, force);
}
cout << ans << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}