@all please discuss your approaches for the DECORATE question.
I’ve gone through the Manacher’s algorithm to find the number of palindromes.But after that how to solve the combinatorial problem?
What I could deduce while trying to solve the question was to find the number of ways for-
seating n distinct objects around a round table with k seats(where clockwise and anti-clockwise arrangements are same) where each object can have any number of copies.here n is the number of distinct palindromes in the string T and k is the number of bouquets.I got hold of this link after the contest was over Necklace (combinatorics) - Wikipedia
But how do we arrive on such formulas.Or is there a simpler approach to this question?
My knowledge of basic combinatorics could only tell me that if there are n distinct objects around a round table with n seats and clockwise and anti-clockwise are same then number of ways is (n-1)!/2.
I went through the codes of people who passed but couldn’t understand the combinatorial part.
I don’t think there is a simple approach to this problem (which consists of 2 distinct problems - counting the number of distinct palindromes and counting the number of arrangements). The first part can be solved in several ways (I used hashing), while for the second part I used the Cauchy-Frobenius lemma (also known as Burnside’s lemma): Burnside's lemma - Wikipedia
This theorem allows you to solve a more general class of problems: counting problems in which you have equivalence classes based on certain conditions (e.g. rotations, reversals, etc.).
The problem of this problem is that it’s well googlable (after getting through the lengthy problem statement and understanding that you just need the number of distinct palindromes and N for computing the result):
Number of bracelets. Afterwards, you just need to handle large numbers (Wolfram Alpha claims the largest possible results to have some thousands of digits), and it’s problem solved
I don’t think I would’ve been able to derive the formula all on my own (from elementary math), I was really just able to solve it thanks to finding this. I wonder how many other people were in the same situation…
@jaskaran_1: I know what you mean. It takes some effort to “map” the theorem to the current problem and understand what needs to be done. I would gladly explain more, but maybe we should wait for the editorial, which might contain all the needed explanations. I wouldn’t want to duplicate the explanations here, particularly since they are not trivial.
I did the hashing, but couldn’t solve the combinatorics part. The hashing I did was just to use a hashmap from java to keep track of all the palindromes found in Manacher’s algorithm (whenever there was a new expansion, try adding it to the hashmap).
I’m really looking forward to reading something explaining how to use Burnside’s Lemma to solve it though (and it seems the editorial for this is just abandoned).
Construct polynomial hashes of string s and of the reverse of s. Handle palindromes of even and odd length separately; the formulas don’t differ much. For every index i, bin-search the largest palindrome which has s[i] as its center character (for odd length) or just-before-the-center char (even length). You can check if there’s a palindrome of length l by comparing a hash and reverse hash of substrings.
If you need distinct palindromes, store their hashes in a set<>, add them starting from the longest and stop when you find out that you’ve already seen this hash.
@xellos >> can u explain how to use hashing to count distinct palindromes? I tried to hash the sub-strings obtained through Manacher’s algorithm and got TLE!
