Xây mảng

Nguồn: CLUE OJ – Chương 20: Quay lui (MarisaOJ) Độ khó: Dễ Quay lui Cắt nhánh

Đề bài

Bạn hãy đếm số lượng dãy số nguyên dương $A$ có độ dài $n$ thoả mãn:

• Giá trị các phần tử không quá $m$.
• $q$ điều kiện dạng $(i, j, k)$ nghĩa là $A_i + A_j = k$.

Input:

• Dòng đầu tiên gồm 3 số nguyên $n, m, q$.
• $q$ dòng tiếp theo mỗi dòng gồm 3 số nguyên $i, j, k$.

Output: một số nguyên duy nhất là số dãy thoả mãn đủ $q$ điều kiện.

Điều kiện: $1 \le n, m, q \le 7$; $1 \le i, j \le n$; $1 \le k \le 14$.

Ví dụ – input

2 2 1
1 2 3

Ví dụ – output

2

Giải thích ví dụ: $n = 2$, $m = 2$, điều kiện $A_1 + A_2 = 3$. Có 2 dãy thoả mãn là $(1, 2)$ và $(2, 1)$.

Lời mở đầu

Đây là bài "sinh dãy" kinh điển của chương Quay lui: với mỗi vị trí, thử lần lượt mọi giá trị có thể, đi sâu vào vị trí tiếp theo, xong thì quay lui đổi giá trị khác. Vì $n, m \le 7$ nên số dãy tối đa chỉ $7^7 \approx 8 \cdot 10^5$, sinh hết vẫn chạy rất nhanh. Mình sẽ làm 2 cách: sinh hết rồi kiểm tra, và cách khéo hơn là cắt nhánh ngay khi thấy dãy đang xây đã sai điều kiện.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 testÝ tưởngCây quay luiCách 1Sinh hếtCách 2Cắt nhánh

Bộ testBộ test chính thức có gì?

Thông số	Phân bố (giá trị: số test)
$n$	2: 4, 3: 11, 4: 19, 5: 23, 6: 17, 7: 26
$m$	2: 2, 3: 10, 4: 11, 5: 21, 6: 27, 7: 29
$q$	1: 72, 2: 19, 3: 7, 4: 2

Có 100 test, tất cả đều nhỏ ($n, m, q \le 7$), trong đó 5 test có $n = m = 7$ – lớn nhất có thể, khi đó có $7^7 = 823\,543$ dãy cần xét. Đáp án nhỏ nhất là 1, lớn nhất là 117.649 (không test nào ra 0). Có 25 test chứa điều kiện dạng $i = j$ (tức $2A_i = k$) – code phải xử lý được trường hợp này.

Đề không chia subtask nên mình coi cả bộ test là một mức. Bảng kết quả hai cách mình làm:

Cách	Ý tưởng	C++	Python
Cách 1	Sinh đủ $m^n$ dãy rồi mới kiểm tra $q$ điều kiện	100/100, ≤ 0,009 s	100/100, ≤ 0,34 s
Cách 2	Kiểm tra điều kiện ngay khi đủ dữ liệu, sai thì cắt nhánh	100/100, ≤ 0,004 s	100/100, ≤ 0,18 s

Ý tưởngCây quay lui: mỗi tầng điền một phần tử

Hãy tưởng tượng ta điền dãy từ trái sang phải. Ở tầng 1 có $m$ lựa chọn cho $A_1$; với mỗi lựa chọn đó, tầng 2 lại có $m$ lựa chọn cho $A_2$, ... Các lựa chọn tạo thành một cây: mỗi đường đi từ gốc xuống lá (tầng $n$) là một dãy hoàn chỉnh. Hàm quay lui Try(i) chính là "đứng ở tầng $i$, thử lần lượt các giá trị $v = 1..m$ cho $A_i$ rồi gọi Try(i + 1)".

• Cách 1 – đi hết tới lá rồi mới kiểm tra $q$ điều kiện. Cây có đủ $m^n$ lá.
• Cách 2 – một điều kiện $(i, j, k)$ chỉ phụ thuộc $A_i$ và $A_j$, nên ngay khi điền xong phần tử thứ $\max(i, j)$ là kiểm tra được rồi. Nếu sai thì khỏi đi tiếp – cả cây con bên dưới bị cắt bỏ.

Em nhập $n, m$ và các điều kiện (mỗi điều kiện 3 số $i\ j\ k$) rồi bấm Tiếp để xem cây quay lui của cách 2 mọc dần (mỗi nút ghi phần đầu dãy đã điền, ví dụ nút 12 nghĩa là $A_1 = 1, A_2 = 2$; gốc ∅ là dãy rỗng):

nút đang xétdãy hợp lệ (được đếm)sai điều kiện → cắt nhánhviền cam: đang trên ngăn xếp

n m Các điều kiện (i j k)

Ví dụ nhanh:

Cách 1Sinh mọi dãy rồi kiểm tra

Hàm Try(i) điền giá trị cho A[i]. Khi i > n nghĩa là đã có một dãy đầy đủ, ta duyệt $q$ điều kiện, sai một cái là bỏ (return), đúng hết thì cnt++.

C++▶ Chạy tay từng dòng codeCách 1: sinh đủ m^n dãy, tới lá mới kiểm tra q điều kiện.

Dữ liệu vào (stdin) – sửa thoải mái2 2 1 1 2 3

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Khung bên phải là ngăn xếp lời gọi: mỗi tầng Try(i) nhớ giá trị v đang thử cho A[i].

1. Không cần "trả lại" giá trị cũ cho A[i] sau khi gọi đệ quy: vòng lặp tiếp theo sẽ ghi đè A[i] = v mới, còn các ô phía sau sẽ được điền lại khi đi xuống.
2. Điều kiện có $i = j$ (ví dụ 1 1 4) tự động thành $A_1 + A_1 = 4$, không cần xử lý riêng.

Không gian$O(n + q)$

Thời gian$O(m^n \cdot q)$ ≈ $5{,}8 \cdot 10^6$

Kết quả chạy thật: C++ đúng 100/100 test, chậm nhất 0,009 giây; Python (dùng itertools.product để sinh dãy) đúng 100/100, chậm nhất 0,34 giây.

Cách 2Cắt nhánh ngay khi sai điều kiện

Viết thêm hàm ok(i): sau khi điền A[i], kiểm tra mọi điều kiện có $\max(X_t, Y_t) = i$ – đó là những điều kiện vừa đủ dữ liệu để kiểm tra. Mỗi điều kiện vì vậy được kiểm tra đúng một lần trên mỗi đường đi, và tới lá thì chắc chắn dãy đã đúng hết.

C++▶ Chạy tay từng dòng codeCách 2: điền A[i] xong gọi ok(i) kiểm tra ngay, sai thì cắt nhánh.

Dữ liệu vào (stdin) – sửa thoải mái2 2 1 1 2 3

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Tầng Try(i) v = ... trên ngăn xếp; khi đang chạy hàm ok(i) thì đỉnh ngăn xếp là lời gọi ok. Điều kiện xanh = đúng, đỏ = sai.

1. Lệnh if(ok(i)) Try(i + 1); là chỗ cắt nhánh: nếu A[i] vừa điền làm sai một điều kiện thì không gọi đệ quy, cả $m^{n-i}$ dãy phía dưới bị bỏ qua.
2. Ở lá (i > n) chỉ cần cnt++.

Không gian$O(n + q)$

Thời gianTệ nhất vẫn $O(m^n \cdot q)$, nhưng thực tế nhỏ hơn nhiều nhờ cắt nhánh

Kết quả chạy thật: C++ đúng 100/100 test, chậm nhất 0,004 giây (nhanh gấp đôi cách 1); Python đúng 100/100, chậm nhất 0,18 giây. Với giới hạn nhỏ thế này thì cách nào cũng qua, nhưng thói quen cắt nhánh sớm rất quan trọng ở các bài quay lui lớn hơn.

Ghi chú của mình: cả 2 cách đều đạt 100/100 test (C++ và Python). Cách 2 là mẫu quay lui chuẩn: thử giá trị → kiểm tra ngay → đúng mới đi sâu.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇