11077 - Find the Permutations

[asif_rahman0]

Plz check my input/output. Is it OK?

Code: Select all

5 3
9 3
4 2
4 3
7 2
10 3
10 9
15 11
15 14
16 11
16 10
18 12
19 13
19 16
21 13
15 13
16 12
16 10
15 14
16 13
11 9
9 2
9 8
6 4
6 5
14 13
0 0

Output:

Code: Select all

50
4536
11
6
175
9450
362880
310989260400
87178291200
2706813345600
1009672107080
369012649234384
7551527592063024
34012249593822720
311333643161390660
283465647360
5056995703824
1009672107080
87178291200
6165817614720
10628640
546
40320
274
120
6227020800

[Nazmul Quader Zinnuree]

My AC gives the following Output.

Code: Select all

50
4536
11
6
175
9450
362880
310989260400
87178291200
2706813345600
1009672107080
369012649234384
7551527592063024
34012249593822720
311333643161390640
283465647360
5056995703824
1009672107080
87178291200
6165817614720
10628640
546
40320
274
120
6227020800

[Nazmul Quader Zinnuree]

Use 'unsigned long long'

There is some cases for "21 x" that do not fit in 63-bit.

[asif_rahman0]

thnx got accepted.

[Riyad]

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

[kp]

Yes, it can be solved in O(n*k)

Hint:
Let c[n][k] is the answer.
Try to find reccursion like

c[n][k] = Function(c[n-1][k],c[n-1][k-1])

[vinay]

Thanks kp..
The rest was easy to formulate...
I have started to love DP

[minskcity]

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.

[sclo]

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.

[Darko]

Use 'unsigned long long'

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 :(

[Stummer]

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.

You should output the number of permutations which requires at least
K swaps. In case

Code: Select all

3 0

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.

[minskcity]

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.

[Stummer]

[quote="minskcity]

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.

[mintae71]

Plz give me correct output of this input....

input

Code: Select all

1 0
2 0
2 1
3 0
3 1
3 2
4 0
4 1
4 2
4 3
5 0
5 1
5 2
5 3
5 4
6 0
6 1
6 2
6 3
6 4
6 5
7 0
7 1
7 2
7 3
7 4
7 5
7 6

[brianfry713]

1
1
1
1
3
2
1
6
11
6
1
10
35
50
24
1
15
85
225
274
120
1
21
175
735
1624
1764
720