Sheokand and String(SHKSTR) TLE

general
, , , ,
1

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

2

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

3

Consider using even faster IO for both reading and writing.

I submitted your code with my even faster IO. [Your code with my IO][1]. 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


[2]. Have added useful messages. Let me know if you face issues!


  [1]: https://www.codechef.com/viewsolution/18878084
  [2]: https://www.codechef.com/viewsolution/18878178
4

@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)

1 Like