Page 2 of 4

Posted: Fri Apr 25, 2003 10:28 pm
by little joey
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'. :cry:

10419 Sum-up the Primes2

Posted: Sat Apr 26, 2003 5:55 am
by konsept
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??

He He

Posted: Sat Apr 26, 2003 8:49 am
by shahriar_manzoor
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 :wink:, so think in that direction.

But..

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

Posted: Wed May 28, 2003 12:17 pm
by Pupirev Sergei
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

10419 sum up the primes help!

Posted: Thu Jun 26, 2003 10:38 pm
by mido
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.

aaaa

Posted: Fri Jun 27, 2003 12:35 am
by shahriar_manzoor
"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.

Posted: Fri Jun 27, 2003 1:18 pm
by mido
thanks for the reply....:)

Posted: Fri Jun 27, 2003 11:03 pm
by mido
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]

Posted: Sat Jul 12, 2003 11:05 pm
by mido
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...:)

10419 why wa

Posted: Mon Mar 01, 2004 1:05 pm
by alu_mathics
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.

Posted: Thu Apr 29, 2004 9:57 am
by alu_mathics
why WA 10419.I have tested all the data of the board.my program works fine for all.But don't know why wa.

Posted: Sun Jun 06, 2004 7:36 pm
by Dukema
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.

Posted: Wed Jun 09, 2004 10:47 am
by alu_mathics
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.

Help

Posted: Fri Sep 24, 2004 8:28 pm
by Silverfox03
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.