codeforce 1600

COFO::1671D Insert a Progression

cofo problem

COFO::1671D Insert a Progression

Link : COFO::1671D

Problem

level : 1600
tag : brute force, constructive algorithms, greedy
TIME
- to understand : 10
- to algorithm : 100
- to code : 10
- to debug : 15
- understanding edit : 30

Point

There’s array a
We get ‘x’
insert numbers from 1 to x into array a
Then find smallest sum of absolute differences of adjacent elements of the sequence

Design

It has easy way to solve it, but I solved it as hard way
Let me introduce both ways, the core logic of them is same anyway
Also, the important thing from this problem is that, we can not decrease initial sum of array a
- We only greedly insert numbers from 1 to x into a

hard way(tree-way)

Let’s say that I have an array b starts from 1 ends with x
And every time I check the value a[i] and a[i+1], I erase common values on b
- So, from min(a[i], a[i+1]) to max(a[i], a[i+1]) will be erased from array b
After finishing above operation for i (1 <= i <= n), let’s check array b
Now I need to check array b which should be attached somewhere
Where can it be ?
- It can choose maximum value from the array or the minimum value from the array
  - If I choose this value, then the sum will be added like, 2 * (maximum - b.back())
- It can also choose a[1] or a[n]
  - If I choose this value, then the sum will be added like, abs(a[n] - b.back())
- The reason the first one is multipled by 2 is that it has to go up and down
  - ex) 1 4 7
  - If the b is 5, 4 -> 5 , 5 -> 7 : so 1 * 2 will be added
And I used map to solve as this way

solution(easy-way)

Let’s deeply think about the problem, what’s the point of this problem?
We need to notice that array a has some kind of graph
- And the minimum value will be mn
- The maximum value will be mx
We have numbers from 1 to x, which can be expressed as [1 2 … x]
[1 2 … ] array a [ … x]
- As you can see above status, numbers from array a can be inside of array x
- Then all I need to is that find the length from 1 to mn and mx to x
This it awesome!
And then I can add up the lengths

Complexity

O(N) or O(NlogN)

Code

tree-way

#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i <(b); i++)
#define r_rep(i, a, b) for(int i = (a); i >(b); i--)
typedef long long ll;
using namespace std;
const int MAXN = 2 * 1e5 + 9;

int a[MAXN];
map<int,int> mp;
void solve() {
    mp.clear();
    int n, x; cin >> n >> x;
    
    ll ans = 0;
    int mn = MAXN, mx = -MAXN;
    rep(i, 1, n + 1) {
        cin >> a[i];
        mn = min(mn, a[i]);
        mx = max(mx, a[i]);
        if(i != 1) ans += abs(a[i] - a[i-1]);
    }
    int cnt = (int)count(a + 1, a + n + 1, a[1]);
    if (n == 1 || cnt == n) {
        if (1 <= a[1] && a[1] <= x) cout << (x-1) << '\n';
        else if (a[1] > x) cout << (a[1] - 1) << '\n';
        else {
            cout << "Exception1 on 1\n";
        }
        return;
    }
    
    
    int mn_side = min(a[1], a[n]), mx_side = max(a[1], a[n]);
    mp[-MAXN] = 0;
    mp[MAXN] = MAXN;
    mp[1] = x;
    auto check = [](map<int,int>::iterator it, int le, int ri) {
        int st = it->fi, en = it->se;
        if (st == MAXN || st == -MAXN) return;
        if (st <= le && ri <= en) {
            if (st == le) mp.erase(it);
            else it->se = le - 1;
            if (ri < en) mp[ri + 1] = en;
        }
        else if (le <= en && en <= ri) {
            if (st <= le -1) it->se = le - 1;
            else mp.erase(it);
        }
        else if (le <= st && st <= ri) {
            mp.erase(it);
            if (ri < en) mp[ri + 1] = en;
        }
        else if (le <= st && en <= ri) {
            mp.erase(it);
        }
        else {
			// no common area
        }
    };

    rep(i, 1, n) {
        if (a[i] == a[i+1]) continue;
        int le = min(a[i], a[i+1]);
        int ri = max(a[i], a[i+1]);
        auto itLE = --mp.lower_bound(le);
        auto itRI = mp.lower_bound(le);
        
        check(itLE, le, ri);
        check(itRI, le, ri);
    }
    
    for(auto it = mp.begin(); it != mp.end(); it++) {
        int st = it->fi, en = it->se;
        // st < en
        if (st == MAXN || st == -MAXN) continue;
        if (mx <= st) {
            ll len1 = (en - mx) * 2;
            ll len2 = (mx_side <= st ? en - mx_side : mx_side - st);
            ll len3 = (mn_side <= st ? en - mn_side : mn_side - st);
            ans += min(len1, min(len2, len3));
        } else if (en <= mn) {
            ll len1 = (mn - st) * 2;
            ll len2 = (mx_side <= st ? en - mx_side : mx_side - st);
            ll len3 = (mn_side <= st ? en - mn_side : mn_side - st);
            
            ans += min(len1, min(len2, len3));
        } else {
            cout << "Exception3 on for()\n";
        }
    }
    cout << ans << '\n';
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int tc; cin >> tc; while(tc--)
        solve();
    return 0;
}

best way

#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i <(b); i++)
#define r_rep(i, a, b) for(int i = (a); i >(b); i--)
typedef long long ll;
using namespace std;
const int MAXN = 2 * 1e5 + 9;


void solve() {
    int n, Xmax;
    cin >> n >> Xmax;
    vector<int> A(n);
    for(auto &a : A) cin >> a;
    int Amax = *max_element(all(A));
    int Amin = *min_element(all(A));
    
    int Xmin = 1;
    ll ans = 0;
    rep(i, 0, n - 1) ans += abs(A[i+1] - A[i]);
    
    Amax = min(Xmax, Amax);
    
    if (Amax < Xmax) {
        ans += min(
                   2 * (Xmax - Amax),
                   Xmax - max(A.front(), A.back()));
    }
    if (Amin > Xmin) {
        ans += min(
                   2 * (Amin - Xmin),
                   min(A.front(), A.back()) - Xmin);
    }
    cout << ans << '\n';
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int tc; cin >> tc; while(tc--)
        solve();
    return 0;
}