Grading Server
Despite running low on oil, the opening ceremony was a great success. Now, the committee is looking forward to the first competition day. But what’s this? The chairman of the Technical Committee noticed some suspicious network activity—apparently someone is planning to hack the grading server!
The grading server possesses a specific computing power $c_G$ which the mysterious hacker will try to reduce to (or below) $0$. But the server is also protected by $f_G$ firewalls, each of which will reduce the impact of any attack by a fixed amount $S$. At each point in time, the hacker can now decide to either
- take down one of these firewalls, permanently reducing $f_G$ by $1$ (down to a minimum of $0$), or
- use all of their own computing power $c_H$ to attack the server, permanently reducing $c_G$ by $\max\left(c_H − f_G \cdot S, 0\right)$.
However, the chairman can strike back by either taking down one of the hacker’s $f_H$ firewalls or by using the grading server’s computing power to attack the hacker, which will similarly reduce 𝑐H by $\max\left(c_G − f_H \cdot S, 0\right)$. The chairman and the hacker take turns in their actions, with the hacker going first.
The committee will not know how much computing power and how many firewalls the hacker possesses until the hack has started. At the same time, because the committee might still be able to upgrade the server, its computing power and the number of its firewalls are also still unknown. To plan their defense, the committee therefore needs a program that tells them for $Q$ different scenarios $(c_H, f_H, c_G, f_G)$ whether the hacker can bring down the grading server even if the chairman makes optimal decisions.
$1 \leq S \leq 3 \times 10^4$
$1 \leq Q \leq 2.5 \times 10^5$
$1 \leq c_H, c_G \leq 10^{12}$
$0 \leq f_H, f_G \leq 10^{12}$
Editorial
Define $\alpha_1 = c_1 - S \cdot f_2$ and $\alpha_2 = c_2 - S \cdot f_1$, which indicates the actual to the opponent.
The state $\left(\alpha_1, f_1, \alpha_2, f_2\right)$ is winning, if and only if player 1 can defeat player 2; otherwise, it is losing.
We say that a player sabotages their opponent if they take down one of their firewalls.
Lemma 1
If $\left(\alpha_1, f_1, \alpha_2, f_2\right)$ is winning, then so is $\left(\alpha_1 + a, f_1 - b, \alpha_2 - c, f_2 + d\right)$. Or if $\left(\alpha_1, f_1, \alpha_2, f_2\right)$ is losing, then so is $\left(\alpha_1 - a, f_1 + b, \alpha_2 + c, f_2 - d\right)$. Where $a, b, c, d$ are non-negative integers. $\square$
Lemma 2
If $\alpha_1 \geq S$ and $\alpha_2 \leq S$, then $\left(\alpha_1, f_1, \alpha_2, f_2\right)$ is winning.
Proof. Player 1 can maintain this by attacking. After player 1 attacks, the situation will be $\left(\alpha_2 - \alpha_1, f_2, \alpha_1, f_1\right)$, because of $\alpha_1 \geq S, \alpha_2 \leq S$, we have $\alpha_2 - \alpha_1 \leq 0$, so player 2 cannot attack, so player 2 sabotages. the situation becomes $\left(\alpha_1, f_1 - 1, \alpha_2 - \alpha_1 + S, f_2\right)$. Notice that $\alpha_1 \geq S$. $\square$
Lemma 3
If $\alpha_2 \geq S$, it is optimal for player 1 to attack.
Proof. Consider a state $\left(\alpha_1, f_1, \alpha_2, f_2\right)$ where $\alpha_2 \geq S$ and $f_2$ is minimal, such that sabotaging is a winning move while attacking is not.
After player 1 sabotages, then player 2 attacks, the situation becomes $\left(\alpha_1 - \alpha_2 + S, f_1, \alpha_2, f_2 - 1\right)$. Notice we assumed that sabotaging is the winning move, then this state is winning. According to Lemma 1, $\left(\alpha_1, f_1, \alpha_2, f_2 - 1\right)$ is also winning. However, $f_2$ is minimal, this leads to a contradiction. $\square$
Corollary 1
From now on, we only consider states $\left(\alpha_1, f_1, \alpha_2, f_2\right)$ where $0 < \alpha_1, \alpha_2 < S$.
If player 1 sabotages, player 2 must attack.
Proof. The situation is $\left(\alpha_2, f_2 - 1, \alpha_1 + S, f_1\right)$, where $\alpha_1 + S \geq S$. According to Lemma 3, it is optimal to attack for player 2. It becomes $\left(\alpha_1 + S - \alpha_2, f_1, \alpha_2, f_2\right)$.
Define $\beta_1 = S - \alpha_1$ and $\beta_2 = S - \alpha_2$. If player 1 sabotages, the state will be $\left(\alpha_1 + \beta_2, f_1, \alpha_2, f_2 - 1\right)$.
Lemma 4
If $\beta_2 \cdot f_2 \geq \beta_1$, $\left(\alpha_1, f_1, \alpha_2, f_2\right)$ is winning.
Proof. Player 1 always sabotages: $\left(\alpha_1 + \beta_2 \cdot f_2, f_1, \alpha_2,0\right)$. $\alpha_1 + \beta_2 \cdot f_2 \geq \alpha_1 + \beta_1 = S$. Accords to Lemma 2, player 1 wins. $\square$
Corollary 2
Player 1 should avoid player 2 winning by Lemma 4. Assume player 1 attacks: $\left(\alpha_1' = \alpha_2 - \alpha_1, f_1' = f_2, \alpha_2' = \alpha_1, f_2' = f_1\right)$. $\beta_1' = S - \alpha_1' = S - \alpha_2 + \alpha_1, \beta_2' = S - \alpha_2' = S - \alpha_1$.
$$ \begin{aligned} \beta_2' \cdot f_2' &\geq \beta_1'\\ \left(S - \alpha_1\right) \cdot f_1 &\geq S - \alpha_2 + \alpha_1\\ \alpha_2 - \alpha_1 + \left(S - \alpha_1\right) \cdot f_1 &\geq S\\ \alpha_2 + S \cdot \left(f_1 - 1\right) &\geq \alpha_1 \left(f_1 + 1\right)\\ \frac{\alpha_2 + S \cdot \left(f_1 - 1\right)}{f_1 + 1} &\geq \alpha_1 \end{aligned} $$
Thus, if $\alpha_1 \leq \frac{\alpha_2 + S \cdot \left(f_1 - 1\right)}{f_1 + 1}$, player 1 cannot attack.
From now on, we only consider states $\left(\alpha_1, f_1, \alpha_2, f_2\right)$ where $\beta_2f_2 < \beta_1 < S$.
Lemma 5
If $\beta_2 f_1 f_2^2 > 8S$, $\left(\alpha_1, f_1, \alpha_2, f_2\right)$ is winning.
Proof. Player 1 sabotages $x$ times: $\left(\alpha_1 + x\beta_2, f_1, \alpha_2, f_2 - x\right)$.
Then player 1 attacks, $\beta_1' = \beta_1 - x \cdot \beta_2$. Thus, even if player 2 takes down all firewalls, we will have $\alpha_2 \leq S - x f_2 \beta_2$. This means $\beta_2' \geq xf_2\beta_1$. Now, player 1 takes down all remaining firewalls, increasing $\alpha_1$ by at least $x f_1 \beta_2 \cdot \left(f_2 - x\right)$.
Let $x = f_2 / 2$, $x f_1 \beta_2 \left(f_2 - x\right) = \frac14 f_1 \beta_2 f_2^2$. $\square$
Lemma 6
There are only $O \left(S \log S\right)$ states $(f_1, \beta_2, f_2)$ where $f_2 > 0$ such that $\left(f_1 + 1\right) \beta_2 f_2^2 \leq 8S$.
Proof.
$$ \begin{aligned} T &= O\left(\sum\limits_{i = 1}^{\sqrt{8S}} \sum\limits_{j = 0}^{\frac{8S}{i^2}}\frac{8S}{i^2j}\right)\\ &= O\left(8S \sum\limits_{i = 1}^{\sqrt S}\sum\limits_j^S\frac1{i^2j}\right)\\ &= O\left(S \sum\limits_{i = 1}^{\sqrt S}\frac1{i^2}\log S\right)\\ &= O\left(S \log S \cdot \frac\pi6\right)\\ &= O\left(S \log S\right) \quad \square \end{aligned} $$
Thus, for every $(f_1, \beta_2, f_2)$, use binary search to determine the minimal $\alpha_1$ such that $(\alpha_1, f_1, S - \beta_2, f_2)$ is winning. We have got a $O\left(S \log^2 S\right)$ algorithm.
Lemma 7
There exists a $\gamma = \gamma\left(f_1, f_2\right)$ such that it is optimal for player 1 to attack if $\alpha_2 \geq \gamma$, or it is optimal for player 1 to sabotage.
Proof. Consider the state $T_1 = \left(\alpha_1, f_1, \alpha_2, f_2\right)$ and $T_2 = \left(\alpha_1 + 1, f_1, \alpha_2 + 1, f_2\right)$.
If attack is a winning move in $T_1$, then so it is in $T_2$.
$T_1' = \left(\alpha_2 - \alpha_1, f_1, \alpha_1, f_2\right)$ and $T_2' = \left(\alpha_2 - \alpha_1, f_1, \alpha_1 + 1, f_2\right)$
According to Lemma 1, $T_2'$ is also losing, so player 1 wins.If sabotage is a losing move in $T_1$, then so it is in $T_2$.
$T_1' = \left(\alpha_1 + \beta_2, f_1, \alpha_2, f_2 - 1\right)$ and $T_2' = \left(\alpha_1 + \beta_2, f_1, \alpha_2 + 1, f_2 - 1\right)$
According to Lemma 1, $T_2'$ is also losing.
Define $c_A\left(f_1, f_2, \alpha_2\right)$ as the minimal $\alpha_1$ such that attack is the winning move in $\left(\alpha_1, f_1, \alpha_2, f_2\right)$.
Define $c_S\left(f_1, f_2, \alpha_2\right)$ as the minimal $\alpha_1$ such that sabotage is the winning move in $\left(\alpha_1, f_1, \alpha_2, f_2\right)$.
Referring to the above example, we will find $c_A\left(f_1, f_2, \alpha_2 + 1\right) \leq c_A\left(f_1, f_2, \alpha_2\right) + 1$ and $c_S\left(f_1, f_2, \alpha_2 + 1\right) \geq c_S\left(f_1, f_2, \alpha_2\right) + 1$.
Hence, $c_S\left(f_1, f_2, \alpha_2 + 1\right) - c_A\left(f_1, f_2, \alpha_2 + 1\right) \geq c_S\left(f_1, f_2, \alpha_2\right) - c_A\left(f_1, f_2, \alpha_2\right)$, let $\delta\left(f_1, f_2, \alpha_2\right) = c_S\left(f_1, f_2, \alpha_2\right) - c_A\left(f_1, f_2, \alpha_2\right)$, then we have $\delta\left(f_1, f_2, \alpha_2 + 1\right) \geq \delta\left(f_1, f_2, \alpha_2\right) \geq 0$.
Thus, $\delta\left(f_1, f_2, \alpha_2\right) \geq 0 \Rightarrow c_S\left(f_1, f_2, \alpha_2\right) \geq c_A\left(f_1, f_2, \alpha_2\right)$. $\square$