# Bài 4
C1 : Xét hết các trường hợp
a + b > 1000 or a + c > 1000 | b + c > 1000 => Yes
else NO
C2 : Xét 2 số lớn nhất
2 số lớn nhất => tổng lớn nhất => đem so sánh với 1000

# Bài 3 : Chênh lệch
Giả sử tồn tại dãy thỏa mãn a1, a2, a3, a4..., am
=> sort lại dãy vẫn thỏa mãn
a[j] - a[i] <= k (a[i] < a[j], i < j)
nếu sort lại => a[i + 1] - a[i] <= k (vì a[i + 1] < a[j])
=> a[j] - a[i] >= a[i + 1] - a[i]
=> Để tối ưu nhất là sort lại
- Nhận xét : Vì ta có thể sắp xếp theo thứ tự tùy ý => sort lại tăng dần
- Gọi dp[i] độ dài lớn nhất kết thúc tại i
- Ban đầu dp[i] = 1 (chính nó)
- Nếu a[i] - a[i - 1] <= k => dp[i] = dp[i - 1] + 1
- lấy max(dp[i]) (1 <= i <= n)

# Bài 1

## Sub1 :
Xét tất cả các cặp, nếu thỏa mãn thì +1 vào đáp án
O($n ^ 2$)

## Dành cho O(n * q * log) :
Nhận xét : Giả sử đang xét tại vị trí i
a[i] + a[j] = B
=> a[j] = B - a[i] (j < i) => Tồn tại 1 giá trị a[j]
a[i] * a[j] = C
=> a[i] * (B - a[i]) = C (1)
Nếu thõa mãn (1) => res += cnt[a[j]] với cnt[x] là số lượng giá trí x trong khoảng từ 1 -> i - 1

Giá trị âm và quá lớn :
=> map<int, int>cnt;
Tóm tắt map<fi, se> : gán kiểu giá trị se cho kiểu giá trị cnt
VD : map<string, int>mp; mp["abc"] = 5

Sau khi xét vị trí i thì cnt[a[i]]++

## Sub cuối :
Chỉ tồn tại 2 giá trị sao cho x + y = A và x * y = B => Giải phương trình bậc 2 tìm x, y
x == y : res += cnt[x] * (cnt[x] - 1) / 2
x != y : res += cnt[x] * cnt[y]

# Bài 2 :

## Sub1 :
Push hết tất cả các giá trị vào 1 vector
Ta xét tất cả các hoán vị đến khi tìm được hoán vị thỏa mãn

do {
    if(check(v)) {
        print(v); Giả dụ
        return 0;
    }
} while(next_permutation(v.begin(), v.end()));

* Lưu ý : Muốn xét hết tất cả các hoán vị thì ta sort lại vector

Gọi id[v] là vị trí hiện tại của của mã số v
- Với a[i] != 0, b[i] != 0 : id[a[i]] + 2 = id[b[i]]
- Với a[i] == 0 : => Thằng ghi tờ giấy i phải ở vị trí 1 => id[b[i]] phải bằng 1
- Với b[i] == 0 : => Thằng ghi tờ giấy i phải ở vị trí n => id[a[i]] = n - 1
=> $O(n!)$

## Sub 2 :
Gọi pos[v] : là chỉ số cuối cùng của thằng có mã số v

- le[i] : mã số của thằng có pos = pos[i] - 2
- ri[i] : mã số của thằng có pos = pos[i] + 2
- Ban đầu ta gán le[i] = ri[i] = -1 với mọi i
- Với mọi tờ giấy thì ta gán : ri[a[i]] = b[i], le[b[i]] = a[i]

Nếu le[v] = -1 => v ở vị trí 1 => pos[v] = 1
=> pos[ri[v]] = 3, pos[ri[ri[v]]] = 5, ...
Nếu le[v] = 0 => pos[v] = 2
=> pos[ri[v]] = 4, pos[ri[ri[v]]] = 6, ...

# Bài 5 :

## Sub 1 :
Sau 1 lần chơi thì độ dài xâu s giảm đi 2
Gọi d là số lần chơi
- Nếu d lẻ => Bob thắng
- Nếu d chẵn => Alice thắng
d = n / 2 (lấy phần nguyên)

# Sub 2 :
Không hề có chiến thuật để thắng
=> Thấy cặp thỏa mãn thì người chơi xóa và đến phiên người còn lại
Ta tìm cặp thõa mãn đầu tiên trên sâu s
=> Tìm i nhỏ nhất thỏa mãn s[i] == s[i + 1]

- le[i] : vị trí ký tự bên trái của xâu mà chưa bị xóa
- ri[i] : vị trí ký tự bên phải của xâu mà chưa bị xóa

Giả sử ta xóa kí tự i :
Đặt current_left = le[i], current_right = ri[i]
=> le[current_right] = current_left
=> ri[current_left] = current_right

Vì ta đang xét vị trí nhỏ nhất thõa mãn
=> Ban đầu khi chưa ký tự nào bị xóa ta push hết các vị trí i sao cho $s[i] = s[i + 1]$ vào một priority_queue

priority_queue<int>pq (sort giá trị)
pq.push(1)
pq.push(3)
pq.push(2)
=> pq.top() = 3
Muốn xóa giá trị trên cùng : pq.pop()
Muốn giá trị trên cùng là nhỏ nhất
=> Khai báo priority_queue<int, vector<int>, greater<int>>pq

Gọi del[i] là trạng thái của vị trí i đã bị xóa chưa

while(!pq.empty()) {
    int id = pq.top(); pq.pop();
    if(del[id]) continue;
    d++;
    del[id] = true; 
    del[ri[id]] = true;
    // Hiện tại muốn xóa thằng id và ri[id]
    int c_le = le[id], c_ri = ri[ri[id]];
    ri[c_le] = c_ri; le[c_ri] = c_le;
    if(c_le > 0 && c_ri < s.size() && s[c_le] == s[c_ri]) pq.emplace(c_le);
}

Nếu d lẻ : Bob thắng, còn không thì Alice thắng

# Bài 6 :

## Sub 1 :
Xét hết tất cả các hoán vị thứ tự của ăn của người khách
Nếu tại vị trí i người khách đó không thể nào ăn được vị đã hết hạn thì res = max(res, i)
vector ban đầu chứa các số từ 1 đên n

int val(vector<int>& v) {
    int day = 0;
    for(int i = 0; i < n; i++) {
        int id = v[i];
        if(day > b[i]) return i;
        day = max(day + 1, a[i] + 1);
    }
    return n;
}

## Sub 3 :
Tại ngày day tồn tại những nem đã lên men mà chưa bị thối rữa
=> Ta chọn thằng sẽ thối rữa sớm nhất => chọn b bé nhất hiện tại

priority_queue<int, vector<int>, greater<int>>pq;
for(int day = 1; day <= 1e6; day++) {
    while(!pq.empty() && pq.top() < day) pq.pop();
    for(int& x : event[day]) pq.emplace(x); // x = b[i]
    if(!pq.empty()) res++, pq.pop();
}
cout << res;