Bài 1
Mình nhận xét là nếu đoạn cần đi nằm giữa tức là không chạm đến vị trí 0 hoặc k- 1 thì sẽ có độ dài là k. Từ đấy ta chỉ cần for 2 vòng for(i, 0, k - 1) for(j = i, j < n - 1, j += i) trong đó i là vị trí bên phải đoạn đầu tiên tức là mình sẽ đi từ 0 đến i còn j là vị trí bên phải từng đoạn tiếp theo.
Bài 3
- subtask 1 có thể làm bằng luồng
- subtask 2 sort lại các giá trị của mỗi người theo a[i] và mảng k tại mỗi k[i], add thêm những người có a[i] <= k[i] <= b[i] vào một multiple_set các giá trị b[i](trong C++), thao tác thêm dùng con trỏ tịnh tiến và xử lý với set nên mất nlogn rồi việc đẩy ra k[i] thằng ta sẽ đẩy từ các giá trị có b[i] nhỏ cho đến b[i] lớn ra ngoài mất Slogn để thực hiện.
- subtask 3 là một subtask khá khó (mặc dù thuật toán không khó đối với những bạn giỏi về ctdl nhưng đòi hỏi việc cài cực kỳ cẩn thận bởi vì có rất nhiều trường hợp khi phân tich). Mình thực hiện thao tác sort tương tự subtask 2 nhưng đến đây chúng ta gặp một vấn đề là số lượng các phần tử quá lớn không thể đẩy vào set được, vì vậy ta phải tính trực tiếp ở mỗi k[i] có còn k[i] người để phủ điểm k[i] không, tại bước thứ i mình sẽ lưu một giá trị need là số lượng đoạn đi qua k[i] mà cần phải trừ đi vì những thằng trước i đã dùng mất. Khi đến vị trí thứ i dễ dàng tính được số lượng đoạn đi qua i bằng số đoạn u có a[u] <= k[i] - số đoạn v có b[v] < k[i]. Tiếp đó ta tính đến những đoạn đi qua cả k[i] và k[i + 1], cái này có thể tính bằng cách dùng bit2D sử dụng lower bound và upper bound trên các cây bit. Những đoạn mà qua i chứ không qua i + 1 lại được chia thành 2 phần những đoạn chỉ qua i và những đoạn qua cả i - 1. Từ các giá trị trên ta có thể tính được xem là có thể có đủ k[i] đoạn qua k[i] không và cần bao nhiêu đoạn nữa để bù đắp lại khi tính đến i + 1. Thuật toán nlognlogn + qlognlogn
- subtask4, từ subtask 3 là có thể gần đủ để AC rồi nếu cài Bit2D khéo nếu thêm một thao tác nữa là sau khi chèn các vị trí vào các cây bit ta không phải sort lại nhờ đã sắp xếp b[i] trước đó thì thuật toán giảm xuóng còn nlogn + qlognlogn nhưng vì số điểm trên mỗi cây bit trung bình chỉ là logn nên thuật chạy rất nhanh (<1s)
Nhận xét: Bài 3 này là một bài đòi hỏi kỹ thuật tốt và sự cẩn thận (Hạnh bị WA 1test chắc là do chưa xét đủ trường hợp), mình cũng đã thử code và debug khá nhiều, mất gần 1h để giả lập test và sau 10000 bộ test đã tìm thấy trường hợp sai và AC sau đó. Những bạn học lực khá giỏi có thành tích cao trong các kỳ thi làng xã như cubeslove, TooSimple, ecnerwal, haghani... cũng phải sau rất nhiều điểm 0 và sau > 10 lần submit mới AC.
Bài 2:
- Khá đơn giản để thử tay với Q = 8
- Q = 7, có nhiều cách làm, có thể làm bằng tay tầm 15,20 phút chỉ cần lưu ý là để cả A, B, C cùng có thể xảy ra thì sẽ chia được nhỏ và dùng các query getNextLight một cách hợp lý. Cách giải của Tâm teamate RR là một ví dụ, bạn chia trường hợp khá tốt, sau 3 bước đã có được thứ tự của A, B, C, D là 24 trường hợp trong khi đó 3 bước thì số bộ mã hoá tối đa được là 3^3 = 27. Vì vậy Tâm rất dễ dàng để đạt được kết quả như ý muốn sau 4 bước còn lại vì 6!/24 = 30 nhỏ hơn rất nhiều so với 3^4 = 81.
- Q = 6, Thử đặt một câu hỏi làm như Tâm ở 3 bước đầu xong mò bằng tay hoặc chạy máy duyệt vét cạn các bước sau có được không. Câu trả lời là không bởi vì sau 3 bước làm của Tâm thì ta sẽ chia ra được 24 tập khác nhau mỗi tập có 30 phần tử chưa xác định mà với 3 câu hỏi thì có thể mã hoá tối đa 3^3 = 27 phần tử nên chắc chắn làm 3 bước đầu như Tâm thì sẽ không bao giờ ra được kết quả tốt nhất. Ta có thể thấy 3^6 = 729 rất gần với 6! = 720 vì vậy với mỗi bước cân ta phải nghiêm ngặt chia các tập ra gần như phải là chia 3, khi đến các bước cân thứ 3 trở đi bắt buộc phải là chia 3 ta sẽ có dãy 80,27,9,3,1 các phần tử trong tập lần lượt sau khi ta chia xong các bước thứ 2, 3, 4, 5, 6 (80 có thể là 81). Một thuật toán khả thi là duyệt đặt cận và tại mỗi bước ta có một bộ các hoán vị khác nhau mà số lượng thì không được lớn hơn giá trị có thể, vì vậy sau khi đặt cận thì ta có thể chạy thuật toán khá nhanh ( mình chưa thử code nhưng nghĩ có thể chạy được. Cách thứ 2 mình đưa ra là ngay ban đầu lấy luôn 2 lần cân cho (A, B, C) và (D, E, F) bởi vì các số thuộc 2 bộ này đang độc lập nên sau 2 bước này ta sẽ có 9 bộ 80 phần tử rồi duyệt đặt cận độ sâu 4 cho từng bộ một. Đây là bài khó để AC nhất ngày 1 nhưng mình nghĩ cũng là bài thú vị nhất và dễ kiếm điểm mà không quá nhiều thuật toán nhất. Chúc các bạn AC hết các bài này :))