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

×

somebody pls explain the author soln for shkstr question of june challenge

asked 13 Jun, 18:15

gyanendra371's gravatar image

3★gyanendra371
2936
accept rate: 33%

i would be pleased if u add comment and explain by example @vijju123

(13 Jun, 18:16) gyanendra3713★

The author has used a solution which looks similar to this solution using tire .Have a note of the ascii values of '|' & '_' before looking into it [https://www.codechef.com/viewsolution/18782372]

link

answered 13 Jun, 18:56

eaugene's gravatar image

4★eaugene
445
accept rate: 20%

this link is not working

(13 Jun, 22:50) gyanendra3713★

Which part is unclear to you?

The addString function is kind of straightforward, although over-concisely done xD. The ptr variable is nothing but the node number. He is traversing the already added strings and adding character/nodes wherever applicable.

The query function is also simple. He will first traverse the try to $min(S.length(),Trie'sPathLength)$. If he didnt end up at a leaf node, he will go for the lexicographically smaller one. In simpler words, what he is doing is as

  1. If current character is in trie - Add it to ans and check for next one in children
  2. If the character is not present (or if entire string is found), break out and print lexicographically smallest (t.fin tells that a string ends with this character/node)

Theres actually nothing else to explain xD. What part is unclear to you?

link

answered 13 Jun, 21:05

vijju123's gravatar image

5★vijju123 ♦
14.9k11856
accept rate: 18%

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:

×164
×15

question asked: 13 Jun, 18:15

question was seen: 160 times

last updated: 15 Jun, 20:02