11027 - Palindromic Permutation

[Darko]

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]

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]

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]

do we really have to generate all permutations upto n or is there a faster way

[Ivan]

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]

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

[david]

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]

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]

can somebody please post some test cases? thank you

[mamun]

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]

thanks mamun

[ivan.cu]

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]

[Martin Macko]

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]

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

[ivan.cu]

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.