Help in WSITES01 (Blocked Website)

I have tried to solve the question in a rather simple and straight forward way by maintaining separate arrays for blocked and unblocked sites and then sorting them both so the blocked sites are displayed in lexicographical order, before applying the logic but it says WA. I have gone through a few discussions and all above mentioned test cases yield the expected output in my solution. I wish to post a question but don’t have the required karma points. I would be obliged to get an upvote or answer to the problem.
In the code:-

array check stores the last index value of all possible filters for that particular blocked site

array final stores the last index value of the final filter to be displayed,

array pos stores which blocked site it is

Sorry if its complicated
please help
This is my solution

Your code fails here-

Input

4
- a
+ ab
+ abc
- abcde

Output 

1
abcd

Expected Output

-1

Reason- Cannot block ‘a’ without blocking good websites ‘ab’ and ‘abc’ as ‘a’ is a prefix to them .

To confused ones, its converted to question and later edited. Its showing only edited tho :confused:

sorry but i did not understand. Can you elaborate. Job is to print a filter for a blocked site satisfying the given conditions. So in the test case above there is no such filter for ‘a’ but ‘abcd’ is a prefix not equal to any unblocked site so why the output should be -1.
Thanks for converting to a question though.

vijju123 got it right.

@anishsamant,
The answer should be -1 because there does not exist a set of filters which when used satisfy the constraints of the problem.
Your program output 1 filter “abcd” which won’t be able to filter out “a” which it needs to do.

"Reason- Cannot block ‘a’ without blocking good websites ‘ab’ and ‘abc’ as ‘a’ is a prefix to them . " - vijju123

https://www.codechef.com/viewsolution/13638603 can someone help with my code

@ghemnis

input

3

  • c
  • co
  • code

output

1

co

but output should be -1

Their is an additional condition that ALL ‘-’ sites must be blocked. Since you cannot block ‘a’ without blocking the good sites, you cannot satisfy all conditions and hence will print -1.

I see your perspective. Take it this way - You cannot leave out the ‘-’ sites unblocked. And if blocking a ‘-’ site blocks a ‘+’ site as well, print -1. Hope this helps! :slight_smile:

I think I am understanding now:-
1)Job is to make sure none of the blocked sites are accessed and for that we need firewalls such that it secures all blocked sites.
2)number of firewalls will be less than or equal to the number of blocked sites.
AM I RIGHT???
just for clarification can you tell me the output if:-
1)we have site ‘-’ ‘x’ instead of ‘-’ ‘abcd’.
2)we have site ‘+’ ‘x’ instead of ‘+’ ‘ab’.
Thanks a lot for the help

In above output, replacing ‘abcde’ or ‘ab’ with x will have no effect, as we have to block “- a” and we cant block it without blocking “abc” (if ab is replaced by x).

Few test cases-

2

+lololol
-google

Output-

‘1
g’

Input

4

+google
+youtube
-goo
-jeop

Output

-1

In case you have extreme trouble in understanding, take one of the correct solutions, paste on codechefs ide, and run against your cases to see what output is needed. It will help clear your mind alot!! :slight_smile:

Ok so number of filters must be equal to the number of ‘-’ sites is it???
If not can you give a test case where number of filters is less than the number of ‘-’ sites. I saw an accepted solution and also ran a few test cases accordingly I made a change in my code. The edited code satisfies all the cases which you said were wrong for the previous code but still gives a wrong answer when i submitted in the practice section(Though 2 more testcases(in subtask 2) are correct now compared to previous).
Thanks for being so patient please check this.
https://www.codechef.com/viewsolution/13640898

No. Number of filters can be less. Heres an example-

3

  • google
  • youtube
  • youzzzzz

Output-

1
y

Since “y” the minimum common prefix to block both websites. Many test cases use this concept of common prefix, contest admin should had specified this explicitly.

so is it that the number of prefix will be less only if the prefix are same

for my code it prints 2 y y

It should print

1
y

instead of 2 y y

If prefixes are same, we reduce the count by 1 and print only once.

yes understood.
Thanks a lot for your patience. Extremely appreciated
Its finally successfully accepted in the practice section.
Thanks again

I am glad it helped dear :slight_smile:

I went through your submission you seem to get WA for two testcases
Here is one testcase which i had tried and gives wrong ans with your code.
7

  • codeing
  • coder
  • coderz
  • code
  • codemania
  • yellow
  • yellows
    expected -1.

Lol, dont worry dear, i solved it for full score now XD. How can i give others test cases for this problem if i cant figure out cases for my own code? :stuck_out_tongue: