You are not logged in. Please login at www.codechef.com to post your questions!

×

SHORTCIR - Editorial

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

This question is marked "community wiki".

asked 23 Nov '12, 16:45

admin's gravatar image

0★admin ♦♦
19.8k350498541
accept rate: 36%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,359
×5
×1

question asked: 23 Nov '12, 16:45

question was seen: 1,051 times

last updated: 23 Nov '12, 16:45