Tìm nhị phân trên không gian đáp án
Tìm nhị phân trên không gian đáp án
Không có mảng nào để tra. Cái bạn tìm là một con số, và thứ duy nhất bạn có là một câu hỏi có hay không về từng con số. Vậy vẫn chia đôi được, với đúng một điều kiện: vị từ phải đơn điệu. Bài này bắt bạn tự phá điều kiện đó rồi xem hậu quả.
Bài trước tìm một giá trị nằm trong mảng. Nhưng phần lớn chỗ tìm nhị phân thật sự đáng giá thì lại không có mảng nào cả. Bạn cần biết mỗi nhóm nặng nhất bao nhiêu, cần biết tốc độ tối thiểu là bao nhiêu, cần biết bán kính nhỏ nhất là bao nhiêu. Cái cần tìm là một con số, và con số đó không nằm sẵn trong danh sách nào để mà tra.
Vậy vẫn chia đôi được. Thứ bạn cần không phải một mảng đã sắp, mà là một vị từ duocKhong(x) trả lời có hay không cho từng giá trị x, kèm một tính chất: nếu x làm được thì mọi giá trị lớn hơn x cũng làm được. Lúc đó dãy các câu trả lời có dạng không, không, không, có, có, có, và tìm một chỗ đổi từ không sang có thì chính là việc tìm nhị phân sinh ra để làm.
Ba chỗ hay sai, và bài này sẽ bắt bạn tự tay làm sai từng chỗ. Thứ nhất, người ta nhớ điều kiện là "mảng đã sắp" nên khi không có mảng thì không biết phải kiểm gì; điều kiện thật là tính đơn điệu của vị từ, và bạn sẽ bật một công tắc để phá nó rồi thấy tìm nhị phân trả lời sai. Thứ hai, lúc vòng lặp dừng thì trả về lo hay hi, và tại sao. Thứ ba, khoảng tìm phải chứa đáp án, mà nếu nó không chứa thì không ai báo lỗi cho bạn: máy vẫn trả về một con số trông rất chững chạc.
Sim dưới đây cho bạn chọn bài toán, sửa dữ liệu vào, chọn khoảng [lo, hi], rồi tính lại thật từng vòng lặp. Mọi tham số đều sửa được. Nếu thấy bài đang dẫn bạn tới một kết luận, hãy vặn núm cho tới khi kết luận đó sai.
1 · Câu hỏi, dữ liệu vào, và vị từ ✎ sửa được
Câu hỏi: Nhóm nặng nhất nhẹ nhất có thể là bao nhiêu, nếu phải chia dãy thành nhiều nhất k nhóm liền kề?
Cái cần tìm là sức chứa nhỏ nhất của một nhóm, một con số, chứ không phải một phần tử nằm sẵn trong mảng. Nên không có gì để so sánh với mảng đã sắp cả. Thứ duy nhất tìm nhị phân được phép hỏi là vị từ duocKhong(x): với mức trần x cho mỗi nhóm thì số nhóm cần dùng có nằm trong ngân sách k hay không. Vị từ đó gọi tới số nhóm cần dùng, và đây là ngân sách: 2.
2 · Vị từ có đơn điệu không ✎ sửa được
| x | số nhóm cần dùng | duocKhong(x) |
|---|---|---|
| … còn 3 giá trị nữa ở phía dưới, bảng chỉ in quanh ranh giới | ||
| 13 | 4 | × không |
| 14 | 3 | × không |
| 15 | 3 | × không |
| 16 | 3 | × không |
| 17 | 3 | × không |
| 18 | 2 | ✓ được |
| 19 | 2 | ✓ được |
| 20 | 2 | ✓ được |
| 21 | 2 | ✓ được |
| 22 | 2 | ✓ được |
| 23 | 2 | ✓ được |
| … còn 9 giá trị nữa ở phía trên | ||
duocKhong đang đúng rồi lại sai trở lại. Có 15 giá trị được và 8 giá trị không được, và toàn bộ phần được nằm liền một khối ở phía trên. Đúng điều kiện để tìm nhị phân dùng được.3 · Khoảng tìm và từng vòng lặp ✎ sửa được
Khoảng đang tìm là [10, 32], tức 23 giá trị ứng viên. Trần số vòng lặp là ⌊log₂ 23⌋ + 1 = 5, và lần này nó tiêu 5 vòng.
| vòng | lo | hi | còn lại | mid | số nhóm cần dùng | duocKhong(mid) | khoảng mới |
|---|---|---|---|---|---|---|---|
| 1 | 10 | 32 | 23 | 21 | 2 | ✓ được | [10, 20] |
| 2 | 10 | 20 | 11 | 15 | 3 | × không | [16, 20] |
| 3 | 16 | 20 | 5 | 18 | 2 | ✓ được | [16, 17] |
| 4 | 16 | 17 | 2 | 16 | 3 | × không | [17, 17] |
| 5 | 17 | 17 | 1 | 17 | 3 | × không | [18, 17], rỗng |
x = 18. Với giá trị đó, cách xếp tốt nhất là:4 · Ranh giới, và vì sao lời đáp là lo
lo lúc vòng lặp dừnghi lúc dừng, luôn bằng lo trừ 1⌊log₂ n⌋ + 1Bất biến của vòng lặp: mọi x nhỏ hơn lo đều đã bị chứng minh là không được, và mọi x lớn hơn hi đều đã bị chứng minh là được. Mỗi vòng chỉ làm đúng một trong hai việc đó, nên hai câu trên không bao giờ hỏng. Vòng lặp dừng khi lo > hi, mà mỗi bước chỉ dịch một đầu đúng một đơn vị qua mid, nên lúc dừng hi luôn bằng lo trừ 1: ở đây 18 và 17. Ghép hai câu lại thì lo chính là ranh giới. Vậy lời đáp là lo, không phải hi: lấy hi là lấy giá trị cuối cùng đã bị chứng minh là không được.
duocKhong(18) đúng và duocKhong(17) sai (số nhóm cần dùng là 3 thay vì 2). Đúng một chỗ đổi từ không sang có, và tìm nhị phân đã chỉ vào đúng chỗ đó.5 · Hai đường tới cùng một con số
| cách tìm | đáp án | số lần gọi duocKhong |
|---|---|---|
| tìm nhị phân trên khoảng | 18 | 5 |
| quét vét cạn mọi giá trị trong khoảng | 18 | 23 |
duocKhong 5 lần thay vì 23 lần. Đó là toàn bộ giá trị của nó: cùng câu trả lời, ít câu hỏi hơn rất nhiều.6 · Khoảng phình ra thì tốn thêm mấy vòng
| khoảng rộng gấp | số giá trị ứng viên | trần số vòng lặp | thêm bao nhiêu vòng |
|---|---|---|---|
| như đang có | 23 | 5 | mốc so |
| 10 lần | 230 | 8 | +3 |
| 100 lần | 2.300 | 12 | +7 |
| 1.000 lần | 23.000 | 15 | +10 |
| 1.000.000 lần | 23.000.000 | 25 | +20 |
log₂. Nhân lên 1.000 lần thì tăng 9 hoặc 10 vòng, tuỳ chỗ rơi. Đây là lý do người ta dám cho khoảng tìm rộng thênh thang: nới từ 23 lên 23.000 giá trị chỉ đắt thêm 10 vòng. Chọn khoảng chật để tiết kiệm là tối ưu sai chỗ, mà lại còn dễ cắt mất đáp án.- Nó đếm số lần gọi vị từ, nó không đo giây. Mỗi lần gọi ở đây quét cả danh sách dữ liệu, nên một vòng lặp tốn công tỉ lệ với số phần tử, không phải một hằng số. Chi phí thật của cả thuật toán là
số vòng × giá một lần gọi vị từ, và cột thứ hai đó là chỗ tiền thật nằm. - Bài chia nhóm ở đây chỉ xét các nhóm liền kề. Cho phép xếp tuỳ ý thì đó là bài toán khác hẳn, thuộc loại NP-đầy đủ, và cách xếp tham lam trong sim không còn tối ưu nữa.
- Bài nhịp làm việc giả định mỗi ngày chỉ làm một hạng mục, làm dư trong ngày thì bỏ. Đổi giả định đó, chẳng hạn cho phép làm gộp hai hạng mục trong một ngày, thì
cost(x)thành công thức khác và đáp án dịch theo. - Bốn bộ dữ liệu đều là số minh hoạ do bài tự đặt, chọn vì tính được bằng tay. Cổng kiểm số canh phép tính, nó không canh và không thể canh chuyện dữ liệu ngoài đời có giống thế hay không.
- Cột quét vét cạn chỉ đi được vì khoảng ở đây nhỏ. Đúng những bài mà tìm nhị phân đáng giá là những bài khoảng tìm quá rộng để vét cạn, tức bạn không có sẵn đường thứ hai để đối chiếu. Ở đó thì cách duy nhất còn lại là chứng minh vị từ đơn điệu bằng lập luận, trước khi viết vòng lặp.
Ở trạng thái mở đầu, sim đang nói gì
Dữ liệu vào là 5 số: 7, 2, 5, 10, 8. Câu hỏi: chia dãy đó thành nhiều nhất 2 nhóm liền kề, thì nhóm nặng nhất nhẹ nhất có thể là bao nhiêu.
Đáp án là 18, và cách chia là [7, 2, 5] nặng 14 cùng [10, 8] nặng 18. Bạn thử tay cũng ra: mọi cách chia thành 2 nhóm liền kề khác đều có một nhóm nặng hơn 18.
Đây là chỗ phải nhìn cho rõ, vì nó là toàn bộ ý của bài: 18 không phải một phần tử nào trong dữ liệu vào. Nó không phải 7, 2, 5, 10 hay 8. Nó là một con số mới, và không có mảng nào chứa nó để mà tra. Cái tìm nhị phân đang chia đôi là khoảng các giá trị có thể, chứ không phải một dãy phần tử.
Khoảng đó là [10, 32], tức 23 giá trị ứng viên, và nó suy ra thẳng từ dữ liệu: nhóm nào cũng phải chứa nổi phần tử lớn nhất nên đáp án không thể nhỏ hơn 10, còn một nhóm duy nhất chứa cả dãy thì nặng đúng tổng nên đáp án không thể lớn hơn 32.
Vị từ là: với trần x cho mỗi nhóm thì cần bao nhiêu nhóm, và số đó có nằm trong ngân sách 2 nhóm hay không. Tìm nhị phân đi thế này, bạn đối chiếu với bảng các vòng lặp trong sim:
| vòng | khoảng đang xét | còn lại | hỏi x | số nhóm cần | duocKhong(x) | khoảng mới |
|---|---|---|---|---|---|---|
| 1 | [10, 32] | 23 | 21 | 2 | được | [10, 20] |
| 2 | [10, 20] | 11 | 15 | 3 | không | [16, 20] |
| 3 | [16, 20] | 5 | 18 | 2 | được | [16, 17] |
| 4 | [16, 17] | 2 | 16 | 3 | không | [17, 17] |
| 5 | [17, 17] | 1 | 17 | 3 | không | [18, 17], rỗng |
Số ứng viên đi 23 → 11 → 5 → 2 → 1 → 0. Năm vòng lặp, mỗi vòng đúng một câu hỏi có hay không, và xong.
Chú ý cột thứ năm. Nó chỉ đổi giá trị đúng một lần, ở giữa 17 và 18: cần 3 nhóm tại 17 và 2 nhóm tại 18. Cái chỗ đổi đó là đáp án. Toàn bộ việc còn lại chỉ là tìm nó cho nhanh.
Điều kiện dùng được là tính đơn điệu
Cái làm cho năm vòng lặp trên có nghĩa không phải là dữ liệu đã sắp. Dữ liệu vào là 7, 2, 5, 10, 8, chưa sắp gì cả, và không cần sắp: đổi thứ tự các phần tử thì đây là một bài toán khác, vì các nhóm phải liền kề.
Cái làm cho nó có nghĩa là: số nhóm cần dùng không bao giờ tăng khi trần x tăng. Nới trần ra thì chỉ có thể cần ít nhóm hơn hoặc bằng, không cách nào cần nhiều hơn. Từ đó suy ra vị từ duocKhong(x), viết là số nhóm ≤ ngân sách, một khi đã đúng thì đúng mãi. Đó chính là tính đơn điệu, và đó là toàn bộ điều kiện.
Muốn thấy điều kiện này quan trọng tới đâu thì phá nó. Bấm preset vị từ không đơn điệu: tám vật cùng nặng 1, chia thành 3 nhóm, và vị từ bị viết thành số nhóm = ngân sách thay vì số nhóm ≤ ngân sách. Đây là một lỗi thật, người ta viết vậy vì nghĩ "đề bài nói chia thành 3 nhóm, nên tôi phải kiểm là đúng 3 nhóm".
Với tám vật nặng 1 và trần x thì cần ⌈8/x⌉ nhóm. Vậy số nhóm = 3 chỉ đúng tại đúng một điểm là x = 3: tại x = 4 thì chỉ cần 2 nhóm, mà 2 không bằng 3 nên vị từ nói không được. Vị từ đã đúng tại 3 rồi lại sai tại 4, tức không đơn điệu, và sim gọi thẳng ra chỗ đổ vỡ đó.
Hậu quả: trên khoảng [1, 8] tìm nhị phân hỏi lần lượt 4, 6, 7, 8, cả bốn đều nhận câu trả lời không, nên nó kết luận không có đáp án nào. Quét vét cạn cả 8 giá trị thì thấy ngay là có, đáp án là 3. Tìm nhị phân không sai ở cài đặt: nó sai vì bị đem dùng ở chỗ không được dùng. Khi nó thăm một điểm sai, nó suy ra "vậy phần đúng nằm bên phải", mà suy luận đó chỉ hợp lệ khi vị từ đơn điệu.
Và đây là chỗ khó chịu nhất. Bật cùng công tắc đó ở trạng thái mở đầu thì đáp án vẫn ra 18, đúng như cũ, dù vị từ đã không còn đơn điệu (nó đúng tới 31 rồi sai tại 32, vì một nhóm duy nhất là 1 nhóm chứ không phải 2). Cổng kiểm số của bài đã quét 400 cấu hình với vị từ hỏng, và đo được 49 cấu hình cho đáp án lệch. Nghĩa là 351 cấu hình còn lại vẫn cho đáp án đúng bằng một vị từ sai. Nên bạn không thể thử vài ca rồi kết luận là ổn: cách duy nhất là chứng minh tính đơn điệu trước khi viết vòng lặp.
Bài toán thứ hai: cùng bộ khung, đổi cost(x)
Bấm preset nhịp làm việc. Có 4 hạng mục cỡ 3, 6, 7, 11 đơn vị, mỗi ngày chỉ làm một hạng mục và làm được x đơn vị, cần xong cả danh sách trong 8 ngày. Hỏi nhịp x nhỏ nhất là bao nhiêu.
Khung y nguyên, chỉ đổi hàm cost(x): số ngày cần dùng là tổng của ⌈hạng mục / x⌉. Khoảng an toàn là [1, 11], tức 11 giá trị: nhịp 1 thì kiểu gì cũng xong, còn nhịp bằng hạng mục lớn nhất thì mỗi hạng mục xong trong một ngày. Đáp án là 4, tìm được sau 3 vòng lặp:
| vòng | hỏi x | số ngày cần | duocKhong(x) |
|---|---|---|---|
| 1 | 6 | 6 | được |
| 2 | 3 | 10 | không |
| 3 | 4 | 8 | được |
Tại nhịp 4 thì bốn hạng mục tốn 1, 2, 2, 3 ngày, cộng lại đúng 8, vừa khít hạn. Tại nhịp 3 thì tốn 1, 2, 3, 4 ngày, tổng 10, quá hạn 2 ngày. Vậy 4 là chỗ đổi.
Một chi tiết đáng nhớ ở bài này: nhịp 5 cũng tốn đúng 8 ngày, không nhanh hơn nhịp 4 chút nào, vì phép làm tròn lên ăn hết phần dư. Hàm cost(x) chỉ cần không tăng, nó không cần giảm ở mọi bước. Tìm nhị phân vẫn chạy đúng trên những đoạn phẳng như vậy, và chính vì có đoạn phẳng nên đáp án là 4 chứ không phải 5.
Có một lưu ý về đề bài, vì bản đặc tả giao cho bài này viết nhầm chiều. Nếu câu hỏi là "mỗi ngày làm được x đơn vị thì tốn ít nhất mấy ngày" thì không cần tìm nhị phân gì cả: đó là một phép cộng các phép chia lấy trần, tính một lần là ra, đúng bằng cột thứ ba của bảng trên. Chiều tìm được là chiều ngược lại: cho hạn rồi tìm nhịp. Nói chung, khi bạn thấy một bài "tìm nhị phân trên đáp án", hãy kiểm xem chiều nào là chiều tính trực tiếp được: chiều đó là cost(x), còn chiều kia mới là chiều đi tìm.
Ranh giới: trả về lo hay hi
Đây là chỗ giết người, và cũng là chỗ dễ vá bừa nhất. Nhìn lại bảng đầu bài: lúc vòng lặp dừng, lo đang bằng 18 và hi đang bằng 17. Trả về lo thì đúng. Trả về hi thì ra 17, mà 17 cần tới 3 nhóm, tức là một giá trị đã bị chính vòng lặp chứng minh là không được.
Vì sao là lo? Vì vòng lặp mang theo một bất biến, và bất biến đó là toàn bộ lý lẽ:
- mọi
xnhỏ hơnlođều đã bị chứng minh là không được; - mọi
xlớn hơnhiđều đã bị chứng minh là được.
Kiểm hai câu đó ở lúc bắt đầu: cả hai đều đúng một cách rỗng, vì chưa có x nào nằm ngoài khoảng ban đầu để mà nói. Rồi kiểm mỗi vòng. Nếu duocKhong(mid) đúng, ta đặt hi = mid - 1, và khi đó "mọi x lớn hơn hi" chính là "mọi x từ mid trở lên": đúng, vì mid được và tính đơn điệu kéo theo mọi giá trị lớn hơn cũng được. Nếu duocKhong(mid) sai, ta đặt lo = mid + 1, và "mọi x nhỏ hơn lo" chính là "mọi x tới mid": cũng đúng, vì mid không được thì mọi giá trị nhỏ hơn càng không được.
Vòng lặp chỉ dừng khi lo vượt hi. Mà mỗi bước chỉ dịch một đầu qua mid đúng một đơn vị, nên lúc dừng hi luôn bằng lo trừ 1, không bao giờ cách xa hơn. Ghép với bất biến: mọi giá trị dưới lo đều không được, mọi giá trị từ lo trở lên đều được. Vậy lo chính là ranh giới, và nó là đáp án. Cổng kiểm số của bài khoá ba mệnh đề này, và khoá chúng trên hai cỡ lưới khác nhau vì chúng đòi hỏi khác nhau. Mệnh đề hi luôn bằng lo trừ 1 chỉ là chuyện vòng lặp thoát ra sao, nên nó đúng kể cả khi vị từ hỏng và cổng khoá nó trên cả 800 cấu hình của lưới. Còn hai mệnh đề kia, đáp án luôn bằng lo và không có ngoại lệ nào dưới lo mà lại được, chỉ có nghĩa khi vị từ đơn điệu, nên cổng khoá chúng trên 400 cấu hình chạy vị từ đúng, và mệnh đề thứ ba thì nó đi kiểm từng giá trị một.
Từ đó ra luôn cách đọc ca không có đáp án: nếu không giá trị nào trong khoảng làm được thì lo bò tới hi + 1. Trong preset vị từ hỏng ở trên, khoảng là [1, 8] và lo dừng ở 9. Con số 9 đó không phải một đáp án, nó là dấu hiệu "không có". Đọc nhầm nó thành đáp án là một trong những cách hỏng lặng lẽ nhất của kiểu tìm này.
Khoảng tìm phải chứa đáp án, và không ai nhắc bạn
Bấm preset khoảng tìm không chứa đáp án. Vẫn dữ liệu 7, 2, 5, 10, 8 và ngân sách 2 nhóm, nhưng khoảng tìm là [20, 32] trong khi đáp án thật là 18. Tìm nhị phân trả về 20, sau 3 vòng, không kèm một lời cảnh báo nào. Quét vét cạn cũng trả về 20. Cả hai đều không sai: chúng trả lời đúng câu "giá trị nhỏ nhất trong khoảng này mà làm được", chỉ có điều đó không phải câu bạn muốn hỏi.
Nên chọn lo và hi là một bước phải làm bằng lập luận, không phải bằng cảm giác. Cách an toàn là suy từ dữ liệu, và với hai bài trên thì nó rất dễ:
- chia nhóm:
lolà phần tử lớn nhất (nhóm nào cũng phải chứa nổi nó),hilà tổng cả dãy (một nhóm chứa hết); - nhịp làm việc:
lolà 1 (nhịp 1 thì kiểu gì cũng xong, chỉ là lâu),hilà hạng mục lớn nhất (mỗi hạng mục xong trong một ngày, không cần nhanh hơn).
Sim hiện khoảng an toàn ngay dưới phần dữ liệu, và nó cảnh báo khi khoảng bạn đang tìm không chứa đáp án. Ngoài đời thì không có ai cảnh báo, nên hãy tự chứng minh: duocKhong(hi) phải đúng, còn duocKhong(lo - 1) phải sai hoặc lo phải là giá trị nhỏ nhất có nghĩa.
Số vòng lặp, và một chỗ đặc tả của bài này bị sai
Số vòng lặp trên một khoảng có n giá trị ứng viên là nhiều nhất ⌊log₂ n⌋ + 1. Với khoảng mở đầu, n = 23 nên trần là 4 + 1 = 5, và lần chạy trên tiêu đúng 5.
Con số đó đo được, và cổng kiểm số của bài đo thật chứ không tin công thức: với mỗi n từ 1 tới 300, nó thử mọi vị trí ranh giới có thể, chạy tìm nhị phân, rồi lấy số vòng lớn nhất. Kết quả khớp ⌊log₂ n⌋ + 1 ở cả 300 giá trị.
Bản đặc tả giao cho bài này ghi công thức là ⌈log₂ n⌉. Đo ra thì công thức đó sai, và sai theo một kiểu rất khó bắt: nó đúng ở hầu hết mọi n, chỉ thiếu đúng 1 tại các luỹ thừa của 2. Phản ví dụ nhỏ và cụ thể: khoảng [1, 8] có 8 giá trị, ⌈log₂ 8⌉ = 3, nhưng nếu không giá trị nào làm được thì tìm nhị phân hỏi lần lượt 4, 6, 7, 8, tức 4 vòng. Trong 300 giá trị n đầu tiên, công thức tiện tay kia lệch ở đúng 9 chỗ: 1, 2, 4, 8, 16, 32, 64, 128, 256, và chỗ nào cũng lệch đúng 1. Cách viết đúng là ⌊log₂ n⌋ + 1, hoặc ⌈log₂(n + 1)⌉ nếu bạn thích dạng trần; hai cách đó là cùng một số nguyên, và cổng đã kiểm trên 200.000 giá trị.
Điều đáng nhớ hơn là trần này lớn chậm tới mức nào. Bảng cuối trong sim tính sẵn cho khoảng đang xem:
| khoảng rộng gấp | số giá trị ứng viên | trần số vòng lặp | thêm |
|---|---|---|---|
| như đang có | 23 | 5 | |
| 10 lần | 230 | 8 | 3 |
| 100 lần | 2.300 | 12 | 7 |
| 1.000 lần | 23.000 | 15 | 10 |
| 1.000.000 lần | 23.000.000 | 25 | 20 |
Nới khoảng tìm gấp nghìn lần chỉ tốn thêm 10 vòng. Chính xác hơn: nhân khoảng lên 1.024 lần thì trần tăng đúng 10, vì 1.024 là 2 mũ 10 và trần là một hàm sàn của log₂; nhân lên 1.000 lần thì tăng 9 hoặc 10 tuỳ chỗ rơi, và cổng đã quét để chắc rằng không bao giờ ra con số khác. Đây là lý do thực dụng nhất của cả bài: đừng bóp khoảng tìm cho chật để tiết kiệm. Tiết kiệm được vài vòng lặp, mà đổi lấy nguy cơ cắt mất đáp án, thì đó là tối ưu sai chỗ. Cứ lấy khoảng rộng rãi mà chắc chắn chứa đáp án.
Sim này đếm gì và không đếm gì
Phải nói thẳng trước khi bạn mang mấy con số này đi đâu.
Sim đếm số lần gọi vị từ, nó không đo giây. Và ở đây khác biệt đó lớn hơn ở bài trước, vì một lần gọi vị từ không hề rẻ: nó quét cả danh sách dữ liệu để tính cost(x). Chi phí thật là số vòng × giá một lần gọi, tức với m phần tử dữ liệu và khoảng rộng n thì cỡ m log n. Nói "chỉ tốn 5 vòng" mà bỏ quên cột thứ hai là nói một nửa.
Bài chia nhóm ở đây chỉ xét các nhóm liền kề. Cho phép gom tuỳ ý phần tử nào với phần tử nào thì đó là bài toán khác hẳn, thuộc loại NP-đầy đủ, và cách xếp tham lam trong sim không còn tối ưu nữa. Cổng kiểm số đã đối chiếu cách xếp tham lam với một phép quy hoạch động và một phép vét cạn mọi chỗ cắt, nhưng cả ba đều là bài liền kề.
Bài nhịp làm việc dựa trên một giả định. Mỗi ngày chỉ làm một hạng mục, làm dư trong ngày thì bỏ. Đó là lý do có phép lấy trần. Cho phép làm gộp hai hạng mục trong một ngày thì cost(x) thành công thức khác và đáp án dịch theo. Giả định là quy ước của đề bài, không phải chân lý.
Cột quét vét cạn chỉ đi được vì khoảng ở đây nhỏ. Đúng những bài mà tìm nhị phân thật sự đáng giá là những bài khoảng tìm quá rộng để vét cạn, tức bạn không có sẵn đường thứ hai để đối chiếu. Ở đó thì chứng minh tính đơn điệu bằng lập luận là việc bắt buộc, không phải việc tuỳ chọn.
Bốn bộ dữ liệu đều là số minh hoạ do bài tự đặt, chọn vì tính được bằng tay, không phải số đo từ hệ thống nào.
Muốn xem lại tìm nhị phân trên mảng, kể cả vị trí chèn và bẫy tràn số của (low + high) / 2, đọc tìm tuyến tính so với tìm nhị phân. Muốn xem log n nằm ở đâu trong bảng xếp hạng các bậc tăng, đọc bậc tăng.
Khi cái cần tìm là một con số chứ không phải một phần tử của mảng, tìm nhị phân vẫn dùng được, và điều kiện không phải "mảng đã sắp" mà là vị từ duocKhong(x) đơn điệu: đúng rồi thì đúng mãi. Cách dựng là tìm một hàm cost(x) tính trực tiếp được và không tăng, rồi so với ngân sách bằng dấu ≤. Viết dấu bằng thay vì ≤ là phá tính đơn điệu, và nó vẫn cho đáp án đúng ở 351 trong 400 cấu hình mà cổng quét, nên thử vài ca không cứu được bạn: phải chứng minh. Lúc vòng lặp dừng thì hi luôn bằng lo trừ 1, và đáp án là lo, vì bất biến nói mọi giá trị dưới lo đã bị chứng minh là không được; lo bằng hi + 1 nghĩa là không có đáp án, đừng đọc nó thành một con số. Khoảng [lo, hi] phải chứa đáp án, mà không ai báo lỗi nếu nó không chứa, nên hãy suy khoảng từ dữ liệu. Và cứ lấy khoảng rộng: trần là ⌊log₂ n⌋ + 1, nên nới khoảng gấp nghìn lần chỉ tốn thêm 10 vòng.
- 1Bạn muốn dùng tìm nhị phân để tìm một con số đáp án. Điều kiện bắt buộc là gì?
- 2Vòng lặp dừng với lo = 18 và hi = 17. Đáp án là gì?
- 3Khoảng tìm là [1, 8], tức 8 giá trị ứng viên. Nhiều nhất bao nhiêu vòng lặp?