title: "CF 1866L - Lihmuf Balling"
description: "There are $N$ boxes. Box $i$ initially contains $i$ balls. The game lasts for $N$ turns. On turn $j$, Pak Chanek always takes box $j$. Lihmuf chooses a value $K$ before the game starts, and on turn $j$ he always takes $$((jK-1)bmod N)+1." date: "2026-06-08T23:51:33+07:00" tags: ["codeforces", "competitive-programming", "binary-search", "brute-force", "math"] categories: ["algorithms"] codeforces_contest: 1866 codeforces_index: "L" codeforces_contest_name: "COMPFEST 15 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)" rating: 2400 weight: 1866 solve_time_s: 155 verified: false draft: false --- CF 1866L - Lihmuf Balling Rating: 2400 Tags: binary search, brute force, math Solve time: 2m 35s Verified: no ## Solution ## Problem Understanding There are $N$ boxes. Box $i$ initially contains $i$ balls. The game lasts for $N$ turns. On turn $j$, Pak Chanek always takes box $j$. Lihmuf chooses a value $K$ before the game starts, and on turn $j$ he always takes$$((jK-1)\bmod N)+1.$$
A box can be selected many times, but only the first selection matters because the box becomes empty immediately afterwards.
For every $K$ between $1$ and $M$, we can determine how many balls Lihmuf obtains. The task is to find the value of $K$ that maximizes that total. If several values of $K$ achieve the same maximum, we must output the smallest one.
The constraints completely determine the shape of the solution. The value of $N$ can be as large as $10^9$, so any algorithm that iterates over boxes or turns is impossible. At the same time, $M$ is only $2000$. That means we can afford to examine every candidate $K$, but for each one we need a formula whose running time depends on $K$, not on $N$.
A few edge cases are easy to mishandle.
Consider:
1 1
There is only one box. Pak always reaches it first, so the answer is 1. Any solution that assumes the sequence generated by Lihmuf contains distinct boxes will fail here.
Consider:
5 1
Lihmuf always chooses exactly the same box as Pak on the same turn. His score is zero. A careless implementation might treat "same turn" as a win for Lihmuf, but Pak always acts first.
Consider:
6 4
For $K=2$, Lihmuf only ever visits boxes divisible by $\gcd(6,2)=2$. The sequence is not a permutation of all boxes. Any derivation that silently assumes $\gcd(K,N)=1$ will produce incorrect results.
## Approaches
The most direct idea is to simulate the game for every $K$. For a fixed $K$, we could generate all $N$ turns, track which boxes are already empty, and accumulate Lihmuf's score.
That simulation is correct because it follows the rules literally. The problem is the cost. With $N=10^9$, even a single simulation is impossible. Repeating it for up to $2000$ values of $K$ is completely out of reach.
The key observation is that $K$ is small while $N$ is huge.
Let
$$d=\gcd(N,K),
\qquad
k=\frac{K}{d},
\qquad
n=\frac{N}{d}.$$
Instead of asking which box is taken, look at the turn number $j$.
For a fixed $j$, the box chosen by Lihmuf corresponds to
$$t_j \equiv kj \pmod n,$$
using residues $1 \ldots n$. More explicitly,
$$t_j = kj - nq,$$
where
$$q=\left\lfloor\frac{kj-1}{n}\right\rfloor.$$
Since $0 \le q < k$, there are only $k$ possible values of $q$. Because $k \le K \le 2000$, this is tiny.
The score contribution of a box depends only on whether Lihmuf reaches it before Pak. After rewriting the condition in terms of $j$ and $q$, every value of $q$ produces one contiguous interval of turns. Over that interval, the chosen box numbers form a simple arithmetic progression. Their total contribution can be computed with arithmetic-series formulas.
The entire score for one $K$ can be evaluated in $O(k)$ time, which is at most $2000$.
| Approach | Time Complexity | Space Complexity | Verdict |
| --- | --- | --- | --- |
| Brute Force | $O(MN)$ | $O(N)$ | Too slow |
| Optimal | $O!\left(\sum_{K=1}^{M} \frac{K}{\gcd(K,N)}\right)$ | $O(1)$ | Accepted |
## Algorithm Walkthrough
### Deriving the scoring formula
Let
$$d=\gcd(N,K), \qquad k=\frac{K}{d}, \qquad n=\frac{N}{d}.$$
For turn $j$, define
$$q=\left\lfloor\frac{kj-1}{n}\right\rfloor.$$
Then the box index in the reduced system is
$$t_j = kj-nq.$$
The actual box number is $d,t_j$.
Lihmuf gets the balls from that box iff he reaches it strictly before Pak. Pak reaches box $d,t_j$ on turn $d,t_j$, so the winning condition is
$$j < d,t_j.$$
Substituting $t_j=kj-nq$,
$$j < d(kj-nq).$$
After rearranging,
$$(dk-1)j > dnq.$$
### Grouping turns by $q$
For a fixed $q$,
$$q=\left\lfloor\frac{kj-1}{n}\right\rfloor$$
is equivalent to
$$\left\lfloor\frac{qn}{k}\right\rfloor + 1
\le j \le
\left\lfloor\frac{(q+1)n}{k}\right\rfloor.$$
Call this interval $[L,R]$.
Inside that interval,
$$t_j = kj-nq$$
is linear in $j$.
### Finding the winning part of the interval
The inequality
$$(dk-1)j > dnq$$
gives
$$j >
\frac{dnq}{dk-1}.$$
Hence the first winning turn is
$$A=
\max!\left(
L,
\left\lfloor\frac{dnq}{dk-1}\right\rfloor+1
\right).$$
All turns from $A$ to $R$ contribute to the score.
### Summing contributions
For every winning turn,
$$\text{box value}
=
d(kj-nq).$$
The contribution of interval $[A,R]$ is
$$d
\left(
k\sum_{j=A}^{R} j
nq(R-A+1) \right).$$ The sum of consecutive integers is computed in constant time.
Complete procedure
- Iterate $K=1$ to $M$.
- Compute $d=\gcd(N,K)$, $k=K/d$, $n=N/d$.
- For every $q=0,1,\dots,k-1$, compute its turn interval $[L,R]$.
- Find the first winning turn $A$.
- If $A \le R$, add the arithmetic-series contribution of that interval.
- The resulting total is Lihmuf's score for this $K$.
- Keep the maximum score and the smallest $K$ achieving it.
Why it works
For every turn $j$, there is exactly one value of $q=\lfloor(kj-1)/n\rfloor$. The intervals generated by different $q$ values partition all turns $1 \ldots n$. Within one interval, the selected box number