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:

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

Unfortunately, there was not sufficient 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)


Comments


  • 13
    Cthulhu  commented on March 31, 2017, 12:28 p.m.

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