Page 1 of 1
11077 - Find the Permutations
Posted: Sat Sep 02, 2006 4:43 pm
by 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
Posted: Sat Sep 02, 2006 4:56 pm
by 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
Posted: Sat Sep 02, 2006 4:59 pm
by Nazmul Quader Zinnuree
Use 'unsigned long long'
There is some cases for "21 x" that do not fit in 63-bit.
Posted: Sat Sep 02, 2006 5:07 pm
by asif_rahman0
thnx got accepted.
algorithm of 101077
Posted: Sat Sep 02, 2006 7:50 pm
by 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
Posted: Sat Sep 02, 2006 7:59 pm
by 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])
@kp
Posted: Sat Sep 02, 2006 9:47 pm
by vinay
Thanks kp..
The rest was easy to formulate...
I have started to love DP
Posted: Sun Sep 03, 2006 5:41 am
by 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.
Posted: Sun Sep 03, 2006 5:48 am
by sclo
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.
Posted: Mon Sep 04, 2006 10:58 am
by 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 :(
Posted: Wed Sep 06, 2006 2:53 pm
by Stummer
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
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.
Posted: Wed Sep 06, 2006 5:06 pm
by minskcity
Stummer wrote: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.
Posted: Thu Sep 07, 2006 2:47 pm
by 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.
Re: 11077 - Find the Permutations
Posted: Sat Sep 25, 2010 10:12 am
by 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
Re: 11077 - Find the Permutations
Posted: Sat Jan 14, 2012 8:06 pm
by 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