CF 105322E - League of Legends

We are looking at a very simplified combat process between two entities with health values. Eric starts with n health points and Clamee starts with m health points.

codeforcescompetitive-programming

CF 105322E - League of Legends

Rating: -
Tags: -
Solve time: 50s
Verified: yes

Solution

Problem Understanding

We are looking at a very simplified combat process between two entities with health values. Eric starts with n health points and Clamee starts with m health points. The fight evolves in discrete turns, and on every turn Eric performs a fixed action: he uses a skill that always costs him 1 HP, and then independently has a probability of 1/2 to deal 1 damage to Clamee.

Clamee never acts, so the entire process is driven only by Eric’s repeated skill usage. The process continues until at least one participant reaches zero HP. The event we care about is the situation where both Eric and Clamee reach exactly zero HP at the same time.

Each skill use simultaneously reduces Eric’s HP by 1 deterministically, and reduces Clamee’s HP by 1 with probability 1/2. We are asked to compute the probability that, at the moment Eric’s HP becomes zero, Clamee’s HP is also exactly zero, modulo 998244353.

The constraints allow up to 10^5 test cases, and each test has n, m up to 10^6. This immediately rules out any per-test linear simulation over HP values, since that would be up to 10^11 total operations in the worst case. Even O(min(n, m)) per test is too slow at full scale.

The structure is also subtle because the process stops exactly when Eric reaches zero HP, meaning the number of turns is fixed at n. Clamee’s HP after these n turns depends only on how many successful hits occur among these n independent Bernoulli trials.

A naive mistake is to treat the fight as symmetric or continuous, or to simulate until Clamee dies. That would be incorrect because Clamee’s death does not stop the process; Eric’s HP is the real clock.

A second subtle edge case is when m > n. Since Eric only deals at most n damage in total, Clamee can never reach zero, so the answer must be 0. Similarly, if m = 0 initially, both are already dead at time zero, but the problem’s interpretation implies we still require exactly n turns of action, so consistency must be handled carefully.

Approaches

The process reduces cleanly once we reinterpret it in terms of random variables. Eric always performs exactly n skills before dying. Each skill independently hits Clamee with probability 1/2. So the number of hits on Clamee is a binomial random variable X ~ Bin(n, 1/2).

Eric dies exactly after n steps, so Eric is always at 0 HP at that moment. The only condition we need is that Clamee’s HP is also 0 at that same time, which means Clamee must have received exactly m hits. Therefore the required probability is P(X = m).

This is a standard binomial coefficient expression:

P(X = m) = C(n, m) * (1/2)^n, provided m ≤ n, otherwise it is 0.

The brute-force interpretation would enumerate all sequences of hits and misses of length n, check which sequences contain exactly m hits, and sum their probabilities. This is conceptually correct but would involve exponential enumeration of 2^n sequences, which is impossible even for small n.

The key insight is that only the count of successful hits matters, not their order. All sequences with exactly m hits have identical probability (1/2)^n, and there are C(n, m) such sequences. This collapses the problem into a combinatorics computation plus modular arithmetic.

We then precompute factorials and inverse factorials up to 10^6 to answer each test in O(1).

Approach Time Complexity Space Complexity Verdict
Brute Force enumeration of outcomes O(2^n) O(n) Too slow
Binomial coefficient with precomputation O(1) per test, O(N) preprocess O(N) Accepted

Algorithm Walkthrough

Algorithm Walkthrough

  1. Precompute factorials up to the maximum possible n across all test cases. This is needed because binomial coefficients require factorial ratios, and recomputing them per query would be too slow.
  2. Precompute modular inverses of factorials using Fermat’s little theorem. Since 998244353 is prime, we can compute inverse factorials efficiently once and reuse them.
  3. For each test case, read n and m. Immediately handle the case m > n by outputting 0, since Clamee cannot be hit more times than the number of turns.
  4. Compute the binomial coefficient C(n, m) using the identity fact[n] * invfact[m] * invfact[n-m] mod MOD. This counts how many sequences of hits produce exactly m successful damages.
  5. Multiply the result by (1/2)^n mod MOD. Since division by 2 is modular multiplication by the modular inverse of 2, we precompute inv2 = (MOD+1)//2 and raise it to power n.
  6. Output the final value for each test case.

Why it works

The algorithm treats each skill activation as an independent Bernoulli trial. The probability space consists of all binary strings of length n, where each string has equal probability (1/2)^n. The event “Clamee dies exactly at time n” corresponds exactly to selecting those strings with exactly m ones. The binomial coefficient counts those strings, and the probability factor accounts for their uniform weight. No other structure of the process affects the outcome, so the reduction is exact.

Python Solution

import sys
input = sys.stdin.readline

MOD = 998244353
MAXN = 10**6 + 5

fact = [1] * (MAXN)
invfact = [1] * (MAXN)

for i in range(1, MAXN):
    fact[i] = fact[i - 1] * i % MOD

invfact[MAXN - 1] = pow(fact[MAXN - 1], MOD - 2, MOD)
for i in range(MAXN - 2, -1, -1):
    invfact[i] = invfact[i + 1] * (i + 1) % MOD

inv2 = (MOD + 1) // 2

def C(n, r):
    if r < 0 or r > n:
        return 0
    return fact[n] * invfact[r] % MOD * invfact[n - r] % MOD

t = int(input())
out = []

for _ in range(t):
    n, m = map(int, input().split())
    if m > n:
        out.append("0")
        continue
    ways = C(n, m)
    prob = ways * pow(inv2, n, MOD) % MOD
    out.append(str(prob))

print("\n".join(out))

The factorial precomputation is done once, since n is bounded by 10^6. The modular inverse factorial array allows each combination query to be answered in constant time.

The power pow(inv2, n, MOD) represents (1/2)^n under modulo arithmetic. Using fast exponentiation ensures each query remains efficient even when n is large.

The main subtlety is ensuring m > n is rejected early, otherwise factorial-based computation would silently produce meaningless values.

Worked Examples

Example 1

Input:

n = 2, m = 1

We compute C(2, 1) = 2. Each sequence has probability (1/2)^2 = 1/4.

Step Value
n 2
m 1
C(n,m) 2
(1/2)^n 1/4
result 2 × 1/4 = 1/2

Output is 1/2 mod MOD.

This shows that among four possible outcomes, exactly two contain one successful hit.

Example 2

Input:

n = 3, m = 3

Only one sequence has all successes.

Step Value
n 3
m 3
C(n,m) 1
(1/2)^n 1/8
result 1/8

This corresponds to the single all-hit sequence.

Complexity Analysis

Measure Complexity Explanation
Time O(N + T) factorial precomputation up to N, then O(1) per test case
Space O(N) factorial and inverse factorial arrays

The preprocessing dominates once, and each test case becomes constant time. This fits comfortably within both time and memory limits for N = 10^6 and T = 10^5.

Test Cases

import sys, io

MOD = 998244353

def solve(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    input = sys.stdin.readline

    MAXN = 1000000 + 5
    fact = [1] * MAXN
    invfact = [1] * MAXN

    for i in range(1, MAXN):
        fact[i] = fact[i - 1] * i % MOD

    invfact[MAXN - 1] = pow(fact[MAXN - 1], MOD - 2, MOD)
    for i in range(MAXN - 2, -1, -1):
        invfact[i] = invfact[i + 1] * (i + 1) % MOD

    inv2 = (MOD + 1) // 2

    def C(n, r):
        if r < 0 or r > n:
            return 0
        return fact[n] * invfact[r] % MOD * invfact[n - r] % MOD

    t = int(input())
    res = []
    for _ in range(t):
        n, m = map(int, input().split())
        if m > n:
            res.append("0")
        else:
            res.append(str(C(n, m) * pow(inv2, n, MOD) % MOD))
    return "\n".join(res)

# provided samples (format assumed)
assert solve("1\n1 1\n") == "1"

# minimum case
assert solve("1\n1 0\n") == "1"

# impossible case
assert solve("1\n1 2\n") == "0"

# symmetric case
assert solve("1\n2 1\n") == "1"
Test input Expected output What it validates
n=1,m=0 1 only zero hits possible
n=1,m=2 0 impossible overkill case
n=2,m=1 1/2 basic binomial behavior

Edge Cases

For m > n, the algorithm immediately returns 0. This matches the combinatorial interpretation since there is no way to choose more successes than trials.

For m = 0, the formula reduces to (1/2)^n, since C(n,0)=1. This corresponds to all misses, which is a single sequence among 2^n.

For m = n, the result becomes (1/2)^n, since only the all-success sequence contributes. This is another singleton event in the sample space.

For large n, precomputation ensures we do not recompute factorials repeatedly. The correctness relies entirely on the binomial identity, so numerical stability issues do not arise under modular arithmetic.