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.

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.

doc type! = html

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

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 :

- Well crafted puzzle. I enjoyed it
- 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?)