Chia gia tài (DOWRY)
Đề bài
Đề tuyển sinh lớp 10 trường Phổ thông Năng khiếu năm 2022 – 2023.
Do tuổi đã cao, Phú Ông quyết định chia toàn bộ ruộng đất của mình cho 3 người con. Đất của Phú Ông là một hình chữ nhật khá rộng lớn.
Bằng $n + 1$ đường rào ngang và $m + 1$ đường rào dọc song song, Phú Ông ngăn đất thành $n$ dòng, $m$ cột. Mảnh đất giới hạn bởi các đường rào ngang và dọc gọi là lô đất, như vậy Phú Ông có $n \times m$ lô đất. Lô đất ở dòng $i$, cột $j$ có giá trị $a_{ij}$.
Để chia đất cho 3 người con, ban đầu ông tách đất thành 2 miếng rời nhau bằng 1 đường rào ngang hoặc rào dọc. Miếng đất thứ nhất được chia cho người con đầu. Với miếng đất thứ hai, ông cũng tách thành 2 miếng rời nhau bằng 1 đường rào ngang hoặc rào dọc trên miếng đất này và chia cho 2 người còn lại. Kết quả là mỗi người con nhận được 1 miếng đất có dạng hình chữ nhật (số lô đất trong mỗi miếng có thể khác nhau). Để công bằng, Phú Ông muốn các miếng đất phải có giá trị bằng nhau. Giá trị của miếng đất bằng tổng giá trị tất cả lô đất thuộc miếng đất đó.
Yêu cầu: hãy giúp Phú Ông tìm ra một cách chia thỏa mong muốn hoặc thông báo không thể thực hiện.
Dữ liệu: vào từ tập tin văn bản DOWRY.INP
- Dòng đầu tiên chứa 2 số nguyên $n$ và $m$ $(1 \le n, m \le 1000)$.
- Dòng thứ $i$ trong $n$ dòng sau chứa $m$ số nguyên $a_{i1}, a_{i2}, \dots, a_{im}$ $(1 \le |a_{ij}| \le 10^6)$ – giá trị của $m$ lô đất tương ứng trên dòng $i$.
Kết quả: ghi ra tập tin văn bản DOWRY.OUT
- Dòng đầu tiên ghi thông báo
YESnếu tìm được một cách chia, ngược lại ghi thông báoNO. - Trường hợp tìm được một cách chia thì 2 dòng tiếp theo chứa mô tả đường tách thứ nhất và thứ hai tương ứng. Mỗi đường tách được mô tả theo dạng
c i– trong đóc$\in$ {N,D} cho biết đường tách là ngang hay dọc vàilà đường tách liền kề với dòng hoặc cột thứi(đường nằm ngay dưới dòngi/ ngay bên phải cộti). Dòng và cột được đánh số bắt đầu từ 1.
Giải thích ví dụ 1: đường ngang N 1 tách dòng 1 (giá trị $3 + 8 + 1 - 6 = 6$) cho người con đầu; miếng còn lại (dòng 2–3) được đường dọc D 2 tách thành 2 miếng giá trị $2 - 3 - 1 + 8 = 6$ và $2 + 2 + 1 + 1 = 6$. Ví dụ 2 không có cách chia.
Ghi chú của đề trên CLUE OJ: đề bài không nói nhưng nếu có nhiều cách chia đúng khác nhau thì các bạn cứ in ra 1 cách chia đúng bất kỳ, hệ thống sẽ tự kiểm tra. Dữ liệu đọc ghi với file với tên file như trong đề bài.
3 4
3 8 1 -6
2 -3 2 2
-1 8 1 1YES
N 1
D 22 2
-8 6
10 -3NOLời mở đầu
Hai đường rào chỉ có vài nghìn vị trí có thể đặt, nên ý tưởng "thử hết" là đúng hướng. Cái khó nằm ở chỗ tính tổng một miếng hình chữ nhật cho nhanh – đây là chỗ mảng cộng dồn 2 chiều tỏa sáng. Ngoài ra bộ test của bài có vài điểm "lệch" so với đề mà nếu không biết, các bạn có thể mất điểm oan; mình đã chạy thử nhiều phiên bản code để chỉ ra từng điểm một.
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 100 test, đề không chia subtask. Nhìn vào dữ liệu và đáp án mẫu thì các test được sinh theo từng "dạng" chia:
| Test | Số test | Dạng | $n$ lớn nhất | $m$ lớn nhất | $n \cdot m$ lớn nhất | $|a_{ij}|$ lớn nhất | YES / NO |
|---|---|---|---|---|---|---|---|
| 1 – 20 | 20 | ngẫu nhiên nhỏ | 10 | 10 | 70 | 10 | 20 / 0 |
| 21 – 40 | 20 | 3 dải ngang (N, N) | 900 | 1000 | 900.000 | 132768 | 20 / 0 |
| 41 – 60 | 20 | 3 dải dọc (D, D) | 1000 | 900 | 900.000 | 132768 | 20 / 0 |
| 61 – 80 | 20 | dải ngang + tách dọc (N, D) | 3000 | 300 | 900.000 | 132768 | 20 / 0 |
| 81 – 98 | 18 | tay, rất nhỏ | 4 | 4 | 6 | 64 | 18 / 0 |
| 99 – 100 | 2 | lớn, đáp án NO | 1000 | 1000 | 1.000.000 | 132768 | 0 / 2 |
Những điều cần biết (mình kiểm tra trực tiếp trên bộ test):
- Test 74 – 80 có $n = 1500$ hoặc $3000$, vượt giới hạn $n \le 1000$ của đề (tích $n \cdot m$ vẫn không quá $10^6$). Khai báo mảng tĩnh
p[1005][1005]sẽ bị truy cập ngoài mảng → lỗi chạy (RE). Hãy dùngvectorcấp phát theo $n, m$ thật. - Giá trị thật chỉ trong khoảng $\pm 132\,768$; vài test nhỏ (test 1, 3, 4...) có ô bằng 0 dù đề ghi $|a_{ij}| \ge 1$ – không ảnh hưởng thuật toán. Tổng cả ruộng có thể tới $10^6 \cdot 1{,}3 \cdot 10^5 \approx 1{,}3 \cdot 10^{11}$ → phải dùng
long long. - Người con đầu có thể nhận miếng dưới / miếng phải. Có 11 test mà đáp án gốc giao cho con cả miếng phải hoặc miếng dưới. Ví dụ ruộng
5 6 / 5 -1(tổng 15, $T = 5$): đườngD 1tách ra cột 2 có giá trị $6 - 1 = 5$ cho con cả, cột 1 được tách tiếp bằngN 1thành $5 \mid 5$. Nếu chỉ xét con cả nhận miếng trên/trái thì ruộng này bị trả lời NO. - Tổng bằng 0 thì đáp án chấp nhận miếng rỗng. Các test 82, 85, 89, 93, 96 có tổng cả ruộng bằng 0 và đáp án là
YESvới đường tách thứ hai nằm sát mép (chẳng hạn ruộng kiểu-3 -4 / 3 4: đườngD 1cho cột 1 tổng 0, cột 2 chỉ chia được nếu đặt đường thứ hai sát mép – người con thứ ba nhận miếng không có lô nào, giá trị 0). Nếu bắt mọi miếng phải có ít nhất 1 lô thì sẽ trả lời NO và sai các test này. Vì vậy trong code mình cho đường tách thứ hai được đặt tới tận mép miếng đất.
Kết quả chạy thật trên từng nhóm test (chấm bằng checker kiểm tra tổng 3 miếng, giới hạn 1 giây):
| Test | Dạng | Cách 1 vét cạn | Cách 2 cộng dồn | Cách 2 + mảng tĩnh | Chỉ cho con cả miếng trên/trái | Cấm miếng rỗng |
|---|---|---|---|---|---|---|
| 1 – 20 | ngẫu nhiên nhỏ | ✔ | ✔ | ✔ | ✘ 5 WA | ✔ |
| 21 – 40 | 3 dải ngang (N, N) | ✔ | ✔ | ✔ | ✔ | ✔ |
| 41 – 60 | 3 dải dọc (D, D) | ✘ 3 TLE | ✔ | ✔ | ✔ | ✔ |
| 61 – 80 | dải ngang + tách dọc (N, D) | ✘ 3 TLE | ✔ | ✘ 7 RE | ✔ | ✔ |
| 81 – 98 | tay, rất nhỏ | ✔ | ✔ | ✔ | ✘ 6 WA | ✘ 5 WA |
| 99 – 100 | lớn, đáp án NO | ✘ 2 TLE | ✔ | ✔ | ✔ | ✔ |
| Tổng | 92/100 | 100/100 | 93/100 | 89/100 | 95/100 |
Ý tưởngThử mọi vị trí 2 đường rào
Gọi $S$ là tổng giá trị cả ruộng. Nếu $S$ không chia hết cho 3 thì chắc chắn NO. Ngược lại mỗi người con phải nhận đúng $T = S / 3$.
- Đường tách thứ nhất: ngang (dưới dòng $i$, $1 \le i < n$) hoặc dọc (bên phải cột $i$, $1 \le i < m$). Nó chia ruộng thành miếng trước (trên/trái) và miếng sau (dưới/phải).
- Miếng nào có tổng đúng bằng $T$ thì có thể giao cho người con đầu; miếng còn lại (tổng $2T$) phải tách tiếp.
- Đường tách thứ hai: thử mọi đường ngang và dọc trên miếng còn lại; nếu phần đầu có tổng $T$ thì phần sau cũng tổng $2T - T = T$ – xong!
Có tối đa $n + m$ vị trí cho đường thứ nhất, mỗi vị trí thử tối đa $n + m$ vị trí cho đường thứ hai: chỉ cỡ $(n+m)^2 \approx 1{,}6 \cdot 10^7$ lần thử. Việc còn lại là tính tổng mỗi miếng thật nhanh. Em nhập ruộng (các dòng cách nhau bởi ;) rồi bấm Tiếp để xem máy thử từng đường rào:
Cách 1Vét cạn: cộng tay tổng mỗi miếng
Hàm sum(r1, c1, r2, c2) cộng tay từng lô trong hình chữ nhật. Hàm tach thử tách một miếng có tổng $2T$ thành 2 miếng tổng $T$ và ghi lại đường tách vào res.
- Điều kiện
(A == T && tach(B)) || (B == T && tach(A)): thử cả 2 khả năng con cả nhận miếng trước hoặc miếng sau. Nhờ "ngắt mạch" của&&, hàmtachchỉ được gọi khi miếng kia có tổng đúng $T$. - Trong
tach, vòngjchạy tới tậnr2(hoặcc2): khi đó phần sau rỗng, chỉ khớp được khi $T = 0$ – đúng như đáp án của bộ test. - Mỗi lần gọi
sumtốn tới $n \cdot m$ phép cộng, nên trường hợp xấu nhất là $O((n+m)^2 \cdot nm)$.
Kết quả chạy thật: đúng 92/100 test (sai 058, 059, 060, 078, 079, 080, 099, 100 – TLE), test đúng chậm nhất 0.38 giây. Cách này qua được nhiều hơn mình tưởng vì nó dừng ngay khi tìm được cách chia và hàm tach chỉ được gọi khi miếng đầu đúng bằng $T$ (rất hiếm). Nó chỉ chậm ở các test mà đường tách nằm xa (dòng/cột thứ vài trăm) hoặc phải thử hết vì đáp án NO (test 99, 100).
Cách 2Mảng cộng dồn 2 chiều – mỗi miếng O(1)
Dựng mảng $p[i][j]$ = tổng hình chữ nhật từ lô $(1, 1)$ tới lô $(i, j)$:
rồi tổng miếng $(r_1, c_1) \to (r_2, c_2)$ là p[r2][c2] - p[r1-1][c2] - p[r2][c1-1] + p[r1-1][c1-1]. Phần tìm kiếm giữ nguyên, chỉ thay hàm sum:
plàvectorcấp phát đúng $(n+1) \times (m+1)$ nên chạy được cả các test $n = 3000$.- Không cần lưu mảng
a: đọc tới đâu tínhptới đó. - Dòng
if(S % 3 != 0)dùng được với cả số âm vì C++ cho-6 % 3 == 0,-5 % 3 == -2 != 0.
Kết quả chạy thật: đúng 100/100 test, test đúng chậm nhất 0.09 giây. Bản Python: đúng 100/100 test, test đúng chậm nhất 0.62 giây.
Còn nếu khai báo mảng tĩnh theo đúng giới hạn đề:
long long p[1005][1005]; // theo đúng giới hạn đề n, m <= 1000thì kết quả là đúng 93/100 test (sai 074, 075, 076, 077, 078, 079, 080 – RE), test đúng chậm nhất 0.09 giây – chính là các test có $n > 1000$.
Nhận xét
Đăng nhận xét