524 - Prime Ring Problem

[aabiague]

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]

[helloneo]

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

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

please delete your code..

[aabiague]

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]

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]

Thanks very much, its AC.

[nymo]

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

[stcheung]

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]

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.

[abhi]

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]

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]

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

[kn]

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

[mukeshtiwari]

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]

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.

[mukeshtiwari]

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