SHORTCIR - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

HARD

EXPLANATION

The solution can be described in several not really hard steps:

  1. Let us build a syntax tree for the expression with AND, OR, NOT as inner nodes and variables as leaves. Respect the standard priority of the operation when building the tree. However associativity doesn’t matter for the sake of this problem. Right away we can define P(V) for each node meaning the probability that this node will return true.

  2. Now we remove all NOTs from the tree using the following rules:
    a. NOT (NOT (E)) = E.
    b. NOT (AND (E1, E2)) = OR (NOT (E1), NOT (E2)).
    c. NOT (OR (E1, E2)) = AND (NOT (E1), NOT (E2)).
    d. NOT (V) = U, where V and U are variables (U is a new variable), having P(U) = 1 – P(V). Using this rule is correct, because all the variables are different.

  3. So after step 2 we have a tree with only AND and OR as inner node. Now we consider those operations to accept more than two operands and merge the nodes of the tree in the following way: AND(E1, AND(E2, E3)) = AND(E1, E2, E3), OR(E1, OR(E2, E3)) = OR(E1, E2, E3).

  4. After step 3 we will end up with AND/OR tree: any child of AND node will be a variable or an OR node, and any child of OR node – a variable or an AND node. For such a tree we can recursively calculate the expected amount of evaluations needed to result this node. The best order of evaluation of children can be derived for each node. The answer is the expected amount of evaluations for the root.

For the best order of evaluations for some inner node let us consider the following node: X = AND(E1, E2, …, En). If we fix any order of evaluations of children: F1, F2, … Fn. Then the expected number of evaluations will be: M(X) = M(F1) + P(F1) * (M(F2) + P(F2) * (M(F3) + …)). Let’s look at any two children. If we place Fi before Fj we get

[… + M(Fi) + P(Fi) * (… M(Fj) …)],

otherwise we get

[… + M(Fj) + P(Fj) * (… M(Fi) …)].

So the lesser is the value of this part the better is the order. We have:

M(Fi) + P(Fi) * M(Fj) ? M(Fj) + P(Fj) * M(Fj)

M(Fi) * (1 – P(Fj)) ? M(Fj) * (1 – P(Fi))

M(Fi)/(1 – P(Fi)) ? M(Fj)/(1 – P(Fj))

That means that in this case we should sort the children by M(E)/(1 – P(E)) to get the best order of evaluations. Similarly can be done for OR nodes.

However such approach turns to produce optimal solutions only for certain types of and/or trees. For example, for and/or trees of depths no more than two.

Additional information can be found in this paper: http://www.cs.toronto.edu/~molloy/webpapers/aotree.ps

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.