MINMOVE - Minimum Rotations
English | Vietnamese |
Cho một xâu S[1..n]. Ta định nghĩa một phép xoay trên S là việc chuyển kí tự đầu tiên của S về cuối xâu. Cụ thể là, sau một phép xoay thì S trở thành T = S[2..n] + S[1].
Ví dụ: S = abcaa, thì sau một phép xoay ta có S = bcaaa.
Tìm số phép xoay ít nhất để biến S thành xâu có thứ tự từ điển nhỏ nhất.
Input
Một dòng duy nhất chứa xâu S. S chỉ chứa các chữ cái in thường trong bảng chữ cái tiếng Anh (‘a’ .. ‘z’), và độ dài của S không quá 100000.
Output
Một dòng duy nhất chứa một số nguyên biểu thị số phép xoay ít nhất.
Example
Input: mississippi Output: 10
Bộ test và giới hạn thời gian đã được cập nhật. Một số bài đã bị "chạy quá lâu" :)
hide comments
rising_stark:
2024-06-30 16:25:59
@coolcoder_iith How did you know it timed out at 12?
|
|
coolcoder_iith:
2019-10-03 20:19:13
time out at #12
|
|
yaswanth:
2019-09-15 17:47:12
Tried n*logn*logn with quite number of optimisations. TLE
|
|
inkretbear:
2018-08-23 23:15:18
Was getting WA on #17 with prefix hash
|
|
hamjosh1:
2016-09-30 13:29:49
learned a lot :D |
|
vsp4:
2016-09-11 19:19:06
Those who are using stl, make sure to use stable_sort if using nlogn*logn solution. Costed me few WA |
|
minhthai:
2016-04-03 05:42:51
"Some accepted solution got TLE."
|
|
lakshay_v06:
2016-02-05 15:33:28
Same as http://www.spoj.com/problems/BEADS/ . O(nlogn) passed. :) |
|
Dhawal Harkawat:
2016-01-22 05:30:20
silly mistake costed two WAs at #10. finally AC. |
|
Sumit Vohra:
2016-01-21 23:37:21
solved using suffix automaton in O(n)
|
Added by: | Race with time |
Date: | 2008-12-29 |
Time limit: | 0.100s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO PERL6 |
Resource: | Based on a problem from ACM Central European Programming Contest |