Như vậy contest 9 đã kết thúc, kết quả chung cuộc như sau:
top 5:
+) a516khoiphan
+) L9zipdang2004
+) L9CaoThuNoSeo
+) L9QuangLD
+) Ma Le Gơ
Các bạn AC nhanh nhất của từng bài:
+) A: L9CaoThuNoSeo
+) B: L9CaoThuNoSeo
+) C: a516khoiphan
+) D: L9CaoThuNoSeo
+) E: a516khoiphan
+) F:
+) G:
Xin chúc mừng tất cả các bạn.
Một bài điểm đặc biệt của contest hôm nay:
+) Các bạn A5 không còn thống trị bảng xếp hạng như contest trước
+) 2 bạn L9CaoThuNoSeo và a516khoiphan AC 3 bài B, C, D gần như cùng lúc.
Sau đây là editorial của các bài tập:
Bài A :
Thuật toán bài này rất tường mình. Các bạn có thể chạy for tất cả các số từ 1 đến số A và nếu tìm thấy một số mà cả A và B đều chia hết thì ta tăng kết quả lên 1.
Độ phức tạp : O(N).
Bài B :
Nếu dãy A là một cấp số cộng thì phần tử thứ 2 trừ phần tử thứ nhất sẽ là kết quả của bài toán. Đặt a2 – a1 = k. Khi đó ta có thể kiểm tra xem với mỗi phần tử trừ đi phần tử trước nó có bằng k hay không.
Độ phức tạp : O(N).
Bài C :
Ta có thể dùng thuật toán đếm phân phối để giải quyết bài toán này. Dùng mảng count là mảng đếm. Ta sẽ duyệt qua mỗi phần tử trong dãy và tăng count[a[i]] lên 1 với a[i] là phần tử ta đang xét và kiểm tra xem phần tử đó có phải xuất hiện nhiều nhất hay không.
Độ phức tạp : O(N).
Bài D :
Ở contest trước, mình có đề cập đến tổng dãy số trong một cấp số cộng. Tổng đó sẽ bằng:
Số số hạng * (Số đầu + Số cuối) / 2.
Vậy tổng 1 + 2 + 3 + 4 + .. + k = k * (k + 1) / 2 = N.
Suy ra K * (k + 1) = N * 2.
Suy ra K xấp xỉ bằng căn bậc 2 của số N * 2.
Do đó ta có thể lấy khoảng 100 số k gần căn bậc 2 của N*2 nhất và kiểm tra xem có số k mà mà k * (k + 1) = 2 * N hay không.
Độ phức tạp : O(100).
Bài E :
Bài này để ý rằng nếu trong dãy số tạo ra có 2 số liên tiếp đã xuất hiện trước trong dãy. Hay f[n] và f[n-1] = f[i] và f[i-1] với i < n. Thì rõ ràng, dãy Fibonacci nhân sẽ lặp lại. Vì số mod khá nhỏ <= 103. Ta có thể suy ra rằng, sự lặp lại này sẽ xuất hiện sau không quá 106 phép tính. Từ nhận xét trên, các bạn có thể tìm quy luật bằng mảng 2 chiều và in ra kết quả trong O(1).
Độ phức tạp : O(mod2).
Bài F :
Đây là một bài khó, đòi hỏi các bạn phải biết thuật toán KMP và quy hoạch động. Đầu tiên, theo tư duy thông thường, ta sẽ gọi f[i][j][k] là kết quả bài toán khi chiều dài của xâu cần tạo là i , j là độ dài lớn nhất mà j chữ cái cuối cùng của xâu S giống với xâu cần tạo và k là chữ L đã xuất hiện được k lần. Gọi xâu cần tạo là r, trạng thái này có nghĩa : r[i] = s[n] , r[i-1] = s[n-1] , …. , r[i – j + 1] = s[n – j + 1] và r[i – j] != s[n – j]. Vậy để tiến đến trạng thái tiếp theo, ta có 3 cách : thêm vào chữ cái L và tăng k lên 1, thêm vào D hoặc P và giữ nguyên k. Vấn đề cuối cùng làm sao để tính j sau khi thêm 1 trong 3 chữ cái ?
Các bạn có thể dùng thuật toán KMP để giải quyết vấn đề này. Gọi next[j][c] với ý nghĩa là số kí tự cuối cùng lớn nhất khi xâu r đang giống xâu s j kí tự cuối thì ta thêm vào một kí tự c sau xâu r. next[j][c] tính được dễ dàng bằng phần tiền xử lý của thuật KMP.
Độ phức tạp : O(n3) cho phần quy hoạch động và O(n2) cho phần tạo mảng next[j][c].
Bài G :
Đây là một bài quy hoạch động chữ số khá thịnh hành trong lập trình thi đấu. Gặp bài này, cách giải chung quy là như sau : Gọi hàm F(n) là kết quả nếu l = 1 và r = n .hay các số từ 1 -> n.
Vậy kết quả của bài toán sẽ là F(R) – F(L – 1).
Để tính F(N) mình làm như sau : Gọi result[i][dig][a][b] là kết quả bài toán khi xét i chữ số đầu, dig là chữ số cuối cùng, a = 0 nếu là dãy giảm và a = 1 nếu là dãy tăng, b = 0 nếu i kí tự đầu trùng với i kí tự của xâu N và bằng 1 nếu ngược lại. Từ đó, ta có thể đơn giản là for tất cả các chữ số từ 0 -> 9 và gọi trạng thái tiếp theo.
Độ phức tạp O(n * 10 * 10).
Các bạn có ý kiến gì về đề cũng như editorial hôm nay có thể comment ở bên dưới, mình và các thành viên trong team ra đề sẽ giải đáp.
