# Solution Sơ loại OLP MTTN 2023 (Chuyên Tin) ## B1: TEAMBUILDING Tóm tắt: Đếm số cách chia mảng $a$ thành các nhóm liên tiếp. Mỗi nhóm thỏa mãn abcxyz. --- ### Sub 1: $n \le 20$ Có $n$ người thì sẽ có $n-1$ "khoảng trống" để ta đặt/ không đặt "vách ngăn" vào. Mỗi cách đặt như vậy là một cách chia nhóm. Ví dụ: [Hình vẽ] (soon^TM) Quay lui $O(2^n)$ --- ### Sub 2: $n \le 500$ Cài chưa chuẩn ? ### Sub 3: $n \le 5000$ Đặt $f(i)$ là số cách để chia $i$ người đầu. Từ $f(i)$ ta cập nhật $f(j)$ với $j > i$. Thêm một nhóm $i+1, i+2, i+3, ..., j$. Nếu được thì $\texttt{f(j) += f(i)}$  (Nguyễn Minh Huy, A5 K37 LQĐ) --- ## B2: FRUITMARKET Tóm tắt: Hoa sẽ đi mua quả theo vòng tròn: mỗi tiệm mua $\le 1$ quả xong rồi qua tiệm tiếp theo. Dừng lại khi không đủ tiền mua quả rẻ nhất. **Bước 1:** Tính xem thử Hoa đã đi được bao nhiêu vòng trước khi $m<$ tổng? Đặt $S$ là tổng dãy $a$. Số vòng $= [m / S]$. Giả sử sau khi mua các vòng thì còn dư $m'$ tiền. ### Thuật trâu: Mô phỏng lại toàn bộ quá trình mua hàng của Hoa. ```cpp for (int i = 1; m >= Min; i++) { if (i > n) i = 1; if (m >= a[i]) { m -= a[i]; ans++; } } ``` ### Sub 1: $n = 2$ Có các giai đoạn: - Còn đủ tiền mua $2$ quả - Chỉ đủ tiền mua quả rẻ nhất - Thiếu tiền Dùng phép chia để xem mỗi giai đoạn xảy ra trong bao lâu (bao nhiêu vòng?) ### Sub 2: $a_1 \le a_2 \le ... \le a_n$ Tính mảng tiền tố (prefix-sum). Mô phỏng lại các vòng đi chợ của Hoa. Do $a$ tăng dần nên những loại quả được mua sẽ là những quả ở các quầy đầu tiên. Do đó chỉ cần TKNP để xác định là mua tới quả nào thì hết tiền, xong lại bắt đầu vòng mới. ```cpp // Credit: OLP4CT587 void sub2() { int res = 0; //prefix-sum for (int i = 1; i <= n; i++) a[i] += a[i - 1]; //trở thành tổng i số đầu tiên while (m >= a[1]) { int k = upper_bound(a + 1, a + 1 + n, m) - a - 1; //upper_bound: tìm vị trí đầu tiên > hẳn m // lại -1 đi để ra vị trí cuối cùng <= res += (m / a[k]) * k; m = m % a[k]; } cout << res; } ``` ### Sub 3: $m \le \min a\cdot 10^6$ Đáp án chắc chắn $\le 10^6$. Tuy nhiên nếu cày trâu như trên thì sẽ TLE (theo lí thuyết) vì có trường hợp quả rẻ nhất nằm ở một vị trí duy nhất, và ta phải chạy for hết $n$ phần tử mới tìm được quầy rẻ đó để mua. VD: ``` n = 1e5, m = 1e18 a[i] = 10^9 với mọi i, ngoại trừ tại vị trí i = ? thì a[i] = 1 ``` Ý tưởng: http://online.vku.udn.vn/src/88371 Dùng DSU, tính mảng $nxt(i)$ là vị trí tiếp theo trên vòng tròn mà $\le m$ (số tiền còn hiện tại)  ### Sub 4: ### Đơn giản Thuật toán sau mô phỏng lại thuật trâu:  Code trên của: baoduong23042007 Giải thích: Vòng lặp `while` bên ngoài thực hiện rất ít lần, vì câu lệnh `m %= sum` sẽ giảm $m$ đi ít nhất $2$ lần (nếu `m > sum`). Nếu `m < sum` thì phần "cày trâu" sẽ giảm $m$ đi xuống rất bé ? ### Phức tạp (Chưa kiểm chứng được đúng sai nhưng thấy có một số thí sinh code BIT) Xét $O(n)$ thời điểm đặc biệt: ngay khi $m$ giảm xuống bé hơn giá trị lớn thứ $i$ trong dãy $a$. Quầy hàng nào đắt hơn $m$ thì ta "xóa" nó đi. Về ý tưởng thì vẫn dùng phép chia (đi thành nhiều vòng) giống subtask 1, cho tới khi $m$ bé hơn mốc tiếp theo. Vậy việc cần quan tâm là xét trong một đoạn liên tiếp sẽ có bao nhiêu số chưa bị "xóa" Có cần BIT hay không? ## B3: DISTANCE Tóm tắt: Cho cây $n$ đỉnh. Có $k$ đỉnh đặc biệt. Hỏi khoảng cách từ $u$ tới đỉnh đặc biệt gần nhất ($\neq u$) là bao nhiêu? ### Sub 1: $n \le 200$ Thuật $O(n^2):$ Tính trước k/cách giữa mọi cặp đỉnh trên cây (BFS/DFS), lưu vào mảng. Sau đó chạy `for` $n^2$ để tìm cà phê gần nhất. ### Sub 2: $n \le 10^5, k \le 50$ Với mỗi $u$, ta duyệt qua $k$ đỉnh đặc biệt, cần lấy k/cách từ $u$ tới đỉnh đó. Vậy lúc đầu cần tính trước bằng cách BFS/DFS từ mỗi một trong $k$ đỉnh. Hoặc: dùng LCA để tính (phức tạp). ĐPT: $O(nk)$ ### Sub 3 + 4: Làm chưa tối ưu la http://online.vku.udn.vn/src/89811 QHĐ trên cây. DFS 2 lần để tính hai loại khoảng cách: - từ nút con cháu cập nhật lên $u$ - từ nút tổ tiên (nằm ngoài cây gốc $u$) cập nhật cho $u$. Đặt `dp_down[u], dp_up[u]` lần lượt là k/c loại 1,2 ở trên. Khoảng cách loại 1 tính được bằng dfs thông thường. Gọi dfs để tính `dp_down` của những nút con cháu trước, sau đó gán `dp_down[u] = max(dp_down[v] + w)`. https://viblo.asia/p/quy-hoach-dong-tren-cay-LzD5d9B4KjY Khoảng cách loại 2 phải tính ngược lại một chút. Tận dụng khoảng cách loại 1, và kết quả từ các nút cha & tổ tiên ta cập nhật cho các nút con cháu. Có hai trường hợp: - `dp_up[v] = dp_up[u] + w` (từ nút tổ tiên của $u$ cập nhật cho $v$) - Từ một nhánh khác trong cây con gốc $u$, gọi là $v_2$, cập nhật cho $v$. Ta có `dp_up[v] = dp_down[v2] + w2 + w1` (từ nút $v_2$, đi theo hai cạnh để tới $u$, rồi tới $v$) Nếu nhóm biểu thức trên lại, ta thấy cần lấy $\max$ của tất cả `dp_down[.] + w[.]` của những nhánh khác $v$. #### Sub 3: Ta lưu hết vào một `multiset`, khi duyệt tới nhánh hiện tại thì xóa nó đi để tính, xong lại thêm vào. ĐPT $O(n\log)$ #### Sub 4: Cần tìm $\max$ mọi nhánh còn lại nhanh hơn. Có thể: - Hướng 1: Làm giống prefix-sum - Hướng 2: Lưu lại hai giá trị bé nhất. ## B4: CARDGAME ### $O(n^2)$ Thử hết mọi đoạn con (chạy for $l,r$), lấy tổng đoạn trừ max ### Full (idea) Giả sử $a_i$ lớn hơn mọi số trong đoạn $[l,r]$ (dùng stack/ gì đó để tìm l min, r max). Tính prefix-sum thôi: Lấy max của S từ i tới r, trừ cho min của S từ l-1 tới i-1. Segment Tree