Result + editorial contest 9

a516zxa - 24/02/2019

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.

CÁC PHẢN HỒI

  • L9QuangLD - 24/02/19 23:26
    A ơi bài E em vẫn chưa hiểu lắm.
  • a516zxa - 24/02/19 23:26
    em chưa hiểu chỗ nào :|
  • a516ami_crush_tuyetni - 24/02/19 23:38
    Chúc các bạn một tuần vui vẻ, có lẽ sau 1 tuần nữa mình mới lại tổ chức contest nữa, có điều gì cần góp ý, các bạn hãy comment
  • a516ami_crush_tuyetni - 24/02/19 23:53
    Xin lỗi các bạn, bài F hoàn toàn có thể duyệt trâu tạo mạng next mà ko cần kmp nhé
  • L9CaoThuNoSeo - 25/02/19 16:34
    em thấy đề như vậy là hay rồi anh! từ bài A đến bài E không đòi hỏi kiến thức gì cao siêu, chỉ có bài E phải để ý để nhận ra chu kì (và cả không ngu để code được). bài F,G thì em chưa có đủ kiến thức cũng như tư duy nên sẽ ko phán xét
  • a516ami_crush_tuyetni - 25/02/19 17:11
    Nếu bài D khó hơn 1 tí thì các bạn nghĩ sao, mức độ có lẽ giống bài CONTEST8D thì các bạn thấy sao ?
  • L9zipdang2004 - 25/02/19 21:45
    e nghĩ mấy contest sau nên chơi đúng kiểu ACM: xáo hết lên, để thí sinh tự mò bài mà làm =)) *các bạn beginner có lẽ k thích điều này?
  • L9toandnn - 26/02/19 15:42
    Em thì thấy bài D như vừa rồi là vừa sức rồi anh ơi.
  • a516ami_crush_tuyetni - 26/02/19 19:35
    Có lẽ lần sau mình sẽ làm khoảng 6 bài và bài 6 vẫn nằm trong vùng kiến thức của các bạn nhưng tất nhiên sẽ khó hơn so với 5 bài kia. Các bạn có đề xuất gì nữa không ?
  • a516ami_crush_tuyetni - 26/02/19 19:36
    Nhưng mình nghĩ trừ bài G contest đầu quá khó, thì những bài contest 9 này các bạn đều có thể hiểu được, vì quy hoạch động thì là quy hoạch động thôi, dù cho người ta có gán tên gì cho nó thì ý tưởng cũng là như nhau
  • em nghĩ bài d có cách giải gọn hơn: lấy k là phần nguyên của sqrt(N), kiểm tra xem nếu (k*k)+k=N thì in ra k, còn không thì in NO.
Back to Top