Page 2 of 3

Posted: Sat Dec 13, 2003 8:01 am
by Andrey Mokhov
He-he... :wink:

Exaustive search is my favorite method to solve problems, especially if it is necessary to use some tricky prunings!!

Of course this problem can be solved a better way - I'm only on 124'th place in the ranklist with 1.941 time... :oops: :oops: But...

A small hint: you needn't generate all bits of the state. I generated only two bits of each triple and then recovered the others.

Bye.
Andrey.

Posted: Tue Dec 16, 2003 1:45 am
by deneb
ok tnx very much

10001 help me

Posted: Fri Aug 06, 2004 8:05 am
by JuaingFall
I don't understand some words,below:
To further simplify the problem each cell state will depend only on its previous state and that of its immediate neighbors (the one to the left and the one to the right).
The Identity automaton (every state evolves to itself) has identifier 204.

who can explain this words,thank you in advance!

the meaning is..

Posted: Wed Sep 01, 2004 10:13 am
by Nick
"To further simplify the problem each cell state will depend only on its previous state and that of its immediate neighbors (the one to the left and the one to the right). "

the paragraph above means that each of the node/cell will change its state to a new state according to its own state, the state of the left and right neighbor. for ex : if you got a cell with a 0 state, and the left is also 0 and the right one is 1 (from the sample automaton in the problem) the cell will change its state from 0 to 1


"The Identity automaton (every state evolves to itself) has identifier 204."

Now, this means that if the automaton has an identifier 204.. the table will look like this

Left Cell Right New
[i-1] [i + 1] State
0 0 0 0 0 * 1
0 0 1 0 0 * 2
0 1 0 1 1 * 4
0 1 1 1 1 * 8
1 0 0 0 0 * 16
1 0 1 0 0 * 32
1 1 0 1 1 * 64
1 1 1 1 1 * 128
204 = Automaton Identifier

every cell with 0 state will evolve into 0 again, and every cell with 1 change to 1..
so the state 10111001100101011 will also become 10111001100101011

10001

Posted: Wed Mar 09, 2005 1:35 pm
by liuchangacm
Could anyone tell me what does the Problem 10001 mean?
I can't understand the evolution rules and how it makes 204 to be an Identity automaton.

Posted: Wed Mar 09, 2005 4:34 pm
by mf
Basically the problem wants you to find the "parent" of given pattern, that is the pattern which will evolute into the given one. If there exists a parent, you print "REACHABLE", otherwise it's "GARDEN OF EDEN". You need backtracking to solve this.

Encoding of the rules is demonstrated in the table in the statement.
Each cell is evaluated, depending on its current state and the state of both its neighbors. Each possible combination (there are just 8 of them) is listed in the table, along with the arbitrarily-chosen new state, which the cell must turn into after the application of the rule. This table is then encoded as 8-bit number by interpreting the numbers in "New state" column as binary digits.

The corresponsing table for identity is:
Left, Cell, Right, New
0 0 0 -> 0
0 0 1 -> 0
0 1 0 -> 1
0 1 1 -> 1
1 0 0 -> 0
1 0 1 -> 0
1 1 0 -> 1
1 1 1 -> 1

Note that the value in "New" column is the same as in the "Cell".
In binary the "New" column is (from bottom to top): 11001100 = 204 (decimal).

See also mathworld's article: http://mathworld.wolfram.com/Elementary ... maton.html

Posted: Wed Mar 09, 2005 5:18 pm
by liuchangacm
I get it. Thank you very much!

I don't follow you...

Posted: Tue May 17, 2005 8:08 am
by jGlass314
Larry wrote:Let's just say it's
110000

011 -> 1
110 -> 0
100 -> 1
000 -> 0
000 -> 0
001 -> 1

so basically, we get
101001 from 110000 on rule 154.

I'm not too sure how you would get to 100000...
Actually, I (almost) agree with DemonCris' original posting--or am unclear in the same way. 154 = 10100100, so shouldn't
000 -> 0
001 -> 0
010 -> 1
011 -> 0
100 -> 0
101 -> 1
110 -> 0
111 -> 1
and therefore 110001 -> 100000 because
111 -> 1
110 -> 0
100 -> 0
000 -> 0
001 -> 0
011 -> 0 ??

10001 Garden of Eden Question

Posted: Wed May 18, 2005 5:05 am
by ironfist
Hi guys,

I have been working on the garden of eden problem for 2 days now, and I cannot seem to get the correct answer.

I am using a recursive algorithm that tries to find the parent state, and backtracks once it runs into a dead end. For a while I was getting TLE, but after adding more prunning, i managed to get my solution in under the alloted time.

However, now i keep on getting WA, but every test case that I throw at it, appears to be correct to me. I was wondering if somone who has gotten the Correct solution could provide me with some test cases and their output? So that I can figure out the problem with my code.

Thanks,

iron.

10001 WA?

Posted: Thu Oct 20, 2005 5:43 pm
by backslashnull
hi everybody,
i need some test cases for this problem.i managed to solve it in 3 sec using backtracking,but got WA.

thanks.

Posted: Fri Oct 21, 2005 8:04 pm
by backslashnull
oh bythe way here is my code:

Code: Select all

#include "fstream"
#include "string.h"
using namespace std;


int rule_table[8][4]={{0,0,0,0},{0,0,1,0},{0,1,0,0},{0,1,1,0},{1,0,0,0},{1,0,1,0},{1,1,0,0},{1,1,1,0}};
int cells;
char current_state[33];
int    making[33];

void set_rules(int a){
	register int i;
	for(i=0;i<8;i++){
		if (a& 1)
			rule_table[i][3]=1;
		else 
			rule_table[i][3]=0;
		a>>=1;
	}
}

bool applyable(int r_number,int index){
	if (making[index]==-1)
		return true;
	if (making[(((index-1)%cells)+cells)%cells]==rule_table[r_number][0] && making[index]==rule_table[r_number][1] && (making[(index+1)%cells]==-1 ||  making[(index+1)%cells]==rule_table[r_number][2]))
		return true;
	return false;
}

void apply_rule(int rule,int index){
	making[(((index-1)%cells)+cells)%cells]=rule_table[rule][0];
	making[index]				=rule_table[rule][1];
	making[(index+1)%cells]=rule_table[rule][2];
}

void clear(int index){
	if(index==0)
		making[0]=making[1]=making[cells-1]=-1;
	else
		making[(index+1)%cells]=-1;
}

bool process(int index){
	register int i;
	if (index==cells-1){
		for(i=0;i<8;i++)
			if (rule_table[i][3]==current_state[index]-'0' && applyable(i,index))
				return true;
		return false;
	}
	for(i=0;i<8;i++){
		if (rule_table[i][3]!=current_state[index]-'0')
			continue;
		if (applyable(i,index)){
			apply_rule(i,index);
			if (process(index+1))
				return true;
			clear(index);
		}
	}
	return false;
}


int main(){
	int automaton;
	while (!cin.eof()){
		memset(current_state,0,sizeof(current_state));
		memset(making,-1,sizeof(making));
		cin >> automaton;
		if (cin.eof())
			break;
		cin >> cells;
		cin >> current_state;
		set_rules(automaton);
		if (process(0))
			cout <<"REACHABLE"<<endl;
		else
			cout <<"GARDEN OF EDEN"<<endl;
	}
	return 0;
}

Posted: Mon Jun 19, 2006 1:48 pm
by Jan
154 = 10011010
164 = 10100100


I think you have got your error.

10001

Posted: Thu Aug 24, 2006 11:51 am
by ayeshapakhi
hi all..........
i've got some problem in solving 10001 garden of eden...
would anyone pls send me some i/o for both possible or impossible cases???
i would be highly greatful to you..
thanks a lot...

10001: TLE? but why?

Posted: Tue Apr 17, 2007 6:54 pm
by gradientcurl
hi. ive thoroughly checked my prog with my own input (on top of what is provided by the question online). ive used backtracking to find the existence of a predecessor. if its not found, then its a GARDEN OF EDEN. also tried with a few random 32 size inputs (which are most probably GARDEN OF EDENs), and it ran in a blink of an eye (right after ive pressed enter). But it was judged as TLE on the OJ. Below is my code. My guess is some form of devious input which will cause it to run extra slow

Code: Select all

removed after AC

Posted: Tue Apr 17, 2007 8:21 pm
by mf
Try this input

Code: Select all

0 32 00000000000000000000000000000001