CF 1854B - Earn or Unlock

Rating: 2200
Tags: bitmasks, brute force, dp
Solve time: 52s
Verified: yes

Solution

Problem Understanding

We are given a scenario where a player wants to maximize their earnings while unlocking skills in a game. There are n skills, each requiring certain previously unlocked skills and providing a coin reward if unlocked. Some skills can be unlocked immediately without prerequisites, while others require a combination of prior skills. The goal is to compute the maximum total coins the player can earn by choosing an order of unlocking skills that respects these prerequisites.

The input describes each skill's reward and its prerequisites. The output is the maximum coins achievable under the constraints.

The constraints are small enough that n is up to 20. This immediately suggests that any solution iterating over all subsets of skills is feasible since 2^20 is about one million, which fits comfortably within typical computational limits. However, naive approaches that try all permutations of unlock orders would require n! operations, which is far too large for n=20. Thus, we need to consider techniques like dynamic programming over subsets or bitmasking.

Edge cases are subtle. One is a skill that is initially unlockable but has zero reward; another is a skill that requires all other skills to unlock. For instance, with three skills where skill 3 requires skills 1 and 2, the optimal order must consider unlocking 1 and 2 before 3. A careless greedy approach that only picks the highest reward first could fail.

Approaches

The brute-force approach is to consider every order of unlocking the skills. For each permutation of n skills, we check whether prerequisites are satisfied at each step, summing the rewards of unlocked skills. While this guarantees correctness, it requires n! operations in the worst case, which is infeasible for n=20.

The optimal approach leverages bitmask dynamic programming. Each subset of skills can be represented as a bitmask of length n, where a bit is set if the corresponding skill is unlocked. The DP state dp[mask] represents the maximum coins obtainable after unlocking the subset mask. The key observation is that we can iterate over all subsets and, for each, consider adding one new skill if its prerequisites are satisfied in the current mask. This reduces the solution space from n! permutations to n * 2^n transitions, which is acceptable for n ≤ 20.

The brute-force works because it considers all possibilities, but fails when n is large. The observation that the problem can be expressed as transitions between subsets allows us to reduce it to a DP on bitmasks, which is efficient and avoids unnecessary checks.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n!)	O(n)	Too slow
Bitmask DP	O(n * 2^n)	O(2^n)	Accepted

Algorithm Walkthrough

Read the number of test cases, then iterate over each test case.
For each skill, store its coin reward and a bitmask of prerequisites.
Initialize a DP array of size 2^n with negative infinity, except dp[0] = 0 since no skills unlocked yields zero coins.
Iterate over all masks from 0 to 2^n - 1. For each mask, consider unlocking a new skill i not yet in the mask.
If the current mask contains all prerequisites for skill i, compute the new mask by setting bit i. Update dp[new_mask] as the maximum of its current value and dp[mask] + coins[i].
After processing all masks, the answer is the maximum value in the DP array, corresponding to any subset of unlocked skills.

The invariant is that dp[mask] always holds the maximum coins obtainable for that exact set of unlocked skills. We never skip any valid transition because we systematically explore every subset and every skill addition. No valid sequence is missed, so the maximum computed at the end is guaranteed to be correct.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    t = int(input())
    for _ in range(t):
        n = int(input())
        coins = []
        prereq_masks = []
        for _ in range(n):
            parts = list(map(int, input().split()))
            c = parts[0]
            k = parts[1]
            prereqs = parts[2:] if k > 0 else []
            mask = 0
            for p in prereqs:
                mask |= 1 << (p - 1)
            coins.append(c)
            prereq_masks.append(mask)
        
        dp = [-1] * (1 << n)
        dp[0] = 0
        for mask in range(1 << n):
            if dp[mask] == -1:
                continue
            for i in range(n):
                if not (mask & (1 << i)) and (mask & prereq_masks[i]) == prereq_masks[i]:
                    new_mask = mask | (1 << i)
                    dp[new_mask] = max(dp[new_mask], dp[mask] + coins[i])
        
        print(max(dp))

if __name__ == "__main__":
    solve()

The solution reads input efficiently and constructs masks for prerequisites. The DP array tracks maximum coins for each subset, and transitions only occur when prerequisites are satisfied. Careful bitwise operations ensure we never unlock a skill prematurely. Using -1 for uninitialized states avoids accidentally summing with invalid subsets.

Worked Examples

Example 1

Input:

mask	dp[mask]	Notes
000	0	base case
001	10	unlock skill 1
011	30	unlock skill 2 after 1
111	60	unlock skill 3 after 1 and 2

This trace confirms prerequisites are enforced, and dp updates accumulate coins correctly.

Example 2

Input:

mask	dp[mask]	Notes
00	0	base case
01	5	unlock skill 1
11	15	unlock skill 2 after 1

The table shows the DP captures the maximum coins for each subset and handles small n properly.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * 2^n)	For each of 2^n subsets, we consider n skills for transitions.
Space	O(2^n)	We store a DP value for every subset of skills.

For n ≤ 20, 2^20 ≈ 1 million and n * 2^n ≈ 20 million operations, fitting comfortably under typical 2-second limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    output = io.StringIO()
    sys.stdout = output
    solve()
    sys.stdout = sys.__stdout__
    return output.getvalue().strip()

# Provided sample
assert run("1\n3\n10 0\n20 1 1\n30 2 1 2\n") == "60", "sample 1"

# Custom cases
assert run("1\n2\n5 0\n10 1 1\n") == "15", "simple two skills"
assert run("1\n1\n100 0\n") == "100", "single skill"
assert run("1\n3\n1 0\n1 1 1\n1 2 1 2\n") == "3", "chain unlocks"
assert run("1\n3\n5 0\n0 1 1\n10 1 1\n") == "15", "skill with zero reward"
assert run("1\n4\n1 0\n2 1 1\n3 2 1 2\n4 3 1 2 3\n") == "10", "all skills unlockable in sequence"

Test input	Expected output	What it validates
2 skills, sequential	15	basic prerequisites
1 skill only	100	minimum input size
3 skills chained	3	sequential unlocks with minimal coins
zero-reward skill	15	algorithm handles zero rewards correctly
4 skills full chain	10	full chain sequence accumulation

Edge Cases

When a skill has no reward but is required for others, the DP correctly includes it only if necessary. For example:

Input:

DP trace:

mask	dp[mask]
000	0
001	0
011	5
111	15

The algorithm chooses skill 1 despite zero reward because it enables skill 2. This confirms the DP correctly enforces prerequisites even when some rewards are zero.