PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
Finding x[k] at each step directly by definition is very slow. Let’s do the following. After we find some x[k] let’s mark all numbers greater than x[k] that definitely can’t be the future elements of this sequence. What are these numbers? Clearly that all numbers of the form a * x[i] - b * x[j] where 1 <= i, j <= k can’t be the elements of this sequence. But all other numbers possibly can belong to this sequence until we find the next element. The element x[k] bring us the following numbers that was not marked earlier: a * x[k] - b * x[i] for 1 <=i <=k and a * x[i] - b * x[k] for 1 <=i < k. So we need to mark only these 2 * k - 1 numbers at kth step. The finding of x[k] now becomes easy. We just need to iterate through all numbers greater than x[k - 1] until we find not marked number. This number is equal to x[k].
Some additional hints. Don’t forget to mark a - b before finding x 2 . Take some bound for numbers that will be marked. We don’t need to mark numbers greater than x[n]. Of course we don’t know it. But we can estimate it. Since at each step we mark at most 2 * k - 1 new numbers it follows that x[k+1] <= x[k] + 2 * k - 1. And hence x[n] <= 1 + 1 + 3 + 5 + … + (2 * n - 3) = (n - 1)2 + 1. Thus we can mark only numbers that is not greater than (n - 1)2 + 1. In fact you don’t need all this stuff and simply can mark all numbers using array with one million elements. Thus we obtain algorithm with complexity O(n2).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.