PROBLEM LINKS
DIFFICULTY
MEDIUM
PREREQUISITES
Simple Math
PROBLEM
You are given a sequence of integers F1, F2, …, FN in strictly increasing order. Find two subsequences such that one subsequence forms an arithmetic progression (AP), the other forms a geometric progression (GP), and each element of the original sequence belongs to either the AP or the GP.
For convenience, let M = max{Fi} throughout this editorial.
QUICK EXPLANATION
A slow but obvious solution iterates over all possible AP subsequence. There are O(N) possible first terms of the AP and for each first term, there are O(N) possible values for the second term. Here is a pseudocode of the function to mark the elements of AP subsequences as “used”.
function mark_ap_subsequence(term1, diff):
usedAP[id[term1]] = true
f = term1 + diff
while f ≤ M:
usedAP[id[f]] = true
f = f + diff
Here, id[f] is the index of the value f in the original position, i.e. Fid[f] = f, or 0 if f is not present. When f is not present, usedAP[id[f]] = usedAP[0]. We do not care about the content of usedAP[0] as we never access index 0 after this calculation.
As can be seen in the function above, we need O(N) time to obtain the remaining elements of the AP. Therefore, we need O(N3) to iterate over all possible AP subsequences.
After we obtain an AP subsequence, we must check whether the remaining elements plus some elements of the AP subsequence can form a GP. There are two cases.
If there is only one element remaining then it is always possible to make a valid GP subsequence with at least two elements (just pick an element from the AP). Otherwise, consider the first two remaining elements, let’s call them A and B with A < B. Let R = B / A. Of course, R = rk for some r and integer k where r is the GP ratio and k is the difference of position indices of A and B in the GP. Since the maximum possible value for Fi is 100,000 and all integers in the input are integers, then the maximum value of k is about 16 (i.e. lg M). We also mark the elements of the GP subsequence as used like we did in the AP subsequence as well.
Since all numbers in the input are integers, we will represent the ratio as a rational number r1/r2. We also introduce a function simplify() that takes a rational number and return the simplest representation of it; i.e., the gcd of the numerator and denominator will be 1.
function simplify(r1, r2):
g = gcd(r1, f2)
return (r1 / g, r2 / g)
function mark_gp_subsequence(term1, r1, r2):
usedGP[id[term1]] = true
(f1, f2) = simplify(term1 × r1, r2)
while f1 ≤ M × f2: // equivalent to while f1 / f2 ≤ M:
if f2 == 1: // equivalent to if f1 / f2 is an integer:
usedGP[id[f1]] = true
else:
break
(f1, f2) = simplify(f1 × r1, f2 × r2)
Iterate over all possible values of k. Given A, B, and k, we can compute r1 / r2 (GP ratio) and obtain the remaining terms of the GP in O(N) time as can be seen in the above pseudocode. If all elements are marked as used in either usedAP or usedGP after we mark AP and GP subsequences, then we have found a solution.
The complexity for finding a valid GP subsequence is O(N lg M).
EXPLANATION
Unfortunately, if we iterate all possible AP and GP subsequences the complexity of the solution will be O(N4 lg M), which is too much and will surely result in Time Limit Exceeded verdict. We need a more clever observation. A very important observation is:
All elements in the original sequence must belong to either AP subsequence or GP subsequence, or both.
By using the above obeservation, it turns out that there are only 6 cases to consider:
- F1 and F2 are the first two AP terms.
- F1 and F3 are the first two AP terms.
- F2 and F3 are the first two AP terms.
- F1 and Fk where k ≥ 4 are the first two AP terms. So F2 and F3 must be the first two GP terms.
- F2 and Fk where k ≥ 4 are the first two AP terms. So F1 and F3 must be the first two GP terms.
- Fp and Fq where p,q ≥ 3 are the first two AP terms. So F1 and F2 must be the first two GP terms.
In short, one of (F1, F2), (F2, F3), (F1, F3) will be the first two terms of AP or GP or both. Therefore, the problem now reduces to finding a valid solution among the 6 possible cases.
Case 1
mark_ap_subsequence(F1, F2 - F1)
(A, B) = the first two elements that are not marked as used in usedAP
for k = 1; k ≤ 16; k++:
if A1/k and B1/k are integers:
(r1, r2) = simplify(B1/k, A1/k)
reset all values of usedGP to 0
mark_gp_subsequence(A, r1, r2)
if all elements are marked as used in either usedAP or usedGP:
found a solution!
Case 2 and Case 3 are similar.
For Case 4 through Case 6, we need to check whether the remaining elements (plus some elements in the GP subsequence) can form an AP subsequence. The method is similar. Suppose that A and B are the first two terms that are not marked. It can be proved that the distance between the positions of A and B in AP is at most 3. Why? Left as an exercise 
Hint: What is the maximum possible length of an integer sequence that is both AP and GP?
Case 4
mark_gp_subsequence(F2, F3, F2)
(A, B) = the first two elements that are not marked as used in usedGP
for k = 1; k ≤ 3; k++:
diff = (B - A) / k
reset all values of usedAP to 0
mark_ap_subsequence(A, A + diff)
if all elements are marked as used in either usedAP or usedGP:
found a solution!
Case 5 and Case 6 are similar.
The time complexity of this solution is O(N lg M).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.