Connection Status:
Competition Arena > ReturnOfTheJedi

ReturnOfTheJedi

SRM 678 · 2016-01-04 · by cgy4ever

SRM 678 · 2016-01-04 · by cgy4ever · Math
Class Name: ReturnOfTheJedi
Return Type: double[]
Method Name: minimalExpectation
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

The following story takes place on Endor, during a battle between the imperial forces and Ewoks.
The Ewoks are currently hiding in a forest.
The Empire is going to send a scout on a flying bike into the forest for reconnaisance.

The Ewoks are preparing a series of traps for the scout.
Each trap has two parameters: p[i] and x[i].
The value (p[i]/100,000) is the probability that a scout who enters the trap survives it.
If the scout does survive, he immediately gains information that is worth x[i] credits.

Ewoks know that the scout will use the following strategy, for some value of K:
  1. The scout will attempt to fly through the first K traps, one after another.
  2. If any of the K traps kills the scout, his mission fails and the Empire gets no information. (That is, the value of the information retrieved by the scout in this case is 0 credits.)
  3. If the scout survives the first K traps, he will turn back, safely leave the forest and bring the collected information to the Empire's headquarters.
You are given the parameters of the Ewoks' N traps: the int[]s p and x with N elements each.
The traps can be placed into the forest in any order.
For each K between 1 and N, inclusive, solve the following problem:

We know that the scout will follow the above strategy, and we know the value K the scout will use.
There are N! possible orders of traps in the forest.
For each of these orders we can calculate the expected value of information that will be obtained by the scout.
Compute the minimum of all those expected values. (In other words, find the order of traps that minimizes the expected value of the scout's information, and compute that expected value.)

Return a double[] with N elements.
For each i between 0 and N-1, inclusive, element i (0-based index) of the return value should be the solution to the above problem for K = i+1.

Notes

  • Each element of your return value must have a relative or absolute error less than 1e-9.

Constraints

  • x will contain between 1 and 400 elements, inclusive.
  • x and prob will contain the same number of elements.
  • Each element in x will be between 1 and 1,000,000,000, inclusive.
  • Each element in p will be between 1 and 100,000, inclusive.
Examples
0)
{100,200,300}
{50000, 20000, 20000}
Returns: {40.0, 20.000000000000004, 12.000000000000002 }

For k = 1: If we use the 0-th trap first, then the expectation will be 100 * 0.5 = 50 If we use the 1-th trap first, then the expectation will be 200 * 0.2 = 40 If we use the 2-th trap first, then the expectation will be 300 * 0.2 = 60 For k = 2: One possible order is {1,2,0}. Expectation is (200 + 300) * 0.2 * 0.2 = 20.

1)
{200,100,500,300,400}
{100000, 100000, 100000, 100000, 100000}
Returns: {100.0, 300.0, 600.0, 1000.0, 1500.0 }
2)
{2,2,100,100}
{100000,100000,10000,10000}
Returns: {2.0, 2.0000000000000004, 2.0200000000000005, 2.0400000000000005 }
3)
{1,1,200,200}
{100000,100000,10000,10000}
Returns: {1.0, 2.0, 4.010000000000001, 4.0200000000000005 }
4)
{1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}
{90000,90000,90000,90000,90000,90000,90000,90000,90000,90000}
Returns: {9.0E8, 1.62E9, 2.1870000000000005E9, 2.6244000000000005E9, 2.952450000000001E9, 3.188646000000001E9, 3.348078300000001E9, 3.4437376800000014E9, 3.4867844010000014E9, 3.4867844010000014E9 }

Submissions are judged against all 26 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ReturnOfTheJedi with a public method vector<double> minimalExpectation(vector<int> x, vector<int> p) · 26 test cases · 2 s / 256 MB per case

Submitting as anonymous