Blocked websites Problem May Long

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

2 Likes
2

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;

2 Likes
3

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

4

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

5

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

1 Like