Challenge: The Matchstick Experiment
Subdomeniu: Probability (probability)
Scor cont: 40.0 / 40
Submission status: Accepted
Submission score: 1.0
Submission ID: 464752993
Limbaj: python3
Link challenge: https://www.hackerrank.com/challenges/matchstick-experiment/problem
Cerinta
In an $n \times m$ grid, $2 \cdot n \cdot m - n - m$ matchsticks are placed at the boundaries between cells. For example, if $n = 5$ and $m = 9$, the $2 \cdot 5 \cdot 9 - 5 - 9 = 76$ matchsticks are placed in the following way:
<!-- https://s3.amazonaws.com/hr-challenge-images/0/1482774196-8139dcea71-Matchstickexperiment1.png -->
**The Experiment**
<!-- 1. Remove each matchstick $i$ that has a certain probability of removal, $p$, from the $2 \cdot n \cdot m - n - m$ matchsticks. -->
1. For each of the $2\cdot n\cdot m - n - m$ matchsticks, remove it with probability $p$.
2. We define a *connected component* to be a maximal set of cells not isolated from one another by matchsticks. We calculate our $score$ as the number of connected components in the grid with $\le 3$ cells, divided by $n \cdot m$.
For example, suppose our grid looks like this after performing the first step:
<!-- https://s3.amazonaws.com/hr-challenge-images/0/1482774211-8d7fdda32a-Matchstickexperiment2.png -->
To calculate our $score$, we need to first find the number of connected components having $\le 3$ cells. The diagram below counts all such components consisting of $\le 3$ connected cells:
<!-- https://s3.amazonaws.com/hr-challenge-images/0/1482774276-e1f1c57162-Matchstickexperiment3.png -->
As you can see, there are $16$ connected components of size $\le 3$. From this, we perform the following calculation:
$$score = \frac{(\text{connected components with size } \le 3)}{n \cdot m} = \frac{16}{45} \approx 0.35555555$$
----
You are given $q$ queries where each query consists of $n$, $m$, and $p$. For each query, find and print the *expected* value of $score$ on a new line.
**Need Help?** Check out [this learning aid](http://www.cs.princeton.edu/courses/archive/fall06/cos341/handouts/variance-notes.pdf) explaining some important properties of *expected values*.Input Format
The first line contains an integer, $q$, denoting the number of queries.
Each of the $q$ subsequent lines contains three space-separated integers describing the respective values of integer $n$, integer $m$, and real number $p$.Output Format
For each query, print a single real number on a new line denoting the answer to the query. Any answer having an absolute error within $10^{-9}$ of the true answer is acceptable.Constraints
+ $0 \le p \le 1$
+ $1 \le q, n, m \le 10^5$
+ $p$ is a real number scaled to two decimal places (e.g., $1.23$).
**Subtask**
+ For $\text{40%}$ of the total score, $q, n, m \le 300$Cod sursa
#!/bin/python3
import sys
def expected_score(n: int, m: int, p: float) -> float:
a = 1.0 - p
# 1D line graph case.
if n == 1 or m == 1:
L = max(n, m)
if L == 1:
e1 = 1.0
else:
e1 = 2.0 * a + max(0, L - 2) * (a * a)
e2 = 0.0
if L >= 2:
interior = max(0, L - 3)
end = 2 if L > 2 else 0
whole = 1 if L == 2 else 0
e2 = p * (interior * a * a + end * a + whole)
e3 = 0.0
if L >= 3:
interior = max(0, L - 4)
end = 2 if L > 3 else 0
whole = 1 if L == 3 else 0
e3 = p * p * (interior * a * a + end * a + whole)
return (e1 + e2 + e3) / L
nm = n * m
# Size-1 components.
e1 = 4.0 * (a ** 2) + (2 * n + 2 * m - 8) * (a ** 3) + (n - 2) * (m - 2) * (a ** 4)
# Size-2 components.
h = 0.0
row_types = [(1, 2)]
if n - 2 > 0:
row_types.append((0, n - 2))
if m == 2:
col_types = [(1, 1, 1)]
else:
col_types = [(1, 0, 1), (0, 1, 1)]
if m - 3 > 0:
col_types.append((0, 0, m - 3))
for rb, rc in row_types:
for cl, cr, cc in col_types:
h += rc * cc * (a ** (6 - 2 * rb - cl - cr))
v = 0.0
col_v_types = [(1, 2)]
if m - 2 > 0:
col_v_types.append((0, m - 2))
if n == 2:
row_pair_types = [(1, 1, 1)]
else:
row_pair_types = [(1, 0, 1), (0, 1, 1)]
if n - 3 > 0:
row_pair_types.append((0, 0, n - 3))
for cb, cc in col_v_types:
for rt, rb, rc in row_pair_types:
v += cc * rc * (a ** (6 - (rt + rb) - 2 * cb))
e2 = p * (h + v)
# Size-3 components.
# Horizontal triples (only when m >= 3)
ht = 0.0
if m >= 3:
row_t_types = [(1, 2)]
if n - 2 > 0:
row_t_types.append((0, n - 2))
if m == 3:
h_start_types = [(1, 1, 1)]
elif m == 4:
h_start_types = [(1, 0, 1), (0, 1, 1)]
else:
h_start_types = [(1, 0, 1), (0, 1, 1), (0, 0, m - 4)]
for rb, rc in row_t_types:
for lt, rt, sc in h_start_types:
ht += rc * sc * (a ** (8 - 3 * rb - lt - rt))
# Vertical triples (only when n >= 3)
vt = 0.0
if n >= 3:
col_t_types = [(1, 2)]
if m - 2 > 0:
col_t_types.append((0, m - 2))
if n == 3:
v_start_types = [(1, 1, 1)]
elif n == 4:
v_start_types = [(1, 0, 1), (0, 1, 1)]
else:
v_start_types = [(1, 0, 1), (0, 1, 1), (0, 0, n - 4)]
for cb, cc in col_t_types:
for ut, dt, sc in v_start_types:
vt += cc * sc * (a ** (8 - 3 * cb - ut - dt))
# L-shaped triominoes inside 2x2 blocks.
lsum = 0.0
if n == 2:
row_block_types = [(1, 1, 1)]
else:
row_block_types = [(1, 0, 1), (0, 1, 1)]
if n - 3 > 0:
row_block_types.append((0, 0, n - 3))
if m == 2:
col_block_types = [(1, 1, 1)]
else:
col_block_types = [(1, 0, 1), (0, 1, 1)]
if m - 3 > 0:
col_block_types.append((0, 0, m - 3))
for r1, r2, rc in row_block_types:
for c1, c2, cc in col_block_types:
d00 = 4 - r1 - c1
d01 = 4 - r1 - c2
d10 = 4 - r2 - c1
d11 = 4 - r2 - c2
block_sum = (
(a ** (d01 + d10 + d11 - 4))
+ (a ** (d00 + d10 + d11 - 4))
+ (a ** (d00 + d01 + d11 - 4))
+ (a ** (d00 + d01 + d10 - 4))
)
lsum += rc * cc * block_sum
e3 = p * p * (ht + vt + lsum)
return (e1 + e2 + e3) / nm
def parse_p(token: bytes) -> float:
p = float(token)
if p > 1.0:
p /= 100.0
return p
def main():
data = sys.stdin.buffer.read().split()
if not data:
return
q = int(data[0])
out = []
ptr = 1
for _ in range(q):
n = int(data[ptr])
m = int(data[ptr + 1])
p = parse_p(data[ptr + 2])
ptr += 3
out.append(f"{expected_score(n, m, p):.12f}")
sys.stdout.write("\n".join(out))
if __name__ == '__main__':
main()
HackerRank Probability – The Matchstick Experiment