Đề thi, đáp án OLP 2016 (Olympic Tin học sinh viên)

Kì thi Olympic Tin học sinh viên năm 2016 cũng diễn ra được hơn 2 tuần rồi, đề thi cũng đã được public và các bạn có thể tải về để xem tại: https://goo.gl/Vknb6P . Với mong muốn giúp các bạn sinh viên có thể học tập tốt hơn và phát triển khả năng lập trình trong những năm tới nên mình viết lời giải để các bạn nào chưa làm được có thể thử sức làm lại những bài mình chưa giải được trong kì thi, hi vọng sẽ giúp các bạn học thêm được nhiều thứ.
Lưu ý đây chỉ là lời giải mang tính tham khảo dựa trên kiến thức của mình chứ không phải lời giải chính thức từ người ra đề của cuộc thi.

Khối Siêu cúp:

  • LAMPS: Bài này ta có thể giải bằng luồng cực đại (https://en.wikipedia.org/wiki/Maxim…), có nhiều cách xây dựng luồng. Cách xây dựng luồng của mình là:
    • Gọi đỉnh xuất phát là S, đỉnh kết thúc là F, ta có c đỉnh đại diện cho c màu khác nhau của đồ thị, cạnh (S,c(i)) có trọng số x là số lượng đỉnh trên đồ thị có màu là thứ i, mặc khác với mỗi màu i ta tạo cạnh (c(i),F) có trọng số là 1, ta lại có k đỉnh đại diện cho k chu trình khác nhau trong đồ thị, với mỗi với mỗi đỉnh u có màu i nằm trong chu trình j thì ta có cạnh (c(i), k(j)) với trọng số là 1. Tìm luồng cực đại trên đồ thị này, gọi giá trị là X thì kết quả bài toán là X – k. (Các bạn hãy tự chính minh tính đúng đắng)
    • Do mỗi cạnh thuộc tối đa 1 chu trình nên ta có tối đa n/3 chu trình trên đồ thị, số lượng đỉnh tối đa của đồ thị luồng là: m + n / 3 + 2 = n * 5 / 3 + 2 ~ 17000 , số lượng cạnh tối đa là: m + n + n / 3 = n * 8 / 3 ~ 27000. Do đó ta cần phải xây dựng đồ thị luồng một cách tối giản nhất (gọp các cạnh trùng) cũng như dùng thuật toán tìm luồng nhanh như Dinic hoặc Preflow Push thì mới có thể đạt điểm tối đa bài này.
  • CAKE: Tư tưởng bài này là khi đổi bánh khối lượng x từ người có tổng khối lượng bánh Tx sang 1 người có bánh khối lượng y tổng khối lượng bánh Ty, trong đó Tx > Ty thì ta cần có y – Tx + Ty < x < y để tổng chênh lệch lúc sau khi đổi giảm đi. Ta có thể sắp các giá trị Tx tăng dần và dùng IT hoặc BIT để đếm số giá trị x thỏa mãng.
  • RADA: Xét mỗi vòng tròn, ta tính tất cả các giao điểm của vòng tròn này với các vòng tròn còn lại, các trường hợp đặc biệt là vòng tròn này chứa các vòng tròn khác hoặc bị chứa thì ta xử lí riêng. Trường hợp 2 vòng tròn giao nhau tại 2 điểm thì cái khó là ta cần tính được 2 giao điểm này, sau đó 2 giao điểm này nằm trên cung tròn sẽ giống như 2 dấu mở ngoặc và đóng ngoặc ‘(‘ ‘)’. Lúc này ta đưa được về bài toán là tìm điểm được bao bởi nhiều cặp dấu mở ngoặc đóng ngoặc nhất.
  • ALICE: Bài này lời giải khá đơn giản nhưng không phải ai cũng có thể nghĩ ra:
    • Trường hợp tồn tại vị trí số 0 nằm bên trái số 1 thì chắc chắc sẽ luôn tồn tại 1 xâu 01.
    • Trường hợp tất cả các số 1 đều nằm bên trái tất cả các số 0, ta sẽ tìm số 1 bên phải nhất và số 0 bên trái nhất, tập trung hỏi vào vòng giữa 2 số này. Cách hỏi là: Nếu vùng này có độ dài lẻ, ta sẽ hỏi vào các vị trí 2, 4, 6, … Ta có thể hỏi ở bất kì 1 vị trí nào trong các vị trí này, trường hợp độ dài chẵn thì hỏi ở đâu cũng được. Khi hỏi xong nhận kết quả trả về là 0 hay 1 thì ta sẽ cập nhật lại vị trí số 1 bên phải nhất hoặc số 0 bên trái nhất, và đi vào tập trung hỏi trong vùng này theo cách tương tự

Khối chuyên tin:

  • TRASH: Xét mỗi vị trí đoạn thứ i, ta có thể chặc nhị phân hoặc dùng 1 biến tăng dần từ trái sang phải để xác định đoạn j nhỏ nhất sau cho j < i và tổng từ đoạn j đến đoạn i <= m. Đpt là O(nlogn) với cách chặc nhị phân hoặc O(n) với cách dùng biến chạy.
  • SQUARES: Đây chỉ đơn giản là bài toán tính tổng của dãy cấp số nhân, sau một vài phép tính ta có kết quả là: L^2 * (4 ^ (N+1) – 1) / 3
  • RECOVERY: Đi từ số thứ n trở về số đầu tiên, ta thấy số ở vị trí a[n] cần được giữ nguyên, xét số ở vị trí a[n-1], nếu số này lớn hơn a[n], ta cần xóa đi 1 số lượng chữ số ít nhất đảm bảo kết quả a[n-1] <= a[n] và a[n-1] lớn nhất có thể, sau đó ta lại tiếp tục xét số a[n-2] và xóa chữ số đi nếu cần thiết giống cách ta xử lí số a[n-1]…. Do việc ưu tiên số lượng chữ số bị xóa đi ít nhất đồng thời cũng sẽ tỉ lệ thuận với việc số còn lại là lớn nhất nên thuật toán tham này chạy đúng.
    • Ta sẽ phải giải quyết bài toán con: Cho 2 số a, b, ta cần xóa đi 1 số lượng chữ số ít nhất ở số a sao cho a <= b và a có giá trị lớn nhất có thể. Giả sử a > b, với trường hợp ta xóa sao cho số lượng chữ số của a bằng số lượng chữ số của b, a <= b và a lớn nhất ta có thể quy hoạch động, trường hợp ta cần xóa sao cho số lượng chữ số của a nhỏ hơn số lượng chữ số của b thì chỉ cần xử lí tham là đủ.
  • GUIDE: Bài này có nhiều lời giải nhưng mình sẽ chỉ cách làm bằng LCA, bạn nào chưa biết về LCA thì có thể xem tại (http://vnoi.info/wiki/algo/data-str…). Xây dựng các cây(có thể có nhiều cây riêng biệt). Với mỗi truy vấn s – f, có 3 trường hợp:
    • f và s thuộc 2 cây khác nhau, trả về kết quả là -1
    • s và f nằm trong cùng 1 cây, f nằm trong cây con góc s, điều này xảy ra nếu s = LCA(s, f). Với trường hợp này ta xác định độ sâu chênh lệch d giữa s và f, sau đó từ f nhảy lên d-1 bước là ra được đỉnh kết quả.
    • s và f nằm tỏng cùng 1 cây, f không nằm trong cây con góc s. Kết quả trong trường hợp này, ta trả về cha của s.

Khối không chuyên:

  • PALIN: Do độ dài xâu S <= 10000 nên hoàn toàn ta có thể làm thuật toán O(n^2) xét hết tất cả các xâu con và kiểm tra palindrome bằng kĩ thuật Hash xâu (http://vnoi.info/wiki/algo/string/h…). Mặc khác ta có thể giải bài toán này với đpt O(nlogn) bằng phương pháp chặc nhị phân ở từng vị trí của xâu để tìm xâu palindrome dài nhất (nhớ xử lí trường hợp xâu độ dài chẵn/lẻ). Ngoài ra ta cũng có thể giải bài toán này với đpt O(n) với việc sử dụng thuật toán Manacher để tìm xâu palindrome xài nhất.
  • TRASH: Xem lời giải bài này ở khối chuyên tin.
  • PRIMETAB: Trước tiên ta cần dùng thuật toán sàng số nguyên tố(http://vnoi.info/wiki/translate/he/…) để xác định số nguyên tố trong bảng được cho. Kết quả đưa về bảng số 0, 1. Giờ ta cần xử lí truy vấn từ dòng x đến dòng y có tồn tại một hình chữ nhật toàn số 1 với kích thước r * c hay không. Ta cần cài đặt 2 lời giải riêng biệt tùy vào input:
    • Xét trường hợp m <= n ( suy ra được m <= sqrt(m*n) ), ta quy hoạch động O(m^2 * n) để tính mảng f[r][i] = c là giá trị lớn nhất mà tại hàng i tồn tại hình chữ nhật toàn số 1 có kích thước r * c, trong đó dòng đầu tiên của hình chữ nhật ở vị trí i. Như vậy với mỗi truy vấn ta sẽ xét tất cả các giá trị r2 >= r và kiểm tra xem giá trị lớn nhất từ f[r2][x] đến f[r2][y-r2+1] có lớn hơn hoặc bằng c hay không? Để kiểm tra giá trị lớn nhất nhanh ta sẽ dùng cây phân đoạn (http://vnoi.info/wiki/algo/data-str…)
    • Xét trường hợp m > n ( suy ra được n <= sqrt(m * n) ), tương tự ta quy hoạch động O(m * n^2) để tính mảng g[c][i] = r là giá trị lớn nhất mà tại hàng i tồn tại hình chữ nhật toán số 1 có kích thước r * c, trong đó dòng đầu tiên của hình chữ nhật ở vị trí i. Như vậy với mỗi truy vấn ta sẽ xét tất cả các giá trị c2 >= c và kiểm tra xem giá trị lớn nhất từ g[c2][i] đến g[c2][y-r+1] có lớn hơn hoặc bằng r hay không?

Khối cao đẳng:

  • NPRIME: Chỉ cần viết được hàm kiểm tra số nguyên tố chạy trong O(sqrt(n)) là có thể làm được bài này. Cách làm tốt hơn là dùng sàn số nguyên tố (http://vnoi.info/wiki/translate/he/…)
  • LRPALIND: Kiểm tra palindrome bằng kĩ thuật Hash xâu (http://vnoi.info/wiki/algo/string/h…).
  • TRASH: Xem lời giải bài này ở khối chuyên tin.
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây……

Speak Your Mind

*