Contest-Style Problems

This lesson presents five full contest problems exactly as they would appear in a HackerRank or Codeforces contest, but with AI/ML contexts. Each problem has a detailed problem statement, sample I/O, constraints, the optimal approach, and a complete solution. Try solving each problem yourself before reading the solution.

Problem A: Data Pipeline Optimization (Greedy + Sorting)

Approach: Earliest Deadline First (EDD)

This is a classic scheduling theory result. Sorting tasks by deadline and processing them in that order minimizes the maximum lateness. The proof uses an exchange argument: swapping any two adjacent tasks where the later-deadline task is scheduled first can only decrease or maintain the maximum lateness.

def min_max_lateness(tasks):
    """Minimize maximum lateness using Earliest Deadline First.
    Time: O(N log N), Space: O(N)
    """
    # Sort by deadline
    tasks.sort(key=lambda x: x[1])

    current_time = 0
    max_lateness = float('-inf')

    schedule = []
    for proc_time, deadline in tasks:
        current_time += proc_time
        lateness = current_time - deadline
        max_lateness = max(max_lateness, lateness)
        schedule.append((proc_time, deadline, current_time, lateness))

    return max_lateness, schedule

# Sample Input
tasks = [(2, 6), (3, 3), (1, 4)]
max_late, schedule = min_max_lateness(tasks)
print(f"Minimum maximum lateness: {max_late}")
for p, d, finish, late in schedule:
    print(f"  Task (p={p}, d={d}): finishes at {finish}, lateness={late}")

# Larger example: ML pipeline with tight deadlines
pipeline_tasks = [
    (10, 15),  # Data loading
    (5, 8),    # Preprocessing
    (3, 20),   # Feature extraction
    (8, 12),   # Model training
    (2, 25),   # Evaluation
]
max_late, schedule = min_max_lateness(pipeline_tasks)
print(f"\nPipeline max lateness: {max_late}")
for p, d, finish, late in schedule:
    print(f"  Task (p={p}, d={d}): finishes at {finish}, lateness={late}")

Complexity: O(N log N) for sorting, O(N) for computing lateness.

Problem B: Model Selection (Binary Search + DP)

Approach: Binary Search on Answer + Greedy Validation

Binary search on the minimum accuracy threshold. For a given threshold, only models with accuracy ≥ threshold are candidates. Among those candidates, greedily pick the K cheapest ones and check if total cost ≤ B.

def max_min_accuracy(models, K, B):
    """Binary search on answer: maximize minimum accuracy under budget.
    Time: O(N log N), Space: O(N)
    """
    # Sort by accuracy
    models.sort(key=lambda x: x[0])
    N = len(models)

    if K > N:
        return -1

    # Binary search on the index of minimum accuracy model
    # If we fix minimum accuracy = models[i][0], we need K models
    # from models[i..N-1] with minimum total cost <= B

    # Preprocess: for each possible starting index i,
    # find K cheapest costs among models[i..N-1]
    # We process from right to left, maintaining a max-heap of size K

    import heapq
    best_answer = -1

    # Try each possible minimum accuracy
    # Key insight: sort eligible models by cost and pick K cheapest
    for i in range(N - K + 1):
        # Models i through N-1 are eligible (accuracy >= models[i][0])
        eligible_costs = sorted([models[j][1] for j in range(i, N)])
        total_cost = sum(eligible_costs[:K])
        if total_cost <= B:
            best_answer = models[i][0]
            break  # Since models sorted by accuracy ascending,
                   # lower i = lower min accuracy, we want highest i that works

    # Optimized: iterate from highest accuracy downward
    # Use a sorted approach
    best_answer = -1
    # Sort eligible models from high accuracy down, accumulate cheapest K
    costs = []
    total = 0

    for i in range(N - 1, -1, -1):
        acc, cost = models[i]
        heapq.heappush(costs, -cost)  # max-heap
        total += cost

        if len(costs) > K:
            # Remove most expensive
            total += heapq.heappop(costs)  # removes -max, adding negative = subtracting

        if len(costs) == K and total <= B:
            best_answer = acc

    return best_answer

# Example
models = [
    (0.70, 100), (0.75, 150), (0.80, 200),
    (0.85, 300), (0.90, 500), (0.95, 800)
]
print(f"Max min accuracy (K=3, B=650): {max_min_accuracy(models[:], 3, 650)}")
# Pick models with acc >= 0.75: costs [150, 200, 300] = 650 <= 650 -> 0.75

print(f"Max min accuracy (K=2, B=500): {max_min_accuracy(models[:], 2, 500)}")
# Pick models with acc >= 0.85: costs [300, 500] = 800 > 500
# Pick models with acc >= 0.80: costs [200, 300] = 500 <= 500 -> 0.80

Complexity: O(N log N) time, O(N) space.

Problem C: Hyperparameter Grid Search (Bitmask Enumeration)

Approach: Enumerate All Combinations with Mixed-Radix Encoding

import heapq
from itertools import product

def grid_search_optimal(hyperparams, score_fn, top_m=5):
    """Exhaustive grid search with top-M tracking.
    Time: O(total_combos * log M), Space: O(M)
    Uses a min-heap of size M to track top results efficiently.
    """
    param_names = list(hyperparams.keys())
    param_values = [hyperparams[name] for name in param_names]

    # Min-heap of size M for top results
    top_heap = []  # (score, config_dict)
    total_evaluated = 0

    for combo in product(*param_values):
        config = dict(zip(param_names, combo))
        score = score_fn(config)
        total_evaluated += 1

        if len(top_heap) < top_m:
            heapq.heappush(top_heap, (score, total_evaluated, config))
        elif score > top_heap[0][0]:
            heapq.heapreplace(top_heap, (score, total_evaluated, config))

    # Sort results descending by score
    results = sorted(top_heap, key=lambda x: -x[0])
    return [(score, config) for score, _, config in results], total_evaluated

# Example: Hyperparameter optimization for a classifier
hyperparams = {
    'learning_rate': [0.001, 0.01, 0.1],
    'batch_size': [16, 32, 64, 128],
    'dropout': [0.1, 0.2, 0.3, 0.5],
    'hidden_dim': [64, 128, 256],
    'optimizer': ['adam', 'sgd'],
}

# Simulated score function (in reality, this would train and evaluate)
def mock_score(config):
    score = 0.85
    if config['learning_rate'] == 0.01:
        score += 0.05
    if config['batch_size'] == 64:
        score += 0.02
    if config['dropout'] == 0.2:
        score += 0.03
    if config['hidden_dim'] == 256:
        score += 0.04
    if config['optimizer'] == 'adam':
        score += 0.01
    # Add some interaction effects
    if config['learning_rate'] == 0.01 and config['optimizer'] == 'adam':
        score += 0.02
    return score

top_results, total = grid_search_optimal(hyperparams, mock_score, top_m=5)
print(f"Evaluated {total} combinations")
print(f"\nTop 5 configurations:")
for i, (score, config) in enumerate(top_results):
    print(f"  {i+1}. Score: {score:.4f}")
    for k, v in config.items():
        print(f"     {k}: {v}")

Complexity: O(total_combinations * log M) time, O(M) space for the top-M heap.

Problem D: Feature Selection (Bitmask DP)

Approach: Bitmask Enumeration over All Subsets

def optimal_feature_selection(n, costs, accuracy_fn, lam):
    """Find optimal feature subset maximizing accuracy - lambda * cost.
    Time: O(2^N * N), Space: O(2^N)
    Works for N <= 20 (up to ~10^6 subsets).
    """
    best_score = float('-inf')
    best_mask = 0

    for mask in range(1 << n):
        # Compute cost of this subset
        total_cost = 0
        features = []
        for i in range(n):
            if mask & (1 << i):
                total_cost += costs[i]
                features.append(i)

        # Compute accuracy for this subset
        acc = accuracy_fn(mask)

        # Objective: accuracy - lambda * cost
        objective = acc - lam * total_cost

        if objective > best_score:
            best_score = objective
            best_mask = mask

    # Extract selected features
    selected = [i for i in range(n) if best_mask & (1 << i)]
    return selected, best_score

# Example: 8 features for a sentiment classifier
feature_names = ["word_count", "avg_word_len", "sentiment_score",
                 "exclamation_count", "caps_ratio", "emoji_count",
                 "sentence_count", "punctuation_ratio"]
n = len(feature_names)
costs = [1, 1, 5, 2, 3, 4, 1, 2]  # Computation cost per feature

# Simulated accuracy function based on feature subset
def accuracy_fn(mask):
    """Simulate model accuracy for a feature subset"""
    base = 0.50
    # Core features contribute most
    if mask & (1 << 2):  # sentiment_score
        base += 0.20
    if mask & (1 << 0):  # word_count
        base += 0.08
    if mask & (1 << 4):  # caps_ratio
        base += 0.06
    if mask & (1 << 5):  # emoji_count
        base += 0.05
    if mask & (1 << 1):  # avg_word_len
        base += 0.03
    if mask & (1 << 3):  # exclamation_count
        base += 0.04
    if mask & (1 << 6):  # sentence_count
        base += 0.02
    if mask & (1 << 7):  # punctuation_ratio
        base += 0.01
    # Diminishing returns for too many features
    count = bin(mask).count('1')
    if count > 5:
        base -= 0.02 * (count - 5)
    return min(base, 0.99)

selected, score = optimal_feature_selection(n, costs, accuracy_fn, lam=0.005)
print(f"Optimal features (lambda=0.005):")
for i in selected:
    print(f"  {feature_names[i]} (cost: {costs[i]})")
print(f"Objective score: {score:.4f}")

# Try different lambda values
print("\nSensitivity analysis:")
for lam in [0.001, 0.005, 0.01, 0.02, 0.05]:
    sel, sc = optimal_feature_selection(n, costs, accuracy_fn, lam)
    names = [feature_names[i] for i in sel]
    print(f"  lambda={lam:.3f}: {len(sel)} features, score={sc:.4f}")

Complexity: O(2^N * N) time and O(2^N) space. Feasible for N ≤ 20.

Problem E: GPU Resource Scheduling (Interval Scheduling + DP)

Approach: Weighted Job Scheduling on M Machines

Sort jobs by end time. Use DP where dp[i][j] represents the maximum profit using jobs 1..i with j GPUs available. For each job, binary search for the latest non-conflicting job to decide include/exclude.

from bisect import bisect_right

def max_profit_scheduling(jobs, M):
    """Schedule N jobs on M GPUs to maximize profit.
    Time: O(N^2 * M) or O(N * M * log N) with binary search.
    """
    N = len(jobs)
    if N == 0:
        return 0

    # Sort by end time
    jobs.sort(key=lambda x: x[1])

    # For each job, find the latest non-conflicting job
    end_times = [job[1] for job in jobs]

    def latest_non_conflict(i):
        """Find latest job j < i such that job j ends <= job i starts"""
        target = jobs[i][0]
        # Binary search for rightmost end_time <= target
        lo, hi = 0, i - 1
        result = -1
        while lo <= hi:
            mid = (lo + hi) // 2
            if end_times[mid] <= target:
                result = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return result

    # For M=1: classic weighted job scheduling
    if M == 1:
        dp = [0] * (N + 1)
        for i in range(N):
            # Don't take job i
            dp[i + 1] = dp[i]
            # Take job i
            j = latest_non_conflict(i)
            dp[i + 1] = max(dp[i + 1], dp[j + 1] + jobs[i][2])
        return dp[N]

    # For M > 1: greedy assignment to M machines
    # Use M copies of the single-machine solution
    # More precisely: repeatedly find the best schedule, remove those jobs,
    # and repeat M times.

    # Alternative: extend DP to track M machines
    # dp[i] = max profit considering first i jobs with M machines
    # We use a priority queue of M machine end times

    import heapq

    # Greedy: sort by end time, assign each job to earliest available GPU
    # that finished before job starts, prioritizing high-profit jobs

    # Better approach for small M: solve weighted interval scheduling
    # for each machine greedily

    remaining = list(range(N))
    total_profit = 0

    for gpu in range(M):
        if not remaining:
            break

        # Weighted interval scheduling on remaining jobs
        current_jobs = [(jobs[i][0], jobs[i][1], jobs[i][2], i) for i in remaining]
        current_jobs.sort(key=lambda x: x[1])

        k = len(current_jobs)
        dp = [0] * (k + 1)
        choice = [False] * k

        cur_ends = [cj[1] for cj in current_jobs]

        for i in range(k):
            dp[i + 1] = dp[i]
            # Find latest non-conflicting
            target = current_jobs[i][0]
            lo, hi, res = 0, i - 1, -1
            while lo <= hi:
                mid = (lo + hi) // 2
                if cur_ends[mid] <= target:
                    res = mid
                    lo = mid + 1
                else:
                    hi = mid - 1

            val = dp[res + 1] + current_jobs[i][2]
            if val > dp[i]:
                dp[i + 1] = val

        # Backtrack to find selected jobs
        total_profit += dp[k]
        selected_indices = set()
        i = k - 1
        while i >= 0:
            target = current_jobs[i][0]
            lo, hi, res = 0, i - 1, -1
            while lo <= hi:
                mid = (lo + hi) // 2
                if cur_ends[mid] <= target:
                    res = mid
                    lo = mid + 1
                else:
                    hi = mid - 1

            if dp[res + 1] + current_jobs[i][2] > dp[i]:
                selected_indices.add(current_jobs[i][3])
                i = res
            else:
                i -= 1

        remaining = [i for i in remaining if i not in selected_indices]

    return total_profit

# Example: Schedule training jobs on 2 GPUs
jobs = [
    (0, 3, 50),    # Job A: time 0-3, profit 50
    (1, 4, 40),    # Job B: time 1-4, profit 40
    (3, 6, 70),    # Job C: time 3-6, profit 70
    (4, 7, 60),    # Job D: time 4-7, profit 60
    (5, 9, 80),    # Job E: time 5-9, profit 80
    (7, 10, 30),   # Job F: time 7-10, profit 30
]

for m in range(1, 4):
    profit = max_profit_scheduling(jobs[:], m)
    print(f"Max profit with {m} GPU(s): {profit}")

# 1 GPU: best non-overlapping subset
# 2 GPUs: can run two jobs in parallel
# 3 GPUs: even more parallelism

Complexity: O(M * N^2) time in the worst case, O(N) space per machine.

Key Takeaways

• Data pipeline scheduling uses the Earliest Deadline First rule, provably optimal for minimizing max lateness.
• Model selection problems often reduce to binary search on the answer with greedy validation.
• Grid search can be optimized with a top-M heap to track the best results in O(log M) per evaluation.
• Feature selection with N ≤ 20 features is tractable via bitmask enumeration over all 2^N subsets.
• Multi-GPU scheduling extends weighted interval scheduling to multiple machines using iterative DP.