Solve three algorithmic OA problems

You are given three independent coding problems.

Problem 1 – Knockout Tournament Match Counts

There are (n) players standing in a line, indexed from 1 to (n). Each player (i) has a distinct skill value (a[i]), and the values (a[i]) form a permutation of the integers from 1 to (n).

Constraints:

• (n) is a power of two (i.e., (n = 2^k) for some integer (k \ge 1)).
• (1 \le n \le 200{,}000).
• Skills are distinct and in the range ([1, n]).

A series of knockout rounds is played according to the following rules:

1. In each round, players are paired from left to right: player #1 vs #2, #3 vs #4, and so on.
2. In each pair, the player with the higher skill value wins the match and advances to the next round; the other player is eliminated and leaves the tournament.
3. After a round finishes, the winners keep their relative left‑to‑right order and form the new sequence of players for the next round.
4. Rounds continue until only one player remains (the overall winner).

Define an array (b[1..n]) where (b[i]) is the total number of matches player (i) participates in before being eliminated or winning the tournament.

Task: Given (n) and the skill array (a[1..n]), compute the array (b[1..n]).

You may assume the input ensures the process always ends with exactly one winner.

Problem 2 – Robot Path Planning with Movement Instructions

You are given a rectangular grid with (R) rows and (C) columns (3 (\le R, C \le 50)). Each cell of the grid is one of:

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

Additional guarantees:

• The outermost border of the grid (first and last row, first and last column) consists entirely of walls # .
• All floor cells (including the starting cell) form a single connected component (i.e., every floor cell is reachable from any other floor cell via moves on floor cells).
• The robot starts on a floor cell (marked * ).

You must control the robot with a sequence of characters drawn from:

• ^ – move up by one cell,
• v – move down by one cell,
• < – move left by one cell,
• > – move right by one cell.

At every step, the robot must remain within the grid and may only move onto floor cells (. or *). You do not need to return to the starting position at the end.

Your task is to construct an instruction string (a sequence of the above movement characters) that satisfies the constraints of each of the following five variants. For every variant, the final instruction sequence must have length at most 100,000. You may output any sequence that meets the stated requirements; optimality (shortest path, etc.) is not required. Assume that for each variant, the described shape guarantees such a sequence exists within the length bound.

Each variant describes the shape of the traversable floor region and specific visitation requirements:

1. Subtask 1 – Rectangular Border Walk
   • All floor cells form a perfect axis-aligned rectangle without holes.
   • The robot's starting position is guaranteed to be at the top-left corner of this rectangular floor region.
   • The robot must visit only the cells on the border (perimeter) of this rectangle, and must visit all border cells at least once. It must not step on interior floor cells.
2. Subtask 2 – Full Rectangular Coverage
   • All floor cells form a perfect axis-aligned rectangle without holes.
   • The robot's starting position can be any floor cell within the rectangle.
   • The robot must visit every floor cell in the rectangle at least once (full coverage).
3. Subtask 3 – Dumbbell Shape (Two Rectangles Connected by One Cell)
   • The floor region consists of two disjoint rectangles (left and right) connected by a single floor cell in the middle (like a dumbbell or two rooms connected by a 1-cell corridor).
   • The robot's starting position can be any floor cell in this shape.
   • The robot must visit every floor cell in the entire shape at least once.
4. Subtask 4 – Simple Path Shape
   • The floor region forms a single simple path: if you build a graph where each floor cell is a node and edges connect orthogonally adjacent floor cells, this graph is a simple path (no branches, no cycles).
   • The robot's starting position can be any floor cell on this path.
   • The robot must visit every floor cell at least once.
5. Subtask 5 – Arbitrary Connected Shape (Full Coverage)
   • The floor region is an arbitrary connected shape (satisfying the global constraints above: connected, surrounded by walls on the outer border, etc.).
   • The robot's starting position can be any floor cell.
   • The robot must visit every floor cell at least once.

Task (for all subtasks): Given the grid and the starting position, output one valid instruction sequence (a string of ^, v, <, >) that keeps the robot on floor cells and satisfies the subtask-specific visitation requirements, with total length at most 100,000. If you implement this in code, you may treat each subtask as a separate test case with its own grid.

Problem 3 – Maximum Sum of Two Numbers Without Shared Digits

You are given an array of (n) integers (a[1..n]).

Constraints:

• (1 \le n \le 200{,}000).
• Assume each (a[i]) is a non‑negative integer that fits in standard 32-bit signed integer range (you may state your own reasonable bound if needed, e.g., up to (10^9)).

We say two numbers have no common digit if, when written in base‑10 without leading zeros, they do not share any digit 0–9. For example:

• 12 and 340 (no common digits) – allowed pair.
• 15 and 51 (share digits 1 and 5) – not allowed.

Task: Select two distinct indices (i \neq j) such that:

• (a[i]) and (a[j]) have no common digit, and
• the sum (a[i] + a[j]) is maximized among all such valid pairs.

Output the maximum possible sum. If no such pair exists (i.e., every pair of numbers shares at least one digit), define and return an appropriate value (e.g., (-1)), and clearly document this behavior in your implementation.