I was working on The Great Ball problem. I was able to solve it using
- event simulation approach
- brute force approach (after coordinate compression).
Wanted to also solve it using segment trees. But my solution does not work. And I am unable to generate a failing test case. This is the script I use to generate randomized test cases.
from random import randint
t = 5
print(t)
num_max = 10000000
for i in range(t):
generated = set()
s = randint(1, 100)
print(s)
for j in range(s):
x = randint(1, num_max-2)
while x in generated:
# print("repeat x %d" % x)
x = randint(1, num_max-2)
generated.add(x)
y = randint(x+1, num_max)
while y in generated:
# print("repeat y - %d from - %d, to - %d" % (y, x+1, num_max))
y = randint(x+1, num_max)
generated.add(y)
print("%d %d" % (x, y))
But out of 12000 test cases that I have generated I can’t find a single failing test case.
I am pretty sure some edge case is killing me.
Here is the link of my solution. Any help is appreciated.