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

×

Sheokand and String(SHKSTR) TLE

While solving this question I first used a Map (Key: Character, Value: TrieNode) to solve the problem. Considering O(1) insertion and lookup, my code should not have resulted in TLE but when I used an array of length 26 to store trie nodes, the code got accepted. So should I avoid using maps or dictionaries in CP and why? Is this because its time complexity for insertion and lookups is not exactly O(1)?

Solution using Map: 30 points

Solution using array of length 26: 100 points

asked 12 Jun, 11:20

baap_42's gravatar image

3★baap_42
11
accept rate: 0%

edited 12 Jun, 11:33


The $O(1)$ doesn't mean it is fast enough.... The time taken by earth for one revolution around the sun is $O(1)$
infact everything periodic is O(1)... As the time took by earth to revolve around sun won't change by the "current year"
and hence it is $O(1)=constant$. Even time taken for rotation is also $O(1)$. So understand there is a difference between both O(1)'s. Both are constant.. but one constant is large enough... And another is not..
Hence my advice is not to use map set unnecessarily... Use them whenever they are required...
Map and sets are meant when "n" is large enough so u need something that doesn't take more time with more "n" and hence maps and sets were useful.. but for 26 characters it is not useful at all

link

answered 12 Jun, 12:43

l_returns's gravatar image

5★l_returns
1.2k19
accept rate: 27%

edited 12 Jun, 12:46

Consider using even faster IO for both reading and writing.

I submitted your code with my even faster IO. Your code with my IO. Notice the difference in speed. I haven't gone through your code, but I solved this using Map(Character, TrieNode) myself. You can have a look at my soln here code. Have added useful messages. Let me know if you face issues!

link

answered 12 Jun, 14:02

kukreja_vlk's gravatar image

4★kukreja_vlk
603
accept rate: 25%

1

@l_returns also has a valid point. Some questions really need to you squeeze the bajezuz out of the hardware. CHSIGN in prev month competition required a lot of optimisation (not related to core logic). You can continue using maps. However if you notice that 1 or 2 are TLE and AC ones are close to Time Limit, consider using alternatives like arrays (or perhaps a better logic <- No shit @kukreja_vlk)

(12 Jun, 14:08) kukreja_vlk4★
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:

×1,237
×179
×41
×29
×15

question asked: 12 Jun, 11:20

question was seen: 157 times

last updated: 12 Jun, 14:08