# Solution bài 1 Round 4 (bài 4) - Compress

Nhận thấy: Vì $n$ rất lớn nên không thể nào duyệt qua $n!$ hoán vị và kiểm tra được.
Ta buộc phải suy luận ra tập các hoán vị thỏa mãn từ dãy $s$ đã cho.

## Subtask 1: $k = 2, \Sigma n \leq 5000$
Nếu biết được $p_1$ thì sẽ có $p_2 = s_1-p_1$. Từ đó có $p_3 = s_2-p_2$. Cứ như vậy sẽ tính được toàn bộ $p$ bằng công thức $p_{i+1} = s_i - p_i$.
Ta duyệt qua $O(n)$ giá trị của $p_1$, sau đó lại tốn $O(n)$ phép tính để tính các giá trị của $p$.
Lọc ra được tối đa $n$ hoán vị *thỏa mãn* (có các giá trị nằm trong phạm vi $[1,n]$). Vì tất cả đều có $p_1$ khác nhau nên chi phí so sánh là $O(1)$ và ta dễ xác định được hoán vị thứ $x$
Độ phức tạp $O(n^2)$

## Subtask 2: $k = 2, \Sigma n \leq 10^5$
Quá trình tính $p$ ở subtask trên có thể rút thành nhận xét như sau: "Với $k = 2$, với $p_1$ cố định thì ta xác định được toàn bộ $p$"
Cụ thể hơn, toàn bộ dãy $p$ đều có thể biểu diễn theo $p_1$.
Thật vậy:
$p_2 = s_1-p_1$
$p_3 = s_2-p_2 = s_2-(s_1-p_1) = p_1-s_2+s_1$
$p_4 = s_3-p_3 = -p_1+s_3+s_2-s_1$
$\dots$
Các số $p_i$ có dạng $p_i = -p_1 + c$ hoặc $p_i = p_1 + c$ với $c$ là hằng số nào đó. Cụ thể: nếu $i$ chẵn thì sẽ có dạng $-p_1 + c$, nếu $i$ lẻ sẽ có dạng $p_1 + c$.
Như vậy giá trị $1$ (GTNN) chỉ có một trong hai dạng như trên. Dù ở dạng nào thì các giá trị $c$ trong mỗi dạng đó đều phân biệt (vì nếu không sẽ tồn tại $p_i = p_j$ với $i \neq j$). Do đó dù giá trị $1$ ở dạng nào thì phải có $1 = \pm p_1 + c$ với $c$ **nhỏ nhất**. Từ đó xác định được toàn dãy $p$.
Độ phức tạp $O(n)$

## Subtask 3: $k = 3, \Sigma n \leq 10^5$
Tương tự như trên, nếu biết được $p_1, p_2$ ta sẽ biết được toàn bộ $p$.
Ta biểu diễn các giá trị của $p$ bởi $p_1, p_2$ và $p_3$.
$p_i = s_{i-2} - p_{i-2} - p_{i-1} = s_{i-2} - (p_{i-2}+p_{i-1}+p_{i-3}) +p_{i-3} = p_{i-3} - s_{i-3} + s_{i-2}$.
Do đó:
$p_4 = p_1 - s_1 + s_2$
$p_5 = p_2 - s_2 + s_3$
$p_6 = p_3 - s_3 + s_4$
$p_7 = p_4 - s_4 + s_5 = p_1 - s_1 + s_2 - s_4 + s_5$
$\dots$
Vậy mỗi số chỉ có dạng $p_1 + c, p_2 + c$ hoặc $p_3 + c$.
Giả sử $1=p_j+c (1\le j\le3)$. Lúc này, bài toán đưa về như subtask 2. Đó là bởi vì đã tính được $p_j = 1-c$ nên mọi số có dạng $p_j + c$ đều tính được. Lúc này, trong $p$, cứ 3 số liên tiếp thì ta biết được giá trị của đúng một số.
Chỉ cần biết thêm giá trị của $p_i (i \neq j, 1 \le i \le 3)$ nữa thì xác định được toàn bộ $p$. Nói cách khác, tất cả những số còn lại đều có thể biểu diễn theo $p_i$ (có dạng $p_i+c$ hoặc $-p_i+c$ như đã phân tích ở trên). Lưu ý rằng GTNN lúc này không phải là $1$ nữa mà là một giá trị chưa xuất hiện trong các số có dạng $p_j + c$ mà ta vừa tính được.
ĐPT $O(n)$

## Subtask 4: $k \le 6, \Sigma n \leq 2.5 \times 10^5$
Để ý rằng: $s_{i+1} - s_i = p_{i+k} - p_i$.
Tổng quát hóa nhận xét ở subtask 2: "Nếu có $k-1$ giá trị đầu tiên của $p$ thì xác định được toàn dãy $p$" $(*)$
Hiển nhiên là không thể duyệt trong ĐPT $O(n^k)$. Ta cần phải có cách hiệu quả để lấy ra được các hoán vị.
Nhận xét: Ta chia $n$ vị trí trong $p$ thành $k$ nhóm, mỗi nhóm gồm những vị trí $i$ đồng dư $\mod k$.
Nếu biết được giá trị của phần tử bất kì trong nhóm, ta xác định được toàn bộ nhóm đấy, vì $s$ đã cho thông tin về hiệu $p_{i+k} - p_i \forall i+k \le n$.
Vậy $(*)$ có thể tổng quát hơn thành $k$ vị trí có số dư cho $k$ khác nhau chứ không hẳn chỉ là những vị trí đầu tiên.
Kí hiệu $m_j$ là vị trí số nhỏ nhất trong nhóm thứ $j$.
Không mất tính tổng quát, giả sử có $p_{m_1} < p_{m_2} < p_{m_3} < \dots < p_{m_k}$. Khi đó $p$ có thể được xác định duy nhất như sau: Ta tiến hành điền lần lượt các giá trị vào các vị trí trong $p$
- Duy trì tập $S$ các giá trị chưa dùng để điền. Lúc đầu $S = \{1,2,3,\dots,n\}$
- Mỗi lần điền, ta sẽ điền cho toàn bộ nhóm $j$ nào đó. Duyệt tăng dần theo $p_{m_j}$ (theo $j$ trong TH này). Vì duyệt tăng dần nên vị trí $m_j$ phải nhận giá trị bé nhất. Gán $p_{m_j} = \min S$ và xóa giá trị này ra khỏi tập $S$.
- Xác định giá trị cho mỗi vị trí trong nhóm $j$: Giả sử phải có $p_i = x$
+ Nếu $x \in S$ thì gán $p_i = x$ và xóa $x$ khỏi $S$
+ Ngược lại, hoán vị đang dựng không thỏa mãn.

Vì $p$ là hoán vị nên $m_j$ phân biệt. Do đó, khi ta so sánh $p_{m_j}$ sẽ có $k!$ trường hợp khác nhau.
Để tìm ra hoán vị có thứ tự từ điển thứ $x$, chỉ cần duyệt qua các hoán vị theo thứ tự tăng dần: Luôn ưu tiên cho những hoán vị có $p_{m_1}$ nhỏ nhất trước, rồi mới ưu tiên theo $p_{m_2}, p_{m_3}, \dots$ ($m_j$ là nhóm có chỉ số $i \equiv j \mod k$) (vì $p_{m_1}$ càng bé thì $p_1$ càng bé, v.v..)

Độ phức tạp $O(k!n)$