---
# System prepended metadata

title: 'Pusheen Contest 2023 #7'
tags: [CLA K22]

---

## Hàng rào
Nhận xét: con bò bề ngang $w$ thỏa mãn điều kiện đề bài, thì các con bò kích thước $w-1$ cũng thỏa, nhưng với bề ngang $w+1$ thì chưa chắc => chặt nhị phân đáp án.

Tuy nhiên việc kiểm tra thỏa mãn điều kiện khó hơn việc kiểm tra "không thỏa điều kiện". Chặt nhị phân, nếu bề ngang này không thỏa thì giảm, ngược lại thì tăng.

## Thành phố sông nước
Nhận xét: Các cây cầu không được cắt nhau. Do nếu tồn tại 2 cây cầu cắt nhau, ta có cách thay thế chúng bằng hai cầu không cắt nhau với chi phí nhỏ hơn.
![](https://hackmd.io/_uploads/SkQYh7pKh.png)

Gọi $dp[i][j][k]$ là tổng chi phí nhỏ nhất để xây $k$ xây cầu xét đến tọa độ thứ $i$ ở bờ Bắc và tọa độ thứ $j$ ở bờ Nam.
$$
dp[i][j][k] = \min(dp[i-1][j][k], dp[i][j-1][k], dp[i-1][j-1][k-1] + dist(i, j))
$$

Độ phức tạp $O(N^2K)$

## Quản lý lương
Cho một cây $n$ nút, mỗi nút có giá trị $w[i]$. Có các loại truy vấn:
1. Tăng các nút trong cây con gốc $A$ lên $x$ đơn vị.
2. Tìm giá trị của nút $A$.

### Thuật trâu 
Với mỗi truy vấn cập nhật, thực hiện DFS trong $O(n)$ 
=> Độ phức tạp $O(mn)$.

### Thuật chuẩn 
![](https://hackmd.io/_uploads/r1liWVTY2.png)

DFS sinh mảng Euler tour, bài toán trở thành cập nhật đoạn, truy vấn điểm.
1. Segment tree lazy update: VNOI
2. Mảng cộng dồn + Fenwick tree: https://robert1003.github.io/2020/01/27/fenwick-tree.html

Độ phức tạp $O(n\log n)$

## Đường tắt
Cho một đa đồ thị vô hướng có trọng số liên thông. Có $c_i$ bé ở đỉnh $i$, các bé này cần di chuyển về đỉnh 1 bằng đường đi ngắn nhất và thứ tự từ điển nhỏ nhất.

Đỉnh $x$, teleport về đỉnh 1 với thời gian là $T$.
Tìm một đỉnh $x$ sao cho tổng thời gian về đỉnh 1 của các bé là nhỏ nhất.

### Bài toán con: không đặt trạm xe
Nếu bỏ qua đỉnh $x$ (không đặt trạm xe), tổng thời gian di chuyển về đỉnh $1$ của các bé là $\sum\limits_i dist[i]\times c[i]$ với $dist[i]$ là độ dài đường đi ngắn nhất từ $i$ về $1$. Ta dùng thuật toán Dijkstra xuất phát từ đỉnh 1 để tính $dist[i]$.

### Bài toán gốc: có đặt trạm xe
Giả sử đặt trạm xe tại một đỉnh $x$ bất kì, để tối ưu thì $T < dist[x]$. Khi đó thời gian di chuyển của các bé giảm đi một lượng là $(dist[x] - T) \times A[x]$ với $A[x]$ là số lượng bé đi qua đỉnh $x$ trên đường về đỉnh $1$ - nói cách khác, $A[x]$ là số lượng bé có đường đi ngắn nhất về đỉnh $1$ qua đỉnh $x$.

#### Tính $A[x]$
![](https://hackmd.io/_uploads/BJ9iuN6F3.png)

Ta dựng đồ thị $G'$ với tập đỉnh là tập đỉnh của đồ thị gốc, 
các cạnh có tính chất sau:
Với mỗi đỉnh $u \neq 1$, xác định đỉnh $v$ sao cho:
1. $dist[v] + c(v, u) = dist[u]$
2. $v$ nhỏ nhất

Ta có thể thấy được luôn tồn tại duy nhất $1$ giá trị $v$ thỏa mãn với mỗi $u \neq 1$.

Đồ thị $G'$ có dạng một cây, và các cạnh trên cây là những cạnh được dùng trên đường đi về đỉnh $1$ của các bé. Khi đó, ta tính được $A[x]$ bằng quy hoạch động trên cây, theo công thức sau:
$$
A[x] = \sum\limits_{i \in subtree(x)} c[i] = \sum\limits_{y \in children(x)} A[y]
$$

Ta dễ dàng tính được $A[x]$ với độ phức tạp $O(n)$.

Sau khi tính $A$, ta duyệt qua từng đỉnh rồi tình giá trị $(dist[x]-T)\times A[x]$ lớn nhất.

Độ phức tạp $O(m \log n)$

Lưu ý: 
- Độ phức tạp của DFS/BFS là $O(n+m)$ với $n$ là số đỉnh và $m$ là số cạnh. Do đó nếu đồ thị dày thì đpt của DFS/BFS có thể lên tới $O(n^2)$.
- Độ phức tạp của Dijkstra (dùng heap) là $O(m \log n)$.
    - Dijkstra $O(n^2 + m)$: https://vnspoj.github.io/wikivn/graph/dijkstra
    - Dijkstra $O(m \log n)$: https://vnspoj.github.io/wikivn/graph/dijkstra_sparse
    - Do đó nếu đồ thị dày thì Dijkstra $O(n^2)$ sẽ tối ưu hơn.
