# 4. Unscrambling a messy bug (IOI 2016)

###### tags: `interactive` `TST`

## Đề bài
- Một cấu trúc dữ liệu (CTDL) $S$ có thể chứa tập hợp các số $n$-bit, với $n=2^b$.
- Thao tác trên CTDL:
* `add_element(x)`: thêm phần tử $x$ vào tập hợp
* `compile_set()`: hàm chuẩn bị tập hợp, gọi đúng $1$ lần sau khi thêm phần tử cuối cùng của tập
* `check_element(x)`: kiểm tra sự tồn tại của phần tử $x$
- Một người cài đặt CTDL trên bị lỗi ở hàm `compile_set()`, khiến các dãy bit trong tập hợp $S$ bị hoán vị vòng quanh. Cụ thể, tồn tại một hoán vị $p=p_0,p_1,\cdots,p_{n-1}$, khiến cho một phần tử $x=a_0a_1\cdots a_{n-1}$ trở thành phần tử $a_{p_0}a_{p_1}\cdots a_{p_{n-1}}$ trong $S$ sau khi `compile`.
- Hãy tận dụng bug của CTDL để xác định hoán vị $p$. Chương trình của bạn cần thực hiện đủ các thao tác sau:
* Chọn ra tập hợp dãy $n$-bit.
* Thêm từng phần tử vào CTDL bằng tối đa $w$ lần gọi hàm `add_element(x)`.
* Gọi hàm `compile_set()` chính xác 1 lần để kích hoạt bug.
* Kiểm tra sự tồn tại của một số phần tử bằng tối đa $r$ lần gọi hàm `check_element(x)`.
* Kết luận hoán vị $p$.

### I/O
#### Nhập xuất
- `int[] restore_permutation(int N, int W, int R);`
* `N`: độ dài dãy bit.
* `W`: giới hạn số lần gọi hàm `add_element(x)` (viết)
* `R`: giới hạn số lần gọi hàm `check_element(x)` (đọc)
* Hàm trả về hoán vị $p$ cần phục hồi.

#### Giao thức
- `void add_element(int x);`
* `x`: phần tử thêm vào CTDL.

- `void compile_set();`
* Hàm kích hoạt bug của CTDL, làm thay đổi các phần tử trong tập hợp như mô tả.

- `bool check_element(int x);`
* `x`: phần tử cần kiểm tra
* Hàm trả về `true` nếu phần tử $x$ nằm trong CTDL, ngược lại hàm trả về `false`.

### Subtask
- **Subtask 1 (20%)**: $n=8, w=256, r=256$, tồn tại tối đa $2$ vị trí $i$ thoả $p_i\ne i$.
- **Subtask 2 (18%)**: $n=32, w=320, r=1024$.
- **Subtask 3 (11%)**: $n=32, w=1024, r=320$.
- **Subtask 4 (21%)**: $n=32, w=1792, r=1792$.
- **Subtask 5 (30%)**: $n=128, w=896, r=896$.

## Lời giải
Ký hiệu $S$ là tập hợp ban đầu, $f$ là phép `compile_set` trên tập $S$, $S'$ là ảnh của tập $S$ qua phép toán $f$. Nói cách khác:

$$
f: S \mapsto S'
$$

### Subtask 1. $n=8,w=256,r=256$, tồn tại tối đa $2$ vị trí $i$ thoả $p_i\ne i$.
- Ở Subtask này, ta cần tìm hai vị trí $i,j$ thoả mãn $p_i\ne i,p_j\ne j$.
- Xét cây nhị phân sau:

* Xét xâu $x=(1\cdots1)(0\cdots0)$, trong đó dãy bit $1$ nằm trong đoạn $[0,n/2-1]$.
* Nếu $f(x)\not\in S$, chứng tỏ $x_i\ne x_j$. Suy ra $i\in [0,n/2-1]$ và $j\in [n/2, n-1]$. Ta có thể thử tất cả giá trị $(i,j)$ có thể, `swap(x[i], x[j])` và kiểm tra $f(x')\in S$.
* Nếu $f(x)\in S$, chứng tỏ $x_i=x_j$. Như vậy, $i,j\in [0,n/2-1]$ hoặc $i,j\in [n/2, n-1]$. Ta truy hồi về $2$ bài toán con trên đoạn $[0,n/2-1]$ và $[n/2, n-1]$. Những bit nằm ngoài đoạn con đang xét có thể đặt tuỳ ý, vì chắc chắn những vị trí ngoài đoạn đang xét không phải là vị trí bị thay đổi.

- Với tư tưởng chia để trị, ta có đoạn mã giả sau:

string get_str(int l, int r) {
    int m = (l + r) / 2;
    string res(N, '0');
    for (int i = l; i <= m; i++)
        res[i] = '1';
    return res;
}

void solve(int l, int r) {
    if (l == r)
        return;
    
    int m = (l + r) / 2;
    string str = get_str(l, r);
    
    if (check_element(str)) {
        solve(l, m);
        solve(m + 1, r);
        return;
    }
    
    for (int i = l; i <= m; i++)
    for (int j = m + 1; j <= r; j++) {
        swap(str[i], str[j]);
        if (check_element(str)) {
            // (i, j) là hai phần tử bị thay đổi.
            throw 1;
        }
        swap(str[i], str[j]);
    }
}

### Subtask 2. $n=32, w=320, r=1024$.
> **Nhận xét 1**. $f(x\cup y)=f(x)\cup f(y), f(x-y)=f(x)-f(y)$.
> *Chứng minh.* $p$ là song ánh $\implies$ $f$ là song ánh $\implies$ đpcm $\square$

> **Nhận xét 2**. Giả sử $\forall(x,y\in S), x\ne y\iff |x|\ne|y|$. Khi đó:
> 1. Với mỗi $x\in S$ có tương ứng duy nhất $x'\in S'$ sao cho $|x|=|x'|$.
> 2. Vì số lượng bit $1$ của các phần tử trong $S$ khác nhau, ta có thể tìm được chính xác ảnh $x'\in S'$ của $x\in S$.
>
> **Hệ quả**. Ta có thể chia các phần tử theo số lượng bit $1$ và xử lý riêng cho từng nhóm.

- Từ 2 nhận xét trên ta có thuật toán sau:
* $S:=\{[0,0],[0,1],\cdots,[0,n-1]\}$
* $p_0=f([0,0])$
* $p_i := f([0,i])-f([0,i-1]), \forall 1\le i<n$
- Dễ thấy $\exists x: f([0,i])=f([0,i-1])\cup\{x\}$, nên ta tính được $p_i=x$ trong $n-i$ phép hỏi `check_element`.
- Tổng số lần viết và đọc:
* $w=n=320$
* $r=\sum_{i=0}^{n-1}(n-i)=n^2-\frac12n(n-1)=\frac12(n^2-n)=496$

### Subtask 3. $n=32, w=1024, r=320$.
- Vì vị trí các chỉ số bình đẳng với nhau, ta có thể thay đổi thứ tự xét chỉ số. Khi đó, với mỗi chỉ số $i$ ta sẽ tìm được $p_i$ trong giá trị **kỳ vọng** $\mathbb{E}(i)=\frac12(n-i)$ lần hỏi.
- Tổng số lần viết và đọc:
* $w=n=320$
* $\mathbb{E}(r)=\frac14n(n-1)=248$.

### Subtask 5. $n=128, w=r=896$
> **Nhận xét 3**. Một thuật toán xác định hoán vị chỉ dựa vào các câu hỏi **YES/NO** cần $\theta(n\log n)$ câu hỏi.
> *Chứng minh.* Xét một Decision Tree mà mỗi hoán vị tương ứng với một nút lá. Cây cân bằng nhất là khi cây đó là cây nhị phân. Mặt khác, cây gồm $n!$ nút lá nên độ cao của cây thấp nhất là $\log n!=\log \prod_{i=1}^n i=\sum_{i=1}^n \log i\le n\log n$ $\square$.
>
> **Hệ quả**. Mỗi lần đọc dữ liệu, ta phải chia được tập kết quả làm đôi. Nói cách khác, không được có câu hỏi lãng phí.

- Ta xem việc tìm ra hoán vị $p$ như việc sắp xếp hoán vị $p_0=(0;1;\cdots;n-1)$ với quan hệ thứ tự không biết trước. Ta sẽ dùng tư tưởng của thuật toán quick sort như sau:

void quick_sort(int l, int r, vector<int> vals) {
    if (l == r) {
        ans[r] = vals[0];
        return;
    }

    int m = (l + r) / 2;
    // left_vals := f([l,m])
    // right_vals := f([m+1,r])
    quick_sort(l, m, left_vals);
    quick_sort(m + 1, r, right_vals);
}

- Để tìm hai tập hợp $V_L, V_R$ ứng với `left_vals` và `right_vals` của đoạn $[l,r]$:
* Ta dựng $\frac{r-l+1}2$ câu hỏi $x$, trong đó:
* $x_l=\cdots=x_r=0$, ngoại trừ 1 bit duy nhất $x_i=1$, với $i\in[l,m]$.
* Các bit còn lại giá trị bằng $1$.
* Để xác định câu trả lời $x'$ của $f(x)$, ta nhận thấy rằng các bit nằm ngoài đoạn $[l,r]$ là phần bù của tập $V(l,r)$ trong hàm `quick_sort`. Do đó, ta chỉ cần tìm thêm 1 bit còn lại trong đáp án.