시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 512 MB | 76 | 25 | 23 | 34.848% |
The OUG ("Ordered University of Germany") is a renowned German university. Since it has a lot of students, student IDs are quite long strings of equal length $\ell$, where each student ID only contains lowercase letters of the English alphabet. Unfortunately for the students, the university's president hates chaos and expects students to always enter lecture halls in ascending lexicographic order of their IDs. As you can imagine, the process of sorting themselves in front of the lecture hall takes quite a lot of time for the students. Georgina, a computer science student, has the following idea to accelerate this process: She plans to fix two integers $i,j$ with $1 \leq i \leq j \leq \ell$ denoting a substring of the student ID starting at the $i$th letter and ending in the $j$th letter. Students then sort themselves lexicographically with respect to this substring of their student ID. Of course, $i$ and $j$ must be chosen in a way such that this new ordering is equal to the lexicographic ordering with respect to their complete IDs. In order to make the process as fast as possible, the length of the substring should be minimal. Can you help Georgina to solve this problem?
The input consists of:
All student IDs only contain lowercase letters of the English alphabet, they are pairwise distinct and appear in ascending lexicographic order.
Output two integers denoting the indices of the first and last letter of the shortest substring so that when students sort themselves lexicographically with respect to this substring of their student ID, the same order establishes as if students sorted themselves lexicographically with respect to their complete student ID.
If there are multiple shortest substrings, you may output any one of them.
4 6 aaaaaa aaabbb aaacaa aaacac
4 6
3 5 cccca ccgda ccgia
4 4
ICPC > Regionals > Europe > Northwestern European Regional Contest > German Collegiate Programming Contest > GCPC 2020 L번