11027 - Palindromic Permutation

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11027 - Palindromic Permutation

Post by Darko » Mon May 15, 2006 7:59 am

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

Post by Ivan » Mon May 15, 2006 8:50 am

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
Location: Calgary, Canada

Post by Darko » Mon May 15, 2006 9:13 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... :(

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

need some help

Post by vinay » Mon May 15, 2006 9:39 am

do we really have to generate all permutations upto n or is there a faster way :oops:
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

Post by Ivan » Mon May 15, 2006 9:43 am

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.

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

Post by vinay » Mon May 15, 2006 10:04 am

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 :D
If I will myself do hashing, then who will do coding !!!

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Mon May 15, 2006 11:54 am

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

Post by Ivan » Mon May 15, 2006 1:30 pm

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

Post by fpavetic » Tue May 16, 2006 10:29 pm

can somebody please post some test cases? thank you

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

Post by mamun » Tue May 16, 2006 11:08 pm

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 10: cbdaebecfdggfaafggdfcebeadbc
Case 11: XXX

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

Post by fpavetic » Fri May 19, 2006 2:59 pm

thanks mamun

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

Help with my WA!!

Post by ivan.cu » Sun Aug 27, 2006 2:49 am

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..
Thank, in advanced.

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

User avatar
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!!

Post by Martin Macko » Sun Aug 27, 2006 3:59 am

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

Post by ivan.cu » Sun Aug 27, 2006 5:24 am

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

Post by ivan.cu » Sun Aug 27, 2006 9:43 am

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.

Post Reply

Return to “Volume 110 (11000-11099)”