COCI 2019/2020 - Contest 4 - Nivelle

View as PDF

Submit solution

Points: 1.50 (partial)
Time limit: 1.5s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2019/2020 - Contest 4
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bojan thấy có ~N~ đồ chơi nằm ở trên kệ, được đánh số từ ~1~ đến ~N~. Mỗi đồ chơi được tô 1 trong trong 26 màu khác nhau. Mỗi màu được thể hiện bởi một chữ cái in thường trong bảng chữ cái tiếng Anh.

Với mỗi tập các đồ chơi, chúng ta có thể định nghĩa độ rực rỡ là số lượng màu của đồ chơi khác nhau, chia cho tổng số đồ chơi có trong tập. Bojan ghét sự rực rỡ. Bojan muốn chọn một đoạn con liên tiếp các đồ chơi.

Hãy giúp Bojan tìm một đoạn con liên tiếp các đồ chơi mà độ rực rỡ là nhỏ nhất có thể.

Input

Dòng đầu tiên chứa số nguyên ~N (1 \leq N \leq 100000)~, số lượng đồ chơi có trên kệ.

Dòng thứ hai chứa xâu ~S~ có độ dài ~N~. Kí tự thứ ~i~ trong xâu thể hiện màu của món đồ chơi thứ ~i~ trên kệ.

Output

In ra 2 vị trí ~L~ và ~R~ ~(1 \leq L \leq R \leq N)~, thể hiện đoạn con đồ chơi cần tìm là ở vị trí ~L, L+1,..., R~.

Nếu tồn tại nhiều đáp án thỏa mãn độ rực rỡ nhỏ nhất, hãy in đáp án bất kì.

Ví dụ

Sample input 1

4
honi

Sample output 1

1 4

Sample input 2

7
nivelle

Sample output 2

4 7

Sample input 3

6
ananas

Sample output 3

1 5

Ràng buộc

  • 6 test đầu có ~N \leq 100~.
  • 6 test sau có ~N \leq 2000~.
  • 6 test sau khác thỏa ~S~ chỉ chứa ~a~, ~b~.
  • 6 test sau khác thỏa ~S~ chỉ chứa ~a~, ~b~, ~c~, ~d~ và ~e~.
  • 6 test còn lại không có ràng buộc gì thêm.

Comments

Please read the guidelines before commenting.



  • 20
    hieuhfgr  commented on June 20, 2024, 2:08 a.m.

    Mô sai (my sol)

    Hints:

    minimize ~(diff)/(r-l+1)~ với ~diff~ là số lượng phần tử khác nhau trong đoạn ~(l, r)~. Vậy ~diff~ có độ lớn là bao nhiêu?

    Ta cố định ~diff~ và duyệt tuần tự theo ~i~

    Solution:

    Bài toán của ta là việc in ra đoạn ~(l, r)~ nhỏ nhất mà sao cho ~diff/(r-l+1)~ là bé nhất. vì ~1 \le diff \le 26~ (chỉ có ~26~ màu khác nhau) nên ta sẽ xét từng đoạn mà bằng với ~diff~. Gọi ~cnt[i][x]~ là số lượng kí tự ~x~ xuất hiện trong đoạn ~s[1..i]~. Vậy việc còn lại của ta là duy trì một con trỏ ~j~ ý nghĩa là ta xét đoạn ~(j, i)~ và kiểm tra điều kiện qua mảng ~cnt~. DPT: O(n*26)

    lần đầu viết sol mong mọi ng đừng downvote T_T