I'm running into some trouble on the recent EDU round problem C, and I'm confused as to why.
Why does the following code TLE:
def sol():
n, k = ivars() # map(int, input().split())
a_list = ilist() # list(map(int, input().split()))
counts = Counter(a_list)
nums = sorted(counts.keys())
l = 0
tc = 0
mx = 0
unique = 0
for r in range(len(nums)):
if r > 0 and nums[r] - nums[r - 1] > 1:
l = r
tc = 0
tc += counts[nums[r]]
while (r - l + 1) > k:
tc -= counts[nums[l]]
l += 1
mx = max(mx, tc)
print(mx)
But this AC:
def sol():
n, k = ivars()
a_list = sorted(ilist()) # This is the only change
counts = Counter(a_list)
nums = sorted(counts.keys())
l = 0
tc = 0
mx = 0
unique = 0
for r in range(len(nums)):
if r > 0 and nums[r] - nums[r - 1] > 1:
l = r
tc = 0
tc += counts[nums[r]]
while (r - l + 1) > k:
tc -= counts[nums[l]]
l += 1
mx = max(mx, tc)
print(mx)
On my local machine, it's saying that the first code should actually be faster. Any ideas as to what might be happening? It seems like too big of a difference to attribute to cache misses or memory alignment.
TLE submission: https://codeforces.me/contest/2025/submission/286279817
AC submission: https://codeforces.me/contest/2025/submission/286279953