Author: Snigdh Verma
Tester: Anand Raut
Editorialist: Bhashkarjya Nath
DIFFICULTY:
MEDIUM
PREREQUISITES:
Data Structures, Trie
PROBLEM:
One day Rashi went to the kitchen. She took out N strings from the cooker and kept the empty cooker on the stove. But Rashi is clever and she has put the entire blame for this on Gopi. To save herself from the false accusations of Rashi, Gopi must answer M queries asked to her. In each of the M queries, she is given an integer K and she needs to tell the number of possible strings which are prefix of at least K strings out of the given N strings.
EXPLANATION:
Subtask-1:
The implementation for the first subtask is quite clear. Just iterate over all the (n*length of string^2) prefixes and count their no of occurrences in all the strings. Then build a suffix array of length n for all the values of k given in the question and return array[k] as the answer of each query.
Subtask-1 &2
Due to the tight constraints the iteration over all the (n*length of string^2) possible prefixes would not fit into the time limit ,we need to optimise the solution using a prefix trie.
We will build a prefix trie and insert all the n strings in the trie and then we would traverse the trie and store the answer for each k in an array by incrementing the value of arr[word count] at each node of the trie and then we would convert this array in a suffix array and return the arr[k] as the answer for each query.
Time Complexity-O(n*(length of string)+m)
Space complexity-O(n*(length of String))
SOLUTIONS:
Setter's Solution
T3z3xo - Online C++0x Compiler & Debugging Tool - Ideone.com