# OLP 31/3 Hai bài contest GRID và hai bài từ OLP sinh viên https://lqdoj.edu.vn/problem/dhbbspell https://lqdoj.edu.vn/problem/labudovi https://oj.vnoi.info/problem/olp_kc22_smartshop https://oj.vnoi.info/problem/olp_ct22_roadimpro ## SPELL BFS theo 3 chiều. Đặt $d(x,y,z) = t:$ tới ô $(x,y)$, đã viết được $z$ kí tự của xâu thì cần tối thiểu là $t$ bước ## LABUDOVI ### Sol 1 Dùng BFS đa nguồn (ban đầu thêm toàn bộ ô không bị đóng băng) để tính thời gian băng tan, đặt là $a(i,j)$. Sau đó, tìm đường đi ngắn nhất. Trọng số đường đi tính theo $\max a$ của các ô thuộc đường đó. Dùng Dijkstra sẽ bị TLE ($\times \log$) Nhận xét $a(i,j)$ của các ô kề chênh lệch không quá $1$. Dùng thuật sau: https://cp-algorithms.com/graph/01_bfs.html (giống dijkstra nhưng sửa `priority_queue` thành `deque`) (thật ra bài này đã làm bài 2) ### Sol 2 (rất tiếc mới có Đạt cài nhưng bị WA 2 test :cry:) Cũng tính thời điểm băng tan như trên. Duyệt các ô băng theo thời điểm băng tan tăng dần, với mỗi ô, nối nó với các ô kề cạnh, sau đó kiểm tra hai ô `L` có liên thông hay không? Dùng DSU. ## SMARTSHOP Lũy thừa $2,3,5$ tăng rất nhanh nên chỉ có tối đa $\log_2{10^9} \le 30$ thiết bị. Tạo ra hết và trâu ## ROADIMPRO Dùng Dijkstra nhưng có một số hướng tiếp cận: - Đặt $f(u,x)$ là khoảng cách ngắn nhất để đi tới $u$ và trên đường đi ta đã thay trọng số một cạnh bất kì thành $x$ - Thay vì nghĩ là "thay đổi trọng số, hãy hình dung là ta xóa một cạnh bất kì đi, và $+t$ vào từng truy vấn. Đặt $f(u,0/1)$ là đi tới $u$ và đã xóa cạnh hay chưa?