Connection Status:
Competition Arena > AntiMatter

AntiMatter

SRM 179 · 2004-01-17 · by dgoodman

SRM 179 · 2004-01-17 · by dgoodman · Dynamic Programming
Class Name: AntiMatter
Return Type: String
Method Name: unstable
Arg Types: (vector<int>)
Problem Statement

Problem Statement

We are studying sub-atomic particles. At regular time intervals, all the particles simultaneously undergo a transformation. The state of each particle can be represented by an integer value (which can be arbitrarily large), and each transformation changes the state of a particle by one of 4 values. At each transformation time, each of the particles independently undergoes one of the 4 changes. Each of the four possibilities is equally likely to occur to each particle.

We believe that whenever two adjacent particles transform to have identical states, they annihilate each other. We will call a pair of particles "unstable" if there is a sequence of transformations that could lead to an annihilation.

We need to estimate the probability that two adjacent particles are unstable. To make this specific, we will choose two particles and assume that each is equally likely to have any initial state between -4999 and 5000 inclusive (a state of 0 is possible). Create a class AntiMatter that contains a method unstable that receives a int[] xform containing the 4 legal transformation amounts and returns the probability that there exists a sequence of transformations for the two particles that would lead to mutual annihilation.

The method should return the probability as a String with a decimal point, exactly eight digits to the right of the decimal point, and no leading zeros. Since there are 100,000,000 equally likely pairs, this probability will be exact.

Constraints

  • xform will contain exactly 4 elements (not necessarily distinct).
  • Each element in xform will be between -10,000 and 10,000 inclusive.
Examples
0)
{6,6,6,6}
Returns: ".00010000"

Every transition of each particle increases its state by 6, so unless the two particles start with identical states and annihilate immediately, they can never reach identical states. There are 10,000 pairs of particles that immediately annihilate.

1)
{0,0,0,0}
Returns: ".00010000"
2)
{2,-3,4,-5}
Returns: "1.00000000"
3)
{9993,-7,743,-7}
Returns: ".00400000"
4)
{-10000,9997,9999,10000}
Returns: "1.00000000"
6)
{1,-1,1,-1}
Returns: ".50000000"

If two particles initially have states that differ by an odd number, then after every transition they will still differ by an odd number, so they can never annihilate. But if they start with an even difference in their states, then the lower one can always increase its state by 1 while the higher one decreases by 1, leading eventually to annihilation. Since half of the 100,000,000 pairs are either even-even or odd-odd, 50,000,000 are unstable.

7)
{0,1,-1,1}
Returns: "1.00000000"

The lower particle can stay at its initial state by transforming by 0 each time, while the higher particle transforms by -1 until annihilation occurs.

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

Coding Area

Language: C++17 · define a public class AntiMatter with a public method string unstable(vector<int> xform) · 19 test cases · 2 s / 256 MB per case

Submitting as anonymous