Algorithmic Interview Problems: Travel Plan, Homework Scheduling, Flower Bed Beauty, and Simple Hash Table Restoration

Problem 1 – C's Travel Plan

Given N attractions each with a priority P_i (smaller value means higher priority), a first available day X_i, and a repeat interval D_i, C must visit attractions in increasing priority order, one per day, only on days X_i + k·D_i (k ≥ 0). The task is to compute the minimal total days needed to finish the plan.

Input : First line N. Next N lines each contain three integers P_i, X_i, D_i.

Output : A single integer – the earliest day on which the last attraction is visited.

Sample (N=2): 1 2 2 2 1 3 → Output: 4.

Analysis : Sort attractions by priority, then simulate the schedule. For each attraction, if the current day ≤ X_i, visit on X_i; otherwise compute the next feasible day using the formula next_visit = ((now - X_i + D_i - 1) // D_i) * D_i + X_i and update the current day.

Reference Code :

n = int(input())
ls = sorted([tuple(map(int, input().split())) for _ in range(n)])
now = 0
for _, x, d in ls:
    if now <= x:
        now = x
    else:
        now = (now - x + d - 1) // d * d + x
print(now)

Problem 2 – U's Homework Scheduling

U has M homework tasks, each released at time t_i and requiring w_i units of work. At any moment U may start or switch to any released but unfinished task. The completion cost of a task equals its finishing time minus its release time. Find the minimum possible total completion cost.

Input : First line M. Next M lines each contain t_i and w_i.

Output : One integer – the minimal sum of completion costs.

Sample : 3 tasks (1,5), (5,1), (7,3) → Output: 10.

Analysis : Sort tasks by release time, then use a min‑heap to always process the currently available task with the smallest remaining work (Shortest‑Job‑First). Simulate time advancement, pushing newly released tasks into the heap, and accumulate completion times.

Reference Code :

from heapq import heappush, heappop

def min_total_completion_time(n, tasks):
    tasks.sort()
    now = 0
    ans = [0] * n
    q = []
    pos = 0
    while pos < n or q:
        if not q:
            heappush(q, (tasks[pos][1], pos))
            now = tasks[pos][0]
            pos += 1
        w, idx = heappop(q)
        if pos == n or (pos < n and w <= tasks[pos][0] - now):
            now += w
            ans[idx] = now
        else:
            w -= tasks[pos][0] - now
            heappush(q, (w, idx))
            heappush(q, (tasks[pos][1], pos))
            now = tasks[pos][0]
            pos += 1
    return sum(ans[i] - tasks[i][0] for i in range(n))

n = int(input())
tasks = [tuple(map(int, input().split())) for _ in range(n)]
print(min_total_completion_time(n, tasks))

Problem 3 – A's Flower Bed Beauty

A flower bed contains N pots, each holding either a rose (0) or a peony (1). The beauty score is the absolute difference between the number of roses and peonies. A single operation may flip all flowers in a contiguous segment (0↔1). Determine how many distinct beauty scores can be obtained after performing at most one operation.

Input : First line N. Second line N integers (0 or 1).

Output : One integer – the count of different possible beauty scores.

Sample : N=2, [0,1] → Output: 2 (beauty scores 0 and 2).

Analysis : Compute the original beauty. For each possible segment, flipping changes the counts by Δ = (segment length) - 2·(number of roses in segment). Using prefix sums, the set of achievable beauty values can be derived as all |total‑2·k| where k ranges between the minimal and maximal achievable number of roses after a flip.

Reference Code :

def solve(a):
    s = [0]
    for x in a:
        s.append(s[-1] + x)
    val = 0
    n = len(a)
    ans = s[n]
    for r in range(1, n + 1):
        ans = max(ans, s[n] - s[r] - s[r] + r + val)
        val = max(val, -r + s[r] + s[r])
    return ans

n = int(input())
a = list(map(int, input().split()))
# b is the flipped version of a
b = [1 if x == 0 else 0 for x in a]
mx, mn = solve(a), n - solve(b)
st = {abs(n - i - i) for i in range(mn, mx + 1)}
print(len(st))

Problem 4 – Simple Hash Table Sequence Restoration

A linear‑probing hash table of size N stores distinct positive integers; empty slots are marked with -1. Given the final table state, reconstruct a possible insertion order that could have produced it, and output the lexicographically smallest such sequence.

Input : First line N. Second line N integers (‑1 for empty, otherwise a stored value).

Output : The insertion sequence (values separated by spaces) with minimal lexicographic order.

Sample : N=5, [-1,1,-1,3,4] → Output: 1 3 4.

Analysis : For each occupied slot i, the original hash index is value % N. If that index is already occupied, the element would have probed forward until reaching i. By building a dependency graph where each element points to the next occupied slot after its original index, we can repeatedly extract the smallest available value using a min‑heap, marking visited positions to avoid cycles.

Reference Code :

from heapq import heappush, heappop, heapify

def restore_sequence(n, a):
    q = [[x, i] for i, x in enumerate(a) if x != -1 and x % n == i]
    vis = [False] * n
    ans = []
    heapify(q)
    while q:
        val, idx = heappop(q)
        ans.append(val)
        nxt = (idx + 1) % n
        if a[nxt] != -1 and not vis[nxt]:
            heappush(q, [a[nxt], nxt])
            vis[nxt] = True
    return ans

n = int(input())
a = list(map(int, input().split()))
result = restore_sequence(n, a)
print(*result)