Blog entries - Codeforces

#	User	Rating
1	Benq	3676
2	jiangly	3670
3	Kevin114514	3657
4	maroonrk	3355
5	Um_nik	3353
6	squareOf105	3346
7	tourist	3343
8	strapple	3324
9	heuristica	3322
10	jiangbowen	3291

#	User	Contrib.
1	Qingyu	158
2	nik_exists	150
2	maspy	150
4	AmShZ	143
5	Um_nik	141
6	Errichto	139
7	adamant	137
8	BledDest	133
8	maroonrk	133
10	qwexd	129

Welcome to the Cheater Got Talent's second episode! It has been 10 days since the last episode; I'm sorry because I've been busy lately. So, here we go—episode 2 of Cheater Got Talent!

And today's guest: a Master whose peak rating is Grandmaster: bismispis. Also, a big shoutout to Christine-'s community for finding this cheater.

Let's take a look at bismispis's contests:

His (or her?) contests look normal, except for the 6th and 7th contests (believe me, this is a coincidence...), where he placed first and where he solved nothing.

Let's take a closer look at his 6th contest:

At first glance, his code seems normal. Although he has long variable names in F (best_leaf, max_cand, etc.), his submissions for A, B, C, D, and E seem to be legitimate. Maybe he solved A–E by himself, then used AI for F. This is just a theory.

There isn't enough evidence to conclude that he cheated, so let's continue with his 7th contest.

(Tip for finding cheaters: If the person you're investigating participated in a contest and solved 0 problems, it's likely that their submissions were skipped.)

Just as we expected, his entire contest was skipped. But, to be honest, his skipped submissions look fine. For example:

His code for H

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 998244353;

int main() {
    ll t;
    cin >> t;
    
    while (t--) {
        ll n;
        cin >> n;
        string s;
        cin >> s;
        
        vector<ll> p(n + 2, 0);
        vector<ll> q(n + 2, 0);
        
        for (ll i = 0; i < n; i++) {
            p[i + 1] = p[i];
            q[i + 1] = q[i];
            if (s[i] == '1') {
                p[i + 1]++;
            }
            if (s[i] == '?') {
                q[i + 1]++;
            }
        }
        p[n + 1] = p[n];
        q[n + 1] = q[n];
        
        auto check = [&](ll l, ll r) {
            if (l >= r - 1) {
                return true;
            }
            ll qs = q[r - 1] - q[l];
            ll ones = p[r - 1] - p[l];
            if (qs > 0) {
                return true;
            }
            if (ones % 2 == 0) {
                return true;
            }
            return false;
        };
        
        vector<vector<vector<int>>> nxt(n + 2, vector<vector<int>>(2, vector<int>(2, n + 1)));
        
        for (ll i = 0; i <= n; i++) {
            for (ll c = 0; c < 2; c++) {
                char tar = '0';
                if (c == 1) {
                    tar = '1';
                }
                for (ll j = i + 1; j <= n; j++) {
                    if (s[j - 1] == tar || s[j - 1] == '?') {
                        if (check(i, j)) {
                            ll par = p[j] % 2;
                            if (nxt[i][c][par] == n + 1) {
                                nxt[i][c][par] = j;
                            }
                        }
                    }
                }
            }
        }
        
        ll ans = 0;
        int lim = n + 2;
        vector<int> dp(lim * lim, 0);
        dp[n + 1] = 1;
        
        for (ll m = 0; m <= n + 1; m++) {
            auto go = [&](ll u, ll v) {
                int val = dp[u * lim + v];
                if (val == 0) {
                    return;
                }
                
                bool acc = false;
                if (u <= n) {
                    if (check(u, n + 1)) {
                        acc = true;
                    }
                }
                if (v <= n) {
                    if (check(v, n + 1)) {
                        acc = true;
                    }
                }
                
                if (acc) {
                    ans = (ans + val) % MOD;
                }
                
                for (ll c = 0; c < 2; c++) {
                    ll nu = n + 1;
                    ll nv = n + 1;
                    
                    if (u <= n) {
                        if (nxt[u][c][0] < nu) {
                            nu = nxt[u][c][0];
                        }
                        if (nxt[u][c][1] < nv) {
                            nv = nxt[u][c][1];
                        }
                    }
                    if (v <= n) {
                        if (nxt[v][c][0] < nu) {
                            nu = nxt[v][c][0];
                        }
                        if (nxt[v][c][1] < nv) {
                            nv = nxt[v][c][1];
                        }
                    }
                    
                    if (nu <= n || nv <= n) {
                        dp[nu * lim + nv] = (dp[nu * lim + nv] + val) % MOD;
                    }
                }
            };
            
            for (ll v = m; v <= n + 1; v++) {
                go(m, v);
            }
            for (ll u = m + 1; u <= n + 1; u++) {
                go(u, m);
            }
        }
        
        cout << ans << endl;
    }
    
    return 0;
}

His code for F

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 300000;
int carr[MAXN];
ll warr[MAXN];
ll smarr[MAXN];
ll arrg[20];

int main() {
    ll t;
    cin >> t;
    
    while (t--) {
        ll n;
        ll k;
        cin >> n >> k;
        
        vector<ll> a(n);
        ll sum = 0;
        
        for (ll i = 0; i < n; i++) {
            cin >> a[i];
            sum += a[i];
        }
        
        sort(a.rbegin(), a.rend());
        
        ll ans = 0;
        
        for (ll i = 0; i < n; i++) {
            ll x = a[i];
            ll l = 0;
            
            if (ans + 1 - x > 0) {
                l = ans + 1 - x;
            }
            
            ll r = (sum - x) / k;
            
            if (l > r) {
                continue;
            }
            
            ll sz = n - 1;
            ll mx = 1LL << sz;
            int idx = 0;
            
            for (ll j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                arrg[idx] = a[j];
                idx++;
            }
            
            smarr[0] = 0;
            for (ll mask = 1; mask < mx; mask++) {
                ll bit = mask & -mask;
                int j = __builtin_ctzll(bit);
                smarr[mask] = smarr[mask ^ bit] + arrg[j];
            }
            
            ll best = -1;
            
            while (l <= r) {
                ll mid = l + (r - l) / 2;
                bool ok = false;
                
                if (mid == 0) {
                    ok = true;
                } else {
                    for (ll mask = 0; mask < mx; mask++) {
                        carr[mask] = -1;
                        warr[mask] = 0;
                    }
                    carr[0] = 0;
                    
                    for (ll mask = 0; mask < mx; mask++) {
                        int cnt = carr[mask];
                        if (cnt == -1) {
                            continue;
                        }
                        
                        ll cw = warr[mask];
                        ll cur = smarr[mask] - cw;
                        ll rem = (~mask) & (mx - 1);
                        
                        while (rem > 0) {
                            ll bit = rem & -rem;
                            rem = rem ^ bit;
                            int j = __builtin_ctzll(bit);
                            
                            ll nmask = mask | bit;
                            int ncnt = cnt;
                            ll nw = cw;
                            
                            if (cur + arrg[j] >= mid) {
                                ncnt++;
                                nw = smarr[nmask];
                            }
                            
                            if (ncnt > carr[nmask]) {
                                carr[nmask] = ncnt;
                                warr[nmask] = nw;
                            } else if (ncnt == carr[nmask]) {
                                if (nw < warr[nmask]) {
                                    warr[nmask] = nw;
                                }
                            }
                        }
                    }
                    if (carr[mx - 1] >= k) {
                        ok = true;
                    }
                }
                
                if (ok) {
                    best = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            
            if (best != -1) {
                ll curval = best + x;
                if (curval > ans) {
                    ans = curval;
                }
            }
        }
        
        cout << ans << endl;
    }
    
    return 0;
}

Maybe his submissions were skipped because his code was similar to someone else's. However, I'm still convinced that he used AI, because:

If you take an even closer look, you'll notice that he submitted G five times, none of which received AC. Let's take a look at his first submission. It seems normal, except for the commented-out lines of code. Just 3 minutes later, at 02:39, he resubmitted it with many changes. You can find his second submission here. Let me remind you that this is a 3-hour contest. He had just solved ABCDEFH, so if he wanted to have a GM-level performance, he needed to solve more problems quickly. That's when he panicked.

Exactly 60 seconds later, he submitted I (at 02:40), which got TLE11. However, if I were him, I would argue that I had already written the solutions for G and I and simply submitted both at once.

As I said above, I think the second argument is weak because he can easily defend himself. That's why the last three submissions for G are important. He submitted the third version of G at 02:43 (3 minutes after his submission for I). His new code has only a few minor changes compared to the one he submitted 6 minutes earlier. Two minutes after receiving RTE3 on the third submission, he submitted the fourth one. This submission contains even fewer changes (you can check it yourself). A GM wouldn't do something like this because they would know that resubmitting code that is already wrong would only result in a 50-point penalty. In his final submission, he reverted the changes he made in the third and fourth submissions and also added a few comments. Someone who was panicking would never do this.

That's why I'm convinced that he used AI.

To be honest, I think the arguments I used in this case are much weaker than the ones I used in the first episode. Still, I believe that bismispis cheated.

So that's the end of the Cheater Got Talent's second episode! Thank you for reading, and I wish you all good luck in the upcoming Div. 1 + 2 contests.

P.S. I forgot to mention this earlier: when he submitted H at 01:13 (which got TLE11), he submitted another version at 01:24 (which was skipped during the main tests), and it differs significantly from the previous one.

Full text and comments »

CheaterGotTalent's blog