Let us start with 2014H - Robin Hood Archery. A common solution assigns each value a random integer in $$$[0,L)$$$ and XORs the values in the interval. If every value appears an even number of times, the result is $$$0$$$. Otherwise, the result is $$$0$$$ with probability at most $$$1/L$$$.

Inspired by the hack used on 282284449 with xorshift, I found that many other submissions can also be hacked. The pitfalls of XOR hashing with mt19937_64 do not seem to be widely known, so I wrote this blog.

If we view both the internal state and the outputs as vectors over $$$\mathbb{F}_2$$$, then the $$$i$$$-th output of mt19937_64 with initial state $$$x$$$ can be written as $$$o_i = BA^i x$$$, where $$$A$$$ is the state transition matrix and $$$B$$$ is the output matrix over $$$\mathbb{F}_2$$$.

Thus, to make the XOR zero for every seed, it is enough to find a nonzero polynomial $$$p(t)=\sum_i a_i t^i$$$ such that $$$p(A)=0$$$. Then

Such a polynomial can be the minimal polynomial of $$$A$$$, whose degree is $$$19937$$$ for mt19937_64. By observing the least significant bit of the first $$$2 \times 19937$$$ outputs, we can recover the recurrence of this bit sequence using Berlekamp–Massey. This recurrence divides the minimal polynomial. Since mt19937_64 is designed to have maximal period, the corresponding polynomial is primitive, hence irreducible. Thus any nonzero recovered recurrence must be the full minimal polynomial.

The following is the test case generator.

#include <bits/stdc++.h>
using namespace std;
template <typename RNG, size_t DEG> auto hack() -> bitset<DEG + 1> {
  RNG rng;
  bitset<DEG + 1> a, b, c;
  b[DEG] = c[DEG] = 1;
  for (size_t l = 0, shift = 1; size_t n : views::iota(0u, DEG * 2)) {
    a >>= 1;
    a[DEG] = rng() & 1;
    if ((c & a).count() % 2 == 0) {
      shift += 1;
      continue;
    }
    auto oc = exchange(c, c ^ (b >> shift));
    if (2 * l <= n) {
      l = n + 1 - l;
      b = oc;
      shift = 1;
    } else {
      shift += 1;
    }
  }
  return c;
}
auto main() -> int {
  constexpr size_t DEG = 19937;
  auto a = hack<mt19937_64, DEG>();
  int64_t seed = 0;
  cin >> seed;
  mt19937_64 rng(seed);
  size_t hash = 0;
  for (size_t i = 0; i <= DEG; i += 1) {
    auto h = rng();
    if (a[i]) {
      hash ^= h;
    }
  }
  std::cout << hash << "\n";
  assert(hash == 0);
}

Using uniform_int_distribution(0, L) incorrectly can still cause the same issue. For example, the implementation is unsafe on common standard-library implementations when $$$L = 2^n-1$$$, because the distribution may degenerate into taking the low $$$n$$$ bits of rng(), which is still linear over $$$\mathbb{F}_2$$$.

Hello, Codeforces!

For the convenience of hacking codes that incorrectly use rolling hashes (i.e., using fixed modulos and bases), I wrote a tool in Rust, which runs entirely on the frontend and requires WebAssembly support.

Try it here and feel free to create issues.

Explanation of parameters:

• length: the length of generated strings;
• $$$\lambda$$$ (lambda)：detail follows;
• $$$\delta$$$ (delta) and $$$\eta$$$ (eta) : parameters of $$$L^2$$$ algorithm;
• precision: floating-point precision in decimal.

Given the modulos $$$\lbrace p_i\rbrace_{i=0}^{n-1}$$$ and the bases $$$\lbrace q_i\rbrace_{i=0}^{n-1}$$$, define $$$h_i(a)=\Big(\sum\limits_{j=0}^{\text{length}-1} q_i^js_j\Big)\bmod p_i$$$, where $$$a$$$ is a string of $$$\text{length}$$$. We want to find two strings $$$a$$$ and $$$b$$$ of $$$\text{length}$$$ such that $$$h_i(a)=h_i(b)$$$ for every $$$i$$$.

If we find a integer array $$$d$$$ of $$$\text{length}$$$ satisfying that $$$h_i(d)=0$$$ for every $$$i$$$, $$$|d_j| \lt 26$$$ for every $$$j$$$, and $$$d_j\ne 0$$$ for some $$$j$$$, we can easily construct $$$a$$$ and $$$b$$$ from $$$d$$$.

Construct a matrix $$$M$$$ of size $$$(n+\text{length})\times(n+\text{length})$$$:

where

• $$$Q$$$ is a matrix of size $$$\text{length} \times n $$$, where $$$Q_{ji}=q_i^j\bmod p_i$$$;
• $$$I$$$ is an identity matrix of size $$$(\text{length} \times \text{length})$$$;
• $$$P$$$ is a diagonal matrix of size $$$n\times n$$$, where $$$P_{ii}=p_i$$$,
• $$$0$$$ is a zero matrix of size $$$n\times \text{length}$$$.

We can find that the matrix $$$M$$$ has the following properties:

• For every row $$$R$$$ of $$$M$$$, that $$$h_i(R[n\cdots n+\text{length}])\equiv R[i] \pmod{p_i}$$$ holds for every $$$i$$$,
• $$$M$$$ is full rank.

Define the following operation:

• $$$R_i\leftarrow R_i-R_j\times k$$$, where $$$k\in \mathbb Z$$$.

We can find that this operation does not affect the properties of the matrix.

If after operations, there exists a row $$$R$$$ satisfying that $$$R[i]=0$$$ for every $$$i \lt n$$$ and $$$|R[i]| \lt 26$$$ for every $$$i\ge n$$$, we can find a solution $$$d=R[n\cdots n+\text{length}]$$$.

Intuitively, we should find the "shortest" row $$$R^*$$$. To make it more likey that $$$R^*[i]=0$$$ for every $$$i \lt n$$$, multiply the first $$$n$$$ columns by a big integer $$$\lambda$$$, i.e.,

This is well known as Shortest Vector Problem (SVP). Here, we use the $$$L^2$$$ algorithm to reduce $$$M$$$. More details about $$$L^2$$$ algorithm can be found in the paper mentioned below.

References:

• On the mathematics behind rolling hashes and anti-hash tests
• An LLL Algorithm with Quadratic Complexity

Hello everyone, this is my first contest, and now it is loaded on the gym.

It was used as 2022 Nowcoder Summer Camp, Day 8 and 2022 Petrozavodsk Summer Camp, Day 6.

All problems are prepared by me. Thanks

• jiangly for the idea of the problem C;
• lzr_010506 for reviewing the problems;
• Suika_predator for the solution of the problem L;
• Gassa for fixing the statements of the problems;
• MikeMirzayanov for Codeforces and Polygon;
• and all testers including 1zhuxiaobaicai, 20203246, 20km_shimakaze, All_Forward, AyoAyowei, Bruce12138, BruceW_07, gg_b0nd, Colorless, DFS_lover, Eden_CY, Frank_DD, GCCCCCCC, HorizonWind, Huah, Iamonlytupids, LKC314, apeiya, EternalJourney, Makaveli, EvenImage, Onozuka, PM250, PaperCloud, Pcjmy, RDDCCD, Randias, Rebelz, Roundgod, Rtx_, SSerxhs, The_Crossing, Tian_chen, Weierstrass, _ChenKerui, _ZLQ, acwing_lindi530, jzz2002, zzzgw, gouzhiqishi77, buns_out, cultu, dgklr, dyxg, emofunc, fr200110217102, fzx, gym580299, hjejeje, kimoyami, lukelin, nhc, no_power, oipotato, pikabi, playf, qiqi20021026, heuristica, stepsys, tarjen, triple__a, xuqijie, destination, yzyyylx, woruo27, and so on.

Hope you enjoy the problems and feel free to discuss them in the comments.