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

×

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.

This question is marked "community wiki".

asked 22 Nov '12, 18:48 19.8k350498541
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) 3★

 0 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 1★abeyaar 334●2●21●40 accept rate: 30%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,852
×3,820
×6
×2

question asked: 22 Nov '12, 18:48

question was seen: 1,714 times

last updated: 24 Mar '14, 21:21