trjhtr

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 B).

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 b operation is in fact a pair of operations: flip coins from a to the end, and flip coins from b + 1 to the end. This leads to the solution:
  
  
  • Decouple the 0 a b operation into a and b+1
    
  
  
  • Maintain the list of flip points, and keep it ordered
  
  
  • To perform a 1 operation, find the largest flip point before A. If its index in flip list is even, the A coin is tails
    up, otherwise it is heads up. Then, traverse the flip list until B
    adding 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.

 if command == 0:
 insort(flips, start)
 insort(flips, end + 1)

Well, the main reason it's slow is insort. As the doc says,

Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.

That said, there's a significant performance improvement possible here without changing data structure. Flipping coins from a to the end and then flipping coins from a to the end is equivalent to doing absolutely nothing. So rather than always insert, toggle whether or not the value is in flips. I see an execution time reduction from about 30s to about 16s with

def toggle(flips, val):
 idx = bisect_left(flips, val)
 if idx < len(flips) and flips[idx] == val:
 del flips[idx]
 else:
 flips.insert(idx, val)

and

 if command == 0:
 toggle(flips, start)
 toggle(flips, end + 1)

Obviously if you want speed then you need to switch to using a better data structure than a list, but within the constraints of list I think this is fairly efficient.

 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]))

The first thing that's suspicious here is insort. However, to my surprise, using flips_temp.append(end + 1) and flips_temp.insert(0, start) made things slightly slower. The real speedup comes from eliminating the copying. Careful analysis shows that the logic is equivalent to

 elif command == 1:
 flip_start = bisect_left(flips, start)
 flip_end = bisect_left(flips, end + 1)

 accum = sum(flips[flip_start+1:flip_end:2]) - sum(flips[flip_start:flip_end:2])
 if flip_start % 2:
 accum = -start - accum
 if flip_end % 2:
 accum = accum + end + 1
 print(accum)

This gave me a further speedup from 16 seconds to 12 seconds.

IMO it would make sense to implement the difference of sums using functools.reduce(operator.sub, ..., 0), but that's much much slower (~40 seconds).