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

asif_rahman0
 Experienced poster
 Posts: 209
 Joined: Sun Jan 16, 2005 6:22 pm
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 63bit.

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

Contact:
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[n1][k],c[n1][k1])

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

Contact:
Post
by vinay » Sat Sep 02, 2006 9:47 pm
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
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 comparisonbased 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 comparisonbased 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 64bit 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
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
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

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