307 - Sticks

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

Moderator: Board moderators

lundril
New poster
Posts: 6
Joined: Tue Mar 19, 2002 2:00 am
Contact:

307: Sticks (NP Complete ?)

Post by lundril » Thu Apr 25, 2002 2:33 pm

After getting a "memory exceeded" I ask myself:

Is this Problem NP Complete, and is my heuristic simply not good enough
or am I to stupid to see the trick.

At the moment I basically use dynamic programming. (I try to iterativly
build up the original sticks from the stick fragments, and store the solutions
of the already checked combinations.)

It would be nice to know the maximum number of stick fragments which
are used in the (secret) input. (This way it would be much easier to generate
realistic sample data for checking my code...)

so long
lundril

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Apr 25, 2002 7:30 pm

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

lundril
New poster
Posts: 6
Joined: Tue Mar 19, 2002 2:00 am
Contact:

Post by lundril » Fri Apr 26, 2002 1:06 am

Ok, so I AM to stupid :-)

I obviously miss some important aspect of the problem, because
I am VERY sure that my solution won't work with 100000 sticks,
even tuned as hell... (So I have to think a lot harder about this... sigh
somehow I don't get it...)

so long
lundril

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Fri Apr 26, 2002 4:44 am

Why doesn't this algorithm work?
[cpp]
#include <cstdio>

void main()
{
int i,j,k,N,S,m;

while(scanf("%d",&N)!=EOF&&N)
{
S=0;
m=0;
for(i=0;i<N;i++)
{
scanf("%d",&k);
S+=k;
if(k>m)
{
m=k;
}
}
for(i=m;i<=S;i++)
{
if(S%i==0)
{
printf("%d\n",i);
break;
}
}
}
}[/cpp]

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Apr 26, 2002 9:24 am

It doesn't work, because there can be this input:
4
4 3 3 2

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Fri Apr 26, 2002 12:31 pm

Thanks! That's the exact case I was looking for. I guess I will use match checking to confirm each "i".

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra » Thu Jun 20, 2002 3:19 pm

Hi!

I wonder if there is any algoritm that can solve this problem without checking a mtch for every i...

because this can take a quite a long time and I wonder how it is possible to solve it in less then 1 second...

If anyone knows this algoritm please reply...

Thanks a lot :)

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

Any tips for problem 307?

Post by mido » Sat Jun 22, 2002 1:54 am

Nothing else to say...it's just that I have been working on this thing for some time...no success till now...trying to use recursion to solve this problem.Any suggestions? :-?

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

input needed

Post by xenon » Fri Jul 05, 2002 4:03 pm

Hi,

I'm in dire need of some discriminative input. My program works for all cases I can think of, but I'm still getting WAs. I will not publish my code because I think (I hope) it would be a spoiler.
Many thanks in advance,

-xenon

Archangel
New poster
Posts: 29
Joined: Wed Jun 26, 2002 9:00 am

WA 307 sticks

Post by Archangel » Sun Sep 15, 2002 12:00 pm

Can anybody help me what the flaw of algorithm I used in this problem? :cry:

1.read in all sticks, store them in a array and sort them in a decreasing order according to their length.
2.when reading in the sticks, I also use a variable to record the maximum length stick and sum of all sticks length.
3.starting from the maximum length, I use a example to describ:

Sample input
7
2 4 6 5 1 10 11

my algorithm

read in->sort(11 10 6 5 4 2 1)->check

sum of all element = 39.so we only need to check 13,39(because 1 and 3 to smaller than maximum element(11))

-> first we check 13.
search the array from the begin index,so we can have (11,2).mark 11 and 2 as used element(when next search we should skip them) and then keep search.when we select 10,we can not find a unselected number to make their sum = 13,so break, answer is not be found yet and increse the maximum length,reset all sticks to unused.
->second we check 39,following the rule above, we can find (11,10,6,5,4,2,1),so answer is found.

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin » Sun Sep 15, 2002 3:56 pm

That looks all well and good. It should at least in theory provide the correct answer, but it might be too slow... you need to optimize the backtracking quite a lot to not get TLE!

Also, I'm not sure how it is now, but earlier there were sticks >50 in the input data (even though the input says there are no such sticks) and those sticks you should just ignore.

The following input
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
0
should yield
47
18
6
5
10
62

Archangel
New poster
Posts: 29
Joined: Wed Jun 26, 2002 9:00 am

Post by Archangel » Sun Sep 15, 2002 6:12 pm

According to your input data, my program can produce the right answer.
And I also add some code to ignore the number that > 50 but still got Wrong Answer! :cry:. I haven't started to optimize my efficiency of my program but at least there is some simple input case that I still don't consider in my program will cause my program to produce the wrong answer.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Sep 15, 2002 10:35 pm

Try this input:
10
21 14 13 11 9 6 4 3 2 1
The sticks can be put together like this:
21 | 14 4 3| 13 6 2 | 11 9 1
Therefore output should be 21.

Archangel
New poster
Posts: 29
Joined: Wed Jun 26, 2002 9:00 am

Post by Archangel » Thu Sep 19, 2002 6:40 pm

Your tricky test case really useful. This test case fail my algorithm. It's seem that I should refigure out a better algorithm to prevent this kind of test case.. :D
By the way, Thanks for paying so much attention to my problem ^^.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Sep 19, 2002 6:46 pm

You probably use the same algorithm as I did before the problem was rejudged. Take the first fitting part and if with recursion it can be put together to form a stick of the wanted length, don't backtrack this step. With the original data set it worked, but now they have added some difficult inputs.

Post Reply

Return to “Volume 3 (300-399)”