Little_Sheep_Yawn's blog

By Little_Sheep_Yawn, history, 2 months ago, In English

Finally made it throughout a year! Congratulations to me!

It seems that the page can be different in different time zones, so it is quite normal if what you see isn't this graph. (FYI, I'm currently in China.)

Wish things will be better!

Full text and comments »

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

By Little_Sheep_Yawn, history, 8 months ago, In English

I was practicing when I came across this problem. And I submitted a few codes which are almost the same, but their running time is quite different. Here's the thing:

The fastest one is here, which only runs 1590ms:

n, mod = map(int, input().split())

dp = [0] * (n * (n - 1) + 1)
diff = [0] * (n * (n - 1) + 1)
msk = n * (n - 1) // 2
v = 1

wing = 0
for i in range(n):
    
    for j in range(msk - wing, msk + wing + 1):
        if dp[j]:
            diff[j] += dp[j]
            diff[j + (n - i - 1) + 1] -= dp[j]
    
    cur = 0
    for j in range(msk - wing, msk + wing + n - i):
        cur += diff[j]
        cur %= mod
        dp[j] = cur
        diff[j] = 0
    
    for j in range(msk - wing, msk + wing + n - i):
        if dp[j]:
            diff[j - (n - i - 1)] += dp[j]
            diff[j + 1] -= dp[j]
    
    cur = 0
    for j in range(msk - wing - (n - i - 1), msk + wing + n - i):
        cur += diff[j]
        cur %= mod
        dp[j] = cur
        diff[j] = 0
    
    for j in range(-(n - i - 1), 0):
        dp[j + msk] += v * (n - i + j) % mod
        dp[j + msk] %= mod
    
    v = v * (n - i) % mod
    wing += n - i - 1

print(sum(dp[msk+1:]) % mod)

Yet, another code which is basically the same as the former one needs 3743ms:

def main():
    n, mod = map(int, input().split())

    dp = [0] * (n * (n - 1) + 1)
    diff = [0] * (n * (n - 1) + 1)
    msk = n * (n - 1) // 2
    v = 1
    
    wing = 0
    for i in range(n):
        
        for j in range(msk - wing, msk + wing + 1):
            if dp[j]:
                diff[j] += dp[j]
                diff[j + (n - i - 1) + 1] -= dp[j]
        
        cur = 0
        for j in range(msk - wing, msk + wing + n - i):
            cur += diff[j]
            cur %= mod
            dp[j] = cur
            diff[j] = 0
        
        for j in range(msk - wing, msk + wing + n - i):
            if dp[j]:
                diff[j - (n - i - 1)] += dp[j]
                diff[j + 1] -= dp[j]
        
        cur = 0
        for j in range(msk - wing - (n - i - 1), msk + wing + n - i):
            cur += diff[j]
            cur %= mod
            dp[j] = cur
            diff[j] = 0
        
        for j in range(-(n - i - 1), 0):
            dp[j + msk] += v * (n - i + j) % mod
            dp[j + msk] %= mod
        
        v = v * (n - i) % mod
        wing += n - i - 1
    
    print(sum(dp[msk+1:]) % mod)
    return

t = 1
for _ in range(t):
    main()

I'm quite puzzled as these two codes seems nothing too different. I really wonder how this could happen as it could cause some unexpected TLEs in other questions. It would really help a lot if you could offer some insights on it.

Thanks in advance!

Full text and comments »

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

By Little_Sheep_Yawn, history, 12 months ago, In English

In recent competitions, I came across this type of RUNTIME ERROR. Here's the thing:

I wrote a program like this:

def main():
    k = 15
    m = 3
    
    for a in range(k + 1):
        for b in range(k + 1):
            for c in range(min(m, k) + 1):
                for d in range(min(m, k) + 1):
                    continue
    return

t = 1
for _ in range(t):
    main() 

But in Atcoder, it showed something like this: (Sorry that the picture isn't clear enough)

It really bothered me and I wonder if anyone could be so kind as to help me with this issue.

(p.s. The RUNTIME ERROR doesn't show in Codeforces, so I'm really confused)

Here are some codes that don't show RUNTIME ERROR:

Code 1:

k = 15
m = 3

for a in range(k + 1):
    for b in range(k + 1):
        for c in range(min(m, k) + 1):
            for d in range(min(m, k) + 1):
                pass

Code 2:

def main():
    k = 15
    m = 3
    
    for a in range(k + 1):
        for b in range(k + 1):
            for c in range(min(m, k) + 1):
                for d in range(min(m, k) + 1):
                    print(d)
    return

t = 1
for _ in range(t):
    main()

Full text and comments »

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