Problem LinkAuthor: Azat Tester: Pawel Kacprzak and Misha Chorniy Editorialist: Bhuvnesh Jain DifficultyEASYMEDIUM PrerequisitesTries, State Transitions ProblemYou are given a list of websites, some of which are blocked. You need to find a set of prefixes such that each of the blocked websites are recognised by some prefix but none of the nonblocked websites are. The aim is to minimise the sum of the length of the prefixes found. Quick ExplanationBuild a tries of the words, storing information regarding the words, their type (blocked or nonblocked). Use transitions during the traversal of trie (dfs) to find the optimal answer, if it exists. ExplanationFirst of all, the problem deals with prefixes. Generally, problems on strings related to prefixes can be solved using hashing or trie. We will use trie to solve this problem. Before starting to solve the problem, like what kind of data structure we would require and what information it should store, let us first analyse when the solution exists or not. The solution will not exist only when the blocked site is a prefix of a nonblocked website.. In all other cases the solution will exist because in the worst case, we might select the whole word for all the blocked websites. Now, suppose the solution exist. We would like to minimise the total length of the selected prefixes. Now, since the length of one prefix is independent of the other, the total length would be minimum when we minimise each prefix selected. For minimising each prefix selected, we just want to selected the first character which differentiates between 2 blocked and nonblocked websites. Such a letter will exist as otherwise the solution would not have existed. Let us understand this through examples. Let the blocked website be "codeforces" and allowed website be "codechef". Now, the $5^{th}$ letter ("f" vs "c") is the one which differentiates the 2 websites. Let the blocked website be "bing" and allowed website be "google". In this case, the $1^{st}$ letter will only differentiate the 2 websites. Let the blocked be "cs" and allowed website be "csacademy". In this case the solution will definitely not exist. As all the prefixes, "c" and "cs" would block both the websites. From the examples, above our data structure should be able to handle 2 type of operations. They are :
Doing this through brute force will take complexity $O(\sum_{i=1}^{i=n} \sum_{j=i+1}^{j=n} min(L_i, L_j)$, where $L_i = $ length of string $i$. This is because the comparison between 2 strings to do the above operations can be done using a simple for loop, which terminates in worst case when either of the string to be processed finishes. In the worst case, it will be quadratic in the sum of length of strings given. Thus, it will only be able to solve subtask 1. For the complete solution, we use tries and store the following information in it to be able to handle above operations efficiently.
After building of the trie, we just do a traversal (dfs) on it. Now, few things should be noted. Whenever we are in state $3$, we can go to state $\{0, 1, 2, 3\}$ in the child node. When we are in state $1$, we can only go to state $\{0, 1\}$ and when we are in state $2$, we can only go to $\{0, 2\}$ in the child node. This information will be enough to be able to handle above operations. Below are the claims for it :
All the above operations can be done in $O(\sum_{i=1}^{i=n} {L}_{i})$, where $L_i = $ length of string $i$. This is because the trie can be build in above complexity and can be traversed in above complexity too. If you had some other logic/algorithm to solve the above problem, feel free to discuss below Time Complexity$O(\sum_{i=1}^{i=n} {L}_{i})$, where $L_i = $ length of string $i$ Solution Links
This question is marked "community wiki".
asked 18 May '17, 13:47

I did it using tries, normal tries and it gets accepted. Here is my solution https://www.codechef.com/viewsolution/13586368 Also can you guys please vote my post. I need karma for posting questions. answered 18 May '17, 16:08

I did it by tweaking the brute force using maps and that's all was needed for AC check out my solution https://www.codechef.com/viewsolution/13616655 answered 18 May '17, 15:23

I did it using trie, brute force implementation using trie is sufficient! answered 18 May '17, 15:19

sort the array lexographically, go to each '' string and find the nearest '+' string above and below it. compare the given '' string with both the '+' strings and find the string with maximum number of continuous matching characters from the beginning and load that substring into a treeset(to avoid duplicates). print the treeset answered 18 May '17, 15:27

Does Codechef provide testcases? It would be helpful for knowing corner cases and debugging. answered 18 May '17, 15:39

I solved the question using mentioned data structure i.e. trie and set, however got WA on two cases in subtask 2. Here is the solution. If someone using same logic could point out the error or provide corner test case, it would be great help. Thanks in advance. answered 18 May '17, 16:06

You can implement it using the binary search tree with the method compareTo method in java.. Pretty fast answered 18 May '17, 17:16

Lexicographically sort both arrays (used a map<string, int=""> for this). Now insert each blocked site into the map of unblocked sites. You'll get upper/lower bounds in O(log n) time. Get the maximum sized prefix by comparing just 2 elements. Add this prefix to final list of filters. You only need to check if the new prefix is a prefix of the last added element in the list of filters or not. (since you took sorted arrays initially, you'll also get the filters sorted). Code answered 18 May '17, 17:19

I am using some help from the Java collections. I don't know why I am getting WA in only 2 of test cases. Can somebody help me? Link to my answer: https://www.codechef.com/viewsolution/13641286