Blog entries - Codeforces

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	dXqwq	3436
8	Radewoosh	3415
9	Otomachi_Una	3413
10	Um_nik	3376

#	User	Contrib.
1	Qingyu	157
2	adamant	153
3	Um_nik	146
3	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

Note. This English translation was produced with the help of ChatGPT.

This year, BSUIR Open XIV took place, and I was very happy to travel to Minsk and attend the contest itself. But what I liked even more was the problem that I proposed there. Overall, I had not seen this idea before, though it feels simple enough that it may well have appeared in some earlier contest. So if you know where this idea had shown up before, please let me know.

Problem. (*BSUIR OPEN XIV*) We are given a $$$100 \times 100$$$ grid. Some pairs of adjacent cells are separated by walls, and there are also walls along the boundary of the grid. A ray starts from the center of cell $$$(r,c)$$$ in direction $$$(x,y)$$$. We need to determine in which cell it will be after traveling a distance of $$$\sqrt{x^2+y^2}$$$, assuming the ray reflects off walls.

Solving the problem

Let us look at the vector $$$(x,y)$$$ and examine the order in which it crosses the vertical and horizontal grid lines. At the point $$$(0,0)$$$ we will ignore the intersection with grid lines, but we will count intersections at the point $$$(x,y)$$$; moreover, for formal reasons, we will assume that at $$$(x,y)$$$ the crossing with the vertical line happens first.

The sequence of crossings can be written as a string:

$$$R$$$ denotes crossing a vertical grid line (moving one cell to the right),
$$$U$$$ denotes crossing a horizontal grid line.

Thus, to each vector $$$(x,y)$$$ we can assign a string $$$s(x, y)$$$ containing the sequence of these crossings. For example,

$$$ s(4,3) = \texttt{RURURRU}. $$$

Assume that $$$x \ge y$$$. This means the vector is “shallow”, so before each crossing of a horizontal line there is a crossing of a vertical line. More precisely, before the $$$k$$$-th symbol U there are

$$$ \left\lfloor \frac{x}{y} \cdot k \right\rfloor - \left\lfloor \frac{x}{y} \cdot (k-1) \right\rfloor $$$

consecutive symbols R.

Therefore, before each symbol U there is a block containing at least $$$\left\lfloor x/y \right\rfloor$$$ symbols R; these blocks together with the symbols U can be compressed into a single symbol. For example,

$$$ s(4,3) = \texttt{RURURRU} = (\texttt{RU})(\texttt{RU})\texttt{R}(\texttt{RU}) \to s(1,3)=\texttt{UURU}. $$$

So, we may conjecture that if $$$s(x, y, R, U)$$$ denotes the string $$$s(x,y)$$$ where the symbols R and U are replaced by strings $$$R$$$ and $$$U$$$, then the following identity holds:

$$$ s(x,y,R,U)= \begin{cases} s(x-y\lfloor x/y\rfloor,\ y,\ R,\ R^{\lfloor x/y\rfloor}U), & x\ge y, \\\\ s(x,\ y-x\lfloor (y-1)/x\rfloor,\ U^{\lfloor (y-1)/x\rfloor}R,\ U), & x \lt y. \end{cases} $$$

This is indeed true. For example, in the case $$$x \ge y$$$ it is enough to check that after substitution, the number of consecutive R letters before the $$$k$$$-th symbol $$$U$$$ is preserved:

$$$ q = \left\lfloor \frac{x}{y} \right\rfloor: \qquad q + \left\lfloor \frac{x-qy}{y}\cdot k \right\rfloor - \left\lfloor \frac{x-qy}{y}\cdot (k-1) \right\rfloor $$$ $$$ = q + \left\lfloor \frac{x}{y}\cdot k - qk \right\rfloor - \left\lfloor \frac{x}{y}\cdot (k-1) - q(k-1) \right\rfloor $$$ $$$ = \left\lfloor \frac{x}{y}\cdot k \right\rfloor - \left\lfloor \frac{x}{y}\cdot (k-1) \right\rfloor. $$$

Thus, the string $$$s(x,y)$$$ can be computed using the Euclidean algorithm. Of course, in the general case we do not need the string itself, but rather some more useful information. The symbols R and U may belong to an arbitrary monoid for which we can efficiently compute the following operations:

product of elements;
exponentiation of an element.

For example, the monoid could consist of permutations, matrices, or any other objects that can be maintained in a segment tree. In particular, one can maintain the number of subsequences UR inside a substring of $$$s(x,y)$$$, which corresponds to computing floor_sum (though in that case one has to be careful about the priority/order of the symbols R and U).

In general form, the vector-tracking algorithm can be implemented as follows:

Download code with no registration and no SMS

template <typename M>
M GridEuclide(u64 x, u64 y, M R, M U) {
    while (x && y) {
        if (x >= y) {
            const u64 k = x / y;
            x -= y * k;
            U = R.Pow(k) * U;
        } else {
            const u64 k = (y - 1) / x;
            y -= x * k;
            R = U.Pow(k) * R;
        }
    }
    return !x ? U.Pow(y) : R.Pow(x);
}

Solution to the original problem

Other generalizations

During the algorithm, instead of building the composition of the monoids $$$R$$$ and $$$U$$$, we may build the sequence of partial quotients together with all intermediate computations. For example, for input $$$(x,y)$$$ the computation table looks as follows. Recall that

$$$ q = \max\left\{\left\lfloor \frac{x}{y}\right\rfloor,\ \left\lfloor \frac{y-1}{x}\right\rfloor\right\}. $$$

Step	Computed value	$$$q$$$	$$$x$$$	$$$y$$$
1	`RU`	1	4	3
2	`RURUR`	2	1	3
3	`RURURRU`	1	1	1

Working with all intermediate computations, we can additionally handle the following scenarios:

composition of the monoids $$$R$$$ and $$$U$$$ on any subsegment $$$(l,r)$$$ of the string $$$s(x,y)$$$.

For example, if we start the vector not from the point $$$(0,0)$$$ but from an arbitrary point $$$(\alpha, \beta)$$$, then the resulting string $$$s(x,y,\alpha,\beta)$$$ may differ from $$$s(x,y)$$$. However, it is also clear that the string $$$s(x,y,\alpha,\beta)$$$ is just a cyclic shift of the string $$$s(x,y)$$$.

To understand exactly which cyclic shift it is, recall that the string $$$s$$$ can be represented as a concatenation of blocks of the form R...RU, where the number of letters R before the $$$k$$$-th letter U is given by

$$$ \left\lfloor \frac{x}{y}\cdot k \right\rfloor - \left\lfloor \frac{x}{y}\cdot (k-1) \right\rfloor = \frac{x}{y}\cdot k - \frac{xk \bmod y}{y} + \frac{x(k-1) \bmod y}{y}. $$$

Therefore, if the vector starts from an arbitrary point $$$(\alpha/y, 0)$$$, then the length of the $$$k$$$-th block is given by a similar formula:

$$$ \left\lfloor \frac{x}{y}\cdot k + \frac{\alpha}{y} \right\rfloor - \left\lfloor \frac{x}{y}\cdot (k-1) + \frac{\alpha}{y} \right\rfloor = \frac{x}{y}\cdot k - \frac{(xk + \alpha) \bmod y}{y} + \frac{(x(k-1) + \alpha) \bmod y}{y}. $$$

If $$$x$$$ and $$$y$$$ are coprime, we may substitute

$$$ \alpha = k_0 x \pmod y. $$$

Then the number $$$k_0$$$ is exactly the desired cyclic shift.

Thus, the proposed algorithm is a universal (and probably not the best in terms of constant factors) way to solve many generalizations of floor_sum. In particular,

$$$ f(l, r, p, q, a, b, c) = \sum_{x=l}^r \left\lfloor \frac{a+bx}{c} \right\rfloor^p x^q $$$

can be computed in time

$$$ O(\log C \cdot pq(p+q)) $$$

in the general case, which is quite nice.

Full text and comments »

teraqqq's blog

Solving the problem

Other generalizations