10001  Garden of Eden
Moderator: Board moderators

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan
Hehe...
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... 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.
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... 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.

 New poster
 Posts: 13
 Joined: Tue Aug 03, 2004 4:24 am
 Location: CHINA
10001 help me
I don't understand some words,below:
who can explain this words,thank you in advance!
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..
"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
[i1] [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
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
[i1] [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

 New poster
 Posts: 3
 Joined: Wed Mar 09, 2005 1:28 pm
10001
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.
I can't understand the evolution rules and how it makes 204 to be an Identity automaton.
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 arbitrarilychosen new state, which the cell must turn into after the application of the rule. This table is then encoded as 8bit 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
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 arbitrarilychosen new state, which the cell must turn into after the application of the rule. This table is then encoded as 8bit 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
I don't follow you...
Actually, I (almost) agree with DemonCris' original postingor am unclear in the same way. 154 = 10100100, so shouldn'tLarry 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...
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
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.
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.

 New poster
 Posts: 3
 Joined: Tue Dec 02, 2003 5:02 pm
10001 WA?
hi everybody,
i need some test cases for this problem.i managed to solve it in 3 sec using backtracking,but got WA.
thanks.
i need some test cases for this problem.i managed to solve it in 3 sec using backtracking,but got WA.
thanks.

 New poster
 Posts: 3
 Joined: Tue Dec 02, 2003 5:02 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[(((index1)%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[(((index1)%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[cells1]=1;
else
making[(index+1)%cells]=1;
}
bool process(int index){
register int i;
if (index==cells1){
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;
}

 Learning poster
 Posts: 60
 Joined: Sun Apr 16, 2006 7:59 pm
10001
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...
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...

 New poster
 Posts: 16
 Joined: Mon Jun 26, 2006 9:33 am
 Contact:
10001: TLE? but why?
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.
Try this input
Code: Select all
0 32 00000000000000000000000000000001