ICPC Asia Hanoi Regional 2024 Writeuptype
status
date
slug
summary
tags
category
icon
password
Đây là một trong những kì thi để đời của mình và anh em trong đội, khi đã vượt mọi kì vọng và được đến quốc đảo Singapore đánh APAC Championship tại NUS. Sau khi quá lâu vẫn không thấy BTC công khai lời giải tất cả các bài ở nguồn nào, mình quyết định viết 1 cái writeup, cũng là để tưởng nhớ và kỉ niệm chiến thắng hào hùng sau bao cố gắng.
A
Đề bài
Có một hòn đảo có thể biểu diễn thành một đa giác đỉnh bất kì không tự cắt, với toạ độ các điểm nguyên. Có truy vấn, mỗi truy vấn gồm 6 số biểu diễn một cơn bão, là một hình tròn có tâm và tâm này sẽ di chuyển theo đường thẳng đến , và trong quá trình di chuyển đó, bán kính của nó sẽ thay đổi đều liên tục từ đến
Với mỗi truy vấn, tính phần diện tích của đảo bị cơn bão quét qua, với sai số tuyệt đối hoặc tương đối không quá .
Giới hạn: .
Lời giải
Một kinh nghiệm thi cử là bài hình sẽ luôn là bài làm sau cùng, hoặc bỏ luôn không nghĩ đến. Hay nói cách khác, cách tốt nhất để làm bài hình là bỏ. Không có đội nào làm được bài này trong kì thi. Tuy nhiên thì khi mình rảnh về thời gian thì có thể làm được hết. Làm xong rồi thì khẳng định được rằng bỏ là đúng, và trong ICPC chẳng có giới hạn kiến thức nên là chuẩn bị hình bao nhiêu cũng là không đủ. Hình là dạng bài khiến ta ảo tưởng nhiều nhất về những gì có thể làm được.
Một thuật toán hình quan trọng sử dụng trong bài toán này là thuật toán cắt đa giác bằng đa giác lồi của Sutherland-Hodgman. Nôm na thì đây là thuật toán cho phép tính phần giao của một đa giác bất kì không tự cắt (chính là đa giác của đề bài cho, sau đây sẽ gọi là
poly) với một đa giác lồi nào đó (sau đây sẽ gọi là clipper).
Chúng ta chia bài toán thành 2 trường hợp lớn, tuỳ vào số tiếp tuyến chung ngoài của 2 hình tròn được cho trong đề bài.
Trường hợp 1: 0 hoặc 1 tiếp tuyến
Trường hợp này xảy ra khi và chỉ khi một hình tròn hoàn toàn nằm trong hình tròn còn lại. Khi này đáp án là diện tích phần giao của đa giác với hình tròn lớn nhất trong hai hình tròn của đề bài. Bài toán này có template hình để giải nên chỉ cần chép lại.
Trường hợp 2: 2 tiếp tuyến
Ta tách phần diện tích được bao phủ bởi cơn bão thành các hình sau:
Trong hình trên, ta đã kẻ 2 tiếp tuyến của hai đường tròn tâm A và B. Đáp án sẽ là tổng diện tích phần giao của hòn đảo với hình thang CDEF và hai hình viên phân còn lại được tạo bởi CF và cung lớn CF, DE và cung nhỏ DE.
Bài toán 1: Tính diện tích giao của hình thang với đa giác
Với bài toán này ta có thể sử dụng thuật toán Sutherland-Hodgman, sử dụng hình thang CDEF để cắt đa giác ban đầu. Các bạn có thể hỏi ChatGPT để sinh cài đặt cho thuật toán này.
Bài toán 2: Tính diện tích giao của hình thang với hai hình viên phân
(WIP)
B
Đề bài
Cho một đồ thị vô hướng đỉnh, khoảng cách giữa 2 đỉnh bất kì là . Chi phí của một đường đi nào đó (không nhất thiết là đường đi đơn) giữa 2 đầu mút là tổng của các cạnh liên tiếp đi qua.
Có cặp đỉnh quan trọng. Mục tiêu là dựng ra một tập các đường đi độc lập nhau, mỗi đường không có quá đỉnh, sao cho với mỗi cặp đỉnh quan trọng đều có ít nhất một đường trong tập đi qua nó. In cách dựng có tổng chi phí bé nhất, cùng thứ tự các đỉnh của mỗi đường đi.
Giới hạn:
Lời giải
Bài toán này là ghép cơ học của 3 bài toán DP bitmask, và cả 3 bài đều phải lưu truy vết. Truy vết đơn giản là xác định những thứ cần phải lưu để bạn biết là phương án tối ưu đã được dựng như thế nào khi tính DP, và code thì cũng na ná nhau.
- Tính chi phí nhỏ nhất
TSP[S][v]để đi qua toàn bộ các đỉnh biểu diễn bởi bitmaskSvà kết thúc tại đỉnhvthuộcS. Đây là bài toán TSP truyền thống với độ phức tạp .
- DP SOS các cặp đỉnh quan trọng. Với mỗi mask cặp
pmthoả điều kiện không có quá đỉnh, ta cần tính một đường đi có chi phí ít nhất mà phủ hết được các cặp trongpm. Gọi giá trị này làmin_cost[pm]. Lưu ý rằng, một đường đi không nhất thiết chỉ đi qua chính xác các đỉnh quan trọng, mà có thể thêm các đỉnh khác làm trung chuyển để giảm tổng chi phí. Phần này tối ưu nhất là cài được trong .
- Sau khi tính được hết
min_cost, ta sẽ tính đượcdp_cover[pm]là chi phí ít nhất để xây một số tuyến đường phủ qua tất cá các cặp trongpm. Độ phức tạp có thể là sử dụng SOS hoặc bằng duyệt submask cũng chấp nhận được. Đáp án tối ưu làdp_cover[(1 << m) - 1]
- Truy vết các đỉnh của mỗi đường đi bằng thông tin truy vết của 3 bài toán ở trên.
Bài này có tối đa 5 test,trung bình mỗi test không quá 1 giây, nên phải code khéo và đừng làm nhiều thao tác thừa.
C
Đề bài
Có lớp, mỗi lớp có học sinh phân biệt xếp thành đội hình . Đếm số cấu hình mà không có 2 học sinh cùng lớp đứng cùng cột. Giải test.
Giới hạn: .
Lời giải
Nếu chỉ xét lớp, thì số cách xếp thoả mãn không có 2 lớp chung cột là . Với mỗi cách xếp trong đó, từng mỗi lớp trong lớp ta có cách điền thứ tự học sinh nên sẽ sinh ra cấu hình thoả mãn đề bài. Do đó đáp số của bài toán cho mỗi test là .
Ta tính trước giai thừa đến giới hạn của đề và mỗi test ta có thể tính kết quả trong , nên độ phức tạp cuối cùng là .
D
Đề bài
Một hoán vị đúng là một dãy chứa đủ số từ đến theo thứ tự bất kì. Với một hoán vị từ đến , gọi là số đoạn con của mà cũng là hoán vị đúng. là hoán vị đặc biệt nếu nó có lớn nhất và có thể có nhiều hoán vị như vậy.
Cho test, mỗi test gồm 2 số . Dựng hoán vị đặc biệt có phần tử và có thứ tự từ điển thứ trong tập các hoán vị đặc biệt.
Giới hạn: .
Lời giải
Để đơn giản tính toán ta coi thứ tự từ điển được đánh số từ .
Hiển nhiên ta có . Ta có thể dựng hoán vị thoả mãn bằng quy nạp.
Giả sử ta đã dựng được hoán vị đặc biệt có phần tử, thì bằng việc đặt số nằm đầu hoặc đuôi của thì ta sẽ có hoán vị đặc biệt phần tử. Theo đó ta cũng chứng minh được số hoán vị đặc biệt có phần tử là , vì với việc cố định số trước, phần tử còn lại có cách điền, hoặc đầu hoặc đuôi.
Khi đã dựng được phần tử, có thể thấy nếu ta đặt tiếp lên đầu thì sẽ làm tăng thứ tự từ điển của hoán vị thêm , còn nếu đặt tiếp ở đuôi thì thứ tự từ điển không tăng. Từ đó ta có phương pháp giải sử dụng hàng đợi 2 đầu (deque):
Độ phức tạp toàn bài là .
E
Đề bài
Bash và Chikapu chơi một trò chơi với một dải băng có ô như sau, Bash đi trước:
- Cả hai thống nhất xâu không có 3 kí tự liên tiếp giống nhau, và xâu , đều là chữ cái Latin viết thường.
- Đến lượt, người chơi sẽ viết một kí tự có trong vào một ô trống.
- Nếu đến lúc nào đó, xâu xuất hiện trong một đoạn con liên tiếp, thì người vừa chơi sẽ thắng.
- Nếu không ai thắng thì kết quả là hoà.
In ra kết quả của trò chơi biết rằng cả hai chơi tối ưu.
Giới hạn:
Lời giải
Đây là một bài game rất khó và không có ai giải được trọn vẹn trong kì thi. Page Code cùng RR đã đăng lời giải của bài này khá chi tiết rồi nên mình sẽ không viết lại nữa.
F
Đề bài
Cho và một xâu có thể nhận một trong các giá trị: $N$,
fizz, buzz hoặc fizzbuzz. Tìm 2 số thoả mãn sao cho bài toán dãy FizzBuzz với đầu vào là có phần tử thứ là đúng giá trị của xâu . Nếu không có thì in ra -1 -1.Giới hạn: .
Lời giải
Bài rất đơn giản, thuần xét trường hợp và cũng dễ câu penalty của các đội. Sau đây mình xin trình bày cách xét trường hợp đơn giản nhất:
G
Đề bài
Cho một mảng gồm số. Bỏ đi một số trong dãy sao cho của dãy là nhỏ nhất.
Lời giải
Với thì đáp án là . Còn lại, sắp xếp dãy rồi in ra .
H
Đề bài
A muốn gửi B một thông điệp bí mật, là một xâu nhị phân
s độ dài n bằng cách sau:- A chọn trước modulo
m >= 3(không nhất thiết là số nguyên tố).
- A tính mảng hash:
hash[0] = 0, hash[i] = (2 * hash[i - 1] + s[i]) % m
- Từ mảng
hashở trên, A dựng xâukeycó các kí tự<, =, >với ý nghĩa:key[i] = "<"nếu tương ứnghash[i - 1] < hash[i]và tương tự. Xâukeynày tính chỉ số từ 1.
B chỉ nhận được
n, m, key và không biết gì về s. Mục tiêu là dựng lại những kí tự chắc chắn của s thành xâu ans. Hay nói cách khác, với tập S gồm tất cả s thoả mãn key, nếu s[i] = "0" với mọi ithì ans[i] = "0", tương tự với s[i] = "1". Nếu không như vậy thì ans[i] = "?". Nếu xâu ans toàn là "?" thì in ra impossible.Giới hạn: .
Lời giải
WIP
I
Đề bài
Bạn có đồng xu, đồng xu thứ có mệnh giá là . Các mẫu số đều là các số nguyên tố phân biệt.
Đếm số giá trị có thể giao dịch bởi các đồng xu ở trên mà người bán bắt buộc phải trả lại tiền thừa theo modulo . Nếu có vô số giá trị như vậy thì in ra Infinity.
Giới hạn: .
Lời giải
Mình đã được nghe 2 cách giải cho bài toán này, một cách sử dụng toán học thuần tuý và thường chỉ có ai học nhiều toán (IMO chẳng hạn, hoặc ChatGPT) mới biết, và một cách dùng FFT mà mình không biết nhưng bạn mình mò ra được công thức tổng quát trước xong rồi FFT công thức đó. Dưới đây mình sẽ trình bày cách dùng toán.
Đặt . Ta sẽ giải bài toán ngược: tính số giá trị có thể trả bằng các mệnh giá ở trên mà không phải trả lại tiền thừa.
Điều này tương đương với tìm số lượng sao cho tồn tại tổ hợp tuyến tính mà các hệ số . Tập các số như vậy tạo thành một Semigroup số học - Wikipedia sinh bởi các .
Trong lý thuyết này, nếu (đúng với mọi test vì các nguyên tố khác nhau), thì:
- Tập hợp này có hữu hạn số lượng giá trị không biểu diễn được (gọi là gaps).
- Số lượng gaps được gọi là genus và có công thức như sau:
ở đây còn gọi là số Frobenius của semigroup.
Độ phức tạp cuối cùng là .
J
Đề bài
Cho một đồ thị vô hướng đỉnh cạnh, mỗi cạnh có trọng số . Ta cần giao hàng theo lịch trình là một hoán vị từ đến . Do đó có chặng giao hàng, chặng thứ là một đường đi đơn từ đến .
Chi phí của một chặng là trọng số cạnh lớn nhất xuất hiện trên chặng đó, và chi phí của lịch trình là tổng chi phí của chặng. Chi phí của lịch trình càng nhỏ thì càng tối ưu.
Tìm ra một lịch trình, sao cho chi phí tối ưu của lịch trình là lớn nhất có thể.
Lời giải
Đây là bài mà mình đã đọc sai đề (do nhầm lẫn về minimax) trong kì thi và dẫn đến mất thời gian của cả đội, may mắn là sai lầm này đã không tước đi tấm vé dự APAC Championship của đội mình, khi mà kết quả cuối cùng, mình với đội đứng sau cùng trường kém nhau khoảng 200 penalty.
Anh Hạnh cũng đã chữa bài này rất cụ thể trên kênh YouTube của anh, nên mình sẽ không viết lại lời giải nữa. Còn về kĩ thuật được sử dụng để giải bài toán trọng số cạnh min/max trên cây khung mà anh Hạnh đã sử dụng, các bạn cũng có thể xem ở đây:
K
Đề bài
Cho một mê cung gồm hành lang vuông góc liên tiếp nhau, mỗi hành lang có độ dài . Trước khi bắt đầu bạn có thể chọn trước độ dài tốc biến nguyên để di chuyển từ điểm bắt đầu của hành lang đến điểm kết thúc của hành lang .
Ở mỗi thời điểm nguyên bạn sẽ tốc biến đúng đơn vị độ dài về phía trước trong đúng giây, nếu cú tốc biến này không chuẩn (khoảng cách từ điểm bạn tốc biến đến điểm cuối của hành lang hiện tại không đủ đơn vị) thì bạn sẽ tốc biến đến điểm cuối của hành lang và bị choáng giây, điều này áp dụng cả với hành lang cuối. Nếu không thì bạn có thể tốc biến tiếp ngay lập tức.
Tính thời gian ngắn nhất có thể để ra khỏi mê cung khi chọn tối ưu.
Giới hạn: .
Lời giải
Chúng ta bắt đầu với một số nhận xét như sau về đáp án tối ưu:
- Với cho trước thì ta có công thức tổng thời gian hoàn thành:
- Với mọi ta có . Dấu bằng thứ nhất xảy ra khi toàn bộ bằng nhau, còn dấu bằng thứ hai xảy ra khi ta cho .
- tối ưu khi là một trong các .
Nhận xét thứ 3 gợi ý rằng chúng ta cần duyệt qua tất cả các và tính nhanh được . Chúng ta chia mảng thành 3 phần:
- Phần mà , khi này với mỗi chúng ta mất giây.
- Phần , mỗi mất giây.
- Phần còn lại thì với mỗi tốn giây.
Mấu chốt của bài toán là tính phần 3 đủ nhanh. Và thật ra, cách đủ nhanh lại rất đơn giản:
Ý tưởng của thuật toán trên là đặt cận và tham lam. Ở một thời điểm bất kì, giá trị của
ans - curr là ngưỡng quyết định xem l[i] hiện tại có tối ưu hơn không. Để có thể quyết định nhanh, ta tham lam lấy các giá trị lớn trước rồi cộng phần dư vào. Ta thấy là với rất lớn so với thì curr sẽ tăng nhanh làm vòng lặp kết thúc sớm, còn lại thì không có quá nhiều giá trị để duyệt.Độ phức tạp khi này là với là số bước duyệt trung bình với mỗi giá trị . Trong khuôn khổ bài viết này ta thừa nhận , chứng minh xin dành cho độc giả như một bài tập.
Độ phức tạp cuối cùng là .
Trong kì thi, đội mình là một trong những đội hiếm hoi 1 đấm AC bài này, trong khi các đội mạnh khác như IBM Cloud, Azure của UET trường mình, hay đến cả gugugaga của NEU, AtCoder của HCMUS, đều phải mất nhiều sub. Đây là lợi thế cực lớn khi đội mình so penalty để kiếm suất dự APAC Championship, và đã cứu được sai lầm sảy chân ở bài J.
L
Đề bài
Cho một đường ray có độ dài và truy vấn. Mỗi truy vấn có 1 trong 2 dạng:
+ l v: thêm một tàu có độ dài và vận tốc vào lịch trình.
- l v: xoá một tàu có độ dài và vận tốc khỏi lịch trình.
Mỗi con tàu có phần mui và phần đuôi. Con tàu sẽ xuất phát với mui chạm vạch xuất phát và chỉ ra khỏi đường ray khi đuôi rời khỏi vạch kết thúc. Mỗi con tàu ta có thể chọn cho nó thời điểm xuất phát bất kì.
Tính tổng thời gian ít nhất để đưa toàn bộ tàu ra khỏi đường ray mà không xảy ra tai nạn. Tai nạn xảy ra vào bất cứ thời điểm nào mà phần của tàu này giao với tàu khác và cả hai tàu chưa ra khỏi đường ray.
Giới hạn: .
Lời giải
Qua cảm nhận, ta có thể rút ra 2 nhận xét đầu tiên về đáp án tối ưu:
- Nếu 2 tàu có cùng vận tốc, thì chúng có thể đi nối đuôi nhau như là 1 tàu, nên ta có thể giả sử tất cả đều khác nhau.
- Thứ tự xuất phát của các con tàu sẽ phụ thuộc vào vận tốc, tàu chậm sẽ đi trước, rồi sau một khoảng thời gian tối ưu ta sẽ cho tàu nhanh hơn đuổi theo sau sao cho không xảy ra tai nạn. Dễ thấy là xếp như vậy tối ưu hơn vì ta lợi thêm về thời gian từ hiệu vận tốc của hai tàu đuổi nhau.
Từ 2 nhận xét trên, bằng việc ngồi nháp toán và chứng minh công thức ta rút ra nhận xét quan trọng nhất của bài toán:
- Giả sử có 2 tàu và với . Để tối ưu nhất về giãn cách thời gian giữa hai tàu mà không xảy ra tai nạn, thì thời điểm đuôi tàu thứ nhất chạm vạch kết thúc cũng chính là lúc mui của tàu thứ hai chạm vạch kết thúc. Nhận xét trên cho ta công thức tính giãn cách thời gian xuất phát tối ưu nhất của hai tàu:
- Áp dụng nhận xét trên cho tàu, thì tổng thời gian tối ưu là:
Do đó ta chỉ cần duy trì 2 giá trị sau qua các thao tác thêm và xoá tàu khỏi danh sách:
- Vận tốc của tàu chậm nhất trong danh sách, có thể dùng multiset.
- Tổng của các tàu còn trong danh sách.
Độ phức tạp cho mỗi truy vấn là .
M
Đề bài
Cho một mê cung gồm phòng giống hệt nhau, không sắp thứ tự, nối tiếp thành một vòng tròn, mỗi phòng đều có phòng liền trước và liền sau (có thể là cùng 1 phòng). Mỗi phòng có một cái đuốc ở trạng thái
0 (tắt) hoặc 1 (bật). Bạn không biết mà phải đoán nó.Đầu tiên, và mỗi khi bạn đến một phòng nào đó, máy chấm sẽ trả về trạng thái
0 hoặc 1 của đuốc trong phòng đó và sau đó bạn có thể chọn thực hiện 1 trong 3 loại truy vấn:> v: Đặt đuốc thành trạng tháivrồi đi tiếp sang phòng liền sau.
< v: Đặt đuốc thành trạng tháivrồi đi tiếp sang phòng liền trước.
! n: Trả lời số phòng lànvà kết thúc. Truy vấn này không tính vào tổng số truy vấn.
Số và trạng thái ban đầu của đuốc trong phòng là cố định, và chỉ có truy vấn của bạn mới thay đổi được trạng thái đuốc. Mục tiêu là đoán được trong tối đa truy vấn.
Giới hạn:
Lời giải
Kì Regional này thực sự là để đời với rất nhiều sự magic, khi mà bài này teammate của mình đã code không cần test tay và AC ngay sau đó trong sự bất ngờ của tất cả mọi người.
Dễ thấy ta sẽ chỉ đi theo một chiều chứ không quay đầu, và phải tìm cách đánh dấu các phòng đã đi qua sao cho có cách để nhận diện lại nó khi ta quay trở lại. 55 truy vấn được thêm vào chính là để làm điều đó. Đơn giản thôi:
- Sinh ngẫu nhiên một số có 55 bit. Ta sẽ chỉnh trạng thái đuốc của 55 phòng đầu tiên đi qua bằng các bit của số này. Các phòng còn lại giữ nguyên.
- Ta lưu lại trạng thái của tất cả các phòng đã đến bằng một xâu nhị phân bit. Khi ta thấy trạng thái của 55 bit đầu tiên lặp lại ở vị trí gần nhất nào đó, thì chúng ta đã xác định được với xác suất đúng là . Với giới hạn của trong đề bài thì thuật toán xác suất trên là đúng và ổn định.
Kết thúc
Việc đạt được thành công tại Regional 2024 và được đi Singapore đối với bản thân mình, là một phần thưởng tuyệt đối điện ảnh sau những năm miệt mài với bộ môn Lập trình thi đấu. Những anh em cùng chung chiến đội, cho đến giờ vẫn luôn sát cánh cùng nhau trên những nẻo đường của cuộc sống, càng khiến cho chiến thắng tuổi trẻ trở nên quý giá vô cùng.
Mình sẽ còn nhiều bài viết khác nữa trong tương lai, đón đọc nhé!
- Author:dnx04
- URL:https://dnx04.vercel.app/article/icpc-regional-hanoi-2024-writeup
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
