Solve three algorithmic OA problems

This is an online assessment (Codility-style, 150 minutes) consisting of three independent coding problems. Solve each one separately; they do not share input or state.

Part 1 — Knockout Tournament Match Counts

There are $n$ players standing in a line, indexed $1$ to $n$. Player $i$ has a distinct skill value $a[i]$, and the values $a[1..n]$ form a permutation of the integers $1$ to $n$ (so all skills are distinct).

A series of knockout rounds is played:

1. In each round, the surviving players are paired from left to right: positions $1$ vs $2$, $3$ vs $4$, and so on.
2. In each pair, the player with the higher skill value wins and advances; the other is eliminated and leaves the tournament.
3. After a round, the winners keep their relative left-to-right order and form the player sequence for the next round.
4. Rounds continue until exactly one player (the overall champion) remains.

Define $b[1..n]$ where $b[i]$ is the total number of matches the original player $i$ participates in (until they are eliminated, or until they win the tournament).

Task: Given $n$ and the skill array $a[1..n]$, return the array $b[1..n]$.

What This Part Should Cover

• Recognizing that match count equals the number of rounds the player remains alive (one match per round per alive player).
• A correct round-by-round simulation (or equivalent divide-and-conquer / segment recursion) that preserves left-to-right winner ordering.
• Complexity argument: total work across all rounds is $\sum_k n/2^k = O(n)$ comparisons plus $O(n \log n)$ for the increments — comfortably within $n \le 200{,}000$.
• Correct handling of the champion (they play $k = \log_2 n$ matches, the maximum).

Part 2 — Robot Path Planning with Movement Instructions

You are given an $R \times C$ grid ($3 \le R, C \le 50$). Each cell is one of:

• # — wall (cannot be entered),
• . — empty floor (can be entered),
• * — the robot's starting cell (also a traversable floor cell).

Guarantees: the outer border (first/last row, first/last column) is entirely walls; all floor cells form a single connected component; the robot starts on a floor cell.

You control the robot with characters ^ (up), v (down), < (left), > (right). Every move must keep the robot inside the grid and on a floor cell (. or *). You do not need to return to the start.

Construct an instruction string for each of the five variants below. For every variant the output length must be at most $100{,}000$. Any valid sequence is accepted — shortest-path optimality is not required. Assume each described shape admits such a sequence within the bound.

The variants:

1. Subtask 1 — Rectangular border walk. All floor cells form a solid axis-aligned rectangle. The start is at the rectangle's top-left corner. Visit exactly the border (perimeter) cells, all of them, and never step on an interior floor cell.

2. Subtask 2 — Full rectangular coverage. Floor cells form a solid rectangle; start anywhere inside; visit every floor cell at least once.

3. Subtask 3 — Dumbbell. Two disjoint rectangles connected by a single floor cell (a 1-cell corridor); start anywhere; visit every floor cell.

4. Subtask 4 — Simple path. The floor cells form a simple path in the orthogonal-adjacency graph (no branches, no cycles); start anywhere on it; visit every cell.

5. Subtask 5 — Arbitrary connected shape. Any connected floor region (per the global guarantees); start anywhere; visit every floor cell.

Task (all subtasks): Output one valid instruction string of ^v<> that keeps the robot on floor cells and meets the variant's visitation requirement, with length $\le 100{,}000$. You may treat each subtask as its own test case with its own grid.

What This Part Should Cover

• A single coverage routine (DFS Euler tour with inverse-move backtracking) handling subtasks 2–5 uniformly, plus the realization that subtask 1 needs its own perimeter walk because interior cells are forbidden.
• A correct, explicit length argument tying $2(V-1)$ to the $100{,}000$ bound.
• Move/inverse-move bookkeeping and a visited set so the robot never re-enters as a "new" cell and never steps onto a wall or out of bounds.
• Handling degenerate shapes (single floor cell ⇒ empty string; a 1-wide rectangle in subtask 1 where the "perimeter" is the whole region).

Part 3 — Maximum Sum of Two Numbers Without Shared Digits

You are given an array of $n$ integers $a[1..n]$ ($1 \le n \le 200{,}000$). Assume each $a[i]$ is a non-negative integer (state a reasonable upper bound, e.g. up to $10^9$, if your method needs one).

Two numbers have no common digit if, written in base-10 without leading zeros, their digit sets are disjoint. For example $12$ and $340$ are allowed; $15$ and $51$ are not (they share 1 and 5).

Task: Choose two distinct indices $i\ne j$ such that $a[i]$ and $a[j]$ share no digit and $a[i] + a[j]$ is maximized. Output that maximum sum. If no valid pair exists, return a sentinel value (e.g. $-1$) and document it.

What This Part Should Cover

• The 10-bit digit-mask reduction and keeping only the max value per mask ($\le 1024$ survivors) — turning a quadratic-in-$n$ search into one over a constant 1024-mask space.
• A correct disjointness test (mask1 & mask2 == 0) and a correct argument that the distinct-index constraint is satisfied automatically.
• Either the $O(1024^2)$ mask-pair scan or the $O(10 \cdot 2^{10})$ SOS/complement approach, with overall complexity $O(n \log(\max a) + 2^{10} \cdot 10)$.
• Defined, documented behavior when no compatible pair exists.