PROBLEM LINKSDIFFICULTYHARD EXPLANATIONLet us first prove that the entire sequence consists only of N1, N, and N+1. The proof proceeds inductively. Suppose for some i > N that the first i terms of the sequence are all N1, N, or N+1. For all j satisfying iN+1 < j ≤ i we have A[j] ≥ N1 = i(iN+1) ≥ ij, hence A[i] ≥ N1. Similarly, for all j satisfying j < iN1 we have A[j] ≤ N+1 < i(iN1) ≤ ij, hence A[i] ≤ N+1. It follows that N1 ≤ A[i] ≤ N+1 for all i. We now have that A[i] depends only on A[iN1] and A[iN]. Specifically: A[i] = N if A[iN] == N1 and A[iN1] == N+1 Now let's consider sequences consisting only of N and N+1, and sequences consisting only of N1 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 N1 and N, we'll have A[i+N]=A[i] for all i. Call the N+1 terms "pegs", and the N1 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 SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 23 Nov '12, 13:21
