I am trying to solve this problem on Codechef, which has a list of \$N\$ coins, all initially tails-up, and a list of \$Q\$ commands. There are two possible commands,
0 A B flips all coins in the interval
[A, B] and
1 A B prints the number of heads-up coins in the interval
[A, B] (both intervals include
After reviewing somebody else's answer that exceeded the time-limit, I came up with a fast
numpy answer, which was still not fast enough for the online judge (3s instead of 0.3s).
However, one other reviewer suggested the following algorithm:
- The key observation is that a
0 a boperation is in fact a pair of operations: flip coins from
ato the end, and flip coins from
b + 1to the end. This leads to the solution:
- Decouple the
0 a boperation into
- Maintain the list of flip points, and keep it ordered
- To perform a
1operation, find the largest flip point before
A. If its index in flip list is even, the
Acoin is tails up, otherwise it is heads up. Then, traverse the flip list until
Badding up lengths of every other interval.
I tried to implement this, using
bisect to keep the list of flips sorted, but it is a lot slower (20s for the same worst-case input as the 3s quoted above).
from bisect import bisect_left, insort n, q = map(int, input().split()) flips =  for _ in range(q): command, start, end = map(int, input().split()) if command == 0: insort(flips, start) insort(flips, end + 1) elif command == 1: flip_start = bisect_left(flips, start) flip_end = bisect_left(flips, end + 1) flips_temp = flips[flip_start:flip_end] insort(flips_temp, end + 1) if flip_start % 2: insort(flips_temp, start) print(sum(flips_temp[1::2]) - sum(flips_temp[:-1:2]))
However, this is probably not the best implementation of that algorithm, maybe there is a way to use
heapq to keep the list sorted (but then slicing and traversing it become harder). So, any comments, especially on how to speed this up, are welcome.
I am aware that one should normally put this into a function and make it re-usable, but since this is time-critical code I think it is fine to leave it all in the global namespace. It is a one-shot script, anyway.
The worst-case input file I used (which I generated using the code in my linked answer from above) can be found here (1.4 MB). It assumes the maximum allowed values for \$N\$ and \$Q\$ and contains a random sequence of the two allowed commands.
I feed it to this code with the following command (and time it at the same time):
time cat flipping_coins.dat | python3 flipping_coins.py
Running only the
cat command already takes 0.17s.
As Ev. Kounis noted in the comments, there is currently no solution in pure Python that successfully beats this challenge. There are, however, a couple of PyPy solutions, which use segment trees.