11077 - Find the Permutations

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11077 - Find the Permutations

Post by asif_rahman0 » Sat Sep 02, 2006 4:43 pm

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

Post by Nazmul Quader Zinnuree » Sat Sep 02, 2006 4:56 pm

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

Post by Nazmul Quader Zinnuree » Sat Sep 02, 2006 4:59 pm

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

Post by asif_rahman0 » Sat Sep 02, 2006 5:07 pm

thnx got accepted. :)

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

algorithm of 101077

Post by Riyad » Sat Sep 02, 2006 7:50 pm

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

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Post by kp » Sat Sep 02, 2006 7:59 pm

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])

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

@kp

Post by vinay » Sat Sep 02, 2006 9:47 pm

Thanks kp..
The rest was easy to formulate...
I have started to love DP :wink:
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

Post by minskcity » Sun Sep 03, 2006 5:41 am

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sun Sep 03, 2006 5:48 am

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
Location: Calgary, Canada

Post by Darko » Mon Sep 04, 2006 10:58 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

Post by Stummer » Wed Sep 06, 2006 2:53 pm

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

Post by minskcity » Wed Sep 06, 2006 5:06 pm

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.

Stummer
New poster
Posts: 12
Joined: Sat Jul 01, 2006 12:16 pm
Location: Munich, Germany

Post by Stummer » Thu Sep 07, 2006 2:47 pm

[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

Post by mintae71 » Sat Sep 25, 2010 10:12 am

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11077 - Find the Permutations

Post by brianfry713 » Sat Jan 14, 2012 8:06 pm

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!

Post Reply

Return to “Volume 110 (11000-11099)”