Блог пользователя Sugar_fan

Автор Sugar_fan, 6 месяцев назад, По-английски

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|<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})$$$:

$$$M=\begin{bmatrix} Q & I\\ P & 0 \end{bmatrix}.$$$

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<n$$$ and $$$|R[i]|<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<n$$$, multiply the first $$$n$$$ columns by a big integer $$$\lambda$$$, i.e.,

$$$M=\begin{bmatrix} \lambda Q & I\\ \lambda P & 0 \end{bmatrix}.$$$

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:

Полный текст и комментарии »

  • Проголосовать: нравится
  • +328
  • Проголосовать: не нравится

Автор Sugar_fan, 2 года назад, По-английски

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

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

Полный текст и комментарии »

Обсуждение Heltion Contest 1
  • Проголосовать: нравится
  • +262
  • Проголосовать: не нравится