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

Post by route » Tue Jan 14, 2003 8:53 am

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

Alexander Grushetsky
New poster
Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine
Contact:

Post by Alexander Grushetsky » Tue Jan 14, 2003 11:16 pm

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)

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

Post by Ghost77 dimen » Wed Jan 15, 2003 6:57 am

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

Post by zsepi » Wed Jan 15, 2003 10:41 am

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

Post by route » Wed Jan 15, 2003 11:10 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

Post by zsepi » Wed Jan 15, 2003 11:28 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.

Alexander Grushetsky
New poster
Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine
Contact:

Post by Alexander Grushetsky » Wed Jan 15, 2003 1:44 pm

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

Post by shahriar_manzoor » Thu Jan 16, 2003 12:26 pm

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

Post by zsepi » Fri Jan 17, 2003 9:23 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.

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

Post by Adrian Kuegel » Fri Jan 17, 2003 1:44 pm

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
New poster
Posts: 24
Joined: Mon Feb 24, 2003 5:08 pm

Post by Pupirev Sergei » Tue Feb 25, 2003 3:13 pm

I got WA all the time :cry:
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;
	}

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

10419 driving me nuts

Post by little joey » Thu Apr 24, 2003 3:49 pm

Can someone verify my output? This problem is driving me crazy :wink:
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
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil » Thu Apr 24, 2003 6:35 pm

hi.

my AC-solution gives the same output as yours.

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

Post by little joey » Thu Apr 24, 2003 8:33 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

Post by shahriar_manzoor » Fri Apr 25, 2003 4:09 pm

Ok! Mail me your code little joey.

- A lazy problemsetter :D

Post Reply

Return to “Volume 104 (10400-10499)”