can anyone help me in this problem , i am getting TLE in task 3 . I checked up the editorial and the approach seems almost similar. can anyone help?
here is the link to my submission.
Note - In the structure Node , mn is the minimum index of the string passing through it, and x is the index of the string ending at that leaf .
so mn is ids[0] and x is leaf_id if you co-relate solution with editor.
This is the same problem i am also geting
Try adding the strings in a set and then check if the string is already present in that set before inserting it in the trie. For ex: There are 2 strings abcdefghij, abcdefghij. Your prog will try to insert both of them but there’s no need to even traverse the trie in the second string. Try doing that and tell me if it fixes it. I’ve done this problem in Python so I don’t understand what you’ve done with str.pushback(‘a’+idx)
Yes, I can help you in this case, and it will perfectly remove the TLE case. In insert function you are putting the index of the string which ends in that node. It is correct but it can take a longer time if last index overwritten is very large and so you are getting TLE. You can store the Minimum value of coordinate of strings which ends there. For example, if string 3 and string 5 ends there you can put minimum of both. So, always put minimum of them . It will remove TLE. Hope this answer helps you. Best Wishes.
YESS! thanks , it worked , and in the end your idea does make sense.
actually i tried doing that eariler , but it still gave me TLE .
but thanks bro.
actually i am creating a string str and pushing char ch whenever it is the right time
here in my code, ch= ‘a’+idx, ‘a’ in ascii is 97
let me explain more by example. -
if idx=0, my ch = 97+0 (ascii) , ch=97 but ch is char so it will convert it into ‘a’
if idx=1, my ch = 97+1 , ch=98 again conversion will take place and it will become ‘b’
and so on…