---
title: Lời giải bài 6 TST 2023
---

# $D_{max} = 33$

Từ hai dữ kiện của đề bài:

- Vùng xanh là một vùng liên thông - hai đỉnh trong vùng xanh có thể đến được với nhau mà chỉ đi qua các đỉnh thuộc vùng xanh khác.
- Đình $P_0$ kề với các đỉnh còn lại $P_1, P_2, \dots, P_{|P| - 1}$

Ta có chiến thuật sau:

1. Trong hàm `request`, `client` gửi đỉnh $P_0$ cho `server`.
2. Trong hàm `query`:
Nếu $P_0$ nằm trong vùng xanh, `server` gửi $1$ cho `client`.
Ngoài ra, do vùng xanh liên thông, nên có tối đa một đỉnh kề với $P_0$ nằm trong vùng xanh.
Nếu không tồn tại đỉnh như thế, `server` gửi $0$ cho `client`.
Ngoài ra, gọi đỉnh đó là $u$, `server` gửi $2 + u$ cho `client`.
3. Trong hàm `answer`:
Nếu `client` nhận được $0$, thì đáp án là $-1$.
Nếu `client` nhận được $1$, thì đáp án là $P_0$.
Ngoài ra, gọi giá trị `client` nhận được là $x$, khi đó đỉnh kề $P_0$ nằm trong vùng xanh là $u = x - 2$.
Nếu $u$ nằm trong $P$, thì đáp án là $u$, ngoài ra đáp án là $-1$.

Để gửi một số $x$ đi, ta chỉ cần chuyển $x$ sang hệ nhị phân. Hàm `request` cần $16$ bit (giá trị tối đa cần gửi là $n - 1$), và hàm `query` cần $17$ bit (giá trị tối đa cần gửi là $n + 1$).

# $D_{max} = 18$

Ta tối ưu chiến thuật trên như sau:

1. Tối ưu cách gửi số bằng cách sử dụng kèm độ dài của xâu gửi đi. Cụ thể hơn, gọi $f(x)$ là độ dài xâu $s$ dùng để gửi đi số $x$, ta có cách gửi tối ưu như sau:

| x | s | f(x) |
| --- | ----- | ---- |
| $0$ | $0$ | $1$ |
| $1$ | $1$ | $1$ |
| $2$ | $00$ | $2$ |
| $3$ | $01$ | $2$ |
| $4$ | $10$ | $2$ |
| $5$ | $11$ | $2$ |
| $6$ | $000$ | $3$ |
| ... | ... | ... |

Vậy với cách gửi tối ưu thì $f(x) = \left\lfloor \log(x + 2) \right\rfloor$.

2. Để giảm số bit cần gửi ở hàm `query` khi đỉnh $P_0$ có bậc nhỏ, ta có thể gửi số thứ tự của đỉnh $u$ kề $P_0$ nằm trong vùng xanh trong danh sách kề của $P_0$.
Cụ thể hơn, gọi $adj[P_0]$ là danh sách kề của $P_0$ và $u = adj[P_0][i]$, thì ta sẽ gửi đi $i$.
3. Do điểm của bài phụ thuộc vào tổng độ dài hai xâu được gửi ở `query` và `request`, nên ta muốn giảm số bit cần gửi ở hàm `request` khi đỉnh $P_0$ có bậc lớn.
Ta có thể sắp xếp lại các đỉnh trong cây giảm dần theo bậc của đỉnh đó, và đánh dấu lại từ bé đến lớn.
Cụ thể hơn, gọi $sorted(u)$ là thứ tự của đỉnh $u$ sau khi được sắp xếp, thì ta sẽ gửi đi $sorted(u)$.

Tại sao cách tối ưu trên lại giúp giảm $D_{max}$ về còn $18$?

Xét một $P_0$ bất kì.
Ở hàm `query`, số bit được gửi đi tối đa xấp xỉ $\log(\deg P_0)$.
Ở hàm `request`, số bit được gửi đi tối đa xấp xỉ $\log(\frac{n}{\deg P_0})$
Vậy tổng số bit được gửi xấp xỉ
$$\log(\deg P_0) + \log(\frac{n}{\deg P_0}) = \log(\deg P_0) + \log(n) - \log(\deg P_0) = \log(n)$$

# $D_{max} = 17$

Ta sẽ tìm điều kiện để $D_{max} = 18$ để tối ưu nốt.

Gọi $a_i$ là đỉnh có bậc lớn thứ $i$ trong cây. Ở đây mình để $a$ là **1-indexed** để dễ tính toán.

Ta có:
- $\deg a_1, \deg a_2, \dots, \deg a_{i - 1}, \deg a_i \ge \deg a_i$
- $\deg a_{i + 1}, \dots, \deg a_n \ge 1$

$$
\begin{align*}
\implies & & i \cdot \deg a_i + (n - i) & \le \sum_{i=1}^n \deg a_i \\
\iff & & i \cdot \deg a_i + (n - i) & \le 2(n - 1) \\
\iff & & i \cdot (\deg a_i - 1) & \le n - 2 \\
\iff & & \deg a_i & \le \frac{n - 2}{i} + 1 \\
\end{align*}
$$

Xét một $P_0 = a_i$ bất kì.
Ở hàm `request`, số bit được gửi là $f(i - 1)$.
Ở hàm `query`, số bit được gửi là $f(2 + (\deg a_i - 1))$.

Điều kiện để tổng số bit được gửi đi là $18$ là:

$$
\begin{align*}
& & f(i - 1) + f(\deg a_i + 1) & \ge 18 \\
\iff & & \left\lceil \log (i + 1) \right\rceil + \left\lceil \log \left( \frac{n - 2}{i} + 4 \right) \right\rceil & \ge 18
\end{align*}
$$

Gọi $x = \left\lceil \log (i + 1) \right\rceil$, $1 \le x \le 16$.
Ta có:

$$
\begin{align*}
& & i + 1 & \ge 2^x \\
\iff & & i & \ge 2^x - 1 \\
\iff & & \frac{n - 2}{i} + 4 & \le \frac{n - 2}{2^x - 1} + 4
\end{align*}
$$

Mặt khác, $\frac{n - 2}{i} + 4 \ge 2^{18 - x}$

$$
\begin{align*}
\implies & & \frac{n - 2}{2^x - 1} + 4 & \ge 2^{18 - x} \\
\iff & & n - 2 + 4 \cdot (2^x - 1) & \ge 2^{18 - x} \cdot (2^x - 1) \\
\iff & & n - 2 + 2^{x + 2} - 4 & \ge 2^{18} - 2^{18 - x} \\
\iff & & n - 6 + 2^{x + 2} + 2^{18 - x} & \ge 2^{18} \\
\end{align*}
$$

Dễ nhận thấy do $n \le 2^{16}$, nên bất đẳng thức chỉ xảy ra khi $x + 2 \ge 18$ hoặc $18 - x \ge 18$.
Kết hợp với khoảng giá trị của $x$, ta có $x = 16$ hay $i \ge 2^{16} - 1$.

Vậy trường hợp tổng số bit được gửi đi là $18$ chỉ xảy ra khi đỉnh $P_0 = a_i$ là một trong hai đỉnh có bậc bé nhất của cây.
Do cây có ít nhất $2$ lá, nên $P_0$ bắt buộc phải là lá, và $|P| = 2$.
Khi đó, ta có thể hoán đổi giá trị của $P_0$ và $P_1$ cho nhau, hiển nhiên các điều kiện của đề bài vẫn thỏa mãn.
Do hai lá không thể kề nhau, nên $P_1 = a_j$ không phải là lá và do đó $j < 2^{16 - 1}$.
Vậy ta luôn tìm được cách tránh trường hợp dùng ít nhất $18$ bit, vậy $D_{max} = 17$.