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

×

TLE in Sheokand and String(SHKSTR)

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.

asked 12 Jun, 10:27

yogeshk972's gravatar image

4★yogeshk972
253
accept rate: 16%

edited 16 Jun, 17:00


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)

link

answered 17 Jun, 16:44

samsep10l's gravatar image

3★samsep10l
283
accept rate: 25%

YESS! thanks , it worked , and in the end your idea does make sense.

(17 Jun, 17:21) yogeshk9724★

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

(17 Jun, 17:40) yogeshk9724★

This is the same problem i am also geting

link

answered 16 Jun, 21:48

code__champ's gravatar image

3★code__champ
594
accept rate: 0%

edited 16 Jun, 21:48

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.

link

answered 17 Jun, 17:11

rs07's gravatar image

4★rs07
01
accept rate: 0%

actually i tried doing that eariler , but it still gave me TLE . but thanks bro.

(17 Jun, 17:27) yogeshk9724★
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:

×668
×179
×107
×41

question asked: 12 Jun, 10:27

question was seen: 174 times

last updated: 17 Jun, 17:40