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

×

[closed] 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

asked 20 May, 00:53

anishsamant's gravatar image

3★anishsamant
12
accept rate: 0%

closed 21 May, 00:50

vijju123's gravatar image

5★vijju123 ♦
11.3k315

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

(20 May, 01:09) vijju123 ♦5★

The question has been closed for the following reason "The question is answered, right answer was accepted" by vijju123 21 May, 00:50


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 .

link

answered 20 May, 01:06

vijju123's gravatar image

5★vijju123 ♦
11.3k315
accept rate: 18%

edited 20 May, 01:07

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.

(20 May, 01:19) anishsamant3★

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! :)

(20 May, 11:12) vijju123 ♦5★

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

(20 May, 13:23) anishsamant3★

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

(20 May, 13:47) vijju123 ♦5★

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!! :)

(20 May, 13:48) vijju123 ♦5★

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

(20 May, 15:15) anishsamant3★

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.

(20 May, 15:18) vijju123 ♦5★

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

(20 May, 15:23) anishsamant3★

for my code it prints 2 y y

(20 May, 15:24) anishsamant3★

It should print

1 y

instead of 2 y y

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

(20 May, 15:28) vijju123 ♦5★

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

(20 May, 16:20) anishsamant3★

I am glad it helped dear :)

(20 May, 16:23) vijju123 ♦5★

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.

(20 May, 16:39) anishsamant3★

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? :p

(20 May, 16:43) vijju123 ♦5★
showing 5 of 14 show all

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

link

answered 20 May, 01:44

ellipse0934's gravatar image

2★ellipse0934
213
accept rate: 0%

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

link

answered 20 May, 04:29

ghemnis's gravatar image

3★ghemnis
1
accept rate: 0%

@ghemnis

input

3 + c - co + code

output

1

co

but output should be -1

link

answered 20 May, 09:52

rdfan19's gravatar image

3★rdfan19
242
accept rate: 50%

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:

×164

question asked: 20 May, 00:53

question was seen: 507 times

last updated: 21 May, 00:50