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

Code: Select all

```
1
aaaabb 3
```

**Moderator:** Board moderators

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?

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

Code: Select all

```
1
aaaabb 3
```

is to determine the 3rd in lexicographic order palindrome which can be

formed using the given set of characters! (NB! You are given

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

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

can you throw some more light on how to use dp here? ThanksIvan 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.

If I will myself do hashing, then who will do coding !!!

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

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

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
```

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
```

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

Thank, in advanced.

ivan[/code]

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)

Try the folloeing input: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.

Code: Select all

```
1
taudsugtdgdrsuardll 62172
```

Code: Select all

`Case 1: gastdlurdudruldtsag`

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

Thank Martin. You found some another sample(s)?

Code: Select all

```
Code was remove, got AC. Thank to all for help received.
```

Last edited by ivan.cu on Sun Aug 27, 2006 9:51 am, edited 1 time in total.

I found the mistake, it's at the **canGenarate **method, the correct is:
Thank a lot Martin.

PD: Finally can use only long on all of methods, including factorial.

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;
}
```

PD: Finally can use only long on all of methods, including factorial.