10419 - Sum-up the Primes

[route]

contains the lexicographically smallest expression that sums up to N
What means by "lexicographically smallest"?
Thank you for your reply.

[Alexander Grushetsky]

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]

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]

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?

[route]

do you mean that the judge now is still wrong?

[zsepi]

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 :)

[Alexander Grushetsky]

I use dynamic programming to pregenerate results.
And my output is the same.

[shahriar_manzoor]

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]

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!!!

[Adrian Kuegel]

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.

[Pupirev Sergei]

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;
	}

[little joey]

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.

[Adil]

hi.

my AC-solution gives the same output as yours.

[little joey]

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]

Ok! Mail me your code little joey.

- A lazy problemsetter