Solve three algorithmic optimization and search problems

You are given three independent coding problems.

Problem 1: Allocate tasks between two workers to maximize reward

You have n independent tasks that must be split between two workers (worker 1 and worker 2). Every task must be done by exactly one of the two workers.

For each task $i$ (0-indexed or 1-indexed, as you prefer), you are given:

• reward1[i] : the reward if worker 1 does task $i$
• reward2[i] : the reward if worker 2 does task $i$

Additionally, worker 1 must do exactly k tasks in total (where $0 \le k \le n$). The remaining $n - k$ tasks must be done by worker 2.

Task:

• Assign each of the $n$ tasks to one of the two workers such that:
  • Worker 1 is assigned exactly $k$ tasks.
  • Worker 2 is assigned the remaining tasks.
• Maximize the total reward, defined as the sum over all tasks of the reward from the worker to whom the task is assigned.

Input format (conceptual):

• Integer n — number of tasks.
• Integer k — number of tasks that must be assigned to worker 1.
• Array reward1 of length n .
• Array reward2 of length n .

Output:

• A single number: the maximum possible total reward .
• (Optionally, you may also be asked to output which task indices are assigned to worker 1, but the core problem is computing the maximum total reward.)

You should design an algorithm that works efficiently for large $n$ (e.g., up to $10^5$ or $10^6$).

Problem 2: Reorient edges in a directed tree toward a root

You are given a directed graph with n nodes labeled from 1 to n and n - 1 directed edges. It is guaranteed that if you ignore edge directions, the underlying undirected graph is a tree (i.e., it is connected and acyclic). However, the current directions of the edges may be arbitrary, so the graph may not currently have a single node reachable from all others.

You are allowed to reverse the direction of any subset of edges. Reversing an edge counts as one operation.

You want to make the graph such that there exists some node r (1 ≤ r ≤ n) with the following property:

• For every node x (including r ), there is a directed path from x to r following the directions of the (possibly reversed) edges.

In other words, after reorienting some edges, all nodes should be able to "flow" to a single root node r along directed paths.

Task:

• Over all possible choices of root node r , determine the minimum number of edge reversals needed to achieve the property that every node has a directed path to r .

Input format (conceptual):

• Integer n — number of nodes.
• n - 1 directed edges, each given as an ordered pair (u, v) meaning there is an edge from u to v .

Output:

• A single integer: the minimum number of edges that must be reversed so that for some node r , every node has a directed path to r .
• (Optionally, you may also be asked to output at least one node r that achieves this minimum.)

Your algorithm should run in time close to linear in n (e.g., $O(n)$ or $O(n \log n)$).

Problem 3: Find the leftmost column with a 1 in a sorted binary matrix

You are given a binary matrix A of size m × n ($m$ rows, $n$ columns). Each cell is either 0 or 1. Each row is sorted in non-decreasing order, meaning:

• All the 0s in a row come before any 1s in that row.
• A typical row therefore looks like: 0 0 0 1 1 1 (possibly all 0s or all 1s).

Task:

• Find the index of the leftmost column (smallest column index) that contains at least one 1 in any row .
• If the matrix contains no 1s at all , return -1 .

You may assume 0-based column indexing (return an integer in [0, n-1]) or 1-based indexing (return in [1, n]); just be clear and consistent in your implementation.

Input format (conceptual):

• Integers m , n — number of rows and columns.
• An m × n matrix A of 0s and 1s, where each row is sorted: all 0s, then all 1s.

Output:

• A single integer: the index of the leftmost column that contains at least one 1 , or -1 if no such column exists.

Complexity requirement:

• Design an algorithm that is asymptotically faster than the naive $O(m \times n)$ scan of the entire matrix in the worst case (for example, $O(m \log n)$ or $O(m + n)$ ).
• Be prepared to explain your algorithm and analyze its time complexity.