Overview

This is a problem where you select exactly \(K\) cards out of \(N\) cards to flip over, maximizing the sum of the numbers on the visible faces.

Analysis

For each card, there are two choices: “face up” or “face down,” but there is a constraint that exactly \(K\) cards must be flipped. Since \(N\) is at most 20, which is small, we can exhaustively search all possible ways to flip the cards. Using bitmask enumeration, each bit represents the state of a card (0: front, 1: back), allowing us to efficiently examine all combinations.

Algorithm

1. Generate all bitmasks from \(0\) to \(2^N - 1\)
2. For each bitmask, count the number of set bits (number of cards to flip)
3. Only when the number of flipped cards equals \(K\), compute the total sum:
   • Cards with the bit set: add the back value \(B_i\)
   • Cards with the bit not set: add the front value \(F_i\)
4. Output the maximum total sum among all valid combinations

Complexity

• Time complexity: \(O(2^N \cdot N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Use bit operations to efficiently check the state of each card

• Count the number of set bits using bin(bit).count('1')

• By initializing ans to a sufficiently small value at the beginning, the maximum value can be safely updated

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    k = int(data[1])
    cards = []
    index = 2
    for i in range(n):
        f = int(data[index])
        b = int(data[index+1])
        index += 2
        cards.append((f, b))
    
    ans = -10**9
    for bit in range(1 << n):
        cnt = bin(bit).count('1')
        if cnt != k:
            continue
        total = 0
        for i in range(n):
            if bit & (1 << i):
                total += cards[i][1]
            else:
                total += cards[i][0]
        ans = max(ans, total)
    
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.