Vậy là contest lqdoj004 đã được tổ chức thành công! Ngoại trừ một sự cố "nho nhỏ" về phần website khiến cho trang bị sập trong vòng hơn 1 tiếng, còn ngoài ra thì cuộc thi này đã diễn ra rất tốt đẹp =)).

BTC xin chúc mừng 5 thí sinh đứng đầu bảng rank:

THÍ SINH	ĐIỂM	THỜI GIAN
[user:Kuro_Neko]	700	03:02:36
thoi_bay_corona	700	03:23:36
NaughtyWind	600	04:33:33
anhkha2003	600	04:51:52
Vinht1k60	600	08:00:45

Và đây là những người AC đầu tiên cho từng bài (Do web bị sập giữa lúc thi nên số liệu cho những bài đầu có thể không đúng với thực tế):

BÀI	THÍ SINH	THỜI GIAN
A	A519LeVanDuc thang BichSonNhat	00:00:13
B	A519LeVanDuc	00:00:31
C	L8cuberlong	00:00:38
D	thang	00:01:00
E	thoi_bay_corona	00:31:33
F	thoi_bay_corona	00:46:06
G	[user:Kuro_Neko]	00:32:18

Sau đây là lời giải cho 7 bài:

---

A - Doraemon và cuộc phiêu lưu ở hòn đảo kho báu [Bản dễ]

Bài này ta chỉ việc làm theo đề bài: Kiểm tra tất cả bộ \((i, j) \, (L \leq i < j \leq R)\) và tìm giá trị tối thiểu của \((i \times j) \bmod M\).

Độ phức tạp: \(O((R-L)^2)\)

---

B - Doraemon và những chú khỉ khá là không liên quan

Ta thấy rằng khi học sinh đến sớm thứ \(x\) đi vào lớp thì lúc đó lớp có tổng cộng \(x\) học sinh - nói cách khác, học sinh thứ \(i\) đến sớm thứ \(A_i\). Vậy ta chỉ cần sắp xếp lại mảng \(A\) và tìm vị trí ban đầu của mỗi phần tử sau khi sắp xếp.

Độ phức tạp: \(O(N \log N)\) hoặc \(O(N)\) tùy cách cài đặt.

---

C - Doraemon và thử thách đầu tiên [Bản dễ]

Xét hàng thứ \(i\), nếu như lúc đầu trên hàng đó có \(0\) hoặc \(1\) con quái vật thì ta chỉ có \(1\) cách tô màu duy nhất (màu trắng hoặc màu của con quái vật tương ứng); còn nếu có \(2\) quái vật thì ta có \(2\) cách tô màu (tùy vào con quái vật bên trái hay bên phải tô màu trước). Vậy đáp án cho bài này là \(2^x\), với \(x\) là số hàng có \(2\) con robot.

Độ phức tạp: \(O(N)\).

---

D - Doraemon và cuộc phiêu lưu ở hòn đảo kho báu [Bản khó]

Do bài này có giới hạn \(L, R \leq 10^9\) nên có thể các bạn nghĩ là sẽ không thể giải được bài này dùng thuật của bản dễ 😉 . Tuy nhiên, ai tinh ý thì sẽ phát hiện ra rằng:

• Trong \(M\) số tự nhiên liên tiếp nhau thì sẽ luôn có 1 số chia hết cho \(M\).

Vậy nếu như \((R - L + 1) \geq M\) thì đáp án sẽ luôn là \(0\), ngoài ra thì các bạn có thể dùng thuật của bản dễ để giải bài này.

Độ phức tạp: \(O(M^2)\)

---

E - Doraemon tự kỷ với trò chơi mới

Bài này rất đơn giản, chỉ cần làm theo yêu cầu đề bài: Với mỗi ô trống, đặt bánh rán nâu vào và kiểm tra xem có thể lật được bao nhiêu bánh rán trắng là xong.

Độ phức tạp: \(O(N^3)\), \(O(N^2 \log N)\) hoặc \(O(N^2)\) \((N = 8)\) tùy cách cài đặt.

---

F - Doraemon, chú mèo máy đến từ tương lai

Ta có vài nhận xét sau:

• \(x \oplus x = 0\). (1)

• Nếu không bit \(1\) nào của \(x\) có cùng vị trí với bit \(1\) của \(y\) (2) thì \(x \oplus y = x + y\).

• Do \(M \leq 10^9\) nên bit có giá trị cao nhất có thể của \(M\) là \(30\) (Do \(2^{30} = 1073741824 > 10^9\)). (3)

• Nếu \(M | x\) và \(M | y\) (4) thì \(M | (x + y)\).

Không mất tính tổng quát, giả sử \(x \leq y \leq z\). Ta có \(x \oplus y \oplus z = 0 \Leftrightarrow x \oplus y = z\) (1). Nếu ta có thể tìm được \(x\) và \(y\) thỏa mãn (2) và (4) thì khi ta lấy \(z = x + y\) thì ta sẽ có \(1\) bộ ba \((x, y, z)\) thỏa mãn. Dựa vào \((3)\), ta có thể chọn \(x = M\) và \(y = M \times 2^{30}\).

Vậy \(1\) bộ ba có thể là \(x = M, y = M \times 2^{30}, z = M + M \times 2^{30}\).

Độ phức tạp: \(O(T)\)

---

G - Doraemon và thử thách đầu tiên [Bản khó]

Đầu tiên ta sẽ loại bỏ hết các hàng và cột không có quái vật nào vì chúng không quan trọng trong bài này.

Gọi \(X\) và \(Y\) là số hàng và cột có quái vật \((1 \leq X \leq N, 1 \leq Y \leq M)\).

Ta ánh xạ một cách tô màu với một đường đi từ ô \((0, 0)\) đến ô \((X, Y)\) như sau:

Xuất phát tại ô \((0, 0)\), tại một thời điểm mà ta đang đứng ở ô \((x, y)\), ta đi sang ô \((x + 1, y)\) nếu ô \((x + 1, y)\) là ô cuối cùng có màu của hàng \(x + 1\), nếu không ta đi sang ô \((x, y + 1)\), và ô \((x, y + 1)\) là ô cuối cùng có màu của cột \(y + 1\) (vì nếu cả hai không phải ô cuối cùng thì ô \((x + 1, y + 1)\) sẽ có màu của cả hàng \(x + 1\) và cột \(y + 1\)).

Ánh xạ là đơn ánh vì với mỗi cách tô màu, ta có một và chỉ một cách đi. Ánh xạ là toàn ánh vì với mỗi cách đi ta chỉ có một cách tô màu. Cách biến đổi từ đường đi về một cách tô màu như sau:

Giả sử ta đang đứng tại vị trí \((x, y)\). Nếu tại lượt sau ta đi sang ô \((x + 1, y)\) thì ô này phải là ô cuối cùng có màu của hàng \(x + 1\). Ta tô các ô từ \((x + 1, 1)\) đến \((x + 1, y)\) bằng màu của hàng \(x + 1\), sau đó tiếp tục làm tiếp. Khi đến một ô \((x, y)\), ta đã tô màu cả bảng từ \((1, 1)\) đến \((x, y)\) nên sau khi làm xong tất cả các ô đều được tô màu.

Vậy ánh xạ là song ánh, suy ra số cách tô màu bằng số đường đi từ ô \((0, 0)\) đến ô \((X, Y)\) hay \(\binom{X + Y}{X}\).

Ở dưới là một ví dụ về ánh xạ giữa cách tô màu và đường đi:

Độ phức tạp: \(O(N \log N)\) hoặc \(O(N)\) tùy vào cách cài đặt.