## 11027 - Palindromic Permutation

Moderator: Board moderators

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am

### 11027 - Palindromic Permutation

I made an assumption about the input and my solution during the contest, of course, failed.

Before I start again - can I expect input like this one?

Code: Select all

``````1
aaaabb 3
``````

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria
The input: aaaabb 3 is absolutely correct. The question they are asking
is to determine the 3rd in lexicographic order palindrome which can be
formed using the given set of characters! (NB! You are given a set of characters, not a string!). Obviously:
1st palindrome is aabbaa;
2nd palindrome is abaaba;
3rd palindrome is baaaab;
4th palindrome does not exist, so in case of an input like aaaabb 4 you
should output XXX.
Hope this helps. (Indeed the problem description is not very clear).

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Actually, that's what I was afraid of, I don't know how to handle those

My assumption was that there would be at most 3 of each letter.

Well, back to the drawing board...

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

### need some help

do we really have to generate all permutations upto n or is there a faster way
If I will myself do hashing, then who will do coding !!!

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria
Actually, in my opinion, the problem is quite similar to problem 10581 "Partitioning for fun and profit"...
The general idea is to find the n-th lexicographic permutation of a set (when n is very large) which can be done using DP.

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:
Ivan wrote:Actually, in my opinion, the problem is quite similar to problem 10581 "Partitioning for fun and profit"...
The general idea is to find the n-th lexicographic permutation of a set (when n is very large) which can be done using DP.
can you throw some more light on how to use dp here? Thanks
If I will myself do hashing, then who will do coding !!!

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm
There's no need for DP here. You can easily compute how many permutations of a string start by a given letter, which allows you to determine what the first character of the nth permutation will be, and you can proceed likewise for the remaining letters. The resulting algorithm has O(string size^2) time complexity.

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria
Thanks david!
You can easily compute how many permutations of a string start by a given letter, which allows you to determine what the first character of the nth permutation will be, and you can proceed likewise for the remaining letters.
Actually I am doing exactly the same thing but I am using "ugly" DP with complexity of approximately (26 * 2 ^ (strlen / 2)). This runs in just below a second
I knew that my solution is not the brightest one, but didn't find a better way during the contest...
But the principle of both solutions is the same (as a hint for all those who haven't solve the problem yet).

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm
can somebody please post some test cases? thank you

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
Input

Code: Select all

``````11
a 1
a 2
ab 1
aa 1
aa 2
aas 1
aas 2
aabbccc 3
aaabbbcc 3
abcdefgabcdefgabcdefgabcdefg 214748364
abcdefgabcdefgabcdefgabcdefg 2147483647
``````
Output

Code: Select all

``````Case 1: a
Case 2: XXX
Case 3: XXX
Case 4: aa
Case 5: XXX
Case 6: asa
Case 7: XXX
Case 8: bacccab
Case 9: XXX
Case 11: XXX
``````

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm
thanks mamun

ivan.cu
New poster
Posts: 21
Joined: Sun Mar 19, 2006 7:50 pm
Location: Cuba

### Help with my WA!!

Some one can see where is my error, here is my code. I got WA and i can't found some WA sample input.

Code: Select all

``````See below..
``````

ivan[/code]
Last edited by ivan.cu on Sun Aug 27, 2006 5:25 am, edited 1 time in total.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: Help with my WA!!

ivan.cu wrote:Some one can see where is my error, here is my code. I got WA and i can't found some WA sample input.
Try the folloeing input:

Code: Select all

``````1
taudsugtdgdrsuardll 62172``````
My AC's output:

Code: Select all

``Case 1: gastdlurdudruldtsag``

ivan.cu
New poster
Posts: 21
Joined: Sun Mar 19, 2006 7:50 pm
Location: Cuba

### The WA persist

Now is correct for the sample above, but the WA persist.

Code: Select all

``````Code was remove, got AC. Thank to all for help received.
``````
Thank Martin. You found some another sample(s)?
Last edited by ivan.cu on Sun Aug 27, 2006 9:51 am, edited 1 time in total.

ivan.cu
New poster
Posts: 21
Joined: Sun Mar 19, 2006 7:50 pm
Location: Cuba

### i got AC

I found the mistake, it's at the canGenarate method, the correct is:

Code: Select all

``````long long canGenerate(){
long long den = 1;
long long num = 0;
for(int i = 0; i < cant_oc; i++){
num += ocurr[real_oc[i]] / 2;
[color=red]den *= fact( ocurr[real_oc[i]] / 2 );[/color]
}

return fact(num) / den;
}
``````
Thank a lot Martin.
PD: Finally can use only long on all of methods, including factorial.