ARIGEOM - Editorial

arigeom
dec12
editorial
medium
simple-math

#1

PROBLEM LINKS

Practice
Contest

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:

  1. F1 and F2 are the first two AP terms.
  2. F1 and F3 are the first two AP terms.
  3. F2 and F3 are the first two AP terms.
  4. F1 and Fk where k ≥ 4 are the first two AP terms. So F2 and F3 must be the first two GP terms.
  5. F2 and Fk where k ≥ 4 are the first two AP terms. So F1 and F3 must be the first two GP terms.
  6. 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.


#2

what about this case:
3,5,11,13,17,21,26,34,52
in this case f1,f2 or f3 is not first element of gp


#3

“Let R = B - A. Of course, R = r^k for some r and integer k…” - shouldn’t it be R = B/A?


#4

i didnt got how the maximum value of k is about 16 (i.e. lg M) and secondly i think instead of “(f1, f2) = simplify(term1 × r, r2)” it should be “(f1, f2) = simplify(term1 × r1, r2)”.


#5

As the maximum possible length of an integer sequence that is both AP and GP is 2, why not the same thing can be used in Case 1-3 ?


#6

hey can anyone figure out the problem in my code, its giving runtime error. here is my


[1]


  [1]: http://ideone.com/0ffdXN

#7

I can’t understand why max. value of k is 16 as r(GP ratio) can be any real number and not only integer?


#8

This test is incorrect - your sequence can’t be represented as union of arithmetic and geometric progressions.


#9

Opps, sorry. This is fixed.


#10

If common ratio is integral, in the worst case r = 2 for which you can have max lg M values in GP. Even if you take common ratio to be non-integral, still the GP terms have to be integral and due to that, the worst case common ratio becomes 1/2 which again leads to max lg M values in GP series.


#11

r can never be 1/2 since its a increasing GP. Now tell me one thing, if the GP is increasing and each term in it is integer, why the minimum value of r is 2, why cant less than 2 ?


#12

why is incorrect in the question you didn’t say that every sequence must be union. in the question you said that "If there are more than one possible pair of beat notations, output any one of them."in my test order is increasing and there are arithmetic and geometric sequence
arithmetic sequence: 3,5 or 11,13 or 13,17,21
geometric sequence :17,34 or 13,26,52


#13

You’ve misunderstood the problem. It is guaranteed that it is a union and the question was to find arithmetic and geometric progressions such that each element of the given sequence belongs to one of the progressions. Well, it is not mentioned explicitly but follows from the storyline of the problem.


#14

r must be of the form a/b where a,b <= 100000. If r is a 17th power then so are a and b, but 2^17 > 100000.


#15

yeah dude u are 100% correct, in case 1-3 also maximum value of k should be 3


#16

In Case 4:
mark_ap_subsequence(A, A + diff), must be mark_ap_subsequence(A, diff) ?


#17

No, it won’t work. Consider the single case
61
2 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 162 486 1458