SUB12OP - Editorial

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))
2 Likes

What is the proof that minimizing A[i] & A[i+1] does not affect A[i+2]

1 Like

the fact that they are iterating from the back, so your ai+2 will be countered as they are giving priority to subtracting 2 than 1. that gives it a better answer. i hope that’s the intuition they using for this particular prob.

1 Like

Can the editorialists please remove the unnecessary template part from their code so it’ll be clean to read and understand. +1 for newbies.

12 Likes

The editorialist’s (my) code linked at the bottom has no templates in it whatsoever. In fact, the tester’s code linked for this problem is also quite clean.

In general when I write editorials I will ensure my own code is (for the most part) easy to read so there’s always at least one clean reference.

2 Likes

I solved the problem by greedy approach and my logic is also completely same as the one explained in the editorial but still my code gives WA. Can anyone tell what am I missing?
Link to my submission :- CodeChef

1 Like

1
4
8 4 5 0
your code will output 9 which is not correct

correct ans=8
8 2 1 0 { apply operation on index 2 → 2times }
7 0 1 0{ apply operation on index 1 → 1times }

1 Like

Sir, but why traversing from left to right doesn’t seem reasonable to you ? What is happening from right to left that answer is coming out to be correct in that case only ? Please clarify it with an elaborate proof.

1 Like

check for the test case

1
3
0 2 4

if you traverse from left to right
0 2 4
-1 0 4
-1 -2 0

if you traverse from right to left
0 2 4
0 0 0

2 Likes

can anyone please explain the dp code it’s not clear in editorial .

2 Likes

Can anyone tell what am I missing? https://www.codechef.com/viewsolution/72117674

1 Like

This is a very interesting problem for me.I tried to do the greedy approach during contest but i couldn’t prove it so didn’t submit.Turns out my idea was right,although i’m not really sure how doing the operations in reverse order of the array make the answer correct.I can’t really find where abritary order would be better than reverse.Can somebody help?

2 Likes

can anyone explain what is wrong with my logic. I am simply using a multiset and just storing the elements which are greater than 0 and then in each iteration i am finding the greatest elem along with idx and simply making it either 0 or -1 and changing adjacent elem accordingly and updating the set.
but i am just able to pass 1 test case.

code: CodeChef

1 Like

1
2
2 5

correct ans=1
your ans=2

same doubt friend…
actually i was doing the same thing as in editorial but transversing the array in forward direction but only two tasks passed. but in case of reverse transversal,it paased all the task… and i also want to know why this is going to be always correct?

same question is in my mind…
what’s was your motivation behind reverse transversal of the loop…

The reason why it is suppose to be transversal is because the i+1th element is decreased by 2 in one operation.Naturally,it will be more profitable to actually take care of it first.This is why we need to iterate backwards.

1 Like

i was also doing that but only difference was for loop (int i=0;i<n-1;i++) in this for loop i was also taking care of (i+1)th index first…

okay got it.
thanks for the help.

Can you please elaborate your intuition behind traversal from back? I think with current explanation, if we start from front but change (i + 1) th elements first(subtract 2), this should also work, but it doesn’t.