Hướng dẫn cho LQDOJ Cup 2023 - Round 2 - Roller
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Subtask \(1\) (\(20\%\) số điểm): \(k = 0, nm \le 500, L = 400\) và dữ liệu vào đảm bảo luôn tồn tại chuỗi nước đi không quá \(13\) bước.
Tutorial
Khi khối hình ở tại một vị trí bất kì trên bảng HCN, ta có nhiều nhất là \(4\) cách để di chuyển nó.
Vì đề bài đảm bảo chuỗi đáp án dài không quá \(13\) bước, ta có thể duyệt vét cạn tất cả các cách đi.
Độ phức tạp: \(\mathcal{O}(4^{13})\)
Solution
Về cài đặt, cần phải chú ý chi tiết: Với vị trí của khối hộp được mô tả bởi ba số \((x,y,d)\), khi lần lượt lật theo bốn hướng (UDLR) thì vị trí mới của khối hộp như thế nào?
Tác giả đề xuất mảng hằng sau:
struct State {
int x,y,d;
State(int x=0, int y=0, int d=-1): x(x), y(y), d(d) {}
};
//U D L R
const int x_nxt[] { 0, 0,+1};
const int y_nxt[] { 0,+1, 0};
const string chars_direction = "UDLR";
const State direction[3][4] = {
{State(-2,0, 2), State(1,0, 2), State(0,-2, 1), State(0,1, 1)},
{State(-1,0, 1), State(1,0, 1), State(0,-1, 0), State(0,2, 0)},
{State(-1,0, 0), State(2,0, 0), State(0,-1, 2), State(0,1, 2)}
};
Trong đoạn code trên, cấu trúc
State đại diện cho tọa độ của một ô (\((x,y,d)\) theo mô tả của đề). Mảng x_nxt, y_nxt là tọa độ của ô còn lại tiếp xúc với bảng, không kể ô góc trái trên (nếu có) tương ứng với \(3\) khả năng của \(d\).Mảng
directions thể hiện chênh lệch về tọa độ \(x,y\) của ô góc trái trên sau khi lật theo các hướng, so với trước khi lật; đồng thời cũng cho biết "hướng" \(d\) của khối hình sau khi lật.
Bonus
Giới hạn \(L = 400\) để thuật toán của subtask cuối có thể giải được subtask 1 này.
Subtask \(2\) (\(30\%\) số điểm): \(k = 0, x_0 = y_0 = 1, d = 0, n\) chia \(3\) dư \(1\), \((m+1)\) không chia hết cho \(3, L = \lfloor \frac{2mn}{3} \rfloor\).
Tutorial
Trong subtask này, giới hạn số nước đi \(L\) rất chặt, nên không thể giải bằng thuật toán của subtask cuối.
Nhận thấy vị trí của khối hộp khá đặc biệt: Dựng thẳng đứng tại ô góc trái trên. Ngoài ra có một điểm khá thuận lợi là bảng không có chướng ngại vật (\(k = 0\)), cùng kích thước \(m,n\) rất đặc biệt.
Để tiếp cận tới lời giải, ta thử nháp với các số nhỏ hơn: \(n = 1\) hoặc \(n = 4,7,\dots\); \(m = 1,3,4,6,7,9,\dots\)
Một cách làm khả dĩ:
- Mỗi khi \(y\) chia \(3\) dư \(1\): Di chuyển
UhoặcDliên tục cho tới khi chạm biên. Vì \(n\) chia \(3\) dư \(1\), nên đảm bảo khi khối hình dừng chân tại \(x = 1\) hoặc \(x = n\), hướng \(d\) của nó luôn là \(0\). - Sau đó, di chuyển
Rmột lần để khối hình nằm vào hai cột tiếp theo. - Lúc này, ta lại đi
UhoặcDtới khi thăm hết hai cột này. - Tiếp đến, lại di chuyển
R, lúc này khối hộp sẽ trở về trạng thái như ở bước 1.
Số nước đi ta đã sử dụng:
- Tại bước \(1\): cần \(\frac{n}{3} \times 2\) với mỗi cột
- Tại bước \(3\): cần \(n-1\) bước
- Cứ mỗi ba cột liên tiếp, ta cần khoảng: \(\frac{2n}{3} + 1 + (n-1) + 1 \le 2n\). Vậy với \(m\) cột, số nước đi sẽ \(\le L\)
Độ phức tạp: \(\mathcal{O}(mn)\)
Note
Khá giống với kiểu bài ad-hoc, constructive của Codeforces. Bạn có thể coi subtask này như một bài riêng lẻ được "đính kèm" vào bài toán.
Subtask \(3\) (\(20\%\) số điểm): \(n,m \le 50, L = 1.5 \cdot 10^6\).
Tutorial
Coi mỗi vị trí có thể đặt khối hộp vào được như một đỉnh của đồ thị. Các phép di chuyển tương ứng với các cạnh. Khi di chuyển từ một vị trí sang một vị trí liền kề, ta coi như đang đi từ đỉnh \(u\) tới đỉnh \(v\) thông qua cạnh \((u,v)\).
Đáp án bài toán khác \(-1\), nếu như mọi vị trí có thể đặt (mọi đỉnh) đều liên thông với nhau.
Vì giới hạn số nước đi rất lớn, nên ta chỉ cần đảm bảo sẽ thăm hết mọi đỉnh.
Tuy nhiên, với cách làm: "Với mỗi đỉnh \(u\) trong đồ thị, ta in ra đường đi từ đỉnh gốc \(r\) (vị trí ban đầu) tới \(u\), rồi lại đi ngược về lại \(r\)", thì số nước đi quá lớn.
Vì số đỉnh rơi vào \(O(3mn)\), nên số thao tác bạn dùng có thể lên tới \(O((mn)^2)\), quá lớn.
Để tối ưu, có thể chỉ in ra đường đi tới các lá, hoặc ưu tiên theo khoảng cách nhỏ nhất, hoặc theo một tiêu chí tham lam đủ tốt.
Độ phức tạp: \(\mathcal{O}((mn)^2 + L)\).
Subtask \(4\) (\(20\%\) số điểm): \(s_i = 1, \forall 1 \leq i \leq m\).
Tutorial
Khi duyệt DFS từ đỉnh gốc, ta có được cây DFS.
Ứng dụng Euler Walk, ta thăm các đỉnh ngay trong quá trình DFS. Tức: sau khi thăm mọi đỉnh trong cây con nút \(u\), khối hộp phải quay lại ngay đúng vị trí của \(u\). Giả sử ta viết được một hàm dfs(u) in ra được một chuỗi các nước đi thỏa mãn điều kiện trên. Với nút cha \(u\) và nút con \(v\) trong cây, ta có thể làm như sau:
- Đi từ \(u\) tới \(v\).
- Bắt đầu từ \(v\), thăm toàn bộ cây con gốc \(v\), sau đó quay lại đứng ở \(v\). Việc này xử lý bằng cách gọi hàm
dfs(v) - Đi từ \(v\) lên \(u\).
Như vậy, mỗi cạnh \((u,v)\) được sử dụng đúng hai lần. Do đó, số nước đi ta cần sẽ là \(2\times (|V| - 1) < 2 \times 3mn = 6mn\) (với \(V\) là tập các đỉnh).
Độ phức tạp: \(\mathcal{O}(mn)\)
Bình luận