Editorial for CTU Open Contest 2018 - Locker Room

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Create Suffix array over $s+s$ ~s+s~.
Binary search by answer
- Scratch out every segment with lesser rank.
- Scratching can be done with $\mathcal O(N)$ ~\mathcal O(N)~ sweep.
- Total complexity $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~.
Keep track of non-scratched segments
- Traverse SA and remove scratched segments.
- Segments in Set: $\mathcal O(\log N)$ ~\mathcal O(\log N)~
- Total complexity $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~.
Note that complexity depends on SA construction. $\mathcal O(N \log^2 N)$ ~\mathcal O(N \log^2 N)~ suffices (if implemented reasonably).

Comments

There are no comments at the moment.