You are not logged in. Please login at www.codechef.com to post your questions!

×

WSITES01 - Editorial

1
3

Problem Link

Practice

Contest

Author: Azat

Tester: Pawel Kacprzak and Misha Chorniy

Editorialist: Bhuvnesh Jain

Difficulty

EASY-MEDIUM

Prerequisites

Tries, State Transitions

Problem

You 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 non-blocked websites are. The aim is to minimise the sum of the length of the prefixes found.

Quick Explanation

Build a tries of the words, storing information regarding the words, their type (blocked or non-blocked). Use transitions during the traversal of trie (dfs) to find the optimal answer, if it exists.

Explanation

First 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 non-blocked 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 non-blocked 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 :

  1. Detecting whether the blocked website is a prefix of any non-blocked website.
  2. Finding efficiently the first point of difference between 2 websites names.

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.

  1. State 0 = no websites.
  2. State 1 = non-blocked websites only.
  3. State 2 = blocked websites only.
  4. State 3 = both blocked and non-blocked websites.

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 :

  1. Whenever, we make have a node at state $3$ and all of its children have state $\\{0, 1\\}$ only, we see that a blocked website is a prefix of a non-blocked website. Thus we should terminate our search here and claim that it is "impossible" to constrict an answer.
  2. Otherwise in all cases, the solution exist. To find the minimal length, whenever we see that a state $3$, has a child with states $\\{0, 1, 2\\}$, we are sure to have found a point of difference between the blocked websites and non-blocked websites. This is when we should stop are search together on this current branch and add the required prefix to our solution.
  3. Otherwise, the whole search space would only consist of wither blocked or non-blocked websites. This is easy as non-blocked website are not required to be searched. Also, for blocked websites, the $1^{st}$ character would only differentiate between the blocked and non-blocked website and thus we can terminate the search here too.

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

Setter's solution

Tester's solution

Editorialist solution

This question is marked "community wiki".

asked 18 May '17, 13:47

likecs's gravatar image

6★likecs
3.7k1774
accept rate: 9%

edited 18 May '17, 22:43

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

(20 May '17, 15:52) gaurav414u2★

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.

link

answered 18 May '17, 16:08

shashank96's gravatar image

1★shashank96
3409
accept rate: 0%

edited 18 May '17, 16:14

There you go :)

(18 May '17, 16:20) siddharthp5384★

What!! I just did it by 2 pointer technique. And I think most of the people would have used this method only or binary search as the number of submissions were > 1700 and surely a trie problem would get < 400-500 submissions at max.

link

answered 18 May '17, 15:13

mathecodician's gravatar image

5★mathecodician
2.6k1630
accept rate: 7%

edited 18 May '17, 15: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 :D

(18 May '17, 15:15) vijju123 ♦5★
3

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

(18 May '17, 15:23) vicennial6★
1

Well yes 2 pointer, binary search, hashing all are basically searching ways. So, my point was just that there were easier ways than tries.

(18 May '17, 15:31) mathecodician5★

@vicennial Why did u choose

int p=31; for calculating

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

(06 Aug, 17:00) deepak_0975★

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

link

answered 18 May '17, 15:23

yash_22's gravatar image

4★yash_22
213
accept rate: 0%

edited 18 May '17, 15:25

Simpler Approach: Lexographicaly sort both the arrays(representing elements to include/not).Then calculate the upper bound for each element you want to include in the other array. Code

link

answered 18 May '17, 15:15

ps_1234's gravatar image

4★ps_1234
593
accept rate: 0%

I did it using trie, brute force implementation using trie is sufficient!

link

answered 18 May '17, 15:19

neilit1992's gravatar image

3★neilit1992
1.1k13
accept rate: 20%

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

link

answered 18 May '17, 15:27

simha's gravatar image

4★simha
1515
accept rate: 0%

Does Codechef provide testcases? It would be helpful for knowing corner cases and debugging.

link

answered 18 May '17, 15:39

moiz_hussain's gravatar image

4★moiz_hussain
1
accept rate: 0%

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.

link

answered 18 May '17, 16:06

devilhector's gravatar image

3★devilhector
384
accept rate: 11%

edited 18 May '17, 16:08

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

link

answered 18 May '17, 17:16

sagar2009kumsr's gravatar image

1★sagar2009kumsr
234
accept rate: 0%

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

link

answered 18 May '17, 17:19

arvindpunk's gravatar image

4★arvindpunk
422
accept rate: 0%

@devilhector I could'nt point out the mistake in your code but i have use the same data structure Tries and Set https://www.codechef.com/viewsolution/13623829. u can see your self if its fairly understandable code. hope it help

link

answered 18 May '17, 19:17

abhishel's gravatar image

2★abhishel
383
accept rate: 10%

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

link

answered 18 May '17, 23:16

dusht0814's gravatar image

4★dusht0814
1945
accept rate: 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

link

answered 30 May '17, 22:33

darkhorse100's gravatar image

2★darkhorse100
1
accept rate: 0%

edited 30 May '17, 22:49

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.

(31 May '17, 00:50) vijju123 ♦5★

Thanks @vijju123

(31 May '17, 19:03) darkhorse1002★

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

link

answered 02 Jun '17, 02:19

shauryauppal's gravatar image

1★shauryauppal
1
accept rate: 0%

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

link

answered 02 Jun '17, 09:05

govindbose's gravatar image

4★govindbose
1
accept rate: 0%

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....

link

answered 28 Jun '17, 23:58

xamitksx's gravatar image

2★xamitksx
11
accept rate: 0%

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
link

answered 04 Jul '17, 11:10

xamitksx's gravatar image

2★xamitksx
11
accept rate: 0%

edited 04 Jul '17, 11:12

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

link

answered 13 Jul '17, 22:49

sonu_628's gravatar image

3★sonu_628
3378
accept rate: 8%

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

(13 Jul '17, 23:06) vijju123 ♦5★

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

link

answered 22 Nov '17, 21:57

tristatl's gravatar image

1★tristatl
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,006
×1,138
×176
×18

question asked: 18 May '17, 13:47

question was seen: 3,688 times

last updated: 22 Nov '17, 21:57