Statistics

Problem Statement for "BinaryTreeAutomaton"

Problem Statement

Did you follow the TCO 2021 online finals?

In this task you too get a chance to write a program in a theoretical model of computation that was used in one of the tasks in the finals.


(This task is, of course, much easier. And don't worry if you didn't follow the TCO, everything you need is in this 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 its 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 https://algo.sk/topcoder/BinaryTreeAutomaton/

(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 select one maximum independent set in the given tree. (No two adjacent vertices may be selected, and the total number of selected vertices should be maximized.)

When your program terminates, vertices in which the 's' flag is set will be taken as those you selected.


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


Your program will be tested on trees with up to 100 vertices.

In each test case you are given int N representing the number of vertices in the trees on which your automaton will be tested. You may create different programs for different values of N, but doing so is not necessary and does not really help solve the task.


The program for the automaton must have the following properties:

  • It must have at most 120 instructions.
  • On any given tree it must terminate after at most 3,000 steps.

Definition

Class:
BinaryTreeAutomaton
Method:
construct
Parameters:
int
Returns:
String[]
Method signature:
String[] construct(int N)
(be sure your method is public)

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 100, inclusive.

Examples

  1. 1

    Returns: {"start", "start::finish:s:" }

    In this test case your program will be tested on a single tree: the tree with just the root. (In the simulator this tree has the description "--".) The example return value contains a program that simply sets the flag and terminates.

  2. 2

    Returns: {"start", "start:l:start::l", "start:xX:explode::r", "start:L:finish:s:", "Hello47::Hello42::" }

    In this test case your program will be tested on two trees that each have two nodes. In the simulator these trees have the descriptions "+---" and "-+--". The example return value contains a program that goes left while it can, and then it selects the current node and terminates. The program also contains an instruction that can never be executed because the conditions 'x' and 'X' will never both be satisfied at the same time, and a useless instruction for an unreachable state "Hello47".

  3. 3

    Returns: {"solve", "solve:bl:checkl::l", "solve:bL:goodl::", "checkl:s:badl::p", "checkl:S:goodl::p", "badl:p:solve::p", "badl:P:terminate::", "goodl:r:checkr::r", "goodl:R:goodr::", "checkr:s:badr::p", "checkr:S:goodr::p", "badr:p:solve::p", "badr:P:terminate::", "goodr:p:solve:s:p", "goodr:P:terminate:s:", "solve:aBr:solve:b:r", "solve:aBR:solve:b:", "solve:Al:solve:a:l", "solve:AL:solve:a:" }

  4. 4

    Returns: {"solve", "solve:bl:checkl::l", "solve:bL:goodl::", "checkl:s:badl::p", "checkl:S:goodl::p", "badl:p:solve::p", "badl:P:terminate::", "goodl:r:checkr::r", "goodl:R:goodr::", "checkr:s:badr::p", "checkr:S:goodr::p", "badr:p:solve::p", "badr:P:terminate::", "goodr:p:solve:s:p", "goodr:P:terminate:s:", "solve:aBr:solve:b:r", "solve:aBR:solve:b:", "solve:Al:solve:a:l", "solve:AL:solve:a:" }

  5. 5

    Returns: {"solve", "solve:bl:checkl::l", "solve:bL:goodl::", "checkl:s:badl::p", "checkl:S:goodl::p", "badl:p:solve::p", "badl:P:terminate::", "goodl:r:checkr::r", "goodl:R:goodr::", "checkr:s:badr::p", "checkr:S:goodr::p", "badr:p:solve::p", "badr:P:terminate::", "goodr:p:solve:s:p", "goodr:P:terminate:s:", "solve:aBr:solve:b:r", "solve:aBR:solve:b:", "solve:Al:solve:a:l", "solve:AL:solve:a:" }

  6. 6

    Returns: {"solve", "solve:bl:checkl::l", "solve:bL:goodl::", "checkl:s:badl::p", "checkl:S:goodl::p", "badl:p:solve::p", "badl:P:terminate::", "goodl:r:checkr::r", "goodl:R:goodr::", "checkr:s:badr::p", "checkr:S:goodr::p", "badr:p:solve::p", "badr:P:terminate::", "goodr:p:solve:s:p", "goodr:P:terminate:s:", "solve:aBr:solve:b:r", "solve:aBR:solve:b:", "solve:Al:solve:a:l", "solve:AL:solve:a:" }

  7. 7

    Returns: {"solve", "solve:bl:checkl::l", "solve:bL:goodl::", "checkl:s:badl::p", "checkl:S:goodl::p", "badl:p:solve::p", "badl:P:terminate::", "goodl:r:checkr::r", "goodl:R:goodr::", "checkr:s:badr::p", "checkr:S:goodr::p", "badr:p:solve::p", "badr:P:terminate::", "goodr:p:solve:s:p", "goodr:P:terminate:s:", "solve:aBr:solve:b:r", "solve:aBR:solve:b:", "solve:Al:solve:a:l", "solve:AL:solve:a:" }

  8. 10

    Returns: {"solve", "solve:bl:checkl::l", "solve:bL:goodl::", "checkl:s:badl::p", "checkl:S:goodl::p", "badl:p:solve::p", "badl:P:terminate::", "goodl:r:checkr::r", "goodl:R:goodr::", "checkr:s:badr::p", "checkr:S:goodr::p", "badr:p:solve::p", "badr:P:terminate::", "goodr:p:solve:s:p", "goodr:P:terminate:s:", "solve:aBr:solve:b:r", "solve:aBR:solve:b:", "solve:Al:solve:a:l", "solve:AL:solve:a:" }

  9. 23

    Returns: {"solve", "solve:bl:checkl::l", "solve:bL:goodl::", "checkl:s:badl::p", "checkl:S:goodl::p", "badl:p:solve::p", "badl:P:terminate::", "goodl:r:checkr::r", "goodl:R:goodr::", "checkr:s:badr::p", "checkr:S:goodr::p", "badr:p:solve::p", "badr:P:terminate::", "goodr:p:solve:s:p", "goodr:P:terminate:s:", "solve:aBr:solve:b:r", "solve:aBR:solve:b:", "solve:Al:solve:a:l", "solve:AL:solve:a:" }

  10. 48

    Returns: {"solve", "solve:bl:checkl::l", "solve:bL:goodl::", "checkl:s:badl::p", "checkl:S:goodl::p", "badl:p:solve::p", "badl:P:terminate::", "goodl:r:checkr::r", "goodl:R:goodr::", "checkr:s:badr::p", "checkr:S:goodr::p", "badr:p:solve::p", "badr:P:terminate::", "goodr:p:solve:s:p", "goodr:P:terminate:s:", "solve:aBr:solve:b:r", "solve:aBR:solve:b:", "solve:Al:solve:a:l", "solve:AL:solve:a:" }

  11. 70

    Returns: {"solve", "solve:bl:checkl::l", "solve:bL:goodl::", "checkl:s:badl::p", "checkl:S:goodl::p", "badl:p:solve::p", "badl:P:terminate::", "goodl:r:checkr::r", "goodl:R:goodr::", "checkr:s:badr::p", "checkr:S:goodr::p", "badr:p:solve::p", "badr:P:terminate::", "goodr:p:solve:s:p", "goodr:P:terminate:s:", "solve:aBr:solve:b:r", "solve:aBR:solve:b:", "solve:Al:solve:a:l", "solve:AL:solve:a:" }

  12. 83

    Returns: {"solve", "solve:bl:checkl::l", "solve:bL:goodl::", "checkl:s:badl::p", "checkl:S:goodl::p", "badl:p:solve::p", "badl:P:terminate::", "goodl:r:checkr::r", "goodl:R:goodr::", "checkr:s:badr::p", "checkr:S:goodr::p", "badr:p:solve::p", "badr:P:terminate::", "goodr:p:solve:s:p", "goodr:P:terminate:s:", "solve:aBr:solve:b:r", "solve:aBR:solve:b:", "solve:Al:solve:a:l", "solve:AL:solve:a:" }

  13. 97

    Returns: {"solve", "solve:bl:checkl::l", "solve:bL:goodl::", "checkl:s:badl::p", "checkl:S:goodl::p", "badl:p:solve::p", "badl:P:terminate::", "goodl:r:checkr::r", "goodl:R:goodr::", "checkr:s:badr::p", "checkr:S:goodr::p", "badr:p:solve::p", "badr:P:terminate::", "goodr:p:solve:s:p", "goodr:P:terminate:s:", "solve:aBr:solve:b:r", "solve:aBR:solve:b:", "solve:Al:solve:a:l", "solve:AL:solve:a:" }

  14. 98

    Returns: {"solve", "solve:bl:checkl::l", "solve:bL:goodl::", "checkl:s:badl::p", "checkl:S:goodl::p", "badl:p:solve::p", "badl:P:terminate::", "goodl:r:checkr::r", "goodl:R:goodr::", "checkr:s:badr::p", "checkr:S:goodr::p", "badr:p:solve::p", "badr:P:terminate::", "goodr:p:solve:s:p", "goodr:P:terminate:s:", "solve:aBr:solve:b:r", "solve:aBR:solve:b:", "solve:Al:solve:a:l", "solve:AL:solve:a:" }

  15. 99

    Returns: {"solve", "solve:bl:checkl::l", "solve:bL:goodl::", "checkl:s:badl::p", "checkl:S:goodl::p", "badl:p:solve::p", "badl:P:terminate::", "goodl:r:checkr::r", "goodl:R:goodr::", "checkr:s:badr::p", "checkr:S:goodr::p", "badr:p:solve::p", "badr:P:terminate::", "goodr:p:solve:s:p", "goodr:P:terminate:s:", "solve:aBr:solve:b:r", "solve:aBR:solve:b:", "solve:Al:solve:a:l", "solve:AL:solve:a:" }

  16. 100

    Returns: {"solve", "solve:bl:checkl::l", "solve:bL:goodl::", "checkl:s:badl::p", "checkl:S:goodl::p", "badl:p:solve::p", "badl:P:terminate::", "goodl:r:checkr::r", "goodl:R:goodr::", "checkr:s:badr::p", "checkr:S:goodr::p", "badr:p:solve::p", "badr:P:terminate::", "goodr:p:solve:s:p", "goodr:P:terminate:s:", "solve:aBr:solve:b:r", "solve:aBR:solve:b:", "solve:Al:solve:a:l", "solve:AL:solve:a:" }

  17. 47

    Returns: {"solve", "solve:bl:checkl::l", "solve:bL:goodl::", "checkl:s:badl::p", "checkl:S:goodl::p", "badl:p:solve::p", "badl:P:terminate::", "goodl:r:checkr::r", "goodl:R:goodr::", "checkr:s:badr::p", "checkr:S:goodr::p", "badr:p:solve::p", "badr:P:terminate::", "goodr:p:solve:s:p", "goodr:P:terminate:s:", "solve:aBr:solve:b:r", "solve:aBR:solve:b:", "solve:Al:solve:a:l", "solve:AL:solve:a:" }

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)2024, TopCoder, Inc. All rights reserved.
This problem was used for: