## 10419 - Sum-up the Primes

Moderator: Board moderators

### 10419 - Sum-up the Primes

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

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

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)
Alexander Grushetsky
New poster

Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine

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

Ghost77 dimen
Learning poster

Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

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.
zsepi
Learning poster

Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

do you mean that the judge now is still wrong?
route
New poster

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

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.
zsepi
Learning poster

Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

I use dynamic programming to pregenerate results.
And my output is the same.
Alexander Grushetsky
New poster

Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine

### 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.
shahriar_manzoor

Posts: 400
Joined: Sat Jan 12, 2002 2:00 am

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.
zsepi
Learning poster

Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

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[0] 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.
Guru

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

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[70],kol=0;char spr[70][5];void makepr()   {   int i,j;   pr[0]=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[70];void sort(int *pr1,int kol1,int *c)   {   int i,j;   char s1[5];   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[70];   memcpy(pr2,pr1,70*sizeof(pr1[0]));   for (i=0;i<kol1;i++)      pr1[i]=pr2[c[i]];   }int a[1001][15];int f[1001][15][70];int q[16000][2],end=0;int c1[70];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][0]=0;   q[0][0]=0;q[0][1]=0;end=1;   for (i=1;i<=61;i++)      {      f[0][0][i]=2;      }   f[0][0][0]=1;   memcpy(c1,f[0][0],70*sizeof(c1[0]));   for (i=0;i<=61;i++)      {      f[0][0][i]=c1[c[i]];      }   while (end>0)      {      i=q[end-1][0],j=q[end-1][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[0][0][0]));                     f[i+pr[k]][j+1][k]--;                     q[end][0]=i+pr[k];                     q[end][1]=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[15],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[0];         for (i=1;i<l;i++)            cout<<"+"<<ans[i];         cout<<"\n";         }      cin>>n>>t;      }   return 0;   }`
Pupirev Sergei
New poster

Posts: 24
Joined: Mon Feb 24, 2003 5:08 pm

### 10419 driving me nuts

Can someone verify my output? This problem is driving me crazy
input:
Code: Select all
`32 347 591 4140 6199 13267 11301 5444 7611 9789 11921 50 0`

output:
Code: Select all
`CASE 1:11+19+2CASE 2:11+11+13+5+7CASE 3:11+11+2+67CASE 4:101+11+11+3+7+7CASE 5:11+11+13+13+17+17+19+19+23+3+3+43+7CASE 6:101+101+11+11+13+3+3+5+5+7+7CASE 7:101+101+11+17+71CASE 8:101+101+103+103+11+2+23CASE 9:101+101+103+103+107+11+11+13+61CASE 10:101+101+103+103+107+107+109+11+11+13+23CASE 11:101+101+149+277+293`

Just tell me if I'm right or wrong.

little joey
Guru

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

hi.

my AC-solution gives the same output as yours.
Learning poster

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

Thanks for checking, Adil. At least my interpretation of the problem seems correct. Now I have to find out why I keep getting WA...

little joey
Guru

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

### Mail me

Ok! Mail me your code little joey.

- A lazy problemsetter
shahriar_manzoor