| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
You are given a binary string (consisting of 0,1) and you can rotate the string in any order. Basically if the string is s1s2s3...s(n-1)s(n) , you can make it s2s3s4,,,s(n-1)s(n)s1 .
Print out the rotation which has the maximum value in binary representation.
For example:
s=0110
ans= 1100
|s| <= 10^5
Can anyone suggest any approach ? I'm unable to think of any fast approach.
It's similiar to this one i guess.
Oh..thanks. But it had no explanation for it's editorial.
Make a new string $$$x = s + s$$$
Replace all '1' by 'z' and all '0' by 'a'.
Find largest lexicographic sub-string of size $$$n$$$ in string $$$x$$$ using the concept mentioned here : https://codeforces.net/blog/entry/75953
When you finally find the required substring , print it till length-'n' only
There is an exact question on Hackerearth same as yours and has linear solution but i can't find it now. But we can solve it using binary search to find lexographically largest prefix(using rolling hash).
This may be overkill, but it shouldn't be hard with a suffix tree.
Thanks. Looks like it's time to finally study suffix array and tree. :P
One can also use a suffix array in the same way.
You can use this:Lexicographically minimal string rotation
Take the complement of the string run the algorithm and then take the complement again.
Thanks for the link!
We can maintain the binary representations of each prefix and suffix of the string. Then for each position, calculate what will be the result in binary if that position was the first one.
Eg — s = 0110
pref vals = 0 1 3 6
suff vals = 6 6 2 0
then for the indices we have 0th — 6
1st — 12 = (6x2 + 0)
2nd — 9 = (2*4 + 1)
3rd — 3 = (0*8 + 3)
Hence answer is 12 (1100). Complexity should be O(n)
The string has length upto 10^5. Calculating actual decimal value will be not possible.
Oh yeah you are right.
Replace 0 with a and 1 with b and then duplicate the string and find suffix array, answer is last value in the array.
funny coincidence: problem asked in blog post is same problem as the first example problem in the stanford suffix array pdf: http://web.stanford.edu/class/cs97si/suffix-array.pdf
to compare to 2 possible choices.binary search for the first i such that first (i-1) characters of both choices are same and ith character is different.this can be done with hashing.you need to do this n-1 times so O(nlogn)
.
What you are looking for is lexicographically maximum cyclic shift of binary string. Link This should help.