Admin at 00:36, 19 June 2017

2017-06-19T00:36:33Z

← Older revision		Revision as of 00:36, 19 June 2017
Line 27:		Line 27:
	** 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 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		** 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



			[[Category:Final Project]]
			[[Category:CS]]
			[[Category:Programming]]
			[[Category:ICPC]]
			[[Category:Java]]
			[[Category:Probability]]

Admin: Created page with "==Outline== * Start with problem statement * Strategy and approach * Motivation and applications once we mention problem-solving approach ==Problem Statement== There are se..."

2017-06-19T00:35:47Z

Created page with "==Outline== * Start with problem statement * Strategy and approach * Motivation and applications once we mention problem-solving approach ==Problem Statement== There are se..."

New page

==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

Butterfly - Revision history

Admin at 00:36, 19 June 2017

Admin: Created page with "==Outline== * Start with problem statement * Strategy and approach * Motivation and applications once we mention problem-solving approach ==Problem Statement== There are se..."