This post will be a tutorial on 313B - Ilya and Queries, as well as some general python I/O optimizations to be aware of.

Solution

As an example, consider the input string #..###. From it, we create arrays

• S = [ # . . # # # ]
• X = [ 0 0 1 0 1 1 ]
• A = [ 0 0 1 1 2 3 ]

where

• S is an array encoding the input string.
• X[i] = 1 if S[i-1] == S[i] and 0 otherwise (X[0] is defined to be 0).
• A is the accumulation of X.

Recall the goal of the problem is to compute the number of elements in the range [l, r) whose right neighbor is the same as itself. A naive solution is to compute the sum of corresponding elements in X (e.g. sum up X[l+1] + X[l+2] + ... + X[r]. However, this is O(n) for a single query as 0 <= l, r <= n. Since just processing each query is O(n) as 0 <= m <= n, the total runtime of this approach is O(n^2). Since 1 <= n <= 10^5, we have a total number of timesteps as 10^10, which is too much for one second.

To speed things up, we can use A. The solution is simply the expression A[r] — A[l]. To see why this is the case, consider the example [l=3, r=6). A[3] is the number of elements up to and including index 2 whose right neighbors are the same as themselves. A[5] is the same, up to index 4, which is the index we want to go up to.

[ 0 0 1 0 1 1 ]
 |---| => A[3] = 1 
 |---------| => A[6] = 3

Encoded in the ith position of A is the answer to [l=0, r=i). To recover [l, r) for arbitrary l and r, we simply subtract A[l] from A[r].

Optimizations

Even with this optimization, my python solution was still exceeding the time limit. After profiling my code, I deduced that the way I was handling I/O was the bottleneck. I replaced

for _ in range(m):
    l, r = [int(num) for num in raw_input().split()]
    print A[r] - A[l]

with

lines = sys.stdin.readlines()
ranges = [[int(num)-1 for num in line.split()] for line in lines]
outputs = [str(SA[r]-SA[l]) for l, r in ranges]
print '\n'.join(outputs)

Eliminating the repeated calls to raw_input() and print gave me a substantial speedup which was fast enough to have my solution finish within the allotted time!