# Pusheen Contest 2023 #4

###### tags: `CLA K22`

## Sushi
**Giá trị kỳ vọng = Tổng (trọng số * xác suất)**

VD1: GTKV khi tung 1 đồng xu 1 lần, mặt ngửa 1, mặt sấp là 0 => $\frac{1}{2} \times 0 + \frac{1}{2} \times 1 = \frac{1}{2}$

VD2: GTKV số lượng lần tung đồng xu để được mặt ngửa
$$
1/2 + (1/4) \times 2 + (1/8) \times 3 + ... = \sum_{x=1}^\infty \frac{1}{2^x}x = 2
$$

Giá trị kỳ vọng(A+B) = GTKV(A) + GTKV(B)

Tìm cách biễu diễn trạng thái:
Phân loại các đĩa sushi theo số lượng sushi có trên đĩa.

Gọi $dp[cnt0][cnt1][cnt2][cnt3]$ là giá trị kỳ vọng của số lần thực hiện thao tác để ăn hết các miếng sushi với $cnt0$ dĩa có 0 sushi, $cnt1$ dĩa có 1 sushi, $cnt2$ dĩa có 2 sushi và $cnt$ dĩa có 3 sushi.

Khi đó:
$dp[cnt0][cnt1][cnt2][cnt3]$ = GTKV số thao tác để ăn miếng sushi đầu tiên + GTKV số thao tác để ăn các miếng sushi còn lại.

Xét GTKV của số thao tác để ăn miếng sushi đầu tiên, ta có:
- Xác suất để chọn 1 dĩa: $1/n$.
- Trường hợp 1: random ra dĩa có 0 sushi
- Xác suất: $\frac{cnt0}{n}$
- Trọng số: $1 + dp[cnt0][cnt1][cnt2][cnt3]$
- Trường hợp 2: random ra đĩa có 1 sushi
- Xác suất: $\frac{cnt1}{n}$
- Trọng số $1 + dp[cnt0+1][cnt1-1][cnt2][cnt3]$
...
- $dp[n][0][0][0]$ giá trị kỳ vọng là 0
- **Độ phức tạp:** $\mathcal{O}(n^4)$ không gian, tùy cách cài đặt $O(n^4)$ hoặc $O(n^3)$ đpt thời gian.

### Cải tiến
Nhận xét: với $cnt1, cnt2, cnt3$ xác đinh, ta luôn tìm được $cnt0 = n-cnt1-cnt2-cnt3$ cho nên ta không cần $cnt0$ trong trạng thái => Giảm độ phưc tạp không gian

$c1 = cnt1, c2 = cnt2, c3 = cnt3, c0 = n-c1-c2-c3$.
$$
\begin{align*}
dp[c1][c2][c3] &= \frac{c0}{n}\times (1 + dp[c1][c2][c3]) + \frac{c1}{n}\times (1 + dp[c1-1][c2][c3]) + \frac{c2}{n}\times (1 + dp[c1+1][c2-1][c3]) + \frac{c3}{n}\times (1 + dp[c1][c2+1][c3-1]) \\
&= \frac{c0+c1+c2+c3}{n} + \frac{c0}{n}\times dp[c1][c2][c3] + \frac{c1}{n}\times dp[c1-1][c2][c3] + \frac{c2}{n} dp[c1+1][c2-1][c3] + \frac{c3}{n}\times dp[c1][c2+1][c3-1] \\
&= 1 + \frac{c0}{n}\times dp[c1][c2][c3] + \frac{c1}{n}\times dp[c1-1][c2][c3] + \frac{c2}{n} \times dp[c1+1][c2-1][c3] + \frac{c3}{n}\times dp[c1][c2+1][c3-1]
\end{align*}
$$

Chuyển vế $\frac{c0}{n} dp[c1][c2][c3]$ qua vế trái.

$$
\frac{c1+c2+c3}{n} dp[c1][c2][c3] = 1 + \frac{c1}{n}\times dp[c1-1][c2][c3] + \frac{c2}{n} \times dp[c1+1][c2-1][c3] + \frac{c3}{n}\times dp[c1][c2+1][c3-1]
$$

Nhân 2 vế cho $\frac{n}{c1+c2+c3}$, gọi $total = c1+c2+c3$.
$$
dp[c1][c2][c3] = \frac{n}{total} + \frac{c1}{total} dp[c1-1][c2][c3] + \frac{c2}{total} dp[c1+1][c2-1][c3] + \frac{c3}{total} dp[c1][c2+1][c3-1]
$$

Độ phức tạp thời gian lẫn không gian là $O(n^3)$

## Deque
Nhận xét: Tại bất kì thời điểm nào trong lúc chơi, dãy số vẫn giữ nguyên tính chất là đoạn con của dãy ban đầu.

Gọi $dp[L][R][0/1]$ là giá trị $X-Y$ tối ưu khi đến lượt của Taro (0), Jiro (1).

Nếu $L > R$ thì $dp[L][R][0/1] = 0$

Xét lượt của Taro:
$$
dp[L][R][0] = \max(dp[L+1][R][1] + a[L], dp[L][R-1][1] + a[R])
$$

Xét lượt của Jiro
$$
dp[L][R][1] = \min(dp[L+1][R][0] - a[L], dp[L][R-1][0] + a[R])
$$

**Độ phức tạp**: $O(n^2)$

## Candies
Cách giải ngây thơ: Gọi $dp[i][c]$ là số cách chia kẹo cho $i$ bạn nhỏ sao cho còn lại $c$ cái kẹo. Đáp án của bài toán sẽ là $dp[n][0]$.

Công thức
- $dp[0][K] = 1$.
- $dp[i+1][c-x] += dp[i][c]$.

với $0 \le x \le \min\{a_{i+1}, c\}$

Độ phức tạp: $O(NK^2)$.

### Cải tiến
Công thức truy hồi
- $dp[0][K] = 1$.
- $dp[i][c] = \sum_{x=0}^{a_i} dp[i-1][c+x]$

Tối ưu đpt bằng cách tối ưu chi phí chuyển.
$dp[i][c] = dp[i-1][c] + dp[i-1][c+1] + \dots + dp[i-1][\min\{K, c+a[i]\}]$

Gọi $prefix[i-1][j] = dp[i-1][0] + dp[i-1][1] + \dots + dp[i-1][j]$. Khi đó:
$$
dp[i][c] = prefix[i-1][\min\{K, c+a[i]\}] - prefix[i-1][c-1]
$$.

Sau khi tính $dp[i][c]$. Ta đồng thời cập nhật $prefix[i][c] = prefix[i][c-1] + dp[i][c]$

Độ phức tạp: $O(NK)$. Do chi phí chuyển được tối ưu còn $O(1)$.

## Slimes
Tại bât kì thời điểm nào, mỗi con slime đều được tạo bởi một đoạn các con slime liên tiếp trong thời điểm ban đầu. Ta có thể biễu diễn mỗi con slime dưới dạng một đoạn con của dãy.

Gọi $dp[L][R]$ là chi phí nhỏ nhất để ghép các con slime trong đoạn $[L..R]$ thành một.

Công thức truy hồi:
$$
dp[L][R] = \min\limits_{L \le k < R}\{dp[L][k] + dp[k+1][R] + sum[L..R]\}
$$

Độ phức tạp: $O(n^3)$.