Pras28's blog

By Pras28, history, 4 weeks ago, In English

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

Full text and comments »

  • Vote: I like it
  • +4
  • Vote: I do not like it