[Community Puzzle] Palindromic Decomposition

[CommunityBot]

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.

[Shell09]

doc type! = html

shell09 Codingame

Got to level 5. Studying with mimo

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

[puma17]

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

[never-again]

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

[pardouin]

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.

[dzosz]

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.

[anon79121980]

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

[SpockyB]

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!

[5DN1L]

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

[SpockyB]

Perfect, thanks!

[Meradrin]

@pardouin

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.

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.

[jrl86]

Hi,

Very nice puzzle exploring multiple paths of optimizations.

Anyhow, I’m in difficulty to understand the decomposition I miss on the last test case (all letters).

There are:
- 1 with the complet string for 3 dec,
- 2 with respectively 1/3 + 2/3 and 2/3 + 1/3 of the string for 6 additionnal decs
- 3 for 1/3 + 1/3 + 1/3 for 1 additionnal dec.

So I don’t any other dec…

would anyone give me a hint as a gift ?

Thanks

[5DN1L]

Here are the decompositions for Test 11 “All letters”:

1. (ε, ε, entire string)
2. (ε, first 51 characters, remaining 102 characters)
3. (ε, first 102 characters, remaining 51 characters)
4. (ε, entire string, ε)
5. (a, middle 151 characters, a)
6. (first 51 characters, ε, remaining 102 characters)
7. (first 51 characters, middle 51 characters, remaining 51 characters)
8. (first 51 characters, remaining 102 characters, ε)
9. (first 102 characters, ε, remaining 51 characters)
10. (first 102 characters, remaining 51 characters, ε)
11. (entire string, ε, ε)

[jrl86]

haha thank you didn’t get the dec 5 … nice I think I’ll have the same for the other repetitive test cases once I’ll have found a way to get my code optimised in python…