How to solve DECORATE?

@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 http://en.wikipedia.org/wiki/Necklace_(combinatorics)

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.

4 Likes

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): http://en.wikipedia.org/wiki/Burnside’s_lemma

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

5 Likes

There’s also this which is practically a direct solution to the problem.

1 Like

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

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…

I wonder, is there any way to count the palindromes without using hashing?

2 Likes

is there any way to count the palindromes without using hashing?

@mugurelionut Well the theorem goes above me.

@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.

4 Likes

@mugurelionut can u please explain how you used hashing to achieve distinct palindromes?

2 Likes

i too want to know how to use hashing to achieve distinct palindromes.
@mugerelionut can u please explain this part?

P.S: i figured out the second part of the problem (counting the number of arrangements), but was struck in this part.

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

Pls. explain how to find the number of distinct subpalindromes using Manacher’s or Hashing.

Use manacher’s algorithm.

Why would you not use hashing? AFAIK it’s the simplest and nicest way to count palindromes…

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.

Use manacher’s algorithm.

Unique palindromes? Do you have a link to your code? Thanks!

@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!

freeman92: you’d see that I wrote it if you actually bothered reading this whole thread before posting

@xellos >> mybad! din’t see that earlier.