10581 - Partitioning for fun and profit

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

Moderator: Board moderators

sunhong
New poster
Posts: 19
Joined: Sat Apr 12, 2003 6:13 pm
Location: China

10581 - Partitioning for fun and profit

Post by sunhong »

I got several WA.But I can't find any mistake in my algorithm.
Is there some trick in the problem?
Can anyone give me some testdata please?

gawry
New poster
Posts: 19
Joined: Fri Aug 02, 2002 5:54 pm

Post by gawry »

I don't think there are any tricks in this problem. Try this input:
3
220 10 1234567
100 2 49
220 5 132345
output should be:
1
1
1
1
2
11
42
42
59
60
49
51
2
26
58
60
74

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

10581

Post by windows2k »

I don't know how to solve the problem.
Could someone give me some hints?
Thx :P

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak »

I used DP to store a 3D table, storing in how many ways using M numbers, starting from I, and sum up to S. After constructing the table, can determine each individual number starting from left to right. I cannot think of a better way (likely due to limited ability/knowledge), though I believe there exists one.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Some cases...

Input:

Code: Select all

5
220 10 50
220 2 31
12 3 4
19 5 3
35 11 11
Output:

Code: Select all

1
1
1
1
1
1
1
1
50
162
31
189
1
4
7
1
1
1
3
13
1
1
1
1
1
1
1
1
1
11
15
Hope these help.
Ami ekhono shopno dekhi...
HomePage

chuzpa
New poster
Posts: 33
Joined: Fri Jun 18, 2004 8:39 am
Location: Mexico
Contact:

thanks!

Post by chuzpa »

They did help, thanks a lot ! I've got Acc. I was misunderstanding the problem.

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

some more test cases

Post by Riyad »

i am getting WA in this problem. could anyone provide more testcases. boundary cases would be very nice. i got correct results for all the above i/o. please help....
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

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

Post by Riyad »

can't get AC still :( can anyone please help. below is my code

Code: Select all

# include <stdio.h>
# include <assert.h>

typedef long long i64 ; 
i64 memo[250][20];

i64 go( int sum , int n ){
	i64& ret = memo[sum][n];
	if(ret !=-1) return ret ; 
	if( !sum && !n ) return ret = 1 ; 
	ret = 0 ; int i ;  
	for( i = 1 ; i <= sum && n > 0 ; ++i ){
		ret += go( sum - i , n - 1 ) ; 
	}return ret ; 
}
void doit( int sum , int n , i64 idx){
	if( !sum && !n ) return ; 
	int i ; 
	i64 ret ; 
	for( i= 1 ; i <= sum ;++i ){
		ret = go( sum - i , n - 1 ) ; 
		if( ret >= idx ){
			printf("%d\n",i);
			doit(sum - i , n - 1 , idx ) ; 
			return ; 
		}
		else{
			idx-= ret ; 
		}
	}
}
int main(){
	int sum , n ;
	i64 idx ; 
	int kase , i , j ; scanf("%d",&kase);
	
	for(i=0;i<=221;++i){
		for(j=0;j<=12;++j){
			memo[i][j]=-1;	
		}
	}
	while(kase--){
		scanf("%d %d %lld",&sum,&n,&idx);
		doit( sum , n , idx ) ; 
	}
	
	return 0 ; 
}
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Try the cases.

Input:

Code: Select all

3
61 8 52
101 8 64
111 6 66
Output:

Code: Select all

1
1
1
1
1
2
26
28
1
1
1
1
1
2
18
76
1
1
1
2
14
92
Hope these help.
Ami ekhono shopno dekhi...
HomePage

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

I/O

Post by Riyad »

but i get this output for your input. could you tell what am i doing wrong?please help.....

Code: Select all

1
1
1
1
1
1
52
3
1
1
1
1
1
1
64
31
1
1
1
1
66
41
what is ur output for

Code: Select all

10 4 10
i get

Code: Select all

1
2
3
4
is it right????
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: I/O

Post by Jan »

Riyad wrote:what is ur output for

Code: Select all

10 4 10
i get

Code: Select all

1
2
3
4
is it right????
Nope. 10 4 10 is not a valid input. Try 10 4 6. You should get the output you have posted.
Ami ekhono shopno dekhi...
HomePage

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol »

Jan ,

I am confused with ur output for the input : 61 8 52

Your output :

1
1
1
1
1
2
26
28

but i got same as Riyad bhai :

1
1
1
1
1
1
52
3

i could print the total sequences :

1 -> 1 1 1 1 1 1 1 54
2 -> 1 1 1 1 1 1 2 53
3 -> 1 1 1 1 1 1 3 52
4 -> 1 1 1 1 1 1 4 51
5 -> 1 1 1 1 1 1 5 50
6 -> 1 1 1 1 1 1 6 49
7 -> 1 1 1 1 1 1 7 48
8 -> 1 1 1 1 1 1 8 47
9 -> 1 1 1 1 1 1 9 46
10 -> 1 1 1 1 1 1 10 45
11 -> 1 1 1 1 1 1 11 44
12 -> 1 1 1 1 1 1 12 43
13 -> 1 1 1 1 1 1 13 42
14 -> 1 1 1 1 1 1 14 41
15 -> 1 1 1 1 1 1 15 40
16 -> 1 1 1 1 1 1 16 39
17 -> 1 1 1 1 1 1 17 38
18 -> 1 1 1 1 1 1 18 37
19 -> 1 1 1 1 1 1 19 36
20 -> 1 1 1 1 1 1 20 35
21 -> 1 1 1 1 1 1 21 34
22 -> 1 1 1 1 1 1 22 33
23 -> 1 1 1 1 1 1 23 32
24 -> 1 1 1 1 1 1 24 31
25 -> 1 1 1 1 1 1 25 30
26 -> 1 1 1 1 1 1 26 29
27 -> 1 1 1 1 1 1 27 28
28 -> 1 1 1 1 1 1 28 27
29 -> 1 1 1 1 1 1 29 26
30 -> 1 1 1 1 1 1 30 25
31 -> 1 1 1 1 1 1 31 24
32 -> 1 1 1 1 1 1 32 23
33 -> 1 1 1 1 1 1 33 22
34 -> 1 1 1 1 1 1 34 21
35 -> 1 1 1 1 1 1 35 20
36 -> 1 1 1 1 1 1 36 19
37 -> 1 1 1 1 1 1 37 18
38 -> 1 1 1 1 1 1 38 17
39 -> 1 1 1 1 1 1 39 16
40 -> 1 1 1 1 1 1 40 15
41 -> 1 1 1 1 1 1 41 14
42 -> 1 1 1 1 1 1 42 13
43 -> 1 1 1 1 1 1 43 12
44 -> 1 1 1 1 1 1 44 11
45 -> 1 1 1 1 1 1 45 10
46 -> 1 1 1 1 1 1 46 9
47 -> 1 1 1 1 1 1 47 8
48 -> 1 1 1 1 1 1 48 7
49 -> 1 1 1 1 1 1 49 6
50 -> 1 1 1 1 1 1 50 5
51 -> 1 1 1 1 1 1 51 4
52 -> 1 1 1 1 1 1 52 3 -> (my output)

is the ordered sequence right ? or somethng is wrong there ??
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Read the description again.
A partition of a positive integer number m into n elements (n ≤ m) is a sequence of positive numbers a1,...,an such that a1+...+an = m and a1 ≤ a2 ≤ ... ≤ an.
Check line 28

Code: Select all

28 -> 1 1 1 1 1 1 28 27
'a1 ≤ a2 ≤ ... ≤ an' but 28>27. So, it's not a valid configuration.

Hope these help.
Ami ekhono shopno dekhi...
HomePage

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol »

got u .

thanks yaar . i am getting bored of these sorts of silly mistakes :oops:
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

SHAHADAT
New poster
Posts: 23
Joined: Thu Jun 22, 2006 8:55 am
Location: sust,bangladesh

Post by SHAHADAT »

CAN ANYBODY TELL ME WHAT IS THE MAXIMUM VALUE OF K?
I AM GETTING TLE
-------------- ASHA TAR AKMATRO VHELA.

Post Reply

Return to “Volume 105 (10500-10599)”