ALTUNI - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Author:
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Binary search

PROBLEM:

In an alternate universe, Codechef’s rating system works as follows:
Your rating starts at R = R_0 for some R_0 of your choice.
Then, N contests happen. In the i-th contest, if R \leq A_i, you can choose to increase it by any integer in [0, B_i]; otherwise it remains the same.
Then, R decreases by 1 (irrespective of whether it was updated in the previous step or not).

If R ever falls below 0, you are banned from the site.
Find the minimum possible value of R_0 such that there exists a way to participate in all N contests and not get banned.

EXPLANATION:

Given that the aim is to minimize R_0, your first instinct might be to perhaps binary search on the value of R_0, and try to figure out a way to optimally simulate contests for a fixed starting value.
However, this won’t quite work: it’s not always true that increasing R_0 won’t make things worse.

For instance, consider A = [1, 0, 0] and B = [100, 0, 0].
With R_0 = 1 you can add 100 to your rating and be safe for the next two contests. However, with R_0 = 2, this option is no longer available; and you’ll be forced to have a rating of -1 in the end.

However, it is still possible to solve this problem with binary search, by modifying the predicate a bit.
Instead of checking whether it’s possible to participate in all contests with a starting rating of exactly X (i.e. R_0 = X), let’s check if it’s possible to participate in all contests with a starting rating of at most X (i.e. R_0 \leq X).

Let’s look at the first contest, with parameters A_1 and B_1.
Our current rating is now anywhere between 0 and X.
There are two possibilities:

  1. Do nothing here, in which case our rating will decrease by 1.
    This allows us to get to every rating till X - 1.
  2. If our rating is at most A_1, we can add any value between 0 and B_1 to it; and then decrease it by 1.
    This allows us to get every rating till \min(X, A_1) + B_1 - 1.

So, after the first contest, our rating can be anywhere between 0 and
\max(X, \min(X, A_1) + B_1) - 1.
If the latter quantity is \lt 0, it means there’s no valid rating for us to be at - so any starting rating \leq X is invalid.
Otherwise, observe that we once again have a contiguous range of possible ratings starting from 0, so we can simply apply the same logic to the second contest, then the third, and so on.

That is, we now have the following algorithm to check whether a starting rating \leq X is valid:

  1. Initialize C = X.
  2. For each i = 1, 2, 3, \ldots, N,
    • Set C \to \max(C, \min(C, A_i) + B_i) - 1.
    • If C \lt 0, stop immediately and report that no starting rating \leq X is valid.
    • If all N contests are processed successfully, the answer is \leq X.

So, a single predicate check can be done quite simply in linear time.
All we need to do now is choose the appropriate bounds for the search.
This is quite easy though: 0 is clearly the lower bound, and N can be chosen as the upper bound - after all, with a starting rating of N we can simply participate in all N contests without ever having to worry about increasing rating.

This gives us a solution in \mathcal{O}(N\log N).

TIME COMPLEXITY:

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

CODE:

Author's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        vector<ll> a(n),b(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        for(ll i=0;i<n;i++) cin>>b[i];
        vector<ll> v,v1,v2;
        for(ll i=n-1;i>=0;i--){
            if(b[i]>0){
                v.push_back(i);
                v1.push_back(a[i]);
                v2.push_back(b[i]);
            }
        }
        v.push_back(0);
        v1.push_back(0);
        v2.push_back(0);
        ll ans=n;
        for(ll i=0;i<(ll)v.size();i++){
            ans-=v[i];
            if(i-1>=0) ans+=v[i-1];
            ll val=0;
            if(ans-v2[i]<=v1[i]) val=v2[i];
            ans=max((ll)0,ans-val);
        }
        cout<<ans<<"\n";
    }
}
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; cin >> n;
    vector<ll> a(n+5), b(n+5);
    rep1(i,n) cin >> a[i];
    rep1(i,n) cin >> b[i];

    auto ok = [&](ll mid){
        ll l = 0, r = mid;
        rep1(i,n){
            ll l2 = l, r2 = r;
            ll mxleq = -inf2;
            if(r < a[i]) mxleq = r;
            else if(l <= a[i]) mxleq = a[i];
            amax(r2,mxleq+b[i]);
            l2--, r2--;
            amax(l2,0ll);
            if(l2 > r2) return false;
            l = l2, r = r2;
        }

        return true;
    };

    ll lo = 0, hi = n+5;
    ll ans = -1;

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

    cout << ans << endl;
}

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 = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi) // 2

        mx = mid
        for ai, bi in zip(a, b):
            mx = max(mx, min(mx, ai) + bi)
            mx -= 1
            if mx < 0: break
        
        if mx < 0: lo = mid + 1
        else: hi = mid
    print(lo)
1 Like
2

I solved this problem in O(n) by going in reverse, code.

1 Like
3

Same here

4

Did by maintaining contiguous ranges of possible scores in Binary Search
https://www.codechef.com/viewsolution/1119596027

6

Did the same, but just forgot we can’t make binary search on R0, but at most R0.

Code: `import java.io.;
import java.util.;
public class Alternate_Universe {
public static boolean fun1(long r, int n, long arr, long brr){
long lLim = 0, uLim = r;
for(int i = 0; i < n; i++){
if(lLim > arr[i]){
lLim–;
uLim–;
if(lLim < 0) lLim = 0;
if(lLim > uLim) return false;
} else{
long myUpper = Math.min(arr[i], uLim);
long uLim1 = myUpper + brr[i];
uLim = Math.max(uLim, uLim1);

                                    lLim--;
                                    uLim--;
                                    if(lLim < 0) lLim = 0;
                                    if(lLim > uLim) return false;
                          }
                }
                return true;
      }
      public static long fun(int n, long[] arr, long[] brr) {
                long low = 0, high = 4 * n, ans = 0;
                while(low <= high){
                          long mid = low + (high - low) / 2;
                          if(fun1(mid, n, arr, brr)){
                                    ans = mid;
                                    high = mid - 1;
                          } else{
                                    low = mid + 1;
                          }
                }
                return ans;
      }
      public static void main(String[] args) throws IOException {
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
                StringTokenizer st = new StringTokenizer(br.readLine());
                int t = Integer.parseInt(st.nextToken());
                while (t-- > 0) {
                          st = new StringTokenizer(br.readLine());
                          int n = Integer.parseInt(st.nextToken());
                          st = new StringTokenizer(br.readLine());
                          long[] arr = new long[n];
                          for (int i = 0; i < n; i++) {
                                    arr[i] = Long.parseLong(st.nextToken());
                          }
                          st = new StringTokenizer(br.readLine());
                          long[] brr = new long[n];
                          for (int i = 0; i < n; i++) {
                                    brr[i] = Long.parseLong(st.nextToken());
                          }

                          bw.write(fun(n, arr, brr) + "\n");
                }
                br.close();
                bw.flush();
                bw.close();
      }

}`

7

hey something weird has happened with the problem statement->

  1. earlier there were multiple test cases, now there are none.
  2. the only sample solution is wrong.
4 Likes
8

Why does R_0 = 0 in the sample case wrong. I’m trying to understand. Is it that the decrement happens after the rating change or before the contest start?

1 Like