## 11077 - Find the Permutations

Moderator: Board moderators

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

### 11077 - Find the Permutations

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

New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Contact:
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
``````

New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Contact:
Use 'unsigned long long'

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

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
thnx got accepted.

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

### algorithm of 101077

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) ???????????????
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
Yes, it can be solved in O(n*k)

Hint:
Try to find reccursion like

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

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

### @kp

Thanks kp..
The rest was easy to formulate...
I have started to love DP
If I will myself do hashing, then who will do coding !!!

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
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.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
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
New poster
Posts: 12
Joined: Sat Jul 01, 2006 12:16 pm
Location: Munich, Germany
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.
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.
Obersturmfuhrer H. Stummer

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
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
New poster
Posts: 12
Joined: Sat Jul 01, 2006 12:16 pm
Location: Munich, Germany
[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.
Obersturmfuhrer H. Stummer

mintae71
New poster
Posts: 18
Joined: Tue Jan 19, 2010 10:50 am

### Re: 11077 - Find the Permutations

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11077 - Find the Permutations

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
Check input and AC output for thousands of problems on uDebug!