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

×

Blocked websites Problem May Long

2
1

I solved the problem using Trie. It looks like my approach is correct but there is one test case failing. Here is the link of my submission. https://www.codechef.com/viewsolution/13622298

Tree Node structure is like this

struct TrieNode {

struct TrieNode *children[26];

bool acc;

bool nAcc;

bool leaf;

};

Here acc flag store whether that node comes under accessible category or not. Same is for nAcc flag for blocked websites. I think issue maybe in no solution condition. My code consider following case as no solution

2 - code + codef

Any help is much appreciated.

asked 18 May, 15:42

manishsingla's gravatar image

3★manishsingla
312
accept rate: 0%

edited 18 May, 22:40


Their is no need to use trie tree. Just take 2 sets one containing all blocked websites and other set containing all unblocked websites. Since sets are automatically arranged lexicographically , just take one blocked website and insert it into the set of unblocked websites.Now you only need to check for two websites only,the one after its position in set2 and the one before its position in set2. The longest same string L will be the answer and insert substring(L+1) itto into another set3. If the length found is equal to length of blocked website taken at that time simply print -1;

link

answered 18 May, 16:10

azad123's gravatar image

3★azad123
212
accept rate: 0%

thanks for your answer @azad123. Can you help me in debug my code?

(18 May, 22:42) manishsingla3★

Hey @manishsingla, your code fails in cases like these

3
- code
+ codech
- codechef

The problem lies here

if(root->children[i]!=NULL  && ( (root->children[i]->acc && root->children[i]->nAcc)
   || (root->children[i]->acc==false && root->children[i]->nAcc) ))
         break;

For the sample input I have provided, when the node e is reached, root->children[i]->acc && root->children[i]->nAcc is satisfied and the algorithm proceeds, whereas actually at this stage itself the no solution status should be detected. Hope this helps :)

link

answered 18 May, 23:04

meooow's gravatar image

5★meooow ♦
5.3k411
accept rate: 46%

edited 19 May, 23:52

@manishsingla, your code fails for this test case :

3 - c + co - com

Actually, test cases of above type did not exist in the small subtask. Basically, this test case for which your solution is failing is the one having -1 as the solution. I too had some trouble while solving this one.

Hope this helps you. BTW, my solution is same as yours. You may look into my solution in the editorial for more help.

link

answered 18 May, 23:03

likecs's gravatar image

6★likecs
3.2k736
accept rate: 9%

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:

×908
×164

question asked: 18 May, 15:42

question was seen: 454 times

last updated: 19 May, 23:52