10419 - Sum-up the Primes

little joey · Post by **little joey** » Fri Apr 25, 2003 10:28 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 · Post by **konsept** » Sat Apr 26, 2003 5:55 am

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[801][64][13];
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 · Post by **shahriar_manzoor** » Sat Apr 26, 2003 8:49 am

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 · Post by **Miguel Angel** » Wed May 28, 2003 4:15 am

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

Pupirev Sergei · Post by **Pupirev Sergei** » Wed May 28, 2003 12:17 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 · Post by **mido** » Thu Jun 26, 2003 10:38 pm

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 · Post by **shahriar_manzoor** » Fri Jun 27, 2003 12:35 am

"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 · Post by **mido** » Fri Jun 27, 2003 1:18 pm

thanks for the reply....

mido · Post by **mido** » Fri Jun 27, 2003 11:03 pm

No luck as of yet..am I way out with this code?...:
[cpp]
#include <iostream.h>

bool prime[300];
bool first[150];
bool used[151][15][1010];
int *output,out_index,lim;
int list[200];
int target,t,i,j,k;

void prepare() //prepares a lexicographically sorted array of primes
{
prime[0]=false;
prime[1]=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[15];
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 · Post by **mido** » Sat Jul 12, 2003 11:05 pm

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 · Post by **alu_mathics** » Mon Mar 01, 2004 1:05 pm

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.

alu_mathics · Post by **alu_mathics** » Thu Apr 29, 2004 9:57 am

why WA 10419.I have tested all the data of the board.my program works fine for all.But don't know why wa.

Dukema · Post by **Dukema** » Sun Jun 06, 2004 7:36 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.

alu_mathics · Post by **alu_mathics** » Wed Jun 09, 2004 10:47 am

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.

Silverfox03 · Post by **Silverfox03** » Fri Sep 24, 2004 8:28 pm

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.

OJ Board

10419 - Sum-up the Primes

10419 Sum-up the Primes2

He He

But..

10419 sum up the primes help!

aaaa

10419 why wa

Help