Implement short algorithms on logs, grids, and strings

Problem Statement

You are tasked with building a diagnostic tool for a distributed system. You must implement three distinct sub-problems:

1. Log Throughput Optimization

You are given a list of logs where each log is a tuple (start_time, end_time, priority). Select the maximum number of logs you can process such that no two processed logs overlap in time. If there is a tie in the count, choose the subset that maximizes the sum of priority values.

2. Nested Metadata Parser

You are given a string representing metadata in the format count[string]. This signifies that the enclosed string should be repeated count times. The strings can be nested (e.g., 2[a3[b]] becomes abbbabbb). Implement a function decode_metadata(s: str) -> str to return the fully expanded string.

3. Grid Sensor Placement

Given an N x N grid, place K sensors such that no two sensors are placed in the same row or column. Additionally, you must avoid a set of forbidden cells provided as (r, c) pairs. Return the total number of ways to place these sensors.

Function Signatures

def max_log_utility(logs: List[Tuple[int, int, int]]) -> int:
    # Returns the maximum priority sum for the max number of non-overlapping logs

def decode_metadata(s: str) -> str:
    # Returns the fully expanded string

def count_sensor_placements(n: int, k: int, forbidden: List[Tuple[int, int]]) -> int:
    # Returns the number of valid ways to place K sensors

Constraints

• Logs: len(logs) "abbabb"`
• max_log_utility([(1, 3, 10), (2, 4, 5), (3, 5, 20)]) -> 30 (Logs 1 and 3 are compatible, sum 10+20=30).