10419 - Sum-up the Primes

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

Moderator: Board moderators

route
New poster
Posts: 39
Joined: Sat Dec 21, 2002 1:25 am

10419 - Sum-up the Primes

contains the lexicographically smallest expression that sums up to N
What means by "lexicographically smallest"?

Alexander Grushetsky
New poster
Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine
Contact:
It should mean that an answer 101+2 "smaller" than 2+101.
As '+'<'0', you should sort lexicographically your primes up to 300 (101,103,107,109,11,113 ...) and when you search an answer, "lexicographically" smaller primes should be earlier and be prefered "lexicographically" bigger primes.

But it seems that the test data for this problem still is incorrect (as it was during contest)

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan
Yes.

The judge data seems have something wrong.

I always got the wrong answer.

I support some input and output of my program.

Input

1000 14
500 13
17 1
9 3
147 3
233 11
0 0

Output
CASE 1:
101+101+103+103+107+107+109+109+11+11+113+13+5+7
CASE 2:
101+101+103+103+11+11+13+13+17+17+2+3+5
CASE 3:
17
CASE 4:
No Solution.
CASE 5:
101+17+29
CASE 6:
101+11+11+13+13+17+17+19+19+5+7

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA
you guys might be right that the judge's input data isn't OK, but what bothers me more at the moment is that I am getting TLE... my prog gives the right answer for all the input seen on the forum or in the description, so I guss it is "just" slow - what could the problem be? I am using a backtracking method, should I try to come up with something smarter than that?
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.

route
New poster
Posts: 39
Joined: Sat Dec 21, 2002 1:25 am
do you mean that the judge now is still wrong?

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA
route wrote:do you mean that the judge now is still wrong?
donno to be honest, since I get TLE... but since there are no accepted solutions, I would assume so...
other:
since my last post, I have tested my program for all the 14000 case and using a primitive timing (difftime), my prog ran in 10.00 seconds... thus I just can't see what the matter could be... If someone would be willing to look at my code to help me out, I would appreciate it - don't wanna post it here, since it's a realtively fresh problem :)
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.

Alexander Grushetsky
New poster
Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine
Contact:
I use dynamic programming to pregenerate results.
And my output is the same.

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

I am sorry

Hello,
I am extremely sorry that the problem had a mistake. A similar problem was used in a contest in Bangladesh. But when I changed the problem statement I did not recode the solution but tried to modify the existing code and forgot to modify in some places.

I am used backtracking method with some bounding and in this way the problem can be solved within 64kb Memory limit . I hope the data will be updated soon and the problems will be rejudged. So until u see that some people has got this problem accepted don't waste your time on it.

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA
pls, could somebody help me now that the judge is judging correctly? I keep on getting TLE, though I dinamically store the results from previous calculations and limit the obviously impossible cases (when the value of t is less than 4). I have a feeling that I might not deel correctly with the input that my program doesn't terminate, or I am seriously stuck.... pls, help, I can't sleep!!!
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Don't make stringcompare all the time.
I avoid it in this way:
I sort the primes indirectly with an indexarray ind[]. After sorting in ind is the index of the lexicographically smallest prime.
Then I don't store the string representation, I store only these indices. For comparison between two lists of indices you need a function that returns the difference between the first values in the lists that differ.

Pupirev Sergei
New poster
Posts: 24
Joined: Mon Feb 24, 2003 5:08 pm
I got WA all the time Can anybody give me test data?
My code is here:

Code: Select all

#include <iostream.h>
#include <string.h>

int pr,kol=0;
char spr;
void makepr()
{
int i,j;
pr=2;kol++;
for (i=3;i<300;i+=2)
{
int ok=0;
for (j=0;pr[j]*pr[j]<=i;j++)
if (i%pr[j]==0) {ok=1;break;}
if (ok==0) {pr[kol]=i;kol++;}
}
}
int c;
void sort(int *pr1,int kol1,int *c)
{
int i,j;
char s1;
for (i=0;i<kol1;i++)
{
int h=pr1[i];
int l=0;
c[i]=i;
while (h>0)
{
s1[l]=char(h%10+'0');
h/=10;
l++;
}
s1[l]=0;
for (j=0;j<l;j++)
spr[i][j]=s1[l-j-1];
spr[i][l]=0;
}
for (i=0;i<kol1;i++)
for (j=i+1;j<kol1;j++)
if (strcmp(spr[c[i]],spr[c[j]])>0)
{

int h=c[i];
c[i]=c[j];
c[j]=h;

}
int pr2;
memcpy(pr2,pr1,70*sizeof(pr1));
for (i=0;i<kol1;i++)
pr1[i]=pr2[c[i]];
}
int a;
int f;
int q,end=0;

int c1;
int main()
{
makepr();
sort(pr,kol,c);

int i,j,k,n,t;
for (i=0;i<=1000;i++)
for (j=0;j<15;j++)
{
a[i][j]=-1;
}
a=0;
q=0;q=0;end=1;
for (i=1;i<=61;i++)
{
f[i]=2;
}

f=1;
memcpy(c1,f,70*sizeof(c1));
for (i=0;i<=61;i++)
{
f[i]=c1[c[i]];
}
while (end>0)
{
i=q[end-1],j=q[end-1];
int p=0;
for (k=0;k<kol;k++)
if (f[i][j][k]>0)
if (i+pr[k]<1001 && j+1<15)
if (a[i+pr[k]][j+1]==-1)
{
a[i+pr[k]][j+1]=i;
memcpy(f[i+pr[k]][j+1],f[i][j],70*sizeof(f));
f[i+pr[k]][j+1][k]--;
q[end]=i+pr[k];
q[end]=j+1;
end++;
p=1;
break;
}
if (p==0) end--;
}

int r=0;
cin>>n>>t;
while (n!=0 && t!=0)
{
r++;
cout<<"CASE "<<r<<":\n";
int ans,l=0;
if (a[n][t]==-1) cout<<"No Solution.\n";
else
{
while (n>0)
{
ans[l]=n-a[n][t];l++;
n=a[n][t];t--;
}
sort(ans,l,c1);
cout<<ans;
for (i=1;i<l;i++)
cout<<"+"<<ans[i];
cout<<"\n";
}
cin>>n>>t;
}
return 0;
}

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

10419 driving me nuts

Can someone verify my output? This problem is driving me crazy input:

Code: Select all

32 3
47 5
91 4
140 6
199 13
267 11
301 5
444 7
611 9
789 11
921 5
0 0
output:

Code: Select all

CASE 1:
11+19+2
CASE 2:
11+11+13+5+7
CASE 3:
11+11+2+67
CASE 4:
101+11+11+3+7+7
CASE 5:
11+11+13+13+17+17+19+19+23+3+3+43+7
CASE 6:
101+101+11+11+13+3+3+5+5+7+7
CASE 7:
101+101+11+17+71
CASE 8:
101+101+103+103+11+2+23
CASE 9:
101+101+103+103+107+11+11+13+61
CASE 10:
101+101+103+103+107+107+109+11+11+13+23
CASE 11:
101+101+149+277+293
Just tell me if I'm right or wrong.

Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:
hi.

my AC-solution gives the same output as yours.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Thanks for checking, Adil. At least my interpretation of the problem seems correct. Now I have to find out why I keep getting WA... shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Mail me

Ok! Mail me your code little joey.

- A lazy problemsetter 