Butterfly

Outline

• Start with problem statement
• Strategy and approach
• Motivation and applications once we mention problem-solving approach

Problem Statement

There are several events that are about to happen.

Each event has either a positive outcome or a negative outcome. These outcomes affect probabilities of outcomes of subsequent events.

Events occur in order given from input. For each event i there is an associated integer base value b_i.

To decide the outcome of an event we roll a fair m-sided die, sides marked 1 through m, and add the amount shown on the die to the base value. If the result is positive, the outcome is positive. Otherwise, if result is zero or negative, the negative outcome occurs.

If the positive outcome occurs, we modify the base values of all subsequent events according to a list of modifiers associated with the event. If the outcome of event i is positive, the new base value of event j is bj + pij, where pij is modifier to event j in case of positive outcome for event i.

If the negative outcome occurs, we do the same but with a different list of modifiers - the base value for event j becomes bj + qij, where qij is associated modifier.

You have power to intervene in a number of events. When you intervene, instead of rolling one die you can roll two die and select the one you prefer. For each event, you must decide whether to intervene immediately before die are rolled. Can you maximize proability of final event having positive outcome?

Input:

• First line is three integers n, k, m, with 1 <= k <= n <= 20, 4 <= m <= 1000
• Then there are 3n lines, with the three lines forming a trio:
  • One line with integer bi denotes base value of event i
  • One line with n - i space separated integers pi,i+1,...,pin denoting modifiers to base values of events i+1 through n in the case of positive outcome for event i
  • One line with n-i space separated integers qi,i+1,...,qin denoting modifiers to base values of events i+1 through n in the case of negative outcome for event i