 # GENARSEQ - Editorial

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.

2 Likes

sir, can you please tell what is wrong with my solution. I feel that it is according to the editorial but I am getting wrong answer. Thanks.

this solution is running on my machine for 4.5 seconds but still getting TLE
can anyone give the reason?? Thank you

//