AIO 2021 Q5: Space Mission

Contest Source: AIO 2021

Consider any optimal range of days required to maximise the gas samples. Then every single day before the launch day must require more cost than the launch day, and every single day after the return day must require more cost than the return day. If this were not true, we could simply move the launchday earlier or the return day later in order to increase the number of gas samples.

This observation is useful, since it narrows down the number of left and right endpoints for our mission. In fact, if we take a look at the valid launch days, then we notice that they form a decreasing sequence in the array in terms of cost, which we’ll call \(l\). Similarly, if we take a look at the valid return days, these form an increasing sequence in the array in terms if cost, which we’ll call \(r\). Now for each launch day, we would like to find the furthest return day such that the sum of the costs is less than \(F\). However, notice that because the two arrays are sorted, the corresponding return day for a given launch day \(i\) in \(l\) will always be greater than or equal to than the corresponding return day for the launch day at \(i-1\). Hence, this lends itself nicely to a two pointers solution.

First, we construct arrays \(l\) and \(r\) in \(O(N)\) time. We can then keep two pointers \(i\) in \(l\) and \(j\) in \(r\), which correspond to our launch day and return day respectively. Then for each \(i\), we increment \(j\) until we cannot go any further, and record the length. The complexity of this is \(O(N)\) time, since both pointers only every increase in the array, so we only consider each element in the array at most once per pointer.

C++ Solution

#include <bits/stdc++.h>
using namespace std;

#define MAXN 100005

int main () {
    freopen("spacein.txt", "r", stdin);
    freopen("spaceout.txt", "w", stdout);

    int N, F;
    cin >> N >> F;
    int cost[MAXN];

    for (int i = 0; i < N; i++) cin >> cost[i];

    // generate l and r vectors
    vector<int> l;
    vector<int> r;
    for (int i = 0; i < N; i++) {
        if (i == 0 || cost[i] < cost[l.back()]) {
            l.push_back(i);
        }
    }
    for (int i = N-1; i >= 0; i--) {
        if (i == N-1 || cost[i] < cost[r.back()]) {
            r.push_back(i);
        }
    }
    reverse(r.begin(), r.end());
    // l is left to right, in descending order of cost
    // r is left to right, in ascending order of cost

    // run two pointers
    int ans = -1;
    int j = 0;
    for (int i = 0; i < (int)l.size(); i++) {
        while (j < (int)r.size() && cost[l[i]] + cost[r[j]] <= F) j++;
        // j is the first element in r that cannot match with l
        if (l[i] < r[j-1]) ans = max(ans, r[j-1] - l[i] + 1);
    }
    printf("%d\n", ans);
}