PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Ashish Gangwar
Preparer: Anton Trygub
Tester: Harris Leung
Editorialist: Nishank Suresh
DIFFICULTY:
1991
PREREQUISITES:
Greedy and/or dynamic programming
PROBLEM:
You have an array A. In one move, you can choose an index i, subtract 1 from A_i, and subtract 2 from A_{i+1}. Find the minimum possible value of |A_1| + |A_2| + \ldots + |A_N| after performing some operations.
EXPLANATION:
This problem can be solved with dynamic programming, though a greedy solution exists as well.
Both solutions use the fact that it is natural to think of iterating from the back to the front (i.e, from N to 1, since reducing some A_i by 2 is ‘better’ than reducing it by 1)
Dynamic programming
First, there’s a fairly simple slow solution that comes to mind:
Let dp_{i, x} denote the minimum possible sum of |A_i| + |A_{i+1}| + \ldots + |A_N|, assuming that exactly x operations are performed on index i (i.e, subtract x from A_i and 2x from A_{i+1}).
dp_{i, x} can be easily computed from dp_{i+1, y}, since we know the values of |A_i| and |A_{i+1}| after knowing x and y (and the contribution of elements at positions greater than i+1 will be contained in dp_{i+1, y}. Of course, this solution is much too slow.
To optimize it, note the following when we are at position i:
- If A_{i+1} \leq 0, it is better to not perform any operation on position i, since our ‘profit’ for each operation performed is always going to be negative
- If A_{i+1} \gt 0, it is optimal to reduce it to either 1, 0, or -1. This is because our profit for these moves is always non-negative
So, for each dp_{i+1, y}, there are at most 3 values of x whose dp_{i, x} needs to be considered. In fact, it is at most two values: if y is even, only x = y/2 needs to be considered, and if y is odd, only x = \lfloor\frac{y}{2}\rfloor and \lceil\frac{y}{2}\rceil need to be considered (bringing y down to 1 and -1, respectively).
This ensures that the total number of states is linear, and transitions are now essentially constant time. So, the whole process runs in \mathcal{O}(N) (or \mathcal{O}(N\log N) if implemented with maps).
Greedy
The following greedy also passes all the tests (though I do not have a formal proof of its correctness, other than the fact that ‘it seems reasonable’).
- Iterate i from N to 2.
- If A_i \leq 0, do nothing
- If A_i \gt 0, bring it down to either 1 or 0 (depending on parity) by performing the appropriate number of moves on position i-1.
- Once the above is done, once again iterate i from N to 2
- If A_i = 1 and A_{i-1} \gt 0, use one operation on position i-1
Now print |A_1| + |A_2| + \ldots + |A_N|.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Preparer's code (C++, dp)
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
using ld = long double;
typedef tree<
pair<int, int>,
null_type,
less<pair<int, int>>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
#define mp make_pair
int MOD = 998244353;
int mul(int a, int b) {
return (1LL * a * b) % MOD;
}
int add(int a, int b) {
int s = (a+b);
if (s>=MOD) s-=MOD;
return s;
}
int sub(int a, int b) {
int s = (a+MOD-b);
if (s>=MOD) s-=MOD;
return s;
}
int po(int a, ll deg)
{
if (deg==0) return 1;
if (deg%2==1) return mul(a, po(a, deg-1));
int t = po(a, deg/2);
return mul(t, t);
}
int inv(int n)
{
return po(n, MOD-2);
}
mt19937 rnd(time(0));
const int LIM = 1000005;
vector<int> facs(LIM), invfacs(LIM), invs(LIM);
void init()
{
facs[0] = 1;
for (int i = 1; i<LIM; i++) facs[i] = mul(facs[i-1], i);
invfacs[LIM-1] = inv(facs[LIM-1]);
for (int i = LIM-2; i>=0; i--) invfacs[i] = mul(invfacs[i+1], i+1);
for (int i = 1; i<LIM; i++) invs[i] = mul(invfacs[i], facs[i-1]);
}
int C(int n, int k)
{
if (n<k) return 0;
if (n<0 || k<0) return 0;
return mul(facs[n], mul(invfacs[k], invfacs[n-k]));
}
struct DSU
{
vector<int> sz;
vector<int> parent;
void make_set(int v) {
parent[v] = v;
sz[v] = 1;
}
int find_set(int v) {
if (v == parent[v])
return v;
return find_set(parent[v]);
}
void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (sz[a] < sz[b])
swap(a, b);
parent[b] = a;
sz[a] += sz[b];
}
}
DSU (int n)
{
parent.resize(n);
sz.resize(n);
for (int i = 0; i<n; i++) make_set(i);
}
};
void print(vector<int> a)
{
for (auto it: a) cout<<it<<' ';
cout<<endl;
}
/*const int mod = 998244353;
template<int mod>
struct NTT {
static constexpr int max_lev = __builtin_ctz(mod - 1);
int prod[2][max_lev - 1];
NTT() {
int root = find_root();//(mod == 998244353) ? 31 : find_root();
int rroot = power(root, mod - 2);
vector<vector<int>> roots(2, vector<int>(max_lev - 1));
roots[0][max_lev - 2] = root;
roots[1][max_lev - 2] = rroot;
for (int tp = 0; tp < 2; ++tp) {
for (int i = max_lev - 3; i >= 0; --i) {
roots[tp][i] = mul(roots[tp][i + 1], roots[tp][i + 1]);
}
}
for (int tp = 0; tp < 2; ++tp) {
int cur = 1;
for (int i = 0; i < max_lev - 1; ++i) {
prod[tp][i] = mul(cur, roots[tp][i]);
cur = mul(cur, roots[tp ^ 1][i]);
}
}
}
template<bool inv>
void fft(int *a, int lg) const {
const int n = 1 << lg;
int pos = max_lev - 1;
for (int it = 0; it < lg; ++it) {
const int h = inv ? lg - 1 - it : it;
const int shift = (1 << (lg - h - 1));
int coef = 1;
for (int start = 0; start < (1 << h); ++start) {
for (int i = start << (lg - h); i < (start << (lg - h)) + shift; ++i) {
if (!inv) {
const int y = mul(a[i + shift], coef);
a[i + shift] = a[i];
inc(a[i], y);
dec(a[i + shift], y);
} else {
const int y = mul(a[i] + mod - a[i + shift], coef);
inc(a[i], a[i + shift]);
a[i + shift] = y;
}
}
coef = mul(coef, prod[inv][__builtin_ctz(~start)]);
}
}
}
vector<int> product(vector<int> a, vector<int> b) const {
if (a.empty() || b.empty()) {
return {};
}
const int sz = a.size() + b.size() - 1;
const int lg = 32 - __builtin_clz(sz - 1), n = 1 << lg;
a.resize(n);
b.resize(n);
fft<false>(a.data(), lg);
fft<false>(b.data(), lg);
for (int i = 0; i < n; ++i) {
a[i] = mul(a[i], b[i]);
}
fft<true>(a.data(), lg);
a.resize(sz);
const int rn = power(n, mod - 2);
for (int &x : a) {
x = mul(x, rn);
}
return a;
}
private:
static inline void inc(int &x, int y) {
x += y;
if (x >= mod) {
x -= mod;
}
}
static inline void dec(int &x, int y) {
x -= y;
if (x < 0) {
x += mod;
}
}
static inline int mul(int x, int y) {
return (1LL * x * y) % mod;
}
static int power(int x, int y) {
if (y == 0) {
return 1;
}
if (y % 2 == 0) {
return power(mul(x, x), y / 2);
}
return mul(x, power(x, y - 1));
}
static int find_root() {
for (int root = 2; ; ++root) {
if (power(root, (1 << max_lev)) == 1 && power(root, (1 << (max_lev - 1))) != 1) {
return root;
}
}
}
};
NTT<mod> ntt;
*/
void solve()
{
int n; cin>>n;
vector<int> a(n); for (int i = 0; i<n; i++) cin>>a[i];
map<int, ll> cur;
cur[a[n-1]] = 0;
for (int i = n-2; i>=0; i--)
{
map<int, ll> tmp;
for (auto it: cur)
{
vector<int> cases;
if (it.first<=0) cases.push_back(0);
else
{
if (it.first%2 == 0) cases.push_back(it.first/2);
else
{
cases.push_back(it.first/2);
cases.push_back(it.first/2 + 1);
}
}
for (auto cand: cases)
{
int new_val = a[i] - cand;
ll new_sum = it.second + abs(it.first - 2*cand);
if (tmp.find(new_val) == tmp.end()) tmp[new_val] = new_sum;
else tmp[new_val] = min(tmp[new_val], new_sum);
}
}
cur = tmp;
}
ll res = 1e18;
for (auto it: cur) res = min(res, abs(it.first) + it.second);
cout<<res<<endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int t; cin>>t;
while (t--) solve();
}
/*
2
5
1 1 1 1 1
6
-4 2 -4 2 -4 2
*/
Tester's code (C++, greedy)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int N=2e5+1;
ll n,k;
ll a[N];
void solve(){
cin >> n;
for(int i=1; i<=n ;i++){
cin >> a[i];
}
for(int i=n; i>=2 ;i--){
if(a[i]>0){
ll k=a[i]/2;
a[i-1]-=k;
a[i]-=2*k;
}
}
for(int i=n; i>=2 ;i--){
if(a[i-1]>0 && a[i]>0){
a[i-1]--;a[i]-=2;
}
}
ll ans=0;
for(int i=1; i<=n ;i++){
ans+=abs(a[i]);
}
cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;while(t--) solve();
}
Editorialist's code (Python, greedy)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in reversed(range(1, n)):
if a[i] > 0:
moves = a[i]//2
a[i] -= 2*moves
a[i-1] -= moves
for i in reversed(range(1, n)):
if a[i] > 0 and a[i-1] > 0:
a[i] -= 2
a[i-1] -= 1
print(sum(abs(x) for x in a))