COCI '19 Contest 4 #5 Nivelle

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Original task description has been altered due to excessive violence. The following program is suitable for minors.

Bojan sees N cute little fluffy edible toys (yaay!) on a store shelf, ordered from 1 to N. Each fluffy toy is colored in one of 26 different colors. Each color is denoted by a lowercase letter from the English alphabet. Bojan wants to eat some of these toys (drool).

For any set of toys, we can define its colorfulness as the number of different colors of toys in a set, divided by the total number of toys in a set. Bojan hates colorfulness. Bojan is very hungry. Bojan wants to eat a contiguous subsequence of toys.

Help Bojan find a contiguous subsequence of toys whose colorfulness is as small as possible.


The first line contains an integer N (1 \le N \le 100\,000), the length of array of toys from task description.

The second line contains a string S of length N. The i-th character of the string represents the color of i-th toy from the shelf.


Output two indices L and R (1 \le L \le R \le N), which denote that the sought contiguous subsequence of toys is located at positions L, L + 1, \dots , R.

If there exists more than one contiguous subsequence with the same minimal colorfulness, you can output L and R which define any of them.


Subtask Score Constraints
1 7 N \le 100
2 17 N \le 2\,000
3 13 S contains only letters a and b
4 25 S contains only letters a, b, c, d and e
5 48 No additional constraints.

Sample Input 1


Sample Output 1

1 4

Sample Input 2


Sample Output 2

4 7

Sample Input 3


Sample Output 3

1 5


There are no comments at the moment.