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.
I did it using tries, normal tries and it gets accepted.
Here is my solution CodeChef: Practical coding for everyone
Also can you guys please vote my post. I need karma for posting questions.
8 Likes
You can implement it using the binary search tree with the method compareTo method in java… Pretty fast
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).
[1]
[1]: https://www.codechef.com/viewsolution/13600585@devilhector I could’nt point out the mistake in your code but i have use the same data structure Tries and Set CodeChef: Practical coding for everyone. u can see your self if its fairly understandable code. hope it help
Hi,
Please help me out, as I was unable to identify for which test case my code is failing. My code was unable to pass two test cases. Kindly have a look & suggest link to solution is : code
https://www.codechef.com/viewsolution/13976703
Can any one tell me any tc on which this soln fails???
I have tried alot to solve this problem
I implemented it using nested dictionaries. I realise this is inefficient, but can someone tell me what testcase mine isn’t working on ?
Hi
I am using Trie for solving this… Total 3 TCs are failing . Could somebody help me…
https://www.codechef.com/viewsolution/14361002
Please help me…
Hi I have tried all below TCs all are running fine . but I am getting WA in two TCs Please suggest any TC which I am missing
4
+ youtube
+ abcd
+ abcdchef
+ zzyy
Output
0
//// all negative
5
- abcdchef
- youtube
- youtubeisbest
- google
- googled
Output :
3
a
g
y
/// show strings in sorted order
6
+ google
+ googld
- googles
- googlea
- googlds
- googldr
OUTPUT :
4
googldr
googlds
googlea
googles
/////////
Any mathched -ve string shorter then positive
4
+ google
+ googld
- goog
- googles
OUTPUT :
-1
//////
Any mathched +ve string Longer then negative
3
- goog
- googles
+ google
OUTPUT :
-1
//same string its not allowed but still i checked this
2
- abc
+ abc
OUTPUT
-1
enter code here
1 Like
this weird , the setter’s and tester’s solution link is just the link to editorial again
Hi，anyone can help me figure out the problem below ?
the only difference for this two solution is
int n;
char c;
scanf("%d",&n);
for(int i = 0; i < n; i++)
{
getchar();
c = getchar();
cin >> s;
and
int n;
char c;
scanf("%d",&n);
for(int i = 0; i < n; i++)
{
cin >> c >> s;
the first one gets wrong answer, but the second one gets accepted.
the first solution link text
the second solution link text
but in local enviroment, I tested the first one , it can input and output normally with the samples.
thanks XD
I was actually about to ask you on mail on how you did it. I always look forward to @meoow and your solutions on any problem 
I’m pretty sure many people solved it using hashing too.(I’m one of them)
3 Likes
Well yes 2 pointer, binary search, hashing all are basically searching ways. So, my point was just that there were easier ways than tries.
1 Like
There you go 
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
Try this-
Input 1:
4
- codechef
- coded
+ coder
+ codechefu
Input 2:
3
- codechef
- coded
+ codechefu
Expected output is -1 for both, your program doesnt print that.