is dp the obvious choice to go for this problem ?? and can some one tell me whats the complexity of the DP .....
is it O(nk) ???????????????
thanx in advance
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN
For each of the input, print in a line the number of permutations which will take at least K swaps.
Now, look at the test case#2... The way I see it, any of 3! = 6 permutations of 3 elements require at least 0 swaps to sort.
PS: n*log(n) lower bound has nothing to do with swapping and comes from comparison-based model.
minskcity wrote:From problem statement, output section:
For each of the input, print in a line the number of permutations which will take at least K swaps.
Now, look at the test case#2... The way I see it, any of 3! = 6 permutations of 3 elements require at least 0 swaps to sort.
PS: n*log(n) lower bound has nothing to do with swapping and comes from comparison-based model.
Yes, that's right, and it is confusing to me at first.
Why do people do this? I mean, seriously - what is wrong with limiting to signed 64-bit integers? Will it change the problem in any way? Yes, I submit mostly in Java. Yes, I should use the best tool for the job. And yes, this just tells me that not getting up for some contests is a good decision. But I really wanted to be proved wrong :(
the answer is 1 - the permutation 1 2 3, which does not requires some
swaps, i. e. it requires at least 0 swaps. If you can do at least x swaps in any permutation to sort it, x<n, because you know elements of permutation. Read the statement carefully.
I did read it carefully. And my English is good enough to know that 0, 1 and 2 all fall under definition "at least 0". I've got the problem AC'd long time ago.
number of permutations which will take at least K swaps
should be
number of permutations for which minimum number of swaps to sort is K
"at least" implies nothing about minimum.
Are you claiming that "1 3 2" does not require "at least 0 swaps" to sort it? Let me know how to sort it in less than 0 swaps then.
number of permutations which will take at least K swaps
should be
number of permutations for which minimum number of swaps to sort is K
"at least" implies nothing about minimum.
Are you claiming that "1 3 2" does not require "at least 0 swaps" to sort it? Let me know how to sort it in less than 0 swaps then.[/quote]
Ok, but I've no problem with problem statement. I understand that
at all.