Subtask 1: ~N \leq 20~

N có giới hạn nhỏ, nên ta có thể quay lui toàn bộ các cách chọn và xét từng cách

Time complexity: ~O(2^n*n)~

Subtask 2: ~N \leq 100~

Ta nhận thấy, việc lấy đi một số lá bài ở trên và một số lá bài ở dưới đồng nghĩa với việc phần bài còn lại sẽ là một đoạn liên tiếp của danh sách ban đầu, nên bài toán quy về đếm số đoạn con liên tiếp sao cho tổng các chữ số ~3~ trong đoạn bé hơn ~K~.

Với ~N \leq 100~, chúng ta có thể duyệt 2 for để xác định điểm đầu và điểm cuối, và thêm 1 for nữa để đếm số lượng số ~3~ trong mỗi đoạn

Time complexity: ~O(n^3)~

Subtask 3: ~N \leq 1000~

Ở subtask này, ta có thể cải tiến cách làm ở subtask 2 bằng cách vừa di chuyển điểm cuối, vừa tăng số lượng số ~3~ hiện tại. Chi tiết phần cài đặt bạn có thể tham khảo dưới đây

Time complexity: ~O(n^2)~

Subtask 4: ~N \leq 100000~, ~K=1~

Ở subtask này, bài toán quy về đếm số đoạn con liên tiếp sao cho đoạn con không chứa số ~3~ nào. Ta có thể duyệt từ trái sang phải, và cập nhật một biến ~x~ là vị trí lớn nhất mà phần tử ở vị trí này có ít nhất 1 chữ số ~3~. Khi đó, với mỗi phần tử ~i~ không có chữ số ~3~ nào, số đoạn con liên tiếp có đuôi là phần tử này sẽ bằng ~i - x~. Ta chỉ cần cộng thêm ~i - x~ vào kết quả là sẽ ra đáp số.

Time complexity: ~O(n)~

Subtask 5: ~N \leq 100000~

Ở subtask này, ta có thể sử dụng một mảng tổng tiền tố ~s[i]~ để lưu tổng chữ số ~3~ trong các phần tử từ ~1~ tới ~N~. Khi đó, với mỗi phần tử ~i~, để tìm được đoạn con lớn nhất có đuôi là ~i~ thỏa mãn đề bài, ta cần tìm ~j~ bé nhất thỏa mãn ~s[i]-s[j]<K~ hay ~s[j]>s[i]-K~. Khi đó, số đoạn con liên tiếp có đuôi là phần tử này sẽ bằng ~i - j~ Ta có thể sử dụng tìm kiếm nhị phân đểm tìm vị trí ~j~ vì mảng tổng tiền tố là không giảm.</p>

Time complexity: ~O(n*{log_2}(n))~

Subtask 6: ~N \leq 1000000~

Ở subtask này, ta có thể áp dụng 2 con trỏ. Chi tiết phần cài đặt các bạn có thể tham khảo dưới đây

Time complexity: ~O(n)~

Tổng quan:

Nhìn chung đây là một bài không quá phức tạp. Những kỹ thuật như tìm kiếm nhị phân, tổng tiền tố hay 2 con trỏ có thể còn hơi xa lạ với các bạn không học chuyên những chắc là đã quá quen thuộc với các bạn lớp Tin. Mình viết bài này để các bạn thư giãn và khởi động một tí sau kỳ thi học kỳ 1 căng thẳng (và cũng là vì mình hơi rảnh :>> )

As long as it works