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

×

GENARSEQ - Editorial

2
2

PROBLEM LINKS

Practice
Contest

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.

This question is marked "community wiki".

asked 22 Nov '12, 18:48

admin's gravatar image

0★admin ♦♦
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) sudharkj3★

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

link

answered 24 Mar '14, 21:21

abeyaar's gravatar image

1★abeyaar
33422140
accept rate: 30%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×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