[Community Puzzle] Palindromic Decomposition


#1

https://www.codingame.com/training/medium/palindromic-decomposition

Send your feedback or ask for help here!

Created by @kozuechan,validated by @bbb000bbbyyy,@Fireball0923 and @Niako.
If you have any issues, feel free to ping them.


#2

doc type! = html

shell09 Codingame

Got to level 5. Studying with mimo

I really understood this puzzle. Go on and make some more!


#3

This puzzle got me thinking…
The naive approach is relatively simple to implement but immediately falls in the big strings. So I went back to the drawing board.

I divided the puzzle to two problems: (1) find all palindromes in the given string, and (2) find all possible decompositions

Took some thinking, then I came up with a nice solution for (1) that executed fast enough.
I also came up with a solution for (2) which was almost(!) good enough. it solved all cases but the “long a” (a string of length 4000, all characters are ‘a’). This is of course a worst-case scenario, and I couldn’t find a generic algo that would solve it in the given time constraint. I ended up treating a uniform string as a special case, providing a mathematical formula based on the length of the string.

Submitted and got 100%

BUT (!!!) I keep thinking that this is not the “right” solution. I can easily see cases where my algo will not execute within the time constraints.

TL;DR :

  1. Well crafted puzzle. I enjoyed it
  2. What’s the complexity for the worst-case (uniform string) of the best possible algo? (actually, what would be considered here the best possible algo?)