## 10419 - Sum-up the Primes

Moderator: Board moderators

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Thanks Shahriar Manzoor for your help. My code is wrong after all, though it was hard to find the mistake. I'll try again from scratch.

To all others: if you get '229+229+271+271' as answer for '1000 4', then you made the same mistake as I did; the correct answer is '131+283+293+293'. konsept
New poster
Posts: 22
Joined: Wed Dec 19, 2001 2:00 am
Contact:

### 10419 Sum-up the Primes2

Hi,
I've been working on this problem for several hours and I always get Time Limit Exceeded when I submit my solution.
I solved this problem using DP.
consider an array
char can;
can[n][k][t] = is it possible to sum to n, using numbers from among the first k primes, using exactly t numbers?
I used this same approach with problem 10419 (the first version of Sum-up the Primes) and got one of the fastest runtimes on the ranklist, so I'm very puzzled as to why this algorithm is too slow for this problem.

Can someone give me a hint on how to make my algorithm faster??

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

### He He

When I made Sumup the primes I intended people to use backtracking with constraints to solve this problem but they got away with more conventional dynamic programming approach so I have made sum up the primes (II) so they have to use backtracking with constraints to solve this problem , so think in that direction.

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

### But..

But your answers are incorrect, because my program output for example, for this

500 13
CASE 2:
2+3+5+11+11+13+13+17+17+101+101+103+103

is
500 13
CASE 2:
2+3+3+5+5+7+7+11+11+13+13+127+293 Miguel & Marina Pupirev Sergei
New poster
Posts: 24
Joined: Mon Feb 24, 2003 5:08 pm
I can't understand you.
For input 500 13
my program output
101+101+103+103+11+11+13+13+17+17+2+3+5
It's smaller than
2+3+5+11+11+13+13+17+17+101+101+103+103

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

### 10419 sum up the primes help!

I've been trying to solve this one for too long now(6 months minimum...as far as I can tell), and I've never beat the TLE.

The best I could reach was to use a normal "take or not to take" backtracking method with a slight modification. Basically, I use an array of primes sorted lexicographically, with each entry but the number 2 repeated twice. In each recursion step, I try using and not using the number(in that order), after which I move on to the next number. Should the using-the-number branch fail to reach a solution, I skip its twin to avoid repeating the branch again.

Tips would be greatly appreciated.

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

### aaaa

"Try the idea of Goldbach's conjecture."

Sorry for the reply above. I thought is as summation of four primes.

For this problem try backtracking with some bounds or more conventional dynamic programming.

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt
thanks for the reply.... mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt
No luck as of yet..am I way out with this code?...:
[cpp]
#include <iostream.h>

bool prime;
bool first;
bool used;
int *output,out_index,lim;
int list;
int target,t,i,j,k;

void prepare() //prepares a lexicographically sorted array of primes
{
prime=false;
prime=false;
for (i=2;i<300;i++)
prime=true;
for (i=2;i<300;i++)
{
for (j=2;i*j<300;j++)
{
prime[i*j]=false;
}
}

lim=0;
for (i=0;i<300;i++)
{
if (prime)
{
list[lim++]=i;
}
}
list[lim]=-1;

for (i=0;i<lim-1;i++)//lexicographical sorting here
{
int index=i;
for (j=i+1;j<lim;j++)
{
int temp_1,temp_2;
temp_1=list[index];
temp_2=list[j];
while (!(temp_1/100))
temp_1*=10;
while (!(temp_2/100))
temp_2*=10;
if (temp_2<temp_1)
index=j;
}

int temp=list;
list=list[index];
list[index]=temp;
}
}

bool check(int index,int sum,int taken)
{
if (sum==target && taken==t) return true;
if (index>=lim) return false;
if (sum!=target && taken==t) return false;
if (sum>target || taken>t) return false;
if ((t-taken)==1 && !prime[target-sum]) return false;

if (used[index][taken][sum]) return false;

used[index][taken][sum]=true;

//call with twice the value of the current prime considered
if (list[index]!=2 && taken+2<=t && check(index+1,sum+2*list[index],taken+2))
{
output[out_index--]=list[index];
output[out_index--]=list[index];
return true;
}

//call with the value
if (check(index+1,sum+list[index],taken+1))
{
output[out_index--]=list[index];
return true;
}

if (check(index+1,sum,taken))
return true;

return false;
}

void main()
{
prepare();
int count=0;
output=new int;
while (cin>>target>>t && (target>0 || t>0) && ++count<9341)
{
cout<<"CASE "<<count<<":"<<endl;

out_index=t-1;

if (t==0 || target==0 || target==1)
{
cout<<"No Solution."<<endl;
continue;
}

if (t==1 && !prime[target])
{
cout<<"No Solution."<<endl;
continue;
}
else if (t==1)
{
cout<<target<<endl;
continue;
}

for (i=0;i<lim;i++)
for (j=0;j<=t;j++)
for (k=0;k<=target;k++)
used[j][k]=false;

if (check(0,0,0))
{
for (i=0;i<t-1;i++)
cout<<output<<"+";
cout<<output<<endl;
cout.flush();
}
else cout<<"No Solution."<<endl;

}
}
[/cpp]

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt
It's over now....I finally solved it...thanks again Mr. Manzoor..;to those interested, the code above is quite close...but some critical changes must be made to suffice the judge's requirements... alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:

### 10419 why wa

I use backtracking for this problem.But it's getting WA.Is the following outputs are correct:
input:
32 3
79 1
79 2
79 3
79 4
1000 1
100 2
1000 2
1000 3
1000 4
1000 5
1000 6
1000 8
1000 9
1000 13
999 13
998 13
47 5
91 4
140 6
199 13
267 11
301 5
444 7
611 9
789 11
921 5
1000 14
500 13
17 1
9 3
147 3
233 11
500 13
1 0
1 1
1 2
561 3
561 5
561 10
561 13
6 2
6 3
6 4
3 1
3 2
9 3
0 0
output:
CASE 1:
11+19+2
CASE 2:
79
CASE 3:
No Solution.
CASE 4:
11+31+37
CASE 5:
11+13+2+53
CASE 6:
No Solution.
CASE 7:
11+89
CASE 8:
No Solution.
CASE 9:
No Solution.
CASE 10:
131+283+293+293
CASE 11:
131+2+281+293+293
CASE 12:
101+101+103+109+293+293
CASE 13:
101+101+103+103+107+107+109+269
CASE 14:
101+101+103+103+107+107+113+2+263
CASE 15:
101+101+103+103+107+107+109+109+11+11+113+2+23
CASE 16:
101+101+103+103+107+107+109+109+11+11+113+17+7
CASE 17:
101+101+103+103+107+107+109+109+11+11+127+2+7
CASE 18:
11+11+13+5+7
CASE 19:
11+11+2+67
CASE 20:
101+11+11+3+7+7
CASE 21:
11+11+13+13+17+17+19+19+23+3+3+43+7
CASE 22:
101+101+11+11+13+3+3+5+5+7+7
CASE 23:
101+101+11+17+71
CASE 24:
101+101+103+103+11+2+23
CASE 25:
101+101+103+103+107+11+11+13+61
CASE 26:
101+101+103+103+107+107+109+11+11+13+23
CASE 27:
101+101+149+277+293
CASE 28:
101+101+103+103+107+107+109+109+11+11+113+13+5+7
CASE 29:
101+101+103+103+11+11+13+13+17+17+2+3+5
CASE 30:
17
CASE 31:
No Solution.
CASE 32:
101+17+29
CASE 33:
101+11+11+13+13+17+17+19+19+5+7
CASE 34:
101+101+103+103+11+11+13+13+17+17+2+3+5
CASE 35:
No Solution.
CASE 36:
No Solution.
CASE 37:
No Solution.
CASE 38:
101+167+293
CASE 39:
101+101+103+107+149
CASE 40:
101+101+103+103+107+11+11+17+2+5
CASE 41:
101+101+103+103+11+11+13+13+17+17+19+23+29
CASE 42:
3+3
CASE 43:
No Solution.
CASE 44:
No Solution.
CASE 45:
3
CASE 46:
No Solution.
CASE 47:
No Solution.
cuii e

alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:
why WA 10419.I have tested all the data of the board.my program works fine for all.But don't know why wa.
cuii e

Dukema
New poster
Posts: 3
Joined: Sun Jun 06, 2004 7:12 pm
I had tried your input in my program. (The Judge accepted it). I hope it helps you. My output is:

CASE 1:
11+19+2
CASE 2:
79
CASE 3:
No Solution.
CASE 4:
11+31+37
CASE 5:
11+13+2+53
CASE 6:
No Solution.
CASE 7:
11+89
CASE 8:
No Solution.
CASE 9:
No Solution.
CASE 10:
131+283+293+293
CASE 11:
131+2+281+293+293
CASE 12:
101+101+103+109+293+293
CASE 13:
101+101+103+103+107+107+109+269
CASE 14:
101+101+103+103+107+107+113+2+263
CASE 15:
101+101+103+103+107+107+109+109+11+11+113+2+23
CASE 16:
101+101+103+103+107+107+109+109+11+11+113+17+7
CASE 17:
101+101+103+103+107+107+109+109+11+11+127+2+7
CASE 18:
11+11+13+5+7
CASE 19:
11+11+2+67
CASE 20:
101+11+11+3+7+7
CASE 21:
11+11+13+13+17+17+19+19+23+3+3+43+7
CASE 22:
101+101+11+11+13+3+3+5+5+7+7
CASE 23:
101+101+11+17+71
CASE 24:
101+101+103+103+11+2+23
CASE 25:
101+101+103+103+107+11+11+13+61
CASE 26:
101+101+103+103+107+107+109+11+11+13+23
CASE 27:
101+101+149+277+293
CASE 28:
101+101+103+103+107+107+109+109+11+11+113+13+5+7
CASE 29:
101+101+103+103+11+11+13+13+17+17+2+3+5
CASE 30:
17
CASE 31:
No Solution.
CASE 32:
101+17+29
CASE 33:
101+11+11+13+13+17+17+19+19+5+7
CASE 34:
101+101+103+103+11+11+13+13+17+17+2+3+5
CASE 35:
No Solution.
CASE 36:
No Solution.
CASE 37:
No Solution.
CASE 38:
101+167+293
CASE 39:
101+101+103+107+149
CASE 40:
101+101+103+103+107+11+11+17+2+5
CASE 41:
101+101+103+103+11+11+13+13+17+17+19+23+29
CASE 42:
3+3
CASE 43:
No Solution.
CASE 44:
No Solution.
CASE 45:
3
CASE 46:
No Solution.
CASE 47:
No Solution.
Let's rock!

alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:
Thanks any way.I got this problem A.C. one month ago using dp.But the problem is that my backtrack solution gives W.A.
cuii e

Silverfox03
New poster
Posts: 6
Joined: Fri Aug 27, 2004 4:05 pm

### Help

alu_mathics:
Can you tell me what's wrong you have made? I had test all data above, they are all ok, but I still got W.A. Maybe I have made the same mistake with you.