Thi đấu lập trình
Đề bài
Bài 3. (4 điểm): THI ĐẤU LẬP TRÌNH
Để chuẩn bị cho kì thi chọn học sinh giỏi cấp tỉnh, Sở Giáo dục tổ chức $N$ lượt thi đấu lập trình đối kháng giữa hai đội A và B. Có $N$ học sinh lần lượt vào tham gia thi đấu, học sinh thứ $i$ $(i = 1..N)$ có thời gian đã học lập trình là $X[i]$ và có chỉ số thông minh là $Y[i]$. Lần lượt từng học sinh từ $1$ đến $N$ sẽ tham gia vào các cuộc thi, mỗi khi đến lượt học sinh thứ $i$ $(i = 1..N)$, ban tổ chức sẽ tổ chức một lượt thi cho tất cả các học sinh đánh số từ $1$ tới $i$, họ sẽ xếp lại đội hình cho cả 2 đội, sao cho đội A gồm $[i/2]$ học sinh có thời gian học lập trình nhiều hơn và số còn lại ở bên đội B, nếu $i$ lẻ thì đội B sẽ có nhiều hơn 1 người (với $i = 1$ thì đội A có 0 học sinh, đội B có 1 học sinh). Ban tổ chức muốn biết sau mỗi lượt chia đội thi đấu như vậy thì độ chênh lệch của tổng chỉ số thông minh giữa 2 đội là bao nhiêu.
Yêu cầu: Giúp ban tổ chức tính độ chênh lệch như mô tả trên sau mỗi lượt thi đấu.
Dữ liệu: vào từ file văn bản THIDAU.INP gồm:
- Dòng đầu chứa số $N$ là số học sinh $(N \le 10^5)$;
- Dòng thứ $i$ trong $N$ dòng tiếp theo ghi hai số nguyên dương $X[i]$ và $Y[i]$ (các số $X[i]$ khác nhau đôi một, $X[i] \le 10^9$, $Y[i] \le 1000$).
Kết quả: ghi ra file THIDAU.OUT gồm $N$ dòng, dòng thứ $i$ $(i = 1..N)$ là độ chênh lệch tìm được sau lượt đấu thứ $i$.
Ràng buộc:
- Có 2 điểm có $N \le 100$;
- 2 điểm còn lại không còn ràng buộc gì thêm.
Lưu ý: $[i/2]$ là phần nguyên của $i/2$. Trên CLUE OJ bài này đọc/ghi file THIDAU.INP / THIDAU.OUT đúng như đề; còn trên Codeforces thì nhập xuất chuẩn. Code bên dưới dùng if(fopen(...)) nên nộp ở đâu cũng chạy được.
5
2 3
1 7
5 5
3 1
8 153
4
5
4
9Giải thích ví dụ:
- Lượt 1: chỉ có bạn $(X, Y) = (2, 3)$ → A rỗng, B = $\{3\}$ → chênh lệch $3$.
- Lượt 2: $X = 2$ lớn hơn $X = 1$ → A = $\{(2,3)\}$, B = $\{(1,7)\}$ → $|3 - 7| = 4$.
- Lượt 3: A gồm $[3/2] = 1$ bạn có $X$ lớn nhất là $(5,5)$, B = $\{(2,3), (1,7)\}$ → $|5 - 10| = 5$.
- Lượt 4: A = $\{(5,5), (3,1)\}$, B = $\{(2,3), (1,7)\}$ → $|6 - 10| = 4$.
- Lượt 5: A = $\{(8,15), (5,5)\}$, B = $\{(3,1), (2,3), (1,7)\}$ → $|20 - 11| = 9$.
Lời mở đầu
Bài này là dạng kinh điển "duy trì $k$ phần tử lớn nhất khi phần tử được thêm vào liên tục" (họ hàng gần với bài tìm trung vị động). Sau mỗi lượt ta phải biết ai đang ở nhóm $[i/2]$ người có $X$ lớn nhất. Sắp xếp lại từ đầu mỗi lượt thì quá chậm; cách hay là giữ hai tập A, B luôn "tách đôi" theo $X$ và chỉ chuyển vài người qua lại mỗi lượt. Mình sẽ cài bằng set (đúng chủ đề Map/Set) rồi bằng priority_queue.
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 OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ 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ì?
| Test | N | X lớn nhất | Y lớn nhất | Đáp án lớn nhất |
|---|---|---|---|---|
| 1 – 30 | 5 … 10 | 30 | 985 | 1.683 |
| 31 – 50 | 100 | 999.056.131 | 998 | 6.820 |
| 51 – 100 | 100.000 | 999.997.752 | 999 | 219.067 |
- 30 test đầu rất nhỏ ($N \le 10$), 20 test tiếp theo $N = 100$, 50 test cuối $N = 10^5$ – đúng với 2 subtask của đề (mỗi subtask 50% số test).
- Mọi test đều có các $X$ khác nhau đôi một (mình đã kiểm tra), nên dùng
set<pair<X, Y>>không lo mất phần tử trùng. - Tổng $Y$ tối đa $10^5 \cdot 1000 = 10^8$ nên kiểu
intlà đủ.
| Subtask | Điều kiện | Các test | Cách 1 sắp xếp lại | Cách 2 hai set | Cách 3 hai heap |
|---|---|---|---|---|---|
| 1 (2 điểm) | $N \le 100$ | 1 – 50 | 50/50 | 50/50 | 50/50 |
| 2 (2 điểm) | $N \le 10^5$ | 51 – 100 | 0/50 | 50/50 | 50/50 |
Ý tưởngHai tập A, B và một "đường cắt"
Hãy tưởng tượng xếp $i$ học sinh theo $X$ giảm dần trên một hàng ngang. Đội A là $[i/2]$ người đầu hàng, đội B là phần còn lại – giữa hai đội có một đường cắt. Khi thêm một người mới:
- Người mới đứng vào đúng chỗ của mình trong hàng: nếu $X$ của bạn ấy lớn hơn người yếu nhất của A thì bạn ấy thuộc phía A, ngược lại thuộc phía B.
- Kích thước A phải là $[i/2]$, nên đường cắt có thể phải dịch đi một bước: A thừa người thì đẩy người yếu nhất của A sang B; A thiếu người thì kéo người mạnh nhất của B sang A.
- Giữ sẵn tổng $Y$ của từng đội ($s_A$, $s_B$) và cập nhật mỗi khi có người chuyển → đáp án là $|s_A - s_B|$.
set (phần tử đầu begin() và cuối prev(end())) hoặc hai priority_queue. Mỗi lượt chỉ có $O(1)$ thao tác, mỗi thao tác $O(\log N)$.Em nhập danh sách học sinh rồi bấm Tiếp để xem đường cắt dịch chuyển qua từng lượt:
Cách 1Sắp xếp lại sau mỗi lượt – O(N² log N)
Làm đúng như đề mô tả: tới lượt $i$, chép $i$ học sinh đầu ra, sắp xếp giảm dần theo $X$, $[i/2]$ người đầu là đội A, còn lại là đội B.
sort(v.rbegin(), v.rend())sắp các cặp(X, Y)giảm dần theoX(các $X$ khác nhau nên không cần quan tâm $Y$).- $j < i/2$ là người thuộc đội A, phép chia nguyên
i / 2của C++ chính là $[i/2]$.
Kết quả chạy thật: bản C++ đúng 50/100 test (quá 1 giây ở các test 51–100), test đúng chạy lâu nhất 0.004s; bản Python đúng 50/100 test (quá thời gian ở các test 51–100), lâu nhất 0.03s. Đúng như dự đoán: qua trọn subtask 1, còn với $N = 10^5$ thì $\sum i \log i$ cỡ $10^{11}$ phép tính – không thể chạy kịp.
Cách 2Hai set – O(N log N)
Cài đặt ý tưởng "đường cắt": A chứa đội A, B chứa đội B, cả hai là set<pair<int, int>> sắp tăng theo $X$.
A.begin()là người có $X$ nhỏ nhất trong A (người yếu nhất đội A);prev(B.end())là người có $X$ lớn nhất trong B.- Người mới vào A nếu $X$ lớn hơn người yếu nhất của A, ngược lại vào B. Khi A đang rỗng ($i = 1$ hoặc $i = 2$) thì cứ cho vào B – vòng
whilephía sau sẽ chỉnh lại. - Hai vòng
whileđưa kích thước A về đúng $[i/2]$. Thật ra mỗi lượt chỉ chạy tối đa 1 lần, nhưng viếtwhilecho an toàn và dễ hiểu. - Khi chuyển người, nhớ cập nhật cả
savàsb. Lưu ý phải đọc*ittrước khierase(it).
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.145s.
Cách 3Hai priority_queue – O(N log N)
Ta chỉ cần lấy "người yếu nhất của A" và "người mạnh nhất của B", không bao giờ xoá ở giữa → hai heap là đủ, và chạy nhanh hơn set. Mẹo gọn: luôn cho người mới vào B, rồi đẩy người mạnh nhất của B lên A; nếu A thừa người thì trả người yếu nhất của A về B.
- Sau khi đẩy người mạnh nhất của B lên A, mọi người trong A đều mạnh hơn mọi người trong B (tính chất "đường cắt" được giữ nguyên).
- Trước lượt $i$, A có $[(i-1)/2]$ người; sau khi kéo 1 người lên thì có $[(i-1)/2] + 1$ người. Nếu $i$ chẵn thì vừa đúng $[i/2]$; nếu $i$ lẻ thì A thừa 1 người → trả về B.
greater<ii>biếnpriority_queuethành heap nhỏ nhất (đỉnh là $X$ nhỏ nhất) cho đội A. Bản Python dùngheapq(heap nhỏ nhất) và lưu $-X$ cho đội B.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.054s; bản Python đúng 100/100 test, lâu nhất 0.47s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất (test đúng) | Ghi chú |
|---|---|---|---|---|
| 1. Sắp xếp lại mỗi lượt | C++ | 50/100 | 0.004s | Quá thời gian ở test 51–100 |
| Python | 50/100 | 0.026s | Quá thời gian ở test 51–100 | |
| 2. Hai set | C++ | 100/100 | 0.145s | Full điểm |
| 3. Hai heap | C++ | 100/100 | 0.054s | Full điểm |
| Python (heapq) | 100/100 | 0.465s | Full điểm |
Nhận xét
Đăng nhận xét