The Most Curious Travesty On Codeforces

My first ever blog on CodeForces here. Firstly, a huge thanks to MikeMirzayanov and all the people behind this wonderful ecosystem for allowing me to improve my programming skills, which enable me to think differently.

Now, onto the travesty, here is problem 3E from the most recent div3(1027). Here is the problem statement: https://mirror.codeforces.com/contest/2114/problem/E

The question itself is rather simple, but consider the following two submissions:

https://mirror.codeforces.com/contest/2114/submission/322609464

https://mirror.codeforces.com/contest/2114/submission/321513639

You may notice that these two codes have the same code. However, curiously, the PyPy compiler gives TLE while the Python compiler gives AC. Considering that CodeForces almost always asks me to switch to PyPy when I try to submit in Python since it is faster, it made me wonder what made Python run faster than PyPy. (I used the latest compilers for both versions.)

Any insights into this would be extremely useful.

Additionally, any inputs to optimise my solution to problem D of the same contest are also welcomed.

PROBLEM: https://mirror.codeforces.com/contest/2114/problem/D

MY SOLUTION: https://mirror.codeforces.com/contest/2114/submission/321675571

PS: 1) Do tag me in case you figure anything out and you comment on this post.

PS: 2) Would be extremely grateful if you could upvote this(idc about contribution et. al. , but what I want is genuine issues like these to reach to those who can solve this so that we can grow together)

State

Command

Result

Yes del

time pypy3.10 E1.py < testE.txt

pypy3.10 E1.py < testE.txt 1.07s user 0.05s system 94% cpu 1.181 total

No del

time pypy3.10 E2.py < testE.txt

pypy3.10 E2.py < testE.txt 0.07s user 0.04s system 66% cpu 0.169 total

Comments (7)

Write comment?

fisher199

11 months ago, hide # |

+28

Hello there!

After analyzing your code, the only thing that kinda stuck out to me was the del operator. After doing a bit of digging, I came across this page: https://doc.pypy.org/en/latest/cpython_differences.html

Here, it states that del can sometimes execute itself in a non-immediate form. So, I simply removed the del operator from your code and it sped up. Here are the specific results on my machine with a generated test:

State	Command	Result
Yes `del`	time pypy3.10 E1.py < testE.txt	pypy3.10 E1.py < testE.txt 1.07s user 0.05s system 94% cpu 1.181 total
No `del`	time pypy3.10 E2.py < testE.txt	pypy3.10 E2.py < testE.txt 0.07s user 0.04s system 66% cpu 0.169 total

The only difference between E1.py and E2.py is that E2.py does not the del command.

E1.py

import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    n = int(input())
    danger = list(map(int, input().split()))
    adj = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int, input().split())
        adj[u - 1].append(v - 1)
        adj[v - 1].append(u - 1)
    threats = [0] * n
    stack = [(0, -1, 0, 0)]
    while stack:
        node, parent, pos, neg = stack.pop()
        threats[node] = danger[node] + neg
        curr_pos_contri = max(0, danger[node] + neg)
        curr_neg_contri = max(0, -danger[node] + pos)
        for child in adj[node]:
            if child != parent:
                stack.append((child, node, curr_pos_contri, curr_neg_contri))
    print(' '.join(map(str, threats)))
    del adj, threats, danger, stack

E2.py

import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    n = int(input())
    danger = list(map(int, input().split()))
    adj = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int, input().split())
        adj[u - 1].append(v - 1)
        adj[v - 1].append(u - 1)
    threats = [0] * n
    stack = [(0, -1, 0, 0)]
    while stack:
        node, parent, pos, neg = stack.pop()
        threats[node] = danger[node] + neg
        curr_pos_contri = max(0, danger[node] + neg)
        curr_neg_contri = max(0, -danger[node] + pos)
        for child in adj[node]:
            if child != parent:
                stack.append((child, node, curr_pos_contri, curr_neg_contri))
    print(' '.join(map(str, threats)))
    # del adj, threats, danger, stack

generator.py

t = int(1e4)
n = int(2e5)//t
a = [str(int(1e9))]*n
e = [(i + 1, i + 2) for i in range(n - 1)]

with open("testE.txt", "w") as f:
	f.writelines(f"{t}\n")
	for _ in range(t):
		f.writelines(f"{n}\n")
		f.writelines(" ".join(a))
		f.writelines("\n")
		for a_, b_ in e: f.writelines(f"{a_} {b_}\n")

→ Reply

CodingNinja007

Hey there, hope you doing well!!!

Removing the del did, in fact, reduce the time taken and got me the AC. Reading docs like these often gets very intimidating, and your explanation was very succinct and clear. Thanks a lot for your help!!!

If you could also help in optimising my solution to problem D(linked in the original blog), it would be wonderful!

Thanks once again for all your help and support. Existence of people like you makes CP so fun and engaging.

11 months ago, hide # ^ |

Uh, the most obvious thing that might be slowing down your code is the Counter perhaps. As a matter of fact, there is no need to actually use that counter, as your find_min_max_second would work just fine... After all, you could make it return the smallest value and the second smallest value even if the two are the same. Does that make sense? Then, inside of your loop, you could just do something like this:

If value is different to $$$m_1$$$, use $$$m_1$$$.
Else, use $$$m_2$$$. If $$$m_2 \neq m_1$$$, then everything works. And, if $$$m_2 = m_1$$$ then it means that this dimension is immutable and nothing changes.

Notice that I use $$$m_1$$$ and $$$m_2$$$ to generalize the minimum in X, then the minimum in Y, the maximum in X, and finally the maximum in Y. Does that make sense?

I'm not too familiar with the exact complexity of the Counter class, but seeing as it uses python dictionary I believe worst case access can be O(n) instead of O(1) (they use hashtables). So then, just by eliminating that counter, your code should pass...

Yeah what you are saying does make sense. I was trying to code your idea but was getting stuck a lot. I'll try it again and will hopefully upsolve this question.

Thanks a lot for all your help :) .

phongnc

I had a similar experience in the most recent Edu round, problem 2111D - Creating a Schedule, submissions 322723177 (AC with Python 3.13) and 322721346 (TLE with PyPy 3.10). The submissions include a call to sort() on a list of length $$$10^5$$$.

I would expect the $$$O(n \text{log}n)$$$ worst-case sorting algo to pass this comfortably, but it didn't. So I went to Google to find out if it's really $$$O(n \text{log}n)$$$ worst-case. Then I came across this, saying starting with version 3.11 an improvement was applied to the sorting algo. In the article the changelog is quoted, saying that Most uses of list.sort() probably won’t see a significant time difference, but may see significant improvements in cases where the former strategy was exceptionally poor. I have yet to read anything further (and not sure whether I will understand if I do), so I am not sure if it is directly related.

akioweh

the issue seems to be your N^2 string building (+= to strings makes a copy every time, so you're copying O(N) chars N times (in a loop) -> O(N^2))

as a proper alternative, use a list arr for string fragments, append to it in a loop, and do ''.join(arr) at the end to obtain a big concatenated string. (or just print(*arr))

(the patch to timsort youve mentioned usually doesnt manifest significant runtime differences unless you specifically look for it, and it definitely does not change the n log n complexity of the sort)

Oh yes, I was also afraid the string concat made it worse, but somehow thought to switch language first before fixing it. And thank you for the note on timsort!

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

#	User	Contrib.
1	Qingyu	157
2	adamant	153
3	Um_nik	146
3	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

CodingNinja007's blog