Editorial for TLE '16 Contest 7 P6 - Everyone Hates Reading - Olympiads Online Judge

Editorial for TLE '16 Contest 7 P6 - Everyone Hates Reading

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.

Author: imaxblue

This problem is a simple string problem that requires the use of a trie. There are two possible approaches:

Store the indices of each string inside the trie, then binary search the lower and upper bounds in each query.
Use a persistent trie and do two queries, one on the $r^{th}$ ~r^{th}~ trie and one on the $l-1^{th}$ ~l-1^{th}~ trie.

Unfortunately, there was insufficient data to prevent incorrect (hashing) solutions from passing. Due to this, the problem can be solved in a trivial way. However, it is encouraged to use a proper solution instead of abusing the test data.

Time complexity: $\mathcal{O}(N \log N)$ ~\mathcal{O}(N \log N)~

Comments

16

Cthulhu commented on March 31, 2017, 4:28 p.m.

I feel really guilty now... I guess I should try implementing the proper solution.