When I was doing the problem C. Pokémon Arena in the last Div. 1 round, I submitted my solution and got a TLE on pretest 20.

• GNU C++20 (64), TLE 3000ms 248951083.

I was not suspecting anything but my code, I thought there may be some degenerate issue, undefined behavior or constant issue, but nothing really found. After some unsuccessful attempts, I was able to pass the pretest using fast IO. It's then I found something weird: it only takes a few hundred milliseconds, which is contradictory to my intuition: cin with sync_with_stdio(false) is fairly fast and it should not take up so much more (at least 10x) time.

After the contest, I submitted exactly the same code with different language. You know what?

• GNU C++17, AC 280ms 248983571.

It's not only me, and some other participants also encountered such issue. For example:

• GNU C++20 (64), TLE 248946386 by fallleaves01.

Here's snippet for the key code:

int n, m;
cin >> n >> m;
vector a(n, vector (m, 0));
vector c(n, 0);
for (int i = 0; i < n; i++) cin >> c[i];
for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		cin >> a[i][j];
	}
}

But there are also some successful cin submissions using GNU C++20 (64). After investigation by (including but not limited to) Sugar_fan, Boboge, -skyline-, the key components of TLE are:

• The language must be GNU C++20 (64).
• vector must be of int. If the elements are long long, it passed. 249050206
• The definition of 2D vector must be before reading c. If swap these two lines, it passed. 249050425

So here's the thing. It could not even be simply interpreted as some branch mispredictions or cache misses, it seems something is completely broken, and we still don't understand what is actually wrong.

ChatGPT is a NLP model released recently, and I found it unexpectedly strong. Here's the evidence.

The Problem : ABC 280 D

You are given an integer $$$K$$$ greater than or equal to $$$2$$$. Find the minimum positive integer $$$N$$$ such that $$$N!$$$ is a multiple of $$$K$$$.

Here, $$$N!$$$ denotes the factorial of $$$N$$$. Under the Constraints of this problem, we can prove that such an $$$N$$$ always exists.

Constraint: $$$2 \leq K \leq 10 ^ {12}$$$

ChatGPT correct submission

Here are the interactions. ChatGPT spoke Chinese to me (which I didn't figure out how to configure it), so I'd provide some translations here.

Human: (The problem statement with hint to use long long)

ChatGPT: We can use code to implement the above algorithm. (Code follows)

Human: This code can not process the case when the factorials are large. You can enumarate the answer, and when newly add n to the factorial, the gcd(K, n) factor can be eliminated, until K = 1. Try to optimize your code.

ChatGPT: In order to solve the above problems, we can optimize the code to handle the case where the factorial is too large. We can use enumeration to find the smallest positive number N that satisfies the condition, and then offset the divisor of gcd (K, n) in K with the order n of N each time until K is 1.

The implementation is as follows. (Code follows)

Human: The code is slow when K has a large prime factor. You can factorize K firstly, if K has a prime factor no less than 1e6, then print it as the answer. Otherwise, we run the previous algorithm to solve the problem.

ChatGPT: In order to speed up the program, we can optimize it to handle the case when K has large prime factor. We can factorize K firstly, if K has a prime factor no less than 1e6, then print it as the answer. Otherwise, we run the previous algorithm. Here's the implementation. (Partial code)

Human: You didn't write code completely, please finish it.

ChatGPT: (More code)

Human: In the above code, you modified k in the factorizing, leading a wrong answer in the latter algorithm. Please copy k to a temporary variable in order to avoid affecting the original code.

ChatGPT: (Same comment, code)

Human: You should output n-1 instead of n.

ChatGPT: (Correct code)

Human: Thank you! Your code passed the problem.

ChatGPT: You're welcome, it's pleasure of mine. Let me know if you have any other questions. I will try my best to help you.

Today when I took part in the Round #740 solving problem D. Top-Notch Insertions, my submission failed on test 2 without knowing why. After asserting I found that rope contains unwanted contents and I didn't fix the problem during the contest.

However, when I replace all __gnu_cxx::rope.erase(x) into __gnu_cxx::rope.erase(x, 1), my code works fine (idk if it will pass system test or not; at least, it passes asserting that all elements are rolled back to the initial state).

Then! I found it unbelievable to see the following code from here:

Look at the line 2318, comments: Erase, single character.

However, it calls erase(__p, __p + 1);, who will erase __p + 1 characters starting from the position __p.

I found it incredible since it's part of libstdc++. I don't know if there's a way to report such failure. Could anyone tell me if I can do something with it? (or instead, NEVER USE SUCH FUNCTION IN THE FUTURE)

Thank you!

UPD: I've submitted the bug to gcc.

Fortunately, it's quickly replied by Jonathan Wakely. Unfortunately, just exactly as adamant predicted, Jonathan Wakely wrotes:

We should just delete this class, so I don't have to keep fixing bugs in code that nobody uses or cares about.

Today when I am trying to solve acmsguru-113 with PyPy3 (because when I was submitting Python3, CodeForces noticed me that "Almost always, if you send a solution on PyPy, it works much faster"), I got lots of Wrong Answer on test 1. I thought it impossible because it's actually a very simple problem and I have confidence in my code. Then I rewrite it in C++, and with identical implementation it's accepted.

Then I realized that there may be problems in input format, so I wrote a tokenizer to solve this problem. However, it's just another WA on 1.

After one hour of struggling in finding bugs and differences, I found nothing but submitted it with Python3 — and it was an accepted!

Here are the python code with tokenizer, and submissions with this code : (It's not allow to view others' submissions so I paste here)

63721667 Oct/29/2019 19:32UTC+8 Lily 113 — Nearly prime numbers Python 3 Accepted 186 ms 0 KB

63721403 Oct/29/2019 19:28UTC+8 Lily 113 — Nearly prime numbers PyPy 3 Wrong answer on test 1 124 ms 0 KB

now_token = input().split()
now_token.reverse()
def nxt_token():
    global now_token
    if len(now_token) > 0:
        ret = now_token[-1]
        now_token.pop()
        return ret
    else:
        now_token = input().split()
        now_token.reverse()
        return nxt_token();

n = int(nxt_token())
while n > 0:
    n -= 1
    x = int(nxt_token())
    ans = False
    i = 2
    while i * i <= x:
        if x % i == 0:
            y = x // i
            ans = (y > 1)
            j = 2
            while j * j <= y:
                if y % j == 0:
                    ans = 0
                    break
                j += 1
            break
        i += 1
    if ans:
        print("Yes")
    else:
        print("No")

I found it true that the data is not corresponding to the input format by asserting, but there must be something else with the PyPy3 interpreter.

Could anybody help me find the reason of it? Thanks a lot. QAQ

UPD: MikeMirzayanov has fixed the issue by updating PyPy. The issue is caused by older versions of PyPy output '\n' instead of '\r\n' on Windows.