[Community Puzzle] Palindromic Decomposition

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 Codingame

Got to level 5. Studying with mimo

I 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 :

  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?)
1 Like

i try it in brute force but failed in performance, so i decided to keep the brute force algorithm but add a pattern matcher for ‘ab’, ‘aab’, ‘aba’, ‘abba’, ‘ababa’, ‘aabaa’, because you can deduct the total palindroms by analyzing results… gl

The constraints here are a bit weird.
The first idea I implemented which was O(N^2) worked up to N = 3300 in Python so it would have obviously worked in C++ for example.
But to get those extra cases working in Python I had to over-optimize the whole thing. The complexity was still O(N^2) tho.

Now that I solved it I see that most Python solutions hardcode the case where all letters are similar cause they probably could’nt optimise enough.
And those who succed without hardcode either use my approach or another DP approach with more precalc but lighter structures.

So a bit of Python optimisation is ok but here it was really a bit too much for a medium puzzle, and a bit weird considering that a naive algorithm would work in faster languages.