10001 - Garden of Eden

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

Moderator: Board moderators

User avatar
gradientcurl
New poster
Posts: 16
Joined: Mon Jun 26, 2006 9:33 am
Contact:

thanks mf

Post by gradientcurl » Wed Apr 18, 2007 4:57 am

for the test case. ive made the prog more robust by tightening some conditions and rotating the circular array to prune cut down the search tree depending on the automaton state. but still it passed the time limit with a slow 8.648 s.

supercomputer42
New poster
Posts: 1
Joined: Wed Oct 17, 2007 12:47 am

Time bounds for this problem?

Post by supercomputer42 » Wed Oct 17, 2007 6:27 am

How much data do I need to be able to process within the given time bound for this problem? I think my current implementation should be fast enough, but it isn't. My implementation is currently able to process a million random 32-bit testcases in 2.5 seconds, and it seems crazy to expect a testsuite with more than a few thousand numbers.

I'm using Java, and the loop I run for each input number is as follows; the innermost loop loops about 500 times per 32-cell input:

Code: Select all

for (int i = 0; i < numCells; i++) {
	int newResultSet = 0;
	for (int lastBits : lastBitsArray[curPattern & 1]) {
		int mapToSet = ((lastBits << 1) & 7);
		int bitsForSet = 3 << mapToSet;
		for (int firstBits = 0; firstBits < 32; firstBits += 8, bitsForSet <<= 8) {
			if ((resultSet & bitsForSet) != 0) {
				newResultSet |= 1 << (lastBits | firstBits);
			}
		}
	}
	resultSet = newResultSet;
	curPattern = curPattern >>> 1;
}
Is there some massively faster way to implement this?

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10001 - Garden of Eden

Post by DD » Thu Oct 23, 2008 5:34 am

Does anyone can help me test the following input? :o

Input:

Code: Select all

255 6 000001
255 6 111111
0 32 00000000000000000000000000000001
0 32 00000000000000000000000000000000
204 32 00000000000000000000000000000000
204 32 00000000000000000000000000000001
90 5 10110
90 5 10001
EDIT: Since I got A.C., the output are listed in the following:

Output:

Code: Select all

GARDEN OF EDEN
REACHABLE
GARDEN OF EDEN
REACHABLE
REACHABLE
REACHABLE
GARDEN OF EDEN
REACHABLE
Last edited by DD on Tue Nov 04, 2008 5:39 pm, edited 1 time in total.
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

theycallhimtom
New poster
Posts: 1
Joined: Mon Oct 27, 2008 9:41 am

Re: 10001 - Garden of Eden

Post by theycallhimtom » Mon Oct 27, 2008 10:09 am

My solution gets TLE. I use a memoized recursive function where the memoization table only has 512 entries.

EDIT: I changed my code to use StringBuilder to build up the output and output it all at once rather than System.out.println() and that fixed the TLE.

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 10001 - Garden of Eden

Post by suneast » Wed Jul 21, 2010 11:10 am

Hi,

I don't think you have to worry about the TLE error, while I am still using stupid backtracking and also got AC :D
just do it.
write it and then submit it...
you will got AC :wink:

atopoxo
New poster
Posts: 1
Joined: Fri Feb 18, 2011 1:49 pm

Re: 10001 - Garden of Eden

Post by atopoxo » Mon May 09, 2011 3:06 pm

I've looked at the problem for about 6 hours ,but I still can't understand the meaning of the problem.can anyone help me to explain the problem , I will appreciate whoever give me a hand.

Sabiha_Fancy
New poster
Posts: 24
Joined: Mon Jul 16, 2012 3:43 pm

Re: 10001 - Garden of Eden

Post by Sabiha_Fancy » Sun Mar 03, 2013 7:20 am

I am getting TLE.help me.

#include<stdio.h>
#include<string.h>

void found(int id1, int *p,int N);

int main()
{
int id,N,i,right,center,left,sum,len;
char A[34],source[34],destination[34];
int identi[10];
while(scanf("%d%d%s",&id,&N,A)==3)
{
A[N]='\0';
len = strlen(A);
found(id,identi,N);
strcpy(source,A);
while(1)
{
for(i=0; i<N; ++i)
{
sum=0;
if(i == (N-1))
right = source[0]-'0';
else
right = source[i+1]-'0';
center = source-'0';
if(i==0)
left = source[N-1]-'0';
else
left = source[i-1]-'0';
sum = (left*4)+(center*2)+(right*1);
destination = identi[sum]+'0';
}
destination='\0';
if(strcmp(destination,A)==0)
{
printf("REACHABLE\n");
break;
}
else if(strcmp(source,A)!=0 && strcmp(destination,source)==0)
{
printf("GARDEN OF EDEN\n");
break;
}
strcpy(source,destination);
}
}
return 0;
}

void found(int id1, int *p,int N)
{
int i=0;
while(id1)
{
p = id1%2;
id1/=2;
i++;
}
while(i<8)
{
p=0;
i++;
}
return;
}
Fancy

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10001 - Garden of Eden

Post by brianfry713 » Tue Mar 05, 2013 12:42 am

Input:

Code: Select all

198 12 111100110101
70 32 00001011000111100011101011110100
178 8 10100100
65 24 110101011101010100101000
176 5 11010
236 28 0100001100011101000100111010
15 8 11111111
233 16 1010110010111000
100 31 1010101111000101000001011111001
92 14 11010111110011
41 8 00111000
50 14 00111001010101
134 4 1100
162 23 00111001001100001011100
8 8 00001000
188 14 10000011001111
229 21 001111011100100000000
35 25 1010100011000101101111101
20 5 11010
242 10 0001010000
250 23 11010001000011100100111
50 9 100101111
245 20 10010000010001000000
168 23 11100010010001101111100
128 21 010110001000100000111
98 25 0101101110101101101111100
53 25 1100110100011001001111101
31 4 1000
73 12 001000000000
153 24 001010111100010001011011
121 27 100000010011111011101111101
135 10 1010010011
101 28 0011111001110000111110111111
126 7 0011000
91 28 0000010001110001111011100001
209 11 01101110101
229 20 00010100101100111010
222 31 0010111111011001011000011111101
194 12 011011101011
77 28 1001001000110001001000110010
178 23 10010001000010011010000
77 24 111101011111100100000100
156 29 11100001100111001011111001101
206 21 011101110101110100011
30 13 1011011011001
123 19 0010100110100100000
200 12 110000110010
200 13 1101100101110
87 29 11001000110010111110011100010
162 8 00001011
150 12 101110101101
229 26 11101001000001101101001101
171 31 0101001001111111000010100011100
204 31 0000101000111101101111010111101
67 5 10001
150 9 101011101
196 6 010001
97 4 0101
199 6 111001
130 28 1100100100100111011011100110
244 31 1101011000010100001100101110010
207 26 00111101110000101010111101
239 11 10000111011
85 20 10111100001110101101
94 25 1111110101010100111100101
51 15 100101011110100
220 4 0101
17 23 00000111010111100111011
47 30 100101101110000001101000110111
230 20 10110101010110100001
168 19 1001111110010000101
231 10 0000010111
107 24 110000110010011101001111
19 14 01001111101111
112 23 10111101110000000001010
203 21 000100101010000110110
179 19 1101010011001111010
1 27 010111100011100000110101110
55 22 1000011001010000001010
236 26 10100001001010000110111110
16 14 01011001000001
243 13 0110000111001
214 21 001101111101111110010
128 17 10111101110011000
164 31 1101011010111001111000111010100
141 6 011010
133 21 100101001101011001111
166 14 01000011110111
201 7 0000011
214 28 0011011011010011001110000000
47 27 010100000011101011000010010
87 7 1010001
133 4 1110
44 16 0110010011111100
106 27 010000111001100000111100011
200 29 00000001000000100111100000001
192 16 0100000100110101
222 28 0110110110000000001111100001
252 17 11101011100110011
97 9 010110010
My AC code generates this output in 0.001 seconds.

Code: Select all

REACHABLE
GARDEN OF EDEN
REACHABLE
GARDEN OF EDEN
REACHABLE
GARDEN OF EDEN
REACHABLE
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
REACHABLE
GARDEN OF EDEN
REACHABLE
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
REACHABLE
REACHABLE
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
REACHABLE
REACHABLE
REACHABLE
GARDEN OF EDEN
REACHABLE
REACHABLE
GARDEN OF EDEN
REACHABLE
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
REACHABLE
REACHABLE
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
REACHABLE
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
REACHABLE
GARDEN OF EDEN
GARDEN OF EDEN
REACHABLE
REACHABLE
REACHABLE
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
REACHABLE
REACHABLE
REACHABLE
REACHABLE
GARDEN OF EDEN
GARDEN OF EDEN
REACHABLE
GARDEN OF EDEN
GARDEN OF EDEN
REACHABLE
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
REACHABLE
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
REACHABLE
GARDEN OF EDEN
REACHABLE
REACHABLE
REACHABLE
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
REACHABLE
REACHABLE
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
GARDEN OF EDEN
REACHABLE
Check input and AC output for thousands of problems on uDebug!

Sabiha_Fancy
New poster
Posts: 24
Joined: Mon Jul 16, 2012 3:43 pm

Re: 10001 - Garden of Eden

Post by Sabiha_Fancy » Tue Mar 05, 2013 4:56 pm

Thanks for your reply. My approach of coding is wrong. Will you explain how to solve this problem? I read all the posts in this thread. But the coding procedure is not clear to me. If you explain i will be glad.
Fancy

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re:

Post by brianfry713 » Tue Mar 05, 2013 10:18 pm

Eobyn wrote:You cannot solve this problem by making an exaustive search. For 32 bit states that would mean searching all (2^32 - 1) different states :o! That uses to much time.
The idea is to look at the automaton, look at the state and somehow compute if there is any possible predecessor state. If there isn't any, then it is a GARDEN OF EDEN.

Eobyn.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 100 (10000-10099)”