# Solution Chung kết OLP MT & TN 2023 (Không chuyên & Chuyên tin)

## TAB
Cơ bản: mảng, for, if
Lưu ý: Nếu cộng ba số $10^9$ lại thì có khả năng tràn số (kiểu `int` chỉ chứa từ $-2^{31} .. 2^{31} - 1)$, tức là tầm 2 tỉ 140 triệu blabla

## BONUS
### Trâu
Chọn một item muốn thay ra (`for`),
và một item muốn thêm vào. $O(n^2)$

### Full
Giả sử bỏ đi món $i$. Biết được ngay còn dư bao nhiêu chỗ trống.
Vấn đề đặt ra: Thêm vào item có weight $\le S'$ có value lớn nhất có thể.
$\rightarrow$ Sort tăng theo $w$. Lúc này những món có $w \le S'$ nằm ở đầu tiên. Ta cần:
- Tính trước $f_i$ là $\max s$ của $i$ món đầu tiên sau sort
- TKNP để biết là lấy ra bao nhiêu món? (tìm vị trí cuối cùng, mà $\le$ giá trị cho trước, bài `maxge`)

## DIGITSUM
### Trâu
Duyệt mọi số từ $1$ tới $n$. ĐPT $O(n \log n)$
### $n = 10^x$
How to?
### $n \le 10^{12}$
#### $k$ lớn - chạy bộ(i)
$O(n \div k \cdot \log)$
#### QHĐ chữ số
Ví dụ: Đếm số lượng số bé hơn $\le n$ thỏa mãn tính chất abcxyz.
Giả sử $n$ có $t$ chữ số. Giả sử số ta đang quan tâm có dạng `????? (t)`
Đặt $f(i,0/1, ...)$: đã điền vào $i$ chữ số đầu tiên, số đã tạo bé hơn hẳn $n$ hay vẫn còn bằng $n$?.
Trong bài này $(...)$ sẽ lưu số dư cho $k$.
Nếu đặt $f$ là tổng, cần thêm mảng $g$ đếm số lượng số thỏa mãn.

$O(\log \cdot k)$

## NUMRING
Bài toán trên vòng tròn $\rightarrow$ gấp đôi mảng $a$.
Ta có $a_1, a_2, a_3, ..., a_{n-1}, a_n; \,\,\, a_1, a_2, a_3, ..., a_{n-1}, a_n$

### Backtrack
Chọn ra $3k$ vị trí bất kì trong $n$. Đệ quy $2^n$

### $k = 1$
Chọn hai vị trí đầu tiên, ở giữa bất kì ($i < j$).
Cần tìm vị trí $k \,\,(k < i+n)$ mà $a_i - a_j + a_k$ đạt max.
Tìm max đoạn liên tiếp --> Tiền xử lý $f(l,r)$ là max của $a$ từ $l$ tới $r$.
$f(l,r) = \max \{f(l,r-1), a_r\}$

### $n \le 200$
Chọn ra $s$ làm vị trí đầu tiên. (`for` $O(n)$)

Đặt $f(i,c,t)$: Giả sử chọn các phần tử trước vị trí $i$, đã chọn được $c$ bộ ($3\times c$ số), đang chọn cho số thứ $t$ của bộ số thứ $c+1$.

Công thức: Từ vị trí $i$, xét vị trí $i+1$, có hai t/hợp:
- Bỏ qua
- Thêm $a_{i+1}$ vào bộ số hiện tại (hoặc tạo bộ mới).

ĐPT: $O(n^3)$

### $n \le 2000$
#### Sol
Thay vì xét mảng trên vòng tròn, ta chỉ cần giải quyết bài toán với $a$ từ $1$ tới $n$ **nhưng** quy luật cộng được xoay vòng tròn:
- Cộng 1, trừ 2, cộng 3 (theo đề)
- Trừ 1, cộng 2, cộng 3
- Cộng 1, cộng 2, trừ 3

Giải bằng QHĐ $O(n^2)$ như trên

#### Deleted
Chưa test
Nếu biết được $a_i$ và $a_k$ là số đầu & số cuối của bộ ($i < k$) thì chắc chắn có số ở giữa là $a_j = \min a[i+1..k-1]$
Bài toán quy về: Chọn các đoạn con không giao nhau, có tổng lớn nhất, và "nằm gọn" trong $n$ phần tử.
Vậy sẽ có $O(n^2)$ đoạn cần quan tâm.
Vẫn xét các $s$ khác nhau. Tuy nhiên, không cần tính lại toàn bộ mảng QHĐ $f(i,c)$, mà chỉ cần thay đổi những chỗ cần thay đổi.
Tức là: Giả sử ta từ $s$ sang $s+1$, cần làm 2 việc:
- Xét thêm những đoạn kết thúc tại $s+1+n\,\,\,-1$
- Xóa đi những đoạn bắt đầu tại $s$.

Dùng `multiset`?