You are not logged in. Please login at to post your questions!


GENARSEQ - Editorial







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).


Can be found here.


Can be found here.

This question is marked "community wiki".

asked 22 Nov '12, 18:48

admin's gravatar image

0★admin ♦♦
accept rate: 36%

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.

(25 Aug '13, 23:35) sudharkj3★

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


answered 24 Mar '14, 21:21

abeyaar's gravatar image

accept rate: 30%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 22 Nov '12, 18:48

question was seen: 1,714 times

last updated: 24 Mar '14, 21:21