CF 105540D - The Emperor
The problem is a probabilistic process on three competing populations. You start with a fixed number of rocks, scissors, and papers. Over time, pairs of individuals are chosen uniformly at random from all remaining individuals.
Rating: -
Tags: -
Solve time: 49s
Verified: yes
Solution
Problem Understanding
The problem is a probabilistic process on three competing populations. You start with a fixed number of rocks, scissors, and papers. Over time, pairs of individuals are chosen uniformly at random from all remaining individuals. If the two chosen types are different, one of them is eliminated according to the rock-paper-scissors rule: rock beats scissors, scissors beats paper, paper beats rock. If the pair is of the same type, nothing happens.
This process continues until only one species remains. The task is to compute, for each of the three species, the probability that it becomes the sole survivor of the entire process.
The input is just three integers representing the initial counts of rocks, scissors, and papers. The output is three real numbers giving the final survival probabilities in that order.
The important constraint is that each count is at most 100, which rules out any exponential state explosion. A state space of size roughly 100 cubed is about one million configurations, which is just about feasible for a dynamic programming approach. Anything involving enumerating all possible sequences of interactions is immediately too large, since the number of possible event sequences grows factorially with the total population size.
A naive idea would be to simulate the random process many times using Monte Carlo. That would converge slowly and cannot guarantee the required precision within time limits, especially when probabilities become very small or very close.
Another common pitfall is trying to model the process as independent pairwise eliminations. For example, assuming rocks independently eliminate scissors at some rate without accounting for scissors also eliminating papers distorts the dynamics. The interaction is cyclic and coupled, so partial models break symmetry and give incorrect probabilities.
A subtle edge case appears when one of the species starts at zero. For example, if scissors is zero initially, rock and paper still interact directly in a reduced two-species system, and the answer should reduce to a deterministic absorption between those two types. Any solution that assumes all three species are always present will mishandle these boundaries.
Approaches
The brute-force perspective is to simulate the entire stochastic process over all possible states and transitions. Each state is defined by a triple (r, s, p), and from that state, the next event depends on choosing any pair of individuals uniformly among all pairs. From a state with n total individuals, there are O(n^2) possible pairs, and each pair either produces a transition or does nothing. Expanding this into a full probability tree leads to an exponential number of branches. Even with memoization over states, enumerating all sequences of events directly is infeasible because the branching factor remains tied to the number of possible interactions.
The key observation is that the process is memoryless with respect to state counts. Once you fix (r, s, p), all future evolution depends only on these counts, not on history. This allows us to define a probability function f(r, s, p) representing the probability that rocks eventually win starting from that state. The same applies to the other two species. The next step is to express f(r, s, p) in terms of smaller states by conditioning on the very next interaction.
From a given state, the next pair chosen is uniformly random among all pairs of distinct individuals. The probability that the next event reduces r by one is proportional to the number of rock-scissors pairs, similarly for scissors-paper and paper-rock. This produces a direct recurrence between states of strictly smaller total population size, because every non-trivial interaction removes exactly one individual. This gives a clean dynamic programming ordering by decreasing total population.
The brute-force fails because it tries to reason over sequences, while the correct formulation compresses all randomness into local transition probabilities between states.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Full simulation of all event sequences | Exponential | O(1) | Too slow |
| DP over states (r, s, p) | O(n³) | O(n³) | Accepted |
Algorithm Walkthrough
We define three DP tables: probR[r][s][p], probS[r][s][p], probP[r][s][p], where each entry represents the probability that rocks, scissors, or papers respectively become the final survivor starting from that state.
- We initialize all DP values to zero except base cases where only one species remains. If r > 0 and s = p = 0, then probR[r][0][0] = 1. Similarly for the other two species. This encodes that if only one species exists, the outcome is already determined.
- We iterate over all states in increasing total population size. This ordering ensures that when we compute a state (r, s, p), all transitions to smaller states are already known.
- For a state (r, s, p), compute the total number of possible interacting pairs among different species. There are r·s rock-scissors pairs, s·p scissors-paper pairs, and p·r paper-rock pairs. The sum of these determines how often the state actually changes.
- We distribute probability mass based on which interaction happens next. If a rock meets scissors, scissors is removed and we move to (r, s−1, p). If scissors meets paper, we go to (r, s, p−1). If paper meets rock, we go to (r−1, s, p). Each transition is weighted by its relative probability among all valid interacting pairs.
- We accumulate contributions into the DP table using these transition probabilities, effectively pushing probability mass from the current state into smaller states.
- We repeat this for all states until reaching the initial configuration (r, s, p), whose values give the final answer.
The reason this ordering works is that every valid transition strictly reduces r + s + p by exactly one. That guarantees the DP graph is acyclic when sorted by total population. The recurrence is therefore well-defined and cannot loop back to an already uncomputed state.
Python Solution
import sys
input = sys.stdin.readline
MAX = 105
r0, s0, p0 = map(int, input().split())
probR = [[[0.0] * MAX for _ in range(MAX)] for _ in range(MAX)]
probS = [[[0.0] * MAX for _ in range(MAX)] for _ in range(MAX)]
probP = [[[0.0] * MAX for _ in range(MAX)] for _ in range(MAX)]
for i in range(MAX):
probR[i][0][0] = 1.0
probS[0][i][0] = 1.0
probP[0][0][i] = 1.0
for r in range(MAX):
for s in range(MAX):
for p in range(MAX):
if r + s + p <= 1:
continue
total = r * s + s * p + p * r
if total == 0:
continue
if r > 0 and s > 0:
probR[r][s][p] += probR[r][s-1][p] * (r * s / total)
probS[r][s][p] += probS[r][s-1][p] * (r * s / total)
probP[r][s][p] += probP[r][s-1][p] * (r * s / total)
if s > 0 and p > 0:
probR[r][s][p] += probR[r][s][p-1] * (s * p / total)
probS[r][s][p] += probS[r][s][p-1] * (s * p / total)
probP[r][s][p] += probP[r][s][p-1] * (s * p / total)
if p > 0 and r > 0:
probR[r][s][p] += probR[r-1][s][p] * (p * r / total)
probS[r][s][p] += probS[r-1][s][p] * (p * r / total)
probP[r][s][p] += probP[r-1][s][p] * (p * r / total)
print(f"{probR[r0][s0][p0]:.12f} {probS[r0][s0][p0]:.12f} {probP[r0][s0][p0]:.12f}")
The implementation directly encodes the recurrence derived from conditioning on the next interaction. Each term corresponds to one of the three possible cross-species encounters. A frequent implementation mistake is to forget that transitions must use already-computed smaller states; iterating by increasing r + s + p ensures this property holds naturally.
Floating-point accumulation is safe here because the state space is small and probabilities remain bounded. Using double precision is sufficient for the required 1e-9 accuracy.
Worked Examples
Consider the input 2 2 2.
| State (r,s,p) | Transition idea | Contribution behavior |
|---|---|---|
| (2,2,2) | all three interactions possible | splits evenly due to symmetry |
| (2,1,2) | reduced scissors state | propagates asymmetry |
| (1,2,2) | symmetric counterpart | mirrors previous case |
This trace shows that symmetry in the initial state leads to equal probabilities, since every transition has a mirrored counterpart exchanging roles of the species.
Now consider 2 1 2.
| State (r,s,p) | Dominant interaction | Effect |
|---|---|---|
| (2,1,2) | paper-rock frequent | rocks get eliminated more often |
| (2,0,2) | rock-paper only | reduces to two-species cycle |
| (1,1,2) | scissors weak presence | scissors rarely survives |
This demonstrates how imbalance in initial counts biases transition flow toward the species that dominates its direct predator.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n³) | Every state (r,s,p) is processed once, with O(1) transitions |
| Space | O(n³) | Three DP arrays over all states |
With n ≤ 100, the total number of states is about one million, which is well within limits for Python or C++ under a 2 second time limit when implemented carefully.
Test Cases
import sys, io
def run(inp: str) -> str:
sys.stdin = io.StringIO(inp)
import math
MAX = 105
r0, s0, p0 = map(int, sys.stdin.readline().split())
probR = [[[0.0] * MAX for _ in range(MAX)] for _ in range(MAX)]
probS = [[[0.0] * MAX for _ in range(MAX)] for _ in range(MAX)]
probP = [[[0.0] * MAX for _ in range(MAX)] for _ in range(MAX)]
for i in range(MAX):
probR[i][0][0] = 1.0
probS[0][i][0] = 1.0
probP[0][0][i] = 1.0
for r in range(MAX):
for s in range(MAX):
for p in range(MAX):
if r + s + p <= 1:
continue
total = r * s + s * p + p * r
if total == 0:
continue
if r > 0 and s > 0:
probR[r][s][p] += probR[r][s-1][p] * (r*s/total)
probS[r][s][p] += probS[r][s-1][p] * (r*s/total)
probP[r][s][p] += probP[r][s-1][p] * (r*s/total)
if s > 0 and p > 0:
probR[r][s][p] += probR[r][s][p-1] * (s*p/total)
probS[r][s][p] += probS[r][s][p-1] * (s*p/total)
probP[r][s][p] += probP[r][s][p-1] * (s*p/total)
if p > 0 and r > 0:
probR[r][s][p] += probR[r-1][s][p] * (p*r/total)
probS[r][s][p] += probS[r-1][s][p] * (p*r/total)
probP[r][s][p] += probP[r-1][s][p] * (p*r/total)
return f"{probR[r0][s0][p0]:.12f} {probS[r0][s0][p0]:.12f} {probP[r0][s0][p0]:.12f}"
# provided samples
assert run("2 2 2\n")[:5] == "0.333"
assert run("2 1 2\n")[:5] == "0.150"
# custom cases
assert run("1 1 1\n") # symmetric smallest nontrivial
assert run("1 0 0\n").startswith("1.000"), "single species"
assert run("10 0 0\n").startswith("1.000"), "edge dominance"
assert run("2 0 2\n") # two species cycle case
| Test input | Expected output | What it validates |
|---|---|---|
| 1 1 1 | symmetric distribution | base symmetry correctness |
| 1 0 0 | 1 0 0 | single-species base case |
| 10 0 0 | 1 0 0 | large single-species stability |
| 2 0 2 | valid probabilities | two-species reduction case |
Edge Cases
For the case 1 0 0, the algorithm immediately hits a base condition where only rocks exist. The DP table initializes probR[1][0][0] to 1, and no transitions apply because total interaction count is zero. The output correctly returns 1 0 0.
For 2 0 2, only rock and paper interact. The transition reduces the system to a two-dimensional chain where only paper-rock interactions matter. The DP naturally collapses scissors dimension to zero and propagates probability through valid transitions, eventually resolving to a deterministic winner distribution depending on which side eliminates the other first.