XORSCHED - Editorial

PROBLEM LINK:

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

Author: hyder1102
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Familiarity with bitwise XOR

PROBLEM:

You are given N, X, Y.
There are N+1 processes, indexed from 0 to N.

Process i arrives at time i\oplus X, and requires a duration of i\oplus Y.

A CPU will perform the tasks in order, always choosing whichever available task arrived first.
Find the total time needed to complete all tasks.

EXPLANATION:

First, we must understand the times at which all the processes appear, i.e. figure out all values of i\oplus X for 0 \le i \le N.

While these values are not necessarily contiguous, it turns out that they can actually be represented as the union of \mathcal{O}(\log N) contiguous intervals.
These intervals can be found as follows.

Let k be the largest integer such that 2^k \le N+1.
Now look at the range of integers [0, 2^k-1].

  • If X \lt 2^k, this range will be mapped back onto itself.
  • If X \ge 2^k, then if p denotes the prefix of N containing only bits \ge k, the range will be mapped onto [p, p+2^k-1].
    • Note that this also works with the first case, which has p = 0.

So, the range [0, 2^k-1] maps onto another range of length 2^k.

That leaves the range of values [2^k, N], which can be solved for recursively (find the largest power of two not exceeding the length of the remaining interval, take the prefix of this length and then see where it maps to.)
You may note that this is essentially writing N as the sum of powers of 2, a la its binary representation.


After finding all these ranges, what do we do with them?

To answer that, we’ll first redefine the objective in a way that makes it easier to work with.

For an integer x, define f(x) to be the sum of all job lengths of jobs that arrive at times \ge x.
Observe that as long as one job arrives \ge x, the finish time of all jobs cannot be smaller than x + f(x).

So, a lower bound on the answer is \max_x (x + f(x)), where the maximum is taken only over all arrival times x (and not all integers x since that would be unbounded.)

This lower bound is indeed the actual answer.
To see why, let x_1 and x_2 be the first two instants of time at which jobs appear; and let the jobs have durations y_1 and y_2 respectively.
Then,

  • If x_1 + y_1 \le x_2, then we’ll be “free” after the first job; so simply dropping that job doesn’t affect the final answer anyway.
    Note that x_1 + f(x_1) \le x_2 + f(x_2) in this case, because we’ll actually have x_2 + f(x_2) = x_1 + f(x_1) + (x_2 - x_1 - y_1) and the second term is non-negative.
  • If x_1 + y_1 \gt x_2, then immediately after completing the first job, we’ll start the second one.
    Observe that this is equivalent to increasing the length of the first job to y_1 + y_2, and dropping the second job entirely.
    Also note that x_1 + f(x_1) \ge x_2 + f(x_2) in this case, for similar reasons to the first case.

Importantly, in both cases we were able to obtain an equivalent input with one less job; while discarding whichever job had the smaller x+f(x) value.
Repeat this argument till we have only a single job with the maximum x+f(x) value, at which point it’s the answer (since there’s only one job.)


Viewing the objective this way also allows us to solve the problem fairly quickly.

Recall that we obtained \mathcal{O}(\log N) ranges of job-receive times.
Let [l, r] be one such range.

Then, the key observation is that l + f(l) \ge x + f(x) for all l \le x \le r, i.e. the left endpoint is the limiting factor here.
More precisely, the function x + f(x) is non-increasing across this interval.
The reason is simply because each point in this interval receives a job (of length at least 1), and so it’s impossible for there to be any “free time”.
As we saw earlier, not having free time means we drop the second job in the list and adjoin its length to the first one; ergo l + f(l) is the only one we need to check.

Thus, there are only \mathcal{O}(\log N) candidates we need to check.
Each one can be checked fairly easily in \mathcal{O}(\log N), since once the left endpoint l of the interval is fixed, we really just want to know the sum of i\oplus Y across all i such that l\oplus X \le i \le N, which can be found in similar fashion to how we found all intervals of i\oplus X.

TIME COMPLEXITY:

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

CODE:

Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int x, y, n; cin >> x >> y >> n;
    n++;
    
    auto get_min = [&](int n, int x, int b){
        n ^= x;
        for (int i = 0; i < b; i++){
            if (n >> i & 1) n -= 1 << i;
        }
        return n;
    };
    
    auto get_sum = [&](int n, int x, int b){
        n ^= x;
        int ans = (n + 1) * (1 << b);
        for (int i = 0; i < b; i++){
            if (n >> i & 1){
                ans -= (1LL << (b - 1)) * (1 << i); 
            } else {
                ans += (1LL << (b - 1)) * (1 << i);
            }
        }
        return ans;
    };
    
    // easy for n = 2^i, break into powers of 2 
    int add = 0;
    int ans = 0;
    vector <pair<int, int>> vec;
    for (int i = 30; i >= 0; i--){
        if (n >> i & 1){
            // i = [add, add + 2^i)
            int min_arrival = get_min(add, x, i);
            int sum_times = get_sum(add, y, i);
            vec.push_back({min_arrival, sum_times});
            add += 1 << i;
        }
    }
    
    sort(vec.begin(), vec.end());
    for (auto [x, y] : vec){
        ans = max(ans, x) + y;
    }
    
    cout << ans << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    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;
}