OJ Board

Posted: **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

Posted: **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).

Posted: **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...

Posted: **Mon May 15, 2006 9:39 am**

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

Posted: **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.

Posted: **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

Posted: **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.

Posted: **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

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

Posted: **Tue May 16, 2006 10:29 pm**

can somebody please post some test cases? thank you

Posted: **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

Posted: **Fri May 19, 2006 2:59 pm**

thanks mamun

Posted: **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]

Posted: **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

Posted: **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)?

Posted: **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.

OJ Board

11027 - Palindromic Permutation

11027 - Palindromic Permutation

need some help

Help with my WA!!

Re: Help with my WA!!

The WA persist

i got AC