Problem Statement This task is about automata that can walk on rooted binary trees and keep notes in the trees' nodes. The trees are general binary trees. I.e., each node has at most two sons: at most one left son and at most one right son. Each node contains 26 boolean variables. These are called flags and they are labelled 'a' to 'z'. Variables 'l', 'r', and 'p' are special: initially they are set to true iff the node has a left son ('l'), a right son ('r'), and a parent ('p'). All other variables are initally set to false. All variables are read-write, but it is generally recommended to leave 'l', 'r', and 'p' untouched. The automaton has a finite number of states. It begins its computation in the root of the tree. A general step of its computation looks as follows: The automaton is located in one of the nodes of the tree. Based on its current state and some flags in the current node, the automaton decides how to change it state, toggle some of the flags in the current node, and then possibly it moves along an edge to an adjacent node. More formally, the program for the automaton is a finite sequence of strings. The first of those strings is the identifier of the starting state. The rest of the program is a sequence of instructions. Each instruction has the following form: "current_state:conditions:new_state:toggle:move". Here: current_state is the identifier of the current state (any string of 1-10 letters and/or digits). conditions is a sequence of distinct conditions that all have to be satisfied. Each condition is a lowercase letter (letter x represents the condition "flag x is set to true") or an uppercase letter (representing the condition that the corresponding flag must be false). new_state is the identifier of the new state into which the automaton switches if this instruction is used. toggle is a list of distinct flags (lowercase letters) that will be toggled (from true to false and vice versa) if this instruction is used. move is either an empty string (with the meaning that the automaton remains in its current node) or a description of a movement: 'l' to the left son of the current node, 'r' to its right son, or 'p' to its parent. Instruction order matters: In each step, the automaton applies the first instruction in the program that can be applied. If no instruction can be applied, the execution of the program terminates. The execution of the program is also terminated if it attempts to move to a non-existing node of the tree (and that step still counts as executed). --------------------------------- Simulator. Simulator for these automata is available at [link will be available for the public after the contest]. (You may download a standalone Python3 version of the simulator, and for small inputs you may also run it online.) --------------------------------- Task. Write a program for the automaton that will find all deepest nodes in the tree. When your program terminates, the deepest nodes of the tree must be precisely those in which the 'x' flag is set. Submit a wrapper program: a program in any supported programming language that will return a String[] containing your program for the automaton. (Remember that element 0 of your return value should be the initial state for your program.) There are multiple test cases for the wrapper program. Each test case consists of a single int N representing the number of nodes in the trees on which your automaton will be tested. (Your wrapper program may return different programs for different values of N, but doing so is not necessary and does not really help you solve the task.) Your wrapper program will be tested twice and you will only score points if both tests pass. In the arena only tests with N <= 30 are allowed. During system tests we will also test your program (outside the arena) on tests with N <= 60,000. The program for the automaton must have the following properties: It must have at most 500 instructions. The instructions must have at most 6500 characters total. On any given tree with at most 30 vertices it must terminate within 20,000 steps. On any given tree with at most 60,000 vertices it must terminate within 200,000,000 steps. Remember that state names must be strings of 1-10 letters and/or digits. Definition Class: BinaryTreeAutomatonHard Method: construct Parameters: int Returns: String[] Method signature: String[] construct(int N) (be sure your method is public) Limits Time limit (s): 2.000 Memory limit (MB): 256 Stack limit (MB): 256 Notes - Please be mindful of the obfuscation rules. When including string constants in your program, please make sure they are in a reasonably human-readable form. - For each N that is actually used as a test case we have a deterministically chosen collection of N-node trees. The exact same collection will be used to test all submitted programs. Constraints - N will be between 1 and 30, inclusive. - (In additional tests N will be up to 60,000.) Examples 0) 1 Returns: {"start", "start::finish:x:" } The returned program will be tested on exactly one tree: the tree with a single node. (In the simulator this tree is encoded "--".) The algorithm will start in the state "start" in the root of the tree. It will perform exactly one step, in which it will change its state to "finish" and set the 'x' flag in the only node of the tree. 1) 2 Returns: {"start", "start:yY:explode::r", "start:l:start::l", "start:r:start::r", "start::finish:x:", "Hello47::Hello42::" } The returned program will be tested on exactly two trees with two nodes each. (In the simulator they are encoded "+---" and "-+--".) The automaton will start in the root of the tree in the state "start". The instruction "start:yY:explode::r" will never be executed: flag 'y' cannot be both set and unset at the same time, hence the conditions "yY" will never be satisfied. Exactly one of the two instructions "start:l:start::l", "start:r:start::r" will be executed exactly once (the automaton will move from the root to the only leaf). Once the automaton reaches the leaf, the previous two instructions no longer apply. Now the automaton will execute "start::finish:x:" and set the 'x' flag in the leaf. After that happens, the program will terminate. This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.