Help with Sheokand and String (SHKSTR)

june18

#1

Hi, my solution fails for 2 of the large test cases. I am unable to identify what’s wrong in my solution

https://www.codechef.com/viewsolution/18880600

Can someone please help me. Thanks a lot in advance :slight_smile:


#2

Although I do not code in python but still I think I can help you because during contest it happened to me as well that my first test case for large input did not pass. Now mistake that I did :- I will explain it through an example. Suppose strings are = abc,apple,pqr,baba,apple,xyz. Here you see apple is repeated twice. So initially in trie when a same word was getting repeated then the order of latest word was getting updated. In this case apple was updated to order number 5. So, when during execution for Integer R <= 4 even if apple was present in (1,4),it was overlooking it as it’s minimum value was updated to 5. I identified it and corrected the code and it got A.C (100 points). I just felt like sharing it with you as you may have done the same mistake.


#3

I’m sorry, I don’t fully understand what you mean by “order”. I don’t think duplicate strings cause any problems in my code (I might be wrong)

Could you give a test case that might break. Thank you.


#4

Example :-

5
pqr
apple
aryan
apple
xyz
2
3 abc
5 abc
Output : -
apple
apple
Suppose this is the test case so apple comes at 2nd position & 4th position
(so order = 2 & 4 ) in list of strings.You first check the output of this test case on your code. If it’s correct then you have not done the mistake that I did.
Advice:-If it’s giving WA it means your task is easy.Run a string generator on your 30 points code (if you applied a simple brute force before) as well on your optimized code(trie). And then check & match output of both the code.


#5

My code outputs correct answer for it. I don’t think duplicate strings are the problem. Thanks anyways rajankur :slight_smile: