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

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.

anyone care to share more short test cases? My code seems to be working only for all short test cases and the long ones are too hard to debug.

I finally beat it. What a great puzzle. A real pick-me-up kind of feeling to 100% it.

Iâm not sure I understand the prompt.

It says âtuple of three stringsâŚâ. Does the decomposition need to be in tuples of 3 strings (as opposed to tuples of 5 strings, etc.)?

If so, how do I decompose a string like âaâ? For âaâ, the answer is 3, so are the 3 decompositions (e, e, a), (e, a, e), ( a, e, e)?

Does this explain why for âoopâ the answer is 4? I guess because (e, oo, p), (oo, e, p), (oo, p, e), (o, o, p)?

If, on the other hand, it can be tuples of any number of strings, then why canât we have (a, b, a, b) as an additional possibility in the example?

Thanks!

It says âtuple of three stringsâŚâ. Does the decomposition need to be in tuples of 3 strings (as opposed to tuples of 5 strings, etc.)?

Yes

If so, how do I decompose a string like âaâ? For âaâ, the answer is 3, so are the 3 decompositions (e, e, a), (e, a, e), ( a, e, e)?

Yes

Does this explain why for âoopâ the answer is 4? I guess because (e, oo, p), (oo, e, p), (oo, p, e), (o, o, p)?

Yes

1 Like

Perfect, thanks!

1 Like

Sadly, I implemented the O(N^2) was not wroking for me in C++. I forced the compiler to optimize the code and in the end I was not able to do it, the next step was maybe to work to never get a missing cache. But, I was telling myself I am trying doing it the wrong way because I use C++. I use a algo in O(N) like the Manacherâs Algorith. After that doing the second part for finding all the palaindromic triple combinasion, that was done in O(N^2) but in my head I can optimize this with a other O(N) on the result of Manacher, but I find that I already pass to much time to learn the Manacherâs Algorith for a medium puzzle.