Posted:

**Wed Oct 09, 2002 12:27 am**By the way, this is not NP-complete problem.

(Parts lenghts are bounded by 50).

(Parts lenghts are bounded by 50).

Page **2** of **4**

Posted: **Wed Oct 09, 2002 12:27 am**

By the way, this is not NP-complete problem.

(Parts lenghts are bounded by 50).

(Parts lenghts are bounded by 50).

Posted: **Mon Oct 28, 2002 7:24 pm**

Hi all! What's the idea behind the dynamic programming?

Thanx a lot!

Thanx a lot!

Adrian Kuegel wrote:My solution worked with an array with 100000 elements. So there are no more than 100000 parts in the input.

But how do you store the used solutions? I think this is your problem. I used another array of 100000 elements to memorize, which parts I had used and reset it after every step (that means after I had not found a solution with length n and had to look for a solution with length n+1).

Posted: **Sun Jan 19, 2003 3:06 pm**

these are test data I have:

9

12 12 12 11 11 11 10 10 10

48

3 7 8 4 1 1 6 3 6 1 5 5 8 4 8 2 7 6 3 3 8 5 6 7 4 8 6 6 8 5 8 3 3 5 5 4 1 8 3 1 2 7 1 6 2 6 8 8

38

2 6 6 8 7 4 1 8 4 1 4 4 3 3 2 3 3 4 6 8 8 7 2 4 1 1 5 8 4 7 6 5 1 3 3 3 1 6

9

5 2 1 5 2 1 5 2 1

4

1 2 3 4

9

2 2 2 2 2 2 2 3 3

40

1 1 2 2 2 2 2 2 3 3 3 4 4 4 4 5 6 7 7 7 8 8 8 9 9 11 11 11 12 12 12 13 14 14 15 16 21 22 35 40

10

21 14 13 11 9 6 4 3 2 1

and these are my output:

33

47

18

6

5

10

62

21

However, I had Wrong Answer judge after 6 sec of running.

I just worn out..

What's wrong?

Can you show me other test data?

below is my algorithm sketch:

1) read input

2) guess target stick length : a number can divide sum of input

3) verify target length : first fit and backtrack

a. number of subset = sum of input / target stick length

b. make all subset size = target stick length

use first fit: that is, blindly select first item of array

c. if fail, backtrack

. erase failed subset from item list

. generate subset of failed(size mismatch) subset

. add subset to the item list and retry until all subset tried

9

12 12 12 11 11 11 10 10 10

48

3 7 8 4 1 1 6 3 6 1 5 5 8 4 8 2 7 6 3 3 8 5 6 7 4 8 6 6 8 5 8 3 3 5 5 4 1 8 3 1 2 7 1 6 2 6 8 8

38

2 6 6 8 7 4 1 8 4 1 4 4 3 3 2 3 3 4 6 8 8 7 2 4 1 1 5 8 4 7 6 5 1 3 3 3 1 6

9

5 2 1 5 2 1 5 2 1

4

1 2 3 4

9

2 2 2 2 2 2 2 3 3

40

1 1 2 2 2 2 2 2 3 3 3 4 4 4 4 5 6 7 7 7 8 8 8 9 9 11 11 11 12 12 12 13 14 14 15 16 21 22 35 40

10

21 14 13 11 9 6 4 3 2 1

and these are my output:

33

47

18

6

5

10

62

21

However, I had Wrong Answer judge after 6 sec of running.

I just worn out..

What's wrong?

Can you show me other test data?

below is my algorithm sketch:

1) read input

2) guess target stick length : a number can divide sum of input

3) verify target length : first fit and backtrack

a. number of subset = sum of input / target stick length

b. make all subset size = target stick length

use first fit: that is, blindly select first item of array

c. if fail, backtrack

. erase failed subset from item list

. generate subset of failed(size mismatch) subset

. add subset to the item list and retry until all subset tried

Posted: **Wed Mar 26, 2003 7:08 am**

Does anybody know how to solve this problem without TLE....?

Posted: **Thu Mar 27, 2003 2:42 am**

This problem is really interesting and hard at the same time. It slowly leads me to **bin-packing** or **integer-partioning** problem ... which is NP-hard ... Most likely, my approach is not right ... could somebody give me a hint on this ...

Thanks a lot,

-turuthok-

Thanks a lot,

-turuthok-

Posted: **Fri Mar 28, 2003 12:47 pm**

is there any tricky case????

Posted: **Tue Apr 01, 2003 5:42 am**

Just an update, ... I've been trying to solve this problem using "backtracking". It sure involves a lot of optimization. But, so far, mine still got TLE.

Still can't think of any DP approach for this ... I definitely need some words of wisdom here ...

BTW, ...

I noticed that as of today, the time-limit for this problem is 10 seconds. I saw lots of AC-ed solutions took more than 10 seconds.

-turuthok-

Still can't think of any DP approach for this ... I definitely need some words of wisdom here ...

BTW, ...

I noticed that as of today, the time-limit for this problem is 10 seconds. I saw lots of AC-ed solutions took more than 10 seconds.

-turuthok-

Posted: **Tue Apr 01, 2003 8:08 am**

If judge don't rejudge this problem yet, it's possible, that in ranklist are solutions which took more then 10 sec of time. But after rejudgement they disappear

Dominik

Dominik

Posted: **Tue Apr 01, 2003 11:54 am**

Could somebody please confirm these input/outputs:

**Input**
**Output**
Is there any critical-input with at most 100 parts ... I know I got TLE >= 10 secs with inputs <= 100 from the judge. For above inputs, my solution gives the outputs pretty quick.

Thanks for any inputs/suggestions ...

-turuthok-

Code: Select all

```
100
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 1 1 1 1 3
100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 47
100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 49
100
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 47 47 47 47 49 49 49 49 49 49 49 49 49 49 49 49 49 49
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 49
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
```

Code: Select all

```
4662
54
74
4911
6
5
```

Thanks for any inputs/suggestions ...

-turuthok-

Posted: **Wed Apr 16, 2003 7:49 pm**

turuthok: your output is correct (or at least my accepted solution outputs the same).

Here are the test cases I used.

Output should be

Here are the test cases I used.

Code: Select all

```
57
50 49 48 43 32 29 28 17 14 13 12 12 9 8 6 28 29 12 32 48 40 8 13 9 49 12 43 17 14 50 2 3 3 2 1 2 37 30 19 2 31 3 12 31 31 23 9 5 49 4 23 49 43 50 25 24 8 8
10
21 14 13 11 9 6 4 3 2 1
48
3 7 8 4 1 1 6 3 6 1 5 5 8 4 8 2 7 6 3 3 8 5 6 7 4 8 6 6 8 5 8 3 3 5 5 4 1 8 3 1 2 7 1 6 2 6 8 8
38
2 6 6 8 7 4 1 8 4 1 4 4 3 3 2 3 3 4 6 8 8 7 2 4 1 1 5 8 4 7 6 5 1 3 3 3 1 6
```

Code: Select all

```
82
21
47
18
```

Posted: **Sun May 18, 2003 4:17 pm**

The problem must be solved by Backtracking.

Posted: **Tue May 20, 2003 2:14 pm**

How did you solve it? Can you share your method with us?

Thanks a lot!!

Thanks a lot!!

Posted: **Tue May 20, 2003 2:19 pm**

The problem can be solved by DP? That's interesting!!anupam wrote:i used dp but getting wa...

is there any tricky case????

What's your method?

Posted: **Thu May 22, 2003 12:26 pm**

Hello Adrian Kuegel!!

What is your method to solve this problem?

Can you share your method with us?

What is your method to solve this problem?

Can you share your method with us?

Posted: **Sat Aug 16, 2003 6:05 am**

Hi, I still can't figure out the problem.

My method is using recursion. and I always get TLE...

(but I think it is fast enough)

The following is my code. I hope you can give me some tips.

Thanks in advance.

[c]#include "stdio.h"

#include "stdlib.h"

#include "string.h"

#define MAX 200

int n,stick[MAX],howmany[MAX],target,yes,count,sum;

int newc,pp;

void sort_stick()

{

int i,j,p;

do{

p=0;

for(i=1;i<=count;i++)

if(stick[i-1]<stick*){*

stick[i-1]^=stick*^=stick[i-1]^=stick**;*

howmany[i-1]^=howmany*^=howmany[i-1]^=howmany**;*

p=1;

}

}while(p);

}

void recursive(int extra,int finishedstick,int total)

{

int i,j,k,tmp,restart=0;

if(total==target){

finishedstick++;

newc=finishedstick;

restart=1;

if( finishedstick>=pp-1 ) yes=1;

}else if( total>target )

return;

if( yes ) return;

j=total;

for(i=extra;i<=count;i++)

if(howmany*>0){*

j+=stick**howmany**;*

if(j>=target) break;

}

if(j<target) return;

for(i=extra;i<=count;i++){

if(howmany*<=0) continue;*

if( (j=restart?stick*:total+stick[i])>target ) continue;*

tmp=howmany[i];

howmany[i]--;

recursive(restart?0:i,finishedstick,restart?stick[i]:total+stick[i]);

if( yes ) return;

howmany[i]=tmp;

if(restart||total+stick[i]==target)

return;

}

}

void main()

{

int N,i,tmp,j,k,minlen;

for( ; ; ){

scanf(" %d ", &n );

if(!n) break;

count=-1;

memset(howmany,0,sizeof(howmany));

minlen=0;

for( i=sum=0 ; i<n ; i++ ){

scanf("%d",&tmp);

if(tmp>minlen) minlen=tmp;

sum+=tmp;

k=0;

for(j=k=0;j<=count;j++)

if( stick[j]==tmp ){

howmany[j]++;

k=1;

break;

}

if(!k){

count++;

stick[count]=tmp;

howmany[count]=1;

}

}

sort_stick();

for(i=minlen;i<=sum;i++){

if(sum%i) continue;

target=i;

pp=sum/i;

yes=0;

recursive(0,0,0);

if(yes) {

printf("\n");

break;

}

}

}

}[/c]

My method is using recursion. and I always get TLE...

(but I think it is fast enough)

The following is my code. I hope you can give me some tips.

Thanks in advance.

[c]#include "stdio.h"

#include "stdlib.h"

#include "string.h"

#define MAX 200

int n,stick[MAX],howmany[MAX],target,yes,count,sum;

int newc,pp;

void sort_stick()

{

int i,j,p;

do{

p=0;

for(i=1;i<=count;i++)

if(stick[i-1]<stick

stick[i-1]^=stick

howmany[i-1]^=howmany

p=1;

}

}while(p);

}

void recursive(int extra,int finishedstick,int total)

{

int i,j,k,tmp,restart=0;

if(total==target){

finishedstick++;

newc=finishedstick;

restart=1;

if( finishedstick>=pp-1 ) yes=1;

}else if( total>target )

return;

if( yes ) return;

j=total;

for(i=extra;i<=count;i++)

if(howmany

j+=stick

if(j>=target) break;

}

if(j<target) return;

for(i=extra;i<=count;i++){

if(howmany

if( (j=restart?stick

tmp=howmany[i];

howmany[i]--;

recursive(restart?0:i,finishedstick,restart?stick[i]:total+stick[i]);

if( yes ) return;

howmany[i]=tmp;

if(restart||total+stick[i]==target)

return;

}

}

void main()

{

int N,i,tmp,j,k,minlen;

for( ; ; ){

scanf(" %d ", &n );

if(!n) break;

count=-1;

memset(howmany,0,sizeof(howmany));

minlen=0;

for( i=sum=0 ; i<n ; i++ ){

scanf("%d",&tmp);

if(tmp>minlen) minlen=tmp;

sum+=tmp;

k=0;

for(j=k=0;j<=count;j++)

if( stick[j]==tmp ){

howmany[j]++;

k=1;

break;

}

if(!k){

count++;

stick[count]=tmp;

howmany[count]=1;

}

}

sort_stick();

for(i=minlen;i<=sum;i++){

if(sum%i) continue;

target=i;

pp=sum/i;

yes=0;

recursive(0,0,0);

if(yes) {

printf("\n");

break;

}

}

}

}[/c]