524 - Prime Ring Problem

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

Moderator: Board moderators

aabiague
New poster
Posts: 4
Joined: Mon Oct 30, 2006 11:29 pm
Location: Cuba

524 - PE

Post by aabiague » Mon Oct 30, 2006 11:37 pm

Hi, who can tell me why this code has PE , please ??? [code]



void ImprimeArrar(int * secuencia)
{
if (!tachado[secuencia[cantElementos-1]+1])
{
for (int i = 0 ; i < cantElementos -1 ; i++)
printf("%d ",secuencia[i]);
printf("%d\n",secuencia[cantElementos-1]);
}
}

[/code]
Last edited by aabiague on Tue Oct 31, 2006 4:05 am, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Tue Oct 31, 2006 3:31 am

you have to search first..
check this out..

http://online-judge.uva.es/board/viewtopic.php?t=4351

please delete your code..

aabiague
New poster
Posts: 4
Joined: Mon Oct 30, 2006 11:29 pm
Location: Cuba

Post by aabiague » Tue Oct 31, 2006 4:14 am

ok, I see the solution before, but I can't find my error, someone can tell me what happen why my code ????? Any sugestions ???

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Tue Oct 31, 2006 4:25 am

aabiague wrote:ok, I see the solution before, but I can't find my error, someone can tell me what happen why my code ????? Any sugestions ???
you may need a blank line after each case except for the last case..

example

Code: Select all

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

aabiague
New poster
Posts: 4
Joined: Mon Oct 30, 2006 11:29 pm
Location: Cuba

Post by aabiague » Tue Oct 31, 2006 4:52 am

Thanks very much, its AC.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Thanks

Post by nymo » Mon Dec 11, 2006 6:26 pm

Thanks, I was only looking for blanks between test cases..., now P.E. matters ;)
regards,
nymo

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Post by stcheung » Wed Jan 03, 2007 9:05 am

And don't repeat my silly mistake of using C++ <set> instead of a boolean array to store the numbers that you have used. I got TLE when using <set> and it took <2 sec after converting to boolean array.

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

Post by soyoja » Wed Jan 31, 2007 4:05 pm

I don't know the other method to solve this problem. However, it is obvious that permutation method is too slow to find all solutions.
When n = 16, almost 16! times ( 209,227,898,888,000 times ) needs to calculate to search all cases.
I love Problem Solving!!! :) :) :)

abhi
Learning poster
Posts: 94
Joined: Fri Nov 25, 2005 7:29 pm

Post by abhi » Wed Jan 31, 2007 7:39 pm

even i am getting PE for this problem.
i do not print any blanks after last integer in the sequence.
but still PE.

should we print a blank line in after the last test case ????

yogeshgo05
New poster
Posts: 47
Joined: Sun Nov 27, 2005 12:43 pm

compile error --- is the judge alrigth .....

Post by yogeshgo05 » Mon Feb 05, 2007 1:18 pm

both of problems 524 & 539 are just workin fine g++ compiler of mine
after a while i m solving in acm .... its changed now i guess....

here's my code for 524 .. plz tell me guys why compile error....

Code: Select all

# include <iostream>
# include <vector>
# include <string>
# include <cstring>
# include <algorithm>
using namespace std;
int prime[36]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0}; 
vector<int> v;
bool edges[35][35];
int count;

void backtrack(int i,int n)
{
 	  extern int count;
		if(v.size()==n-1)
 	  {
		  if(prime[i+1]!=1)
		   { return ;}
		   else if (prime[i+1]==1)
		   {
			 	  for( int j=0;j<v.size();j++)
			 	  			 cout<<v[j]<<" ";
			 	  			cout<<i<<"\n";
			 	  			 //v.pop_back();
			 	  			 return ;
			 }
      }
      
      
      for(int j=2;j<=n;j++)
      {
		 		  if(edges[i][j]==false && prime[i+j]==1)
		 		  {
							count++;
							edges[i][j]=true;
							for(int k=2;k<=n;k++)edges[k][i]=true;
							edges[j][i]=true;
							v.push_back(i);
							backtrack(j,n);
							edges[i][j]=false;
							edges[j][i]=false;
							for(int k=2;k<=n;k++)edges[k][i]=false;
							v.pop_back();
				  }
      }
      
      
		count--;
}

int main()
{  int n;
int count=0;
 	 while(cin>>n)
	  {  cout<<"Case "<<(++count)<<":\n";memset(edges,false,sizeof(edges));backtrack(1,n);v.clear();}
	  return 0;
}				


jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Mon Feb 05, 2007 1:25 pm

I don't know if it is the problem, but "extern int count" might lead to CE...

kn
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am

Post by kn » Mon Apr 30, 2007 9:50 pm

Well, 2 even numbers can never be neighbours;
2 odd numbers can never be neighbours.

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

Post by mukeshtiwari » Wed Jun 06, 2007 6:48 am

hi everybody i tried to solve this problem but getting WA ...plz help me ..here is code . My algorithm is
Start generating permutation and check the condition of primality and if condition voilate then prune it . here is my code kindly check it .

Code: Select all

#include<cstdio>
#include<iostream>
using namespace std;
int a[20];

	int prime(int n)
	    {
		if(n==1)
		  return 0;
		if(n==2)
		  return 1;
		if(n%2==0)
		  return 0;
		for(int i=3;i*i<=n;i++)
			if(n%i==0)
				return 0;
		return 1;
	     }
	void perm(int k,int n,int* count)
		{
			
			int temp;
			if(k==n && prime(a[0]+a[n-1]))
			  {
				(*count)++;
				for(int i=0;i<n-1;i++)
					printf("%d ",a[i]);
					printf("%d\n",a[n-1]);
			  }
			else
			  {
				for(int i=k;i<n;i++)
				 if(prime(a[k-1]+a[i]))
				 {
					
					temp=a[i];
					a[i]=a[k];
					a[k]=temp;
					perm(k+1,n,count);
					temp=a[i];
					a[i]=a[k];
					a[k]=temp;
				 }
				
			}
		}
			
	int main()
		{
			int n,k=0,count;
			while(scanf("%d",&n)==1)
			{
				count=0;
				if(k!=0)
				 printf("\n");
				k=k+1;
				printf("Case %d:\n",k);
				for(int i=0;i<20;i++)
					a[i]=i+1;
				perm(1,n,&count);
				//printf("count=%d\n",count);
			}
		}
	

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Jun 06, 2007 11:40 am

For input 10,

1st Part of Output:

Code: Select all

Case 1:
1 2 3 4 7 6 5 8 9 10
1 2 3 4 7 10 9 8 5 6
1 2 3 4 9 8 5 6 7 10
1 2 3 8 5 6 7 4 9 10
1 2 3 8 5 6 7 10 9 4
1 2 3 10 7 4 9 8 5 6
1 2 3 10 7 6 5 8 9 4
...
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

Post by mukeshtiwari » Tue Jun 12, 2007 7:06 pm

sorry for late reply . thnkx for help . i got accepted..

Post Reply

Return to “Volume 5 (500-599)”