How to play cat and mouse game ft leetcode contests

Links

#

My banned leetcode post link

Prelude

#

As a prevailing trend, the current Leetcode problem setters have once again engaged in post-contest hacking, targeting the rolling hash solution for the 3036. Number of Subarrays That Match a Pattern II problem.

This has resulted in 3 people getting hacked among top 25 in Leetcode Weekly Contest 384. I firmly oppose the notion of rejudging after the contest has concluded. Many share this sentiment, including prominent figures such as:

1. Petr Mitrichev, a former world no 1 competitive programmer. He wrote against this practice 11 years ago
2. Alex Wice, a former top-ranked Leetcode participant - Here
3. Joshua Chen, the current second-ranked participant on Leetcode - Here

Despite the widespread disapproval, it appears that these individuals are adamant about persisting with their disruptive behavior. Until they cease such actions, I am compelled to introduce strategies to navigate this challenging scenario, aiming to empower participants to maintain an advantage against such unfair practices in this cat and mouse game. This endeavor aims to shed light on the absurdity of such actions.

How to avoid getting hacked?

#

Unordered_map in C++

#

1. You’ve been gearing up for an upcoming FAANG interview, and in your preparations, you learned that employing a hashmap yields O(1) time complexity. Consequently, you opted to utilize the STL unordered_map in your LeetCode contest submission. However, after the contest concluded, you discovered that your solution had been compromised through hacking.

Yes, you heard it right. It is very easy to create collisions against unordered_map. Refer here for details. To safeguard against such compromises, consider incorporating the following code snippet when utilizing an unordered_map:

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

unordered_map<long long, int, custom_hash> safe_map;

Set/Dict in python

#

2. But hey, why do I care. I use python. However, you’re at a greater risk as it’s even easier to hack sets/dicts in Python. You can refer to here for more information.

To mitigate this risk, moving forward, it’s advisable to include the following snippet in your code. You can find a sample implementation here.

from random import getrandbits

RANDOM = getrandbits(32)

class Wrapper(int):
    def __init__(self, x):
        int.__init__(x)
    def __hash__(self):
        return super(Wrapper, self).__hash__() ^ RANDOM

Rolling hash algorithm

#

3. Now, returning to the initial hacking method targeting the rolling hash algorithm.

For future implementations, it is recommended to employ three distinct modulo values and a randomized bases. Fixed bases with two modulo values are susceptible to hacking, refer here.

Here’s a code snippet to help you implement this precaution:

typedef uint64_t ull;
static int C; // initialized below

// Arithmetic mod two primes and 2^32 simultaneously.
// "typedef uint64_t H;" instead if Thue-Morse does not apply.
template<int M, class B>
struct A {
    int x; B b; A(int x=0) : x(x), b(x) {}
    A(int x, B b) : x(x), b(b) {}
    A operator+(A o){int y = x+o.x; return{y - (y>=M)*M, b+o.b};}
    A operator-(A o){int y = x-o.x; return{y + (y< 0)*M, b-o.b};}
    A operator*(A o) { return {(int)(1LL*x*o.x % M), b*o.b}; }
    explicit operator ull() { return x ^ (ull) b << 21; }
    bool operator==(A o) const { return (ull)*this == (ull)o; }
    bool operator<(A o) const { return (ull)*this < (ull)o; }
};
typedef A<1000000007, A<1000000009, unsigned>> H;

struct HashInterval {
    vector<H> ha, pw;
    HashInterval(string& str) : ha(sz(str)+1), pw(ha) {
        pw[0] = 1;
        rep(i,0,sz(str))
            ha[i+1] = ha[i] * C + str[i],
            pw[i+1] = pw[i] * C;
    }
    H hashInterval(int a, int b) { // hash [a, b)
        return ha[b] - ha[a] * pw[b - a];
    }
};

vector<H> getHashes(string& str, int length) {
    if (sz(str) < length) return {};
    H h = 0, pw = 1;
    rep(i,0,length)
        h = h * C + str[i], pw = pw * C;
    vector<H> ret = {h};
    rep(i,length,sz(str)) {
        ret.push_back(h = h * C + str[i] - pw * str[i-length]);
    }
    return ret;
}

#include <sys/time.h>
int main() {
    timeval tp;
    gettimeofday(&tp, 0);
    C = (int)tp.tv_usec; // (less than modulo)
    assert((ull)(H(1)*2+1-3) == 0);
    // ...
}

Epilogue

#

In conclusion, a note for @Leetcode admin:

Firstly, allow me to introduce myself. I am one of the contest administrators, problem setters, and testers overseeing ICPC regionals in India. Additionally, I had the privilege of being part of the team that clinched the title of Asia West Champion in a previous ICPC World Finals.

Secondly, I would like to address the purpose of this blog. My intention is to convey a straightforward message: please stop the practice of rejudging contests post-competition. I firmly believe that the majority of contests remain valid and fair without the need for rejudging. The more frequent rejudging occurs, the more it reflects on the competency of your team, especially when such actions were unnecessary from the outset. This is my stance, unequivocally. Period.