WSITES01 - Editorial

editorial
, , ,
10

You can implement it using the binary search tree with the method compareTo method in java… Pretty fast

11

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
12

@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

13

Did it using Trie(2-D array implementation).
https://www.codechef.com/viewsolution/13598320

14

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

15

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

16

I implemented it using nested dictionaries. I realise this is inefficient, but can someone tell me what testcase mine isn’t working on ?

https://www.codechef.com/viewsolution/13598055

17

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…

18

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
19

this weird , the setter’s and tester’s solution link is just the link to editorial again

20

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

21

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 :smiley:

22

I’m pretty sure many people solved it using hashing too.(I’m one of them)

3 Likes
23

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
24

There you go :slight_smile:

25

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

26

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.

27

Thanks @vijju123

28

Yes. This editorial only has editorialist’s solution at the moment.

29

@vicennial Why did u choose

int p=31; for calculating

ans=(ans*p+(i-‘a’+2))%MOD;