CF 104568B - Red Tape Committee

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

Solution

Problem Understanding

We are asked to assemble a committee of exactly K people from a pool of N candidates. Each candidate behaves independently, and each one has a known probability Pi of voting “Yes”. A vote is always either Yes or No, so each candidate is a biased coin flip.

Once the committee is chosen, all K members vote, and we care about the probability that the final result is a tie, meaning exactly K/2 votes are Yes and K/2 are No. The task is not to analyze a fixed committee, but to choose which K people to include so that this tie probability is as large as possible.

The input consists of multiple test cases. For each one, we are free to pick any subset of size K, and then we compute the probability distribution induced by independent Bernoulli variables on that subset. The output is the maximum possible probability of landing exactly at K/2 successes.

The constraints imply that brute forcing all subsets is impossible once N grows. Even for moderate N, the number of ways to choose K people is combinatorial, on the order of C(N, K), which becomes astronomically large for N = 200. Even evaluating a single committee requires computing a distribution over K+1 possible vote totals, which already suggests a quadratic dependency on K. This immediately rules out any approach that tries to enumerate committees directly.

A subtle failure case for naive reasoning is assuming that picking people with probabilities closest to 0.5 is always optimal. That intuition is often correct in isolation but fails when combined selection interacts non-linearly. For example, consider probabilities 0.49, 0.51, 0.9, 0.1 with K = 2. Greedily picking the two closest to 0.5 gives 0.49 and 0.51, but picking 0.1 and 0.9 yields a deterministic tie with probability 1.0. The correct solution must consider interactions between chosen probabilities, not just their individual balance.

Approaches

A direct approach fixes a subset of K people and computes the probability that exactly K/2 of them vote Yes. For a fixed subset, this is a classic convolution of K independent Bernoulli distributions. Each candidate contributes a two-term polynomial, where the coefficient of x^0 is (1 − Pi) and the coefficient of x^1 is Pi. Multiplying all K polynomials gives a degree-K polynomial, and the coefficient at x^(K/2) is the tie probability.

This computation for one subset costs O(K^2), because each new person updates the DP distribution by shifting and mixing probabilities. However, the difficulty is that we do not know which K people to choose.

If we brute force all subsets of size K, we would need to evaluate C(N, K) possibilities, and each evaluation costs O(K^2), leading to an exponential explosion that is completely infeasible for N up to 200.

The key observation is that we do not need to decide the subset explicitly in a combinatorial way. Instead, we can build it incrementally using dynamic programming over items, tracking both how many people we have selected and what distribution over vote counts we can achieve.

We define a DP state that represents the best achievable distribution after considering some prefix of candidates and selecting exactly j of them. For each j, we maintain an array over possible numbers of Yes votes. When processing a new candidate with probability p, we decide whether to include them. If we include them, the distribution shifts via convolution with (1 − p, p). If we exclude them, we carry forward the previous state. This is essentially a knapsack where the “value” is a probability distribution instead of a scalar.

This transforms the problem from combinatorial subset enumeration into structured DP over selections.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force subsets + DP per subset	O(C(N, K) · K^2)	O(K)	Too slow
DP over items and selection size	O(N · K^2)	O(K^2)	Accepted

Algorithm Walkthrough

## Algorithm Walkthrough

We create a DP table where dp[j][t] represents the maximum probability (over all ways of selecting j people so far) that exactly t of them vote Yes. The goal is dp[K][K/2] after processing all candidates.
Initialize the table with dp[0][0] = 1, meaning selecting nothing yields zero Yes votes with probability 1. All other states start at 0 because they are impossible.
Process each candidate one by one. For a candidate with probability p, we consider whether to include them in the committee.
We update selection counts in reverse order from j = K down to 1. This prevents overwriting states we still need from smaller j, ensuring each candidate is used at most once.
If we include the candidate in a group of size j, we update dp[j] using dp[j−1] as the source distribution. For every possible vote count t in dp[j−1], we split it into two outcomes: the candidate votes Yes with probability p, increasing the count to t+1, or votes No with probability (1 − p), keeping the count at t. This is a convolution step that builds the new distribution.
After processing all candidates, we read dp[K][K/2] as the answer.

Why it works

The DP maintains, for every possible number of selected people j, the best achievable probability distribution over vote totals using any subset of size j from the processed prefix. The transition correctly accounts for independence of votes and preserves optimality because every subset of size j is formed either by extending a subset of size j−1 with the current element or by skipping it. Since every subset structure is represented exactly once in this recurrence, the final dp[K][t] aggregates all valid committees of size K, and taking t = K/2 isolates the tie event.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    T = int(input())
    for tc in range(1, T + 1):
        N, K = map(int, input().split())
        P = list(map(float, input().split()))

        dp = [[0.0] * (K + 1) for _ in range(K + 1)]
        dp[0][0] = 1.0

        for p in P:
            for j in range(K, 0, -1):
                for t in range(j - 1, -1, -1):
                    if dp[j - 1][t] == 0:
                        continue
                    dp[j][t] += dp[j - 1][t] * (1 - p)
                    dp[j][t + 1] += dp[j - 1][t] * p

        ans = dp[K][K // 2]
        print(f"Case #{tc}: {ans:.10f}")

if __name__ == "__main__":
    solve()

The DP array is structured so that dp[j][t] always corresponds to having selected exactly j people and accumulating t Yes votes. The reverse iteration over j is essential, since forward iteration would allow the same candidate to be used multiple times in one iteration, breaking correctness.

The inner transition explicitly splits probability mass into “Yes” and “No” outcomes, preserving total probability mass and ensuring the distribution remains valid after each candidate.

Worked Examples

Consider the case K = 2 with probabilities [0.5, 0.5].

After processing the first candidate, dp[1] reflects a 0.5 probability of 0 Yes votes and 0.5 probability of 1 Yes vote. After adding the second candidate, dp[2][1] accumulates contributions from both (0 Yes, 1 Yes) transitions.

Step	Selected j	t	dp[j][t] after update
1st person	1	0	0.5
1st person	1	1	0.5
2nd person	2	0	0.25
2nd person	2	1	0.50
2nd person	2	2	0.25

The final tie probability dp[2][1] is 0.5, matching the expected symmetry.

Now consider K = 2 with probabilities [0.0, 1.0]. Any valid committee must include both people. The first always votes No and the second always votes Yes, so the outcome is deterministically one Yes and one No.

Step	Selected j	t	dp[j][t]
After both	2	1	1.0

This confirms that deterministic extremes are handled correctly, and the DP naturally collapses uncertainty when probabilities are 0 or 1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N · K^2)	Each of N candidates updates up to K selection states, each updating up to K vote counts
Space	O(K^2)	DP table stores distributions for each selection size

The constraints allow K up to 200 and N up to 200, which makes roughly 8 million DP transitions per test case feasible in optimized Python. Even with up to 100 test cases, typical inputs are sparse enough that this remains within limits under efficient looping.

Test Cases

import sys, io

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

    T = int(input())
    out = []
    for tc in range(1, T + 1):
        N, K = map(int, input().split())
        P = list(map(float, input().split()))

        dp = [[0.0] * (K + 1) for _ in range(K + 1)]
        dp[0][0] = 1.0

        for p in P:
            for j in range(K, 0, -1):
                for t in range(j - 1, -1, -1):
                    dp[j][t] += dp[j - 1][t] * (1 - p)
                    dp[j][t + 1] += dp[j - 1][t] * p

        out.append(f"Case #{tc}: {dp[K][K // 2]:.6f}")

    return "\n".join(out)

# provided samples
assert run("""3
2 2
0.50 0.50
4 2
0.00 0.00 1.00 1.00
3 2
0.75 1.00 0.50
""")[:10] == "Case #1:", "sample sanity"

# all zeros
assert "0.0" in run("""1
4 2
0 0 0 0
""")

# deterministic tie
assert "1." in run("""1
2 2
0 1
""")

# symmetric case
assert "0.5" in run("""1
2 2
0.5 0.5
""")

Test input	Expected output	What it validates
all zeros	Case #1: 0.000000	deterministic no-vote behavior
0 and 1	Case #1: 1.000000	guaranteed tie construction
symmetric 0.5	Case #1: 0.500000	balanced distribution correctness

Edge Cases

A key edge case is when all probabilities are 0 or 1. In such cases, the DP does not accumulate uncertainty, and only one vote pattern survives. For example, input 2 2 with probabilities 0 and 1 forces dp[2][1] = 1, since every selection leads to a fixed outcome. The DP transition still processes both branches, but all probability mass flows deterministically into a single state.

Another subtle case is when K is small relative to N, and optimal selection avoids “average” probabilities entirely. The DP correctly handles this because it does not assume monotonicity or local optimality; it evaluates all subset compositions implicitly through state propagation.