This post will be a tutorial on 313B - Илья и запросы , as well as some general python I/O optimizations that provided me with enough of a speedup to have my solution finish in the allotted time.
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 ifS[i-1]
==S[i]
and 0 otherwise (X[0]
is defined to be 0).A
is the accumulation ofX
.
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
. Also, just processing each query is O(n)
as 0 <= m
<= n
, the total runtime of this approach is O(n^2)
. Hence the total number of timesteps for this solution in the worst case is 10^10 as 1 <= n
<= 10^5, which is too much computation for the allotted time.
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 i
th 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]
.
I/O 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!