PROBLEM LINKS
DIFFICULTY
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.