# OLP MTTN 2023 - Sơ loại bảng Không chuyên
## Bài 1 - THREE
Ta có: $3 = 1+1+1 = 1+2$, tức có 3 cách tạo thành tổng bằng 3.
- Những phần tử $3$ chỉ tạo thành các tập $\{3\}$
- Những phần tử $2$ chỉ có thể ghép thêm với $1$ để tạo thành $\{1,2\}$
- Những phần tử $1$ có thể ghép với $2$ (như trên), hoặc ghép thêm 2 số $1$ khác thành bộ $\{1, 1, 1\}$.
Tuy nhiên, cách sau tốn nhiều số hơn, mà muốn tạo thành nhiều tập thì phải ưu tiên tập có ít số hơn

$\Rightarrow$ thứ tự ưu tiên tạo tập số: $\{3\}, \{1, 2\}, \{1,1,1\}$.

// nhập a, b, c
int tap3 = c;
int tap12 = min(a, b); a -= tap12, b -= tap12;
int tap111 = a / 3;
int answer = tap3+tap12+tap111;

## Bài 2 - TRANSFORM
Với một số $X$ bất kỳ:
- nếu chọn phép nhân đôi: $2X$ là một số chẵn
- nếu chọn phép viết số 1 đằng sau: $\overline{X1}=10X+1$ là một số lẻ.

$\Rightarrow$ để tìm trạng thái liền trước của $X$:
- Nếu $X$ chẵn thì chỉ có thể kết luận trạng thái trước dùng phép nhân đôi để tạo ra $X$
- Nếu $X$ lẻ thì chỉ có thể kết luận trạng thái trước dùng phép **viết số 1 đằng sau** để tạo ra $X$ $\Rightarrow$ $X$ chia $10$ **phải dư** $1$.

Vì thế, thay vì tìm cách tạo $B$ từ $A$, ta sẽ truy ngược từ $B$ về $A$.
- Nếu trong quá trình truy ngược mà tìm ra $A$ $\Rightarrow$ dừng luôn và kết luận tạo được
- Nếu trạng thái hiện tại lẻ và không có chữ số cuối dùng là $1$ (tức chia 10 dư 1), và trong cả quá trình không có $A$ $\Rightarrow$ không tạo được.

bool check(int a, int b) {
    while (b > 0) {
        if (a == b) return true;
        
        if (b % 2 == 0) b /= 2;
        else {
            if (b % 10 == 1) b /= 10;
            else break; // dừng vòng lặp
        }
    }
    
    // xuống đây tức là không có a
    return false;
}

## Bài 3 - SWORD
Hướng nghĩ:
- Đầu tiên, có những con boss nào có $p_i \leq S$, thì ta tiêu diệt hết, và $S \leftarrow S + g_i$ tương ứng.
- Sau khi diệt hết đợt 1, $S$ tăng lên, từ đó ta diệt thêm các con boss có độ khó $p_i$ cao hơn $\rightarrow$ cho hết các con này vào đợt 2
- Tương tự, sau đợt 2 sẽ tới đợt 3 với các con boss khó hơn, $\dots$ cho tới khi không còn boss hợp lý.

$\Rightarrow$ các con boss sẽ được tiêu diệt theo thứ tự $p_i$ tăng dần.
$\Rightarrow$ sắp xếp các boss theo thứ tự $p$ (nếu cùng $p$ thì $g$ như nào không quan trọng, vì cùng $p$ sẽ cùng bị tiêu diệt một lần, chứ không có chuyện hai boss cùng $p$ mà một con bị diệt một con thì không)

struct Boss{int p, g;};
bool operator < (Boss a, Boss b); // sắp xếp theo Boss::p

int n; long long S;
Boss bosses[MAX];

main() {
    // nhập Boss
    sort(bosses + 1, bosses + 1 + n);
    int count = 0;
    for (i = 1 -> n) {
        if (bosses[i].p > S) break; 
        S += bosses[i].g; count++;
    }
    
    cout << count;
}

## Bài 4 - COLORBOX
**Lưu ý:** Không nhất thiết phải giữ lại toàn bộ các màu (các giá trị khác nhau) có trong mảng, tức được phép mất đi một(vài) màu.

Ở đây giả sử ta **bắt buộc phải xóa ít nhất một đoạn**. Nếu các phần tử khác nhau đôi một, lập tức in ra $0$ rồi kết thúc chuogw trình.

### Subtask 1 - $n \leq 10^2$
1. Chọn ra một đoạn $l, r$
2. Đếm xem phần còn lại (gồm $[1; l-1]$ và $[r+1; n]$) có hai cây màu nào trùng màu không.
3. Tìm đoạn $[l;r]$ ngắn nhất trong số các đoạn thỏa mãn điều kiện 2

Để kiểm tra điều kiện 2, ta sẽ tạo một mảng đếm phân phối `dpp[]` số lần xuất hiện của các màu, và một biến `cnt` đếm số màu xuất hiện **nhiều hơn** một lần.
- Khi `dpp[màu]++`, nếu `dpp[màu] == 2` thì `cnt++`.

int dpp[MAX_N], cnt = 0;

int answer = 0;
for (l = 1 -> n) for (r = l -> n) {
    for (i = 1 -> l-1) {
        ++dpp[a[i]]; if (dpp[a[i]] == 2) cnt++;
        // if (++dpp[a[i]] == 2) cnt++;
        // cnt += (++dpp[a[i]] == 2);
    }
    for (i = r+1 -> n) cnt += (++dpp[a[i]] == 2); // lưu ý: ++a != a++
    
    if (cnt == 0) // không có vi phạm
        answer = max(answer, r-l+1);
    // sau đó nhớ xóa hết dữ liệu trong mảng dpp và biến cnt.
}

cout << answer;

Độ phức tạp: $\mathcal{O(n^3)}$; gồm cho $\mathcal{O(n^2)}$ cho việc chọn cặp $(l,r)$ và $\mathcal{O}(n)$ cho việc đánh dấu màu.

### Subtask 2 - $n \leq 10^3$
Khi duyệt các cặp $(l, r)$, với $l$ cố định thì mỗi lần chỉ thay đổi $r$ đi $1$ đơn vị $\Rightarrow$ bỏ bớt một số ra khỏi tập các số còn lại đang xét.

$\Rightarrow$ thay vì với mỗi cặp $(l, r)$ ta duyệt các số nằm ngoài đoạn, để **lợi dụng** sự thay đổi nhỏ này:
- với mỗi $l$, ban đầu ta xét tất cả các số trong mảng $A$.
- khi duyệt $r$, ta lần lượt bỏ đi $A[r]$ ra khỏi tập các số còn lại.

**Ví dụ:**
Giả sử $n=4$
|l|r|các số được xét|
|-|-|-|
|1|chưa duyệt|$A_1,A_2,A_3,A_4$|
|1|1|$A_2,A_3,A_4$|
|1|2|$A_3,A_4$|
|1|3|$A_4$|
|1|4||
|2|chưa duyệt|$A_1,A_2,A_3,A_4$|
|2|2|$A_1,A_3,A_4$|
|2|3|$A_1,A_4$|
|2|4|$A_1$|
|3|chưa duyệt|$A_1,A_2,A_3,A_4$|
|3|3|$A_1,A_2,A_4$|
|3|4|$A_1,A_2$|
|4|chưa duyệt|$A_1,A_2,A_3,A_4$|
|4|4|$A_1,A_2,A_3$|

Vì thế, ta cần hỗ trợ thêm phép **xóa** phần tử:
- Sau khi `--dpp[màu]`, nếu `dpp[mau] == 1` thì `cnt--`

for (l = 1 -> n) {
    for (i = 1 -> n) cnt += (++dpp[a[i]] == 2)
    
    for (r = l -> n) {
        cnt -= (--dpp[a[i]] == 1);
        
        if (cnt == 0) answer = max(answer, r-l+1);
    }
}

Độ phức tạp: $\mathcal{O}(n^2)$
Ta có thể cải tiến thuật toán bằng cách dừng $r$ ngay khi `cnt == 0`, khi đó $r$ là vị trí cuối đoạn tối thiểu để phần ngoài có các phần tử độc nhất, từ đó dựng lên các đoạn ngắn nhất. (*)

### Subtask 3+4 - $n \leq 10^6$
Nhận thấy: Với một đoạn $(l, r)$ bất kỳ:
- Nếu $l$ tăng thì phần ngoài thêm được một phần tử
- Nếu $l$ giảm thì phần ngoài giảm đi một phần tử
- Nếu $r$ tăng thì phần ngoài giảm đi một phần tử
- Nếu $r$ giảm thì phần ngoài thêm được một phần tử.

Từ (*), khi ta thử tìm $r$ nhỏ nhất thỏa mãn điều kiện của từng giá trị $l$, ta thấy **khi $l$ tăng thì $r$ cũng tăng**
Vì khi $l$ tăng thì bên ngoài thêm một phần tử:
- nếu không trùng thì giữ $r$
- nếu có trùng thì $r$ phải tăng để xóa bớt phần tử cho tới khi không còn trùng nữa.

Vì thế, cũng như lúc nãy, ta dựng `dpp[]` và `cnt` cho toàn mảng $A$
- Đầu tiên, với $l=1$, ta tìm $r$ tối thiểu thỏa mãn, tức loại bỏ khỏi mảng đpp như thuật toán ở hai subtask trên cho tới khi `cnt==0`
- Tiếp theo, $l$ tăng thành 2 $\Rightarrow$ thêm `A_1` vào `dpp` và cập nhật `cnt`. Nếu `cnt!=0` thì ta tăng $r$ (loại bỏ $A_r$ rồi tăng $r$ lên 1đv) cho tới khi `cnt==0`
- Tương tự, tăng $l$ thành 3, 4, 5, ... tương ứng với cho $A_2, A_3, A_4 \dots$ vào mảng rồi cập nhật $r$, cho tới khi $r > n$ (tức không có $r$ thỏa mãn) thì dừng.

for (i = 1 -> n) cnt += (++dpp[a[i]] == 2)

  
r = 0;
for (l = 1 -> n) {
    while (cnt > 0) {
        r++; if (r > n) break;
        cnt -= (--dpp[a[r]] == 1);
    }
    if (r > n) break;
    answer = max(answer, r-l+1);
    
    cnt += (++dpp[a[l]] == 2);
}