The problem: Minions and Voting Practice Coding Problem
I have created a 2* N * log(N) solution, using binary search.
It’s similar to what I saw as the official solution, but for some reason I’m getting time limit exceeded on the last two test cases. Meanwhile, there are tons of submissions with the N^2 brute force solution, but they pass the test cases?
The only thing I could think of is my binary search getting stuck in an infinite loop, but I tested for that so I don’t know.
Maybe I missed something because it took me a while to debug my code to get it to work.
Here’s the code:
https://www.codechef.com/viewsolution/1105236165
Minions and Voting Practice Problem in 1800 to 2000 difficulty problems
for _ in range(int(input())):
N = int(input())
S = list(map(int, input().split()))
pSum = [0] * (N + 1)
for i in range(1, N + 1):
pSum[i] = pSum[i - 1] + S[i - 1]
cacheArray = [0] * (N + 1)
for i in range(N):
ai = S[i]
if ai >= pSum[N] - pSum[i + 1]:
cacheArray[i] += 1
else:
l = i + 1
r = N
mid = (l + r) // 2
while l < r:
currNum = pSum[mid] - pSum[i + 1]
if ai >= currNum:
l = mid + 1
elif ai < currNum:
r = mid
else:
break
if l > r:
break
mid = (l + r) // 2
cacheArray[i] += 1
cacheArray[mid-1] -= 1
cs = 0
total = [0] * N
for i in range(0, N):
total[i] = cs
cs += cacheArray[i]
cacheArray = [0] * (N + 1)
for i in range(N):
ai = S[i]
if ai >= pSum[i] - pSum[1]:
cacheArray[0] += 1
cacheArray[i] -= 1
else:
l = 0
r = i
mid = (l + r) // 2
while l < r:
currNum = pSum[i] - pSum[mid+1]
if ai >= currNum:
r = mid
elif ai < currNum:
l = mid + 1
else:
break
if l > r:
break
mid = (l + r) // 2
cacheArray[mid] += 1
cacheArray[i] -= 1
cs = cacheArray[0]
for i in range(1, N + 1):
total[i-1] += cs
cs += cacheArray[i]
print(" ".join(list(map(str, total))))