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

×

HARD

# EXPLANATION

Let us first prove that the entire sequence consists only of N-1, N, and N+1. The proof proceeds inductively. Suppose for some i > N that the first i terms of the sequence are all N-1, N, or N+1. For all j satisfying i-N+1 < j ≤ i we have A[j] ≥ N-1 = i-(i-N+1) ≥ i-j, hence A[i] ≥ N-1. Similarly, for all j satisfying j < i-N-1 we have A[j] ≤ N+1 < i-(i-N-1) ≤ i-j, hence A[i] ≤ N+1. It follows that N-1 ≤ A[i] ≤ N+1 for all i.

We now have that A[i] depends only on A[i-N-1] and A[i-N]. Specifically:

A[i] = N if A[i-N] == N-1 and A[i-N-1] == N+1
A[i] = N+1 if A[i-N] != N-1 and A[i-N-1] == N+1
A[i] = N-1 if A[i-N] == N-1 and A[i-N-1] != N+1
A[i] = N if A[i-N] != N-1 and A[i-N-1] != N+1

Now let's consider sequences consisting only of N and N+1, and sequences consisting only of N-1 and N. For a sequence consisting only of N and N+1, we'll have A[N]=N, and then A[i+N+1]=A[i] for all i. For a sequence consisting only of N-1 and N, we'll have A[i+N]=A[i] for all i. Call the N+1 terms "pegs", and the N-1 terms "holes". Pegs are periodic with period N+1, and holes are periodic with period N. What happens when a sequence contains both pegs and holes? Simple. Every time a peg and hole collide, the peg fills the hole and they are both eliminated.

So all we have to do is figure out which pegs fill which holes and when. The process works as follows. Create a stack. Starting at the beginning of the sequence, every time a peg is found push it on the stack. Every time a hole is found, match it with the top peg from the stack (unless the stack is empty, in which case do nothing). If i is the index of the peg, and j the index of the hole, then the index x at which they collide will satisfy x = i (mod N+1) and x = j (mod N). We can use the Chinese Remainder Theorem to find that x = j * (N+1) - i * N (mod N * (N+1)).

Now to answer each query, compute the position of the peg and hole associated with the query. If there is a peg or a hole, check if it has been eliminated.

# SETTER'S SOLUTION

Can be found here.

# TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 23 Nov '12, 13:21 19.8k350498541
accept rate: 36%

 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
×1,359
×9
×3

question asked: 23 Nov '12, 13:21

question was seen: 1,702 times

last updated: 23 Nov '12, 13:21