CF 105928M - Bridge IV

Two players are dealt full information about a bridge-like game. For every suit, each player already knows exactly how many tricks they would win if they became the declarer and chose that suit.

codeforcescompetitive-programming

CF 105928M - Bridge IV

Rating: -
Tags: -
Solve time: 1m 9s
Verified: yes

Solution

Problem Understanding

Two players are dealt full information about a bridge-like game. For every suit, each player already knows exactly how many tricks they would win if they became the declarer and chose that suit. The only uncertainty is the bidding process, which determines who becomes declarer and which contract is played.

A contract is defined by a level from 1 to 7 and a suit ordered as clubs, diamonds, hearts, spades, and no trump. Higher level always beats lower level, and within the same level the suit order determines strength. Players alternate bids starting from Diluc. Each bid must strictly improve over the previous one, otherwise it is illegal. Either player can pass, and once both pass consecutively the auction ends, with the last bidder becoming declarer. If nobody ever bids, the result is zero.

Once a contract is chosen, the declarer must take at least level plus six tricks. The final score depends on whether they succeed or fail, their vulnerability, the contract, and the margin of success or failure. Success gives a combination of trick points, a contract bonus, possible overtrick rewards, and a slam bonus for high levels. Failure transfers a penalty to the defender based on undertricks, with different scaling depending on vulnerability.

The task is to compute the final score of Diluc after both players bid optimally, knowing that both players are perfectly rational and fully aware of all trick outcomes.

The key constraint is that there are at most 104 test cases, and each test only contains a constant amount of data: five integers per suit for each player. This immediately implies that any solution must be linear or near constant per test case, since anything worse than O(t · 70) is fine, but anything involving simulation of bidding sequences or state search over auctions would be unnecessary and risky.

A subtle edge case is when both players’ best possible outcomes are negative. In that situation, both prefer the auction to end with no contract, yielding zero. A naive approach that always forces a contract would incorrectly output a negative value instead of 0.

Another edge case is when Diluc’s best contract is positive but Kaeya’s best contract, when played as declarer, gives Diluc an even worse negative score. In that case, Kaeya will force the auction into his own contract even if Diluc also has a good option, because overbidding is always possible up to any contract.

Approaches

A brute-force interpretation of the rules would simulate the entire bidding process as a game tree. Each state would contain the current highest bid, whose turn it is, and whether the previous player passed. From each state, a player could either pass or make any valid higher bid. The tree depth can reach up to 35 meaningful levels per suit layer, and branching involves multiple suits and levels. Even though the state space is finite, exploring it directly leads to an exponential explosion because each player’s choice influences all later bidding sequences.

The key observation is that the bidding system does not introduce hidden interaction beyond selecting a final contract. Once a contract is fixed and a declarer is assigned, the score is completely determined. Since both players have full knowledge of all outcomes, bidding is equivalent to selecting which terminal contract becomes active under perfect competition.

This reduces the problem to evaluating every possible contract twice, once assuming Diluc is declarer and once assuming Kaeya is declarer. Each evaluation produces a deterministic score. After that, the auction is simply a contest over which terminal outcome is chosen, with the extra possibility that both players prefer passing if all outcomes are negative.

The bidding process therefore collapses into a max-selection over terminal utilities, with Diluc receiving either his best declarer score, or the negative of Kaeya’s best declarer score, or zero if neither side benefits from forcing a contract.

Approach Time Complexity Space Complexity Verdict
Full bidding state search Exponential Exponential Too slow
Evaluate all contracts directly O(70 · t) O(1) Accepted

Algorithm Walkthrough

## Algorithm Walkthrough

  1. For a fixed player acting as declarer, iterate over all 35 possible contracts defined by level from 1 to 7 and suit from clubs to no trump. This is sufficient because every possible auction ends in exactly one of these contracts.
  2. For each contract, compute the required number of tricks as level plus six, and compare it with the known trick count for that player in that suit. This determines success or failure.
  3. If the declarer succeeds, compute trick points using the suit-dependent formula, then add the contract bonus, overtrick bonus using the difference between actual and required tricks, and slam bonus if the level is 6 or 7. Each component is independent, so they can be accumulated directly.
  4. If the declarer fails, compute the number of undertricks and convert it into defender score according to vulnerability rules. This score is treated as negative for the declarer because the problem is zero-sum.
  5. Take the maximum score over all contracts for Diluc as declarer. This represents his best achievable outcome if he wins the auction.
  6. Repeat the same computation for Kaeya as declarer to obtain Kaeya’s best achievable score.
  7. The final answer for Diluc is the maximum among Diluc’s best score, the negation of Kaeya’s best score, and zero, since both players may rationally choose to pass and end the bidding with no contract.

The core invariant is that every legal bidding sequence must terminate in exactly one contract, and both players have full control over which terminal contract is reached by continuing to outbid until either they achieve their preferred outcome or choose to stop. Since utilities are fully determined at terminal states and independent of the path taken to reach them, intermediate bidding decisions do not create additional structure beyond selecting the final contract.

Python Solution

import sys
input = sys.stdin.readline

def score_declarer(tricks, need, level, suit, vuln):
    # suit index: 0 C, 1 D, 2 H, 3 S, 4 N
    if tricks >= need:
        y = tricks - need

        if suit in (0, 1):
            trick_points = 20 * level
            over = 20 * y
        elif suit in (2, 3):
            trick_points = 30 * level
            over = 30 * y
        else:
            trick_points = 30 * level + 10
            over = 30 * y

        if trick_points >= 100:
            contract_bonus = 500 if vuln else 300
        else:
            contract_bonus = 50

        slam = 0
        if level == 7:
            slam = 1500 if vuln else 1000
        elif level == 6:
            slam = 750 if vuln else 500

        return trick_points + contract_bonus + over + slam

    z = need - tricks
    if vuln:
        if z == 1:
            return -200
        if z == 2:
            return -500
        if z == 3:
            return -800
        return -(300 * z - 100)
    else:
        if z == 1:
            return -100
        if z == 2:
            return -300
        if z == 3:
            return -500
        return -(300 * z - 400)

def best(tricks, vuln):
    best_val = -10**18
    for level in range(1, 8):
        need = level + 6
        for suit in range(5):
            best_val = max(best_val, score_declarer(tricks[suit], need, level, suit, vuln))
    return best_val

def solve():
    t = int(input())
    out = []

    for _ in range(t):
        v1, v2 = map(int, input().split())
        diluc = list(map(int, input().split()))
        kaeya = list(map(int, input().split()))

        d_best = best(diluc, v1)
        k_best = best(kaeya, v2)

        ans = max(d_best, -k_best, 0)
        out.append(str(ans))

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

if __name__ == "__main__":
    solve()

The implementation separates declarer scoring into a single function so that success and failure cases remain symmetric and easy to verify. The best function enumerates all contracts without any pruning because the search space is constant and small. The final combination step directly encodes the zero-sum structure of the bidding: Diluc either plays his best contract, loses to Kaeya’s best contract, or both pass.

A common implementation pitfall is forgetting that overtrick scoring depends on the suit, not the contract level. Another is mishandling the contract bonus threshold at exactly 100 trick points, which is inclusive. The slam bonus is also independent and must be added after all other components.

Worked Examples

Consider a simplified trace where Diluc is not vulnerable and has a strong spade suit, while Kaeya is weaker overall. For a single contract evaluation, suppose we test 4S.

Step Level Suit Need Tricks Outcome
Evaluate 4 S 10 12 Success

Here Diluc succeeds by 2 tricks. Trick points are 30 × 4 = 120, which triggers the high contract bonus tier. Overtricks contribute 30 × 2, and no slam bonus applies. This confirms how overtricks and contract bonuses stack independently once success is determined.

Now consider a failure case for Kaeya as declarer in a high contract.

Step Level Suit Need Tricks Outcome
Evaluate 6 N 12 9 Failure

Kaeya is down by 3 tricks, so undertrick scoring applies. Because vulnerability changes the penalty curve, the same shortfall would produce different magnitudes depending on v2. This demonstrates why scoring must be computed separately for each player rather than inferred from symmetry.

Complexity Analysis

Measure Complexity Explanation
Time O(t) Each test evaluates 70 contracts with constant-time scoring
Space O(1) Only a fixed amount of storage per test case

The constant factor is small enough that even the maximum number of test cases runs comfortably within limits, since each test involves only a few hundred arithmetic operations.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from __main__ import solve
    return sys.stdout.getvalue().strip() if solve() else ""

# Sample-style checks (placeholders, since full samples were not fully structured)
# These would be replaced with exact I/O when available.

# Minimal edge: both pass optimal -> 0
assert run("""1
0 0
0 0 0 0 0
0 0 0 0 0
""") == "0"

# High asymmetry: one player dominates all suits
assert run("""1
0 0
13 13 13 13 13
0 0 0 0 0
""") != ""

# All equal weak hands
assert run("""1
0 0
0 0 0 0 0
0 0 0 0 0
""") == "0"
Test input Expected output What it validates
all zeros 0 both pass scenario
strong vs weak positive bidding selects best contract
symmetric weak 0 tie-breaking via pass

Edge Cases

A key edge case is when every contract yields negative score for both players. In that situation, both players rationally choose not to force a contract, and the correct output is zero. The algorithm handles this because the final answer explicitly includes zero in the maximum.

Another edge case is when Diluc’s best contract is positive but still worse than Kaeya’s best contract from Diluc’s perspective. The computation of max(d_best, -k_best, 0) correctly captures this competition between who gets declarer rights, ensuring Kaeya can override Diluc’s plan if his own optimal contract produces a stronger outcome.