Блог пользователя danhnguyen0902

ARITHMETIC SEQUENCE
Автор danhnguyen0902, 11 лет назад, По-английски

I've heard that the following problem belongs to a Russian programming contest. Does anyone know where it is or how to solve it?

An arithmetic sequence is a sequence of numbers a[1], a[2],... a[N] such that a[i + 1] — a[i] is equal for all 0 ≤ i < N. Given a sequence of N positive integers and M queries [x, y], write a program answer each query whether the consecutive numbers from position x to y form an arithmetic sequence (they could not originally be in increasing order).

Example:

Input:

5 3 (N M)

1 3 2 5 4 (N positive integers)

1 5 (x y)

2 4 (x y)

4 5 (x y)

Output:

YES

NO

YES

Explain:

  • The sequence 1 3 2 5 4 forms an arithmetic sequence, which is 1 2 3 4 5.

  • The sequence 3 2 5 does not form an arithmetic sequence.

  • The sequence 5 4 also forms an arithmetic sequence, which is 4 5.

Constraints:

  • 40% test: N, M <= 1,000 .

  • 30% test: N <= 1,000 and M <= 10^6 .

  • 30% test: N <= 10^5 and M <= 10^5.

  • a[i] <= 10^9

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What are the constraints?

→ Ответить
»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Oh, sorry. I misread statement.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    I don't think this approach is correct. Because this works only when you can't reorder elements in sequence. But in the sample input the sequence (1, 3, 2, 5, 4) creates arithmetic sequence, because you can order elements such as (1, 2, 3, 4, 5).

    meantime you realized ...

    → Ответить
»
11 лет назад, # |
← Rev. 3   Проголосовать: нравится -11 Проголосовать: не нравится

fksnfosjfksfndskfndsfksdfnkfsdjnj :)

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am not sure but I think it can be solved in order: O(sqrt(N)*N*lgn). Something like IOI 2011 elephant.

→ Ответить
»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

Maybe some kind of "hashing" will work: suppose we have a function from list of numbers to number such that:

  1. It doesn't depend on order of numbers in list.
  2. It can be calculated in sublinear time for arithmetic sequence as well as for subarray of the given array(after some preprocessing of course).
  3. Its values rarely coincide for different inputs.

Then we can find min, max and length of the range given in query, that is, there is only one candidate for arithmetic sequence that our range can form, and we just compare their hashes.

Sum of k-th powers is an example of such function, maybe you can think of something else.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    I was trying this example followed your approach: 1 7 4 8 6 2

    Suppose we're querying subarray 7 4 8. Its max = 8, min = 4, length = 3, and its hash value = 4^k + 7^k + 8^k (k > 0). However, the arithmetic progression corresponding to those max, min, length values should have been 4 6 8, and its hash value = 4^k + 6^k + 8^k, which is less than the hash value above. Thus, we say that 7 4 8 is not an arithmetic progression.

    But the time required to point out the correct arithmetic progressions is linear. Could it be better than that? Am I missing anything here?

    → Ответить
»
11 лет назад, # |
  Проголосовать: нравится +54 Проголосовать: не нравится

That's a nice problem.

First, use 2 min/max interval trees to determine the smallest and largest element in the given range (e.g. in the assumed arit. progression). From those 2 elements (call them b, c) and the length (y - x + 1), we know the difference between 2 elements of our progression .

Now, we check some border cases (y = x: immediately answer yes and don't try division by 0); if the diff. is 0, then b = c and all the elements of this range are equal, so answer yes, too.

Otherwise, no 2 elements may be equal, as the sequence is monotonous with non-zero difference. To check this, we make a linear pass to determine, for every index y, the rightmost index x such that in the range [x, y], there're 2 elements equal to ax. How to do this: Just store the 2nd to last already seen occurence of every element you've seen more than once in a map (the answer for some y is the maximum of those); when you increment y, only such occurence of ay + 1 can change, so you update that and check if it increases the maximum.

The other necessary condition for a "YES" answer is that all elements in the range [x, y] must be equal modulo d. Now, realize that the answer to this is independent on their order, and it's equivalent to checking if the difference between every 2 consecutive elements in range is divisible by d. So, we transform our array to an array of differences a[i] - a[i - 1] for i > 0; on this array, we need to check if d divides all elements in range [x, y - 1], or equivalently, that d divides the GCD of this range. That can be done with a GCD interval tree (check IOI 2013, task Game for more info about this). Using this tree, we answer the 2nd half of the question.

Those 2 conditions are also sufficient — obviously if there are no equal elements and all are equal modulo d, then there must be exactly 1 element of every (integer division) quotient between and (Dirichlet :D), and those form an arithetic sequence after sorting.

So we need to check those 2 condiditions. All in all, with interval trees and an STL map, we get time. (If the time limits for the batch with M ≤ 106 are tight, we can compute the answers for all segments using DP and then answer each query in O(1) time, or O(N2 + M) total...)

→ Ответить