Given an array C of positive integers, find the largest distance (in index) between two elements in the array such that the two values add up to at most F.
Right out of the problem description, we know that we can just compare all possibilities of pairs in the array and then keep track of the maximum distance apart that any valid pair has. This solves subtask 1.
The observations of this problem can be developed through working out cases by hand (which, you may have realised by now, is a powerful technique).
For the sake of convenience, the array \(C\) will be one-indexed (\(C_1\) will be the first element).
Suppose the indices \(i\) and \(j\) were the left and right elements of an optimal pair. Then,
- All the elements \(C_1\) to \(C_{i-1}\) must be larger than \(i\).
- All the elements \(C_{j+1}\) to \(C_N\) must be larger than \(j\).
Otherwise, we would be able to move \(i\) further to the left or \(j\) further to the right and be able to afford the longer mission! If a mission is the longest it can possibly be, this should not be able to happen.
You may have noticed that the diagram did not show the best possible range, which is from the second to the tenth. In fact, there also exist other ranges of \((i,\,j)\) which satisfy our property but are not the longest.
As a result, if \(C_i\) is not smaller than all of the elements before it, then we do not need to consider it as a starting point. Similarly, if \(C_j\) is not smaller than all of the elements after it, then we do not need to consider it as an ending point.
What we can do is collect the indices of all of the good starting points and all of the good ending points into two lists.
At this point, we can compare each starting point to each ending point. This allows us to solve subtask 2, since there will be at most 100 starting and ending points in this subtask. We just have remove the elements in the array that are larger than or equal to F first.
This is less of an "observation", and more of an inbuilt property in the two lists we have made. The list of valid start points is in descending order of value, and the list of valid end points is in ascending order of value (provided that you insert the elements in the original order).
Since for each possible ending point, we have to take the furthest possible starting point, as we iterate through ending points, the furthest possible starting point we take must slowly move further along the list. This means that we can run a single for loop to iterate over the ending list, and keep track of the furthest starting position simply by checking if the previous furthest starting position is still valid.
infile = open("spacein.txt", "r")
outfile = open("spaceout.txt", "w")
Ns, Fs = infile.readline().split(" ")
N, F = int(Ns), int(Fs)
C = [int(infile.readline()) for i in range(N)]
starts = []
ends = []
# Find valid starting points
for i, val in enumerate(C):
if not starts or val < starts[-1][0]:
starts.append((val, i))
# Find valid ending points
for i, val in reversed(list(enumerate(C))):
if not ends or val < ends[-1][0]:
ends.append((val, i))
# Reverse ends to get original order
ends = ends[::-1]
# Store answer
ans = -1
# Store the previous "best starting point"
prev_start = 0
for val, i in ends:
# Update the position of the "best starting point"
while prev_start < len(starts) and val + starts[prev_start][0] > F:
prev_start = prev_start + 1
# If the output is a valid mission, record its length in the answer
if prev_start < len(starts) and val + starts[prev_start][0] <= F:
ans = max(ans, i - starts[prev_start][1] + 1)
# We cannot launch and exit on the same day
if ans == 1:
ans = -1
outfile.write(str(ans) + "\n")