Cheongrin's Game Development (Hard)

1. Task counts and days

Let $T$ be the common final progress and $m$ the number of days. Task $i$ must be selected $c_i=(T-a_i)/b_i$ times. The following conditions are necessary and sufficient:

$$c_i\in\mathbb Z_{\ge0},\qquad \sum_{i=1}^N c_i=Km,\qquad \max_i c_i\le m.$$

Necessity is immediate. For sufficiency, when $m>0$ days remain, choose the $K$ tasks with the largest remaining counts. At least $K$ counts are positive, and at most $K$ counts equal $m$, so every count equal to $m$ is selected. Decrementing the selected counts leaves total and maximum at most . Repetition constructs a valid schedule.

2. Bounding the final progress

Set $C=10^{18}$, $H=\max_i a_i$, and . Progress cannot decrease, and each task is selected at most once per day, so any solution with satisfies . By the input promise, if no solution with exists in this interval, the answer is impossible. The bound alone does not guarantee , so the day count must also be checked.

3. Generalized CRT

Integrality requires $T\equiv a_i\pmod{b_i}$ for every task. Maintain the merged congruence $T$, with , initially . Substituting into the next congruence gives .

Let $g=\gcd(D,b_i)$. If $g$ does not divide $a_i-r$, there is no solution. Otherwise, with , compute

$$x\equiv\frac{a_i-r}{g}\left(\frac Dg\right)^{-1}\pmod q$$

with $0\le x<q$, then update $r\leftarrow r+Dx$ and $D\leftarrow Dq$. When , use . Compute the inverse with the extended Euclidean algorithm.

If $D>U$ during merging, the only possible value in $[0,U]$ is $r$. Stop merging and directly check $T=r$ against the entire input: congruences, range, total count, maximum count, and day limit. Congruences not yet merged must also be checked.

4. Linear expressions and lower bounds

If all congruences have been merged and $D\le U$, write $T=r+Dt$. Define integers

$$\alpha_i=\frac{r-a_i}{b_i},\quad\beta_i=\frac D{b_i},\quad A=\sum_i\alpha_i,\quad W=\sum_i\beta_i.$$

Then $c_i=\alpha_i+\beta_i t$ and . Since , the day count increases with . Start with .

The condition $c_i\le m$ becomes $(K\beta_i-W)t\le A-K\alpha_i$. If , this gives the lower bound

$$t\ge\left\lceil\frac{K\alpha_i-A}{W-K\beta_i}\right\rceil.$$

Update $\ell$ with these bounds. Leave the other tasks for the final candidate check. Ceiling division must work correctly for negative numerators as well.

5. The first congruence candidate

The total count must be divisible by $K$, so solve $Wt\equiv-A\pmod K$. Let $g=\gcd(W,K)$. If does not divide , there is no solution. Otherwise divide by and use a modular inverse to obtain , where and . For , set . The first candidate at least is

$$t_*=t_0+P\left\lceil\frac{\ell-t_0}{P}\right\rceil.$$

First check $t_*\le\lfloor(U-r)/D\rfloor$. If this fails, report impossibility without performing the large multiplication. Otherwise compute $T=r+Dt_*$ and directly verify all original conditions.

6. Why one candidate is enough

All conditions with $K\beta_i<W$ were included in the lower bound. For every other task, $(K\beta_i-W)t$ is nondecreasing, so if its inequality fails at the first candidate, it fails at every later candidate. The day count also increases; if the first candidate has , later candidates cannot help. Thus a successful first candidate is optimal, and a failed first candidate implies impossibility.

7. Integer bounds and complexity

We have $U\le10^{27}+10^9$, and merging only while $D\le U$ gives $$. Reduce residues before multiplying by an inverse. The sums and lower-bound numerators are safely bounded in absolute value by . Multiply the candidate by only after checking its range, then recompute counts from to obtain the day count. Every intermediate value in this implementation therefore fits a signed -bit integer. Do not compute the unrestricted LCM or multiply an out-of-range candidate by .

With $B=\max_i b_i$ and fixed-width arithmetic, the time complexity is $O(N\log B+\log K)$ and the space complexity is .

8. Subtask solutions

In subtask 1, $b_i=1$. Set $d_i=H-a_i$, , and . The conditions become and . If , only an initially equal array is possible. Otherwise find the lower bound and enumerate the residue of from to , giving time.

In subtask 2, enumerate final progress from $H$ through $100\,000$ and check the necessary and sufficient conditions. Since $D\le\operatorname{lcm}(1,2,3,4,5)=60$, , and , the first candidate above has and the minimum feasible progress is below . The enumeration is therefore sufficient and takes time. Subtask 3 uses the full solution.

Solution written by GPT