BALDIFF - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Binary search

PROBLEM:

You’re given an array B that’s sorted in ascending order.
The cost of an array C of the same length is defined to be \max_{i=1}^N |B_i - C_i|.

Find the minimum possible cost of an array C such that:

  1. C is sorted in ascending order.
  2. C_i - C_{i-1} \leq X for all i.

EXPLANATION:

Our cost is the maximum of several pointwise differences; conversely, if we fix the maximum allowed pointwise difference, the set of values allowed at each index forms a contiguous range.

That is, let’s fix M to be the maximum allowed value of |B_i - C_i|.
This essentially means that we’re allowed to choose C_i from the range
[B_i-M, B_i+M].

With M fixed, we’d like to know whether a valid array C exists.
This can be done greedily ^\dagger, by always choosing the highest value available to us.

That is,

  • Choose C_1 = B_1 + M.
  • C_2 is limited by both C_1 + X and B_2 + M, so set it to the minimum of those two upper bounds.
    Note that if C_1+X \lt B_2 - M, there’s no valid choice at this index: either we’ll choose an element that’s more than M away from B_2, or we’ll choose something that’s more than X away from C_1.
  • C_3 is limited by C_2 + X and B_3 + M, set it to the minimum of those.
    Again, if C_2+X \lt B_3-M then no solution exists.
  • In general, set C_i := \min(C_{i-1} + X, B_i + M), and we run into an issue if C_{i-1}+X \lt B_i - M.

When M is fixed, the array C can be constructed easily in linear time; or we can decide that this M is invalid.

Now, note that if M is invalid, M-1 is also invalid.
This means that the smallest valid M can be found using binary search.

Our check for whether M was valid also gave us the construction, so no extra effort is required there.

^\dagger A proof of correctness for the greedy is attached.

Proof of correctness

Suppose we have some solution array C, but C_1 isn’t as large as possible, i.e, not B_1 + M.
Then, for every index i such that C_i \lt B_1 + M, set C_i = B_1 + M.

Since C was already sorted, this operation will affect some prefix of C, and it’ll remain sorted.
It’s easy to see that the C_i - C_{i-1} \leq X condition won’t be broken either:

  • If indices i and i-1 both weren’t changed, they already satisfied the condition since we started with a valid C.
  • If indices i and i-1 both were changed, they both equal B_1 + M now and have a difference of 0.
  • If only index i-1 is changed, it’s value must have increased - and so it moves closer to the value at index i, meaning it cannot break the inequality.

Finally, note that this operation is also valid in terms of elements being valid for their ranges.
This is because, if C_i \lt B_1 + M, then C_i \lt B_i + M as well (since B_1 \leq B_i for any i).
We also already know that C_i \geq B_i - M initially, so after being increased it’ll still satisfy this.

This proves that making C_1 as large as possible is optimal.
Now, apply the same argument to the remaining indices, from 2 to N.

TIME COMPLEXITY:

\mathcal{O}(N\log{10^9}) per testcase.

CODE:

Author'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());
int n, x;
const int N = 2e5 + 69;
int a[N];

bool check(int op){
    int last = a[1] + op;
    for (int i=2; i<=n; i++){
        //set it to highest possible 
        int hi = min(a[i] + op, last + x);
        if (hi < a[i] - op) return false;
        
        last = hi;
    }
    return true;
}

void print(int op){
    a[1] += op;
    for (int i=2; i<=n; i++){
        int hi = min(a[i] + op, a[i-1] + x);
        a[i] = hi;
        assert(a[i] >= a[i-1]);
    }
}

void Solve() 
{
    cin>>n>>x;
    
    for (int i=1; i<=n; i++) cin>>a[i];
    
    int l = 0, r = 1e10;
    while (r != l){
        int mid = (l + r)/2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    
    print(l);
    cout<<l<<"\n";
    for (int i=1; i<=n; i++){
        assert(a[i] >= 0);
        cout<<a[i]<<" \n"[i==n];
    }
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    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;
}
Tester's code (C++) 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case)
{
    ll n,k; cin >> n >> k;
    vector<ll> a(n+5);
    rep1(i,n) cin >> a[i];

    auto ok = [&](ll mid, bool construct){
        auto b = a;
        b[n] -= mid;
        rev(i,n-1,1){
            ll at_least = b[i+1]-k;
            if(b[i] >= at_least){
                b[i] = max(b[i]-mid,at_least);
            }
            else{
                if(abs(b[i]-at_least) > mid){
                    return false;
                }
                b[i] = at_least;
            }
        }

        if(construct){
            rep1(i,n) cout << b[i] << " ";
            cout << endl;
        }

        return true;
    };

    ll lo = 0, hi = 2*inf1;
    ll ans = -1;

    while(lo <= hi){
        ll mid = (lo+hi) >> 1;
        if(ok(mid,0)){
            ans = mid;
            hi = mid-1;
        }
        else{
            lo = mid+1;
        }
    }

    cout << ans << endl;
    ok(ans,1);
}

int main()
{
    fastio;

    int t = 1;
    cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}
Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    lo, hi = 0, 10**9
    while lo < hi:
        mid = (lo + hi)//2
        possible = True
        cur = a[0] + mid
        for i in range(1, n):
            nxt = min(cur + k, a[i] + mid)
            if nxt < a[i] - mid: possible = False
            cur = nxt
        if not possible: lo = mid + 1
        else: hi = mid
    
    print(lo)
    ans = [a[0] + lo]
    for i in range(1, n): ans.append(min(ans[-1] + k, a[i] + lo))
    print(*ans)
2 Likes