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