Soluție HackerRank pentru The Matchstick Experiment, subdomeniul Probability, în Python 3. Include cerința formatată, exemple, explicația pașilor și cod…
- Problemă: The Matchstick Experiment
- Domeniu: Probability
- Limbaj: Python 3
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
Cerință
In an n × m grid, 2 · n · m - n - m matchsticks are placed at the boundaries between cells. For example, if n = 5 and m = 9, the 2 · 5 · 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 · n · m - n - m matchsticks. -->
1. For each of the 2· n· 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 ≤ 3 cells, divided by n · 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 ≤ 3 cells. The diagram below counts all such components consisting of ≤ 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 ≤ 3. From this, we perform the following calculation:
score = frac{(text{connected components with size } ≤ 3)}{n · m} = (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 ≤ p ≤ 1
+ 1 ≤ q, n, m ≤ 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 ≤ 300
Cod sursă
#!/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()