Yesterday, Furioso_Slient authored a blog article, in which he said that his submissions in Codeforces Round 1063 (Div. 2) were incorrectly skipped, and insisted he didn't cheat in the contest. I disagreed, and posted a comment to that blog post, showing some evidence that his submissions were indeed suspected to be AI-generated.

Today, he apparently made a reply to my comment, but I couldn't read it, because he deleted his original blog post for some reason. Now my comment is gone as the parent blog post is deleted. In this blog post, I recover what I wrote in my comment earlier with massive rewrites and additions, and try to explain why this person is a cheater. I usually don't write this kind of blogs, but I'm doing this time because (1) I don't want to waste my effort to investigate his submissions, and (2) I want to make him responsible for his own actions.

Evidence

I want to highlight his in-contest submissions to 2163B - Siga ta Kymata. He made six submissions in total; here are links to each of them in the chronological order:

• A: 348317920, submitted at 18:29:22, WA2.
• B: 348320121, submitted at 18:32:54, WA2.
• C: 348324641, submitted at 18:40:18, WA2.
• D: 348340077, submitted at 19:07:48, WA2.
• E: 348341711, submitted at 19:11:01, WA2.
• F: 348352209, submitted at 19:32:37, WA2.

I want to encourage you to look at the differences between A and B, and the differences between D and E (use the "Compare" button in the submission page). Those two pairs of submissions are only about 4 minutes apart each, yet there are surprisingly many differences between them (each pair).

Regarding A->B. This should be very clear; A is only 24 LOC but B suddenly becomes 161 LOC. It's very surprising if a human could write this amount of code in this short time period, in response to the WA verdict.

Regarding D->E. This is interesting in a different way. If you look at the diffs, you can see a lot of code churns that aren't fundamentally necessary. Examples include:

• A space after the keywords if, for, and while is consistently deleted.
• Variable names are renamed for no good reason — get_min -> qm, get_max -> qx, L -> l, R -> r, and l -> len.
• Prefix ++ operators are rewritten to postfix ones for no reason.
• Arguments passed to ios::sync_with_stdio() and cin.tie() are changed to false and nullptr, because they are cool, I suppose?
• When a vector of pairs is printed, a structured binding is used for no reason:

-            for (auto& pr : o) {
-                cout << pr.first << ' ' << pr.second << '\n';
+            for(auto [l, r] : o) {
+                cout << l << " " << r << '\n';

At this point, it should be clear: a sane human contestant doesn't make such code changes during a contest. It's undeniably clear that he used AI for writing his submissions. The admins skipping his submissions was a right call.

That's it. Opinions welcome.

I wrote a comment that contains a lot of math (but without source code) and tried to post it, then I got the following message:

The message window blocked me from posting a comment, and it was not possible to bypass the blocking, even though my post didn't contain any source code. I wasn't sure what part of my post causing this message to show up, so I ended up creating a blog post containing the message I originally wanted to post as a comment.

I kind of understand the motivation of this message box, but detection of source code seems buggy, and it's inconvenient to not be able to bypass it when a comment without source code is incorrectly blocked.

Admins, can you please fix this? Thanks!

Problem E. Monotone Subsequence

Suppose you made a query $$$[i_1, i_2, \ldots, i_k]$$$ and got a response $$$[j_1, j_2, \ldots, j_c]$$$. From the definition of visible skyscrapers, you can tell $$$i_1 = j_1$$$, and the following holds:

Based on this, think about the following algorithm:

• Initially $$$S_0 = \{ 1, 2, \ldots, n^2 + 1 \}$$$.
• Do the following $$$n$$$ times. In the $$$r$$$-th round $$$(1 \le r \le n)$$$, make a query consisting of all indices in $$$S_{r-1}$$$. Suppose you get a response $$$[j_1, j_2, \ldots, j_c]$$$. If $$$c \ge n+1$$$, you take any subsequence of length $$$n+1$$$ out of the response and make it an answer (because it's clearly increasing), then quit. Otherwise, $$$S_r = S_{r-1} \setminus \{ j_u \; | \; 1 \le u \le c \}$$$, then repeat.

Let's say you have completed $$$n$$$ rounds without making an answer. Clearly $$$S_0 \supset S_1 \supset \cdots \supset S_n$$$. Furthermore, $$$\left| S_{r-1} \right| - \left| S_{r} \right| \le n$$$, thus $$$\left| S_n \right| \ge (n^2 + 1) - n \cdot n = 1$$$.

Consider a directed graph $$$G$$$ consisting of $$$n^2 + 1$$$ vertices, initially with no edges. In round $$$r$$$, for every $$$i \in S_r$$$, there exists $$$j \in S_{r-1} \setminus S_{r}$$$ that satisfies $$$j \lt i$$$ and $$$p_j \gt p_i$$$, according to the relationship stated above. For every such $$$(i, j)$$$, add an edge $$$(j, i)$$$ to $$$G$$$. Then, for every $$$i \in S_r$$$, there is a path of length $$$r$$$ in $$$G$$$, ending at the vertex $$$i$$$ (this can be easily proven by induction). Therefore, after all rounds are processed, there is a path of length $$$n$$$ in $$$G$$$, ending at a vertex $$$i$$$ for any $$$i \in S_n$$$. Take any such path, then the $$$n + 1$$$ vertices in that path is an acceptable answer, because it forms a decreasing sequence.

Implementation note: The following is an easy way to find the final path. First, create an array $$$b = [-1, -1, \ldots, -1]$$$ of length $$$n^2 + 1$$$. For every round, record back edges: do $$$b[i] := j$$$ for every edge $$$(j, i)$$$ added to $$$G$$$. Then you can backtrack and recover the path, starting from any vertex in $$$S_n$$$.