This article examines several algorithmic problems featuring dynamic programming, state management, and graph traversal techniques.

Problem 1: Frozen Dumplings

Consider a scenario where daily dumpling prices vary, and storage costs accrue for each day a dumpling is kept. Given prices for n days and a daily storage cost c, the goal is to minimize total expenditure.

Approach

This problem can be solved using a greedy strategy with a runing minimum. For each day, we decide whether to buy on that day or use previously purchased dumplings.

def min_cost(prices, storage_cost):
    n = len(prices)
    total = 0
    min_price = prices[0]
    
    for i in range(n):
        min_price = min(min_price + storage_cost, prices[i])
        total += min_price
    
    return total

The algorithm maintains the minimum effective price (including storage costs) and accumulates the cost for each day.

Problem 2: Pizza Cutting

A circular pizza undergoes n rotations by angles a₁, a₂, ..., aₙ. After each rotation, a cut is made from the center in the 12 o'clock direction. The task is to find the maximum central angle between any two consecutive cuts.

Approach

This problem reduces to finding the maximum gap in a circular sequence of angles.

def max_angle(rotations):
    cuts = [0]
    for angle in rotations:
        cuts.append((cuts[-1] + angle) % 360)
    
    cuts.sort()
    max_gap = 0
    for i in range(len(cuts) - 1):
        max_gap = max(max_gap, cuts[i + 1] - cuts[i])
    
    # Handle wrap-around
    max_gap = max(max_gap, 360 - cuts[-1] + cuts[0])
    return max_gap

Problem 3: Maximum Color Blocks

Given an array of length n with initial colors, we can modify up to m positions to any color in [1, k]. Find the maximum number of contiguous color blocks achievable.

Approach

This is a DP problem where we consider the state of each position and count transitions.

def max_blocks(n, m, k, colors):
    dp = [[[-1] * (m + 1) for _ in range(k + 1)] for _ in range(n)]
    
    def solve(pos, prev_color, remaining):
        if pos == n:
            return 1
        if dp[pos][prev_color][remaining] != -1:
            return dp[pos][prev_color][remaining]
        
        # Keep current color
        result = solve(pos + 1, prev_color, remaining)
        
        # Change to different colors
        for new_color in range(1, k + 1):
            if new_color != colors[pos] and remaining > 0:
                if new_color != prev_color:
                    result += solve(pos + 1, new_color, remaining - 1)
        
        dp[pos][prev_color][remaining] = result
        return result
    
    return solve(0, colors[0], m)

Problem 4: Restaurant Exploration with Health States

A sequence of n dishes is served. Each dish has type X (0 = antidote, 1 = poisonous) and tastiness Y. The eater starts with a healthy stomach. Antidote dishes maintain health, while poisonous dishes cause discomfort. When uncomfortable, antidote restores health but poisonous causes death.

The goal is to maximize total tastiness while surviving.

Approach

This is a DP problem with two states: healthy and uncomfortable.

def max_tastiness(n, dishes):
    healthy = 0
    uncomfortable = float('-inf')
    
    for x, y in dishes:
        new_healthy = max(healthy + (y if x == 0 else 0), 
                         uncomfortable + (y if x == 0 else float('-inf')))
        new_uncomfortable = max(healthy + (y if x == 1 else float('-inf')),
                               uncomfortable + (y if x == 1 else float('-inf')))
        healthy = new_healthy
        uncomfortable = new_uncomfortable
    
    return max(0, healthy, uncomfortable)

Problem 5: Ingredient Transformation

Given n ingredients and m transformation operations (each can convert between two ingredients in 1 hour), find the number of fastest transformation paths from ingredient 1 to ingredient n.

Approach

This requires BFS to find the minimum distance, then counting paths of that length.

from collections import defaultdict, deque

def count_shortest_paths(n, operations):
    graph = defaultdict(list)
    for a, b in operations:
        graph[a].append(b)
        graph[b].append(a)
    
    # BFS to find distance
    dist = [-1] * (n + 1)
    dist[1] = 0
    queue = deque([1])
    
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if dist[neighbor] == -1:
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)
    
    if dist[n] == -1:
        return 0
    
    # Count paths of minimum length
    MOD = 10**9 + 7
    count = [0] * (n + 1)
    count[1] = 1
    
    for d in range(dist[n]):
        for node in range(1, n + 1):
            if dist[node] == d:
                for neighbor in graph[node]:
                    if dist[neighbor] == d + 1:
                        count[neighbor] = (count[neighbor] + count[node]) % MOD
    
    return count[n]

Conclusion

These problems demonstrate various algorithmic techniques including greedy optimization, dynamic programming with state management, and graph traversal with path counting. Each problem requires careful analysis of constraints and appropriate algorithm selection.