FINDSEQ - Editorial






For both of the editorials below the credit goes solely to Anton Lunyov. These are pasted from his mail of solution explanations.

O(N * N * logN) approach:

Let’s fix i1 and i3, such that A[i[1]] and A[i[3]] are in the same relation as B1 and B3, and try to check whether there exists a subsequence (i[0], i1, i2, i3, i4) that satisfies conditions of the problem.

Clearly segments on which lie i[0], i2 and i4 are disjoint. Denote the segment for i[j] by [x[j], y[j]].

Let B[R] be the maximum in the set S={ B[0], B2, B4 }, B[L] be the minimum in S, and B[M] be the middle element.

Values A[i[1]] and A[i[3]] dictate some segments on which should lie values A[i[0]], A[i[2]] and A[i[4]]. Segment [X[j], Y[j]] for A[i[j]] depends on relation between B1, B3 and B[j] and can be found easily.

After we find these segments it is clear that it is advantageous to take for i[L] such value on the segment [x[L], y[L]] that A[i[L]] is minimal possible under condition A[i[L]]>=X[L]. The similar is true for i[R] but we should maximize A[i[R]] under condition A[i[R]]>=X[R].

After i[L] and i[R] is chosen they dictate some changes to the segment for A[i[M]]. In some cases this segment becomes empty and it means that required subsequence does not exist in this case. Otherwise we should check whether there exists some i[M] in [x[M], y[M]] such that A[i[M]] in [X[M], Y[M]], where [X[M], Y[M]] can be modified after choosing i[L] and i[R].

To answer the question for the fixed pair (i1, i3) quickly we at first change array A[] by the new one where all relations between elements are saved but values are between 1 and N and then compute values S[j][V] - the total amount of numbers not greater than V among the numbers A1, …, A[j]. This can be done by simple dynamic programming in O(N*N) time.

With this array we can answer in O(1) time on the following question: for how many j in [x, y] we have A[j] in [X, Y]. With this ability we can find values A[i[L]] and A[i[R]] by binary search in O(log N) time (but not the values of i[L] and i[R] itself) and then in O(1) time check whether there exist appropriate i[M].

Once we find that for the given pair (i1, i3) the required subsequence do exist, we can restore the answer in O(N) time knowing values A[i[L]],A[i[R]] and segment for A[i[M]], print it and stop further checks. Using some additional O(1) checks before applying binary search we can decrease the total number of pairs for which we should use binary search in some cases.

O(N*N) approach:

Take the notations of the previous solution. Let’s precompute the following values:

pref_min[j][V] = min(A[i] : 1<=i<=j, A[i]>=V).
pref_max[j][V] = max(A[i] : 1<=i<=j, A[i]<=V).
suff_min[j][V] = min(A[i] : j<=i<=n, A[i]>=V).
suff_max[j][V] = max(A[i] : j<=i<=n, A[i]<=V).

Each of this tables can be precomputed in O(N*N) time.
Consider for example pref_min[][]:
pref_min[j][V]=min(pref_min[j-1][V], A[j]>=V?A[j]:inf);

Now how can we use this information?

Let i1 and i[3] be fixed
Consider indexes L and R.
(Just for clarity: Let B[R] be the maximum in the set S={ B[0], B2, B4}, B[L] be the minimum in S, and B[M] be the middle element.)

At least for one of them, say L, corresponding segment [x[L], y[L]] for i[L] has the form [1,i1-1] or [i[3]+1,n].
Hence we can choose A[i[L]] in the way we want (for clarity: it is advantageous to take for i[L] such value on the segment [x[L], y[L]] that A[i[L]] is minimal possible under condition A[i[L]]>=X[L]) just looking at value pref_min[i[1]-1][X[L]] or suff_min[i[3]+1][X[L]].

WLOG assume that [x[L], y[L]] = [i[3]+1, n].

Now consider those of indexes M and R for which corresponding segment is [1, i1-1].
If this index is R then A[i[R]]=pref_max[i[1]-1][Y[R]].
If this index is M then A[i[M]]=pref_min[i[1]-1][X[M]] since after minimizing A[i[L]] it is advantageous to minimize A[i[M]] in its segment (but note that X[M] may change after computing of A[i[L]])
Finally for last value among R and M that left we need to look at our table S[][] to see whether there exist such value that
i1<i[K]<i3 and X[K] <= A[i[K]] <= Y[K] where K is M or R.

Unfortunately my implementation of this O(N*N) approach performs much slower than Anton Lunyov’s code of O(N * N * logN) for any of the test cases we could make.


Can be found here.


Can be found here.