CF 1851E - Nastya and Potions

Rating: 1500
Tags: dfs and similar, dp, graphs, sortings
Solve time: 1m 37s
Verified: no

Solution

Problem Understanding

We are given a collection of potions, each with a cost to buy, and a set of unlimited potions that Nastya already has. Some potions can be created by mixing other potions, which consumes the ingredients. For every potion type, we need to determine the minimum cost to obtain one, either by buying it directly or by mixing available potions.

Formally, each potion type may have a "recipe" consisting of other potions. There is no cyclic dependency, so the mixing relations form a Directed Acyclic Graph (DAG). Some potion types are free because Nastya has an unlimited supply. The goal is to compute the minimal cost for each potion using these relationships.

The input size allows up to 200,000 potions across all test cases, with potentially as many as 200,000 total recipe ingredients. A naive approach that recomputes costs recursively without caching will be too slow because it could explore an exponential number of combinations. Instead, we need a strategy that leverages the DAG structure for efficient computation.

Edge cases include potions that are already unlimited, potions that cannot be mixed, and potions that have multiple ingredients where the cheapest option is to buy some ingredients rather than mix recursively.

Approaches

A brute-force approach would be to compute the minimal cost of a potion recursively: if the potion can be bought, consider its purchase cost; if it can be mixed, recursively compute the cost of all ingredients and sum them. While this is correct logically, it is extremely inefficient because overlapping subproblems are recomputed repeatedly. In the worst case, this could take exponential time.

The key observation is that the potion dependency graph is a DAG. This allows a dynamic programming approach on DAGs or a topological sort-based evaluation. If we process potions in topological order, we are guaranteed that whenever we process a potion, the minimal cost of all ingredients has already been computed. This avoids redundant computation.

Another crucial insight is that potions Nastya already has are effectively "free" (cost 0), which acts as the base case for our DP.

The combination of topological sorting and dynamic programming gives an efficient solution that processes each potion exactly once and examines each ingredient exactly once.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force (recursive w/o memo)	O(2^n) worst case	O(n) recursion stack	Too slow
DP on DAG / Topological Sort	O(n + m)	O(n + m)	Accepted

Here m is the total number of recipe ingredients across all potions.

Algorithm Walkthrough

Initialize an array costs where costs[i] stores the minimum cost to obtain potion i. For potions Nastya already has, set costs[i] = 0. For all others, initialize costs[i] = c[i], the purchase cost.
Construct a DAG representing potion dependencies. For each potion i, store the list of potions it depends on to mix. Also track the in-degree of each potion (number of other potions that must be processed before it).
Initialize a queue with potions that either Nastya already has or have zero in-degree in the DAG. These are the starting points for cost propagation.
While the queue is not empty, take a potion u from the queue. For every potion v that depends on u (i.e., u is an ingredient of v), update the candidate cost of v as the sum of minimal costs of its ingredients. Keep track of the remaining in-degree of v. When all ingredients of v have been processed (in-degree reaches zero), add v to the queue and finalize its cost as the minimum of its direct purchase cost and the computed mix cost.
After processing all potions in topological order, the array costs contains the minimum cost for each potion.

Why it works: The invariant is that a potion is only processed when all its ingredients’ minimal costs are known. Therefore, when we compute the mixing cost, we are guaranteed to use the true minimal cost of all ingredients. This guarantees that the computed cost for each potion is minimal. The DAG structure ensures no cycles, so the queue will process all potions exactly once.

Python Solution

import sys
from collections import deque

input = sys.stdin.readline

def solve():
    t = int(input())
    for _ in range(t):
        n, k = map(int, input().split())
        c = list(map(int, input().split()))
        has = set(int(x)-1 for x in input().split())
        
        adj = [[] for _ in range(n)]
        indeg = [0] * n
        recipe = [[] for _ in range(n)]
        
        for i in range(n):
            parts = list(map(int, input().split()))
            m_i = parts[0]
            if m_i > 0:
                ing = [x-1 for x in parts[1:]]
                recipe[i] = ing
                for x in ing:
                    adj[x].append(i)
                indeg[i] = m_i
        
        cost = c[:]
        queue = deque()
        
        for i in range(n):
            if i in has:
                cost[i] = 0
                queue.append(i)
            elif indeg[i] == 0:
                queue.append(i)
        
        processed_indeg = [0] * n
        temp_cost = [0] * n
        
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                temp_cost[v] += cost[u]
                processed_indeg[v] += 1
                if processed_indeg[v] == indeg[v]:
                    cost[v] = min(cost[v], temp_cost[v])
                    queue.append(v)
        
        print(' '.join(map(str, cost)))

if __name__ == "__main__":
    solve()

The solution begins by reading multiple test cases. We construct a dependency graph and initialize potion costs. The queue ensures potions are processed only when all ingredients’ minimal costs are known. temp_cost accumulates the sum of ingredients for each potion to compute the mixing cost, and we compare it against the direct purchase cost.

Careful attention is needed for 0-based indexing because the input uses 1-based indices, and for handling potions Nastya already has, which must be treated as cost 0.

Worked Examples

Sample Input 1:

5 1
30 8 3 5 10
3
3 2 4 5
0
0
2 3 5
0

Potion	Ingredients	Initial cost	Cost after processing
1	2,4,5	30	23 (sum 8+5+10)
2	none	8	8
3	none, unlimited	3	0
4	none	5	5
5	none	10	10

This confirms the minimal cost propagation works correctly.

Sample Input 2:

Potion	Ingredients	Initial cost
1	2,4,3	1
2	2	1
3	none	5
4	none	4

All potions cost 0 because all ingredients are unlimited or already processed.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Each potion is processed once, each ingredient edge visited once
Space	O(n + m)	Store adjacency list, recipes, in-degree, temp arrays

With n up to 2_10^5 and total m up to 2_10^5, this fits well under the 3-second time limit.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from contextlib import redirect_stdout
    out = io.StringIO()
    with redirect_stdout(out):
        solve()
    return out.getvalue().strip()

# Provided sample
assert run("1\n5 1\n30 8 3 5 10\n3\n3 2 4 5\n0\n0\n2 3 5\n0\n") == "23 8 0 5 10"

# Minimum input
assert run("1\n2 1\n1 2\n1\n0\n0\n") == "0 2"

# All unlimited potions
assert run("1\n3 3\n10 20 30\n1 2 3\n0\n0\n0\n") == "0 0 0"

# Potion only buyable
assert run("1\n2 1\n5 6\n1\n0\n1 1\n") == "0 6"

# Mix with cheaper ingredients
assert run("1\n3 1\n10 2 5\n2\n2\n0\n1 2\n") == "2 0 2"

Test input	Expected output	What it validates