# Giao lưu THT bảng A & B
# Lần 2: 26/3

## Bảng A
---
## Vẽ hình
Đặt tâm tại $(0,0)$. Bán kính lấy $r = 1$, khoảng cách giữa tâm 2 hình tròn kề nhau là $2r$

Vẽ từng lớp
Giả sử ô đầu tiên tại lớp thứ $i$ là ô ở trái cùng .

## Xóa xâu
Xâu chứa khác $A,B,C \Rightarrow$ `No`
Điều kiện: `cnt_A + cnt_C = cnt_B`

## Kho báu
Đếm số hình tại từng lớp:
- Trong cùng: $1$
- Lớp $n = 1: 4$
- Lớp $n = 2: 4 \times 2$
- ...

## Chậm mà chắc
*Liên tưởng tới bài toán con ốc sên: Ban ngày trèo lên $a$ mét, ban đêm tụt xuống $b$ mét.*
### Trâu AC? :open_mouth:
Nhi orz
Các bạn thử suy nghĩ vì sao code này đúng?

#### Đoạn code trên làm gì?
Tìm số $i$ nhỏ nhất mà $1+2+\dots+i\,\,\,+1 \ge n$ (để ý lúc đầu $a=1$)
Nói cách khác: Tổng $1..i \ge n-1$. Đáp án là $2i+1$, tức dùng $i+1$ lần bước tới và $i$ lần bước lùi.
#### Phân tích & chứng minh
Ở đây chỉ xét $i\ge2$
Nhận thấy nếu tổng $1..i \ge n-1$ thì chênh lệch tổng so với $n-1$ phải $< i$, vì trước đó ta có tổng $1..i-1$ vẫn còn $< n-1$ (do $i$ là số nhỏ nhất thỏa mãn). Tức là, chênh lệch của tổng **so với $n$** phải $< i-1$.
Ta viết:
$-1\le$ chênh lệch $< i-1$
Sau khi thêm một lần bước tới vào "ngày" hôm sau, ta có:
$i \le$ chênh lệch $< i+i$.
Như vậy trong $i$ lần lùi về phải bù được lượng chênh lệch này.
Nhận thấy nửa đầu ($i \le$ chênh lệch) luôn thỏa mãn vì mỗi "đêm" phải lùi về tối thiểu $1$ đơn vị.
Xét nửa sau, từ điều kiện này, cần có: khoảng cách tối đa lùi được $\ge$ chênh lệch, tức $1+2+\dots+i \ge 2i-1$, hay $1+2+\dots + i-1 \ge i-1$, luôn đúng.

#### Nghĩ theo kiểu dãy số & tìm quy luật
Xin mời Minh 9B.

### Tìm kiếm nhị phân
$x$ lần di chuyển tới, sẽ được quãng đường
$1+2+...+x$
Trừ đi tổng khoảng cách lùi?
từ
$x-1$ (mỗi ngày lùi $1$)
cho tới
$1 + 2 + 3 + ... + (x-1)$
Vậy khoảng cách đạt được cuối cùng nằm trong đoạn
$[x, 1+2+...+x - (x-1)] = [x, x(x-1)/2 + 1]$
TKNP với $x$ từ $1$ tới $n$

## Bảng B
---
## Bảo vệ trái đất
Max dãy

## Tổng cặp tích
Đoạn code cày trâu ngây thơ nhất

int res = 0;
for (int i = 1; i <= n; i++) {
    for (int j = i+1; j <= n; j++) {
        res += a[i] * a[j];
        res %= MOD;
    }
}	

Thử viết lại code.

int res = 0;
for (int i = 1; i <= n; i++) {
    int sum_i = 0;
    for (int j = i+1; j <= n; j++) {
        sum_i += a[i] * a[j];
        sum_i %= MOD;
    }
    res += sum_i;
}	

Tách bạch tổng cần tính ra theo từng $i$, thấy được cần tính $a_i \cdot a_{i+1} + a_i \cdot a_{i+2} + a_i \cdot a_{i+3} + \dots + a_i \cdot a_n$.
Đặt nhân tử chung, cần tính $a_i \cdot(a_{i+1} + a_{i+2} + \dots + a_n)$
Vậy với mỗi số thứ $i$, cần tính tổng tất cả $a_j$ đằng sau nó.
Để tính nhanh, dùng prefix-sum, nhưng thật ra không cần thiết.
Chỉ cần chạy `for` ngược về, duy trì một biến tổng.

int sum_after = 0, res = 0;
for (int i = n; i > 0; i--) {
    res += a[i] * sum_after;
    sum_after += a[i];
}

## Tổng mũ
Cần tính nhanh $a^b \mod c$ bằng chia để trị

### Ý tưởng
https://viblo.asia/p/phep-nhan-an-do-thuat-toan-binh-phuong-va-nhan-gDVK2dmrlLj
Để tính $a^b$, ta tính từ $a^{b/2}$.
Sau $O(1)$ phép tính, số mũ giảm đi một nửa. Do đó ĐPT là $O(\log)$

M = 10**9
def luythua(a,b):
    if b == 0: return 1
    if b % 2 != 0: return a * luythua(a,b-1) % M
    T = luythua(a, b//2)
    return T*T % M

Ý tưởng được thể hiện trong đoạn code trên:
- $a^0 = 1$
- Nếu $b$ chẵn thì chỉ cần **một** lần tính $a^{b/2}$, rồi bình phương kết quả này để có $a^b$)
- Nếu $b$ lẻ thì đưa về trường hợp $b$ chẵn
- Lưu ý: Nếu không đặt biến `tạm = lũy_thừa(a, b/2)` mà code thẳng luôn `return luythua(a,b/2) * luythua(a,b/2)` sẽ bị TLE (ĐPT $O(b)$ thay vì $O(\log)$).
### Đặc quyền Python user
Chỉ cần gọi `pow(a,b,c)` thì sẽ tự động có được thuật toán xịn (chia để trị) với ĐPT $O(\log c)$

## Leo thang
Bài toán: Tìm vị trí đầu tiên trong $a$ mà $>t$.

Đặt $M_i$ là $\max$ của $i$ phần tử đầu tiên.
Cần TKNP trên mảng $M$ ra vị trí $j$ lớn nhất mà $M_j \le t$. Thấy rằng $M$ tăng dần và $j+1$ là vị trí đầu tiên $>t$, tức $M_{j+1}$ (hay $A_{j+1}$) đều $>t$.

### Giải thích kỹ hơn
Thử "chày cối" TKNP giống subtask 2. Điều kiện cần đặt ra bây giờ không phải là `if a[mid] < t` nữa, mà phải là `mọi số từ 1 tới mid có < t hay không?`.
Để tính nhanh được $\max$ của các số từ đầu tới một vị trí $i$ nào đó, ta áp dụng ý tưởng của prefix-sum:
$M_i = \max(M_{i-1}, a_i)$

## Chia kẹo
### Sub 1:
Mỗi gói kẹo có hai lựa chọn: cho shiba hoặc minhduc. Coi như xâu nhị phân 0/1.
Đệ quy quay lui $O(2^n)$

#### Cụ thể
`void backtrack(int i, long long shiba)`
Đã xét được $i$ gói kẹo đầu tiên, tổng mà Shiba nhận được là `shiba`.
Tới cuối cùng, ta lấy tổng $n$ số trừ cho `shiba`

### Sub 2:
Đặt $\texttt{dp[i][j] = true/false}$ là xem thử trong $i$ gói kẹo đầu tiên ta có lấy ra được một vài gói có tổng $j$ hay không?

#### Chuyển trạng thái:
Đang ở trạng thái `dp[i][j]`, mà `dp[i][j] = true`. Xét hai trường hợp:
- TH 1: Thêm gói kẹo thứ $i$ cho người hiện tại. Gán `dp[i+1][j + a[i]] = true`
- TH 2: Gán `dp[i+1][j] = true`

#### Lấy ra đáp án
Nếu `dp[n+1][j] = true` thì ....

### Sub 3:
Duyệt phân tập (meet in the middle).


### Sub 4:
Tối ưu sub2 bằng bitset.
Vì thông tin ta lưu là biến boolean true/false nên thay vào đó có thể dùng số nguyên để biểu diễn. Một số int có 32 bit tương ứng với 32 biến boolean, 32 vị trí trong mảng $dp[i]$.