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

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Sat Dec 13, 2003 8:01 am

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.

User avatar
deneb
New poster
Posts: 6
Joined: Mon Nov 17, 2003 3:39 pm

Post by deneb » Tue Dec 16, 2003 1:45 am

ok tnx very much

JuaingFall
New poster
Posts: 13
Joined: Tue Aug 03, 2004 4:24 am
Location: CHINA

10001 help me

Post by JuaingFall » Fri Aug 06, 2004 8:05 am

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!

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

the meaning is..

Post by Nick » Wed Sep 01, 2004 10:13 am

"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

liuchangacm
New poster
Posts: 3
Joined: Wed Mar 09, 2005 1:28 pm

10001

Post by liuchangacm » Wed Mar 09, 2005 1:35 pm

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.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Wed Mar 09, 2005 4:34 pm

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

liuchangacm
New poster
Posts: 3
Joined: Wed Mar 09, 2005 1:28 pm

Post by liuchangacm » Wed Mar 09, 2005 5:18 pm

I get it. Thank you very much!

jGlass314
New poster
Posts: 1
Joined: Tue May 17, 2005 7:57 am

I don't follow you...

Post by jGlass314 » Tue May 17, 2005 8:08 am

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 ??

ironfist
New poster
Posts: 1
Joined: Wed May 18, 2005 5:00 am

10001 Garden of Eden Question

Post by ironfist » Wed May 18, 2005 5:05 am

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.

backslashnull
New poster
Posts: 3
Joined: Tue Dec 02, 2003 5:02 pm

10001 WA?

Post by backslashnull » Thu Oct 20, 2005 5:43 pm

hi everybody,
i need some test cases for this problem.i managed to solve it in 3 sec using backtracking,but got WA.

thanks.

backslashnull
New poster
Posts: 3
Joined: Tue Dec 02, 2003 5:02 pm

Post by backslashnull » Fri Oct 21, 2005 8:04 pm

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;
}

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

Post by Jan » Mon Jun 19, 2006 1:48 pm

154 = 10011010
164 = 10100100


I think you have got your error.
Ami ekhono shopno dekhi...
HomePage

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

10001

Post by ayeshapakhi » Thu Aug 24, 2006 11:51 am

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...

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

10001: TLE? but why?

Post by gradientcurl » Tue Apr 17, 2007 6:54 pm

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
Last edited by gradientcurl on Wed Apr 18, 2007 4:51 am, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Apr 17, 2007 8:21 pm

Try this input

Code: Select all

0 32 00000000000000000000000000000001

Post Reply

Return to “Volume 100 (10000-10099)”