Girls In Code SOUTHEAST ASIA
← November 2025 questions

NOVEMBER 2025 / ADVANCED / QUESTION 4

Question 4

Archived question

Try the question in your own editor, then check your output below.

View original booklet · page 33 ↗
THE QUESTION

Text from the official booklet. Refer to the PDF for original mathematical notation, formatting, and linked input files. Printed samples and inputs are reproduced as published.

The city is under threat from an invasion of rogue robots. A defender robot is tasked
with collecting energy cores scattered along a straight corridor to power up and stop the
invasion.
The corridor contains n energy cores, represented as an integer sequence e1, e2, . . . , en,
where ei is the energy level of the i-th core from the entrance.
The robot needs to collect exactly m cores to fully charge. The i-th core it collects must
have an energy level of at least r[i] to meet its charging requirements.
However, the robot is too big and can only move forward from the entrance to the end
of the corridor, and it must decide in real-time whether to pick up the core at its current
position.
The robot’s engineers have a special device: it can generate one artificial energy core
with any energy level k and place it anywhere in the corridor (before, after, or between
existing cores) at most once before the collection begins.
Your task is to determine the minimum energy level k the robot must generate to ensure
it can collect exactly m cores satisfying the energy requirements.
If the robot can collect all required cores without generating a new one, output 0.
If it’s impossible to meet the requirements even with one artificial core, output −1.
Input format:
• First line: t (1 ≤ t ≤ 104) — the number of test cases
• For each test case:
– First line: n m(1 ≤ m ≤ n ≤ 2 × 105)
– Second line: e1, e2, . . . , en (1 ≤ ei ≤ 109)
– Third line: r1, r2, . . . , rm (1 ≤ ri ≤ 109)
Output format: For each test case, output a single integer — the minimum energy
level k the robot must generate, 0 if no generation is needed, or −1 if it’s impossible.
Constraints:
• The sum of n across all test cases does not exceed 2 × 105
Sample Input:
7
9 5
3 5 2 3 3 5 8 1 2
4 6 2 4 6
6 3
1 2 6 8 2 1
5 4 3
5 3
4 3 5 4 3
7 4 5
6 3
8 4 2 1 2 5
6 1 4
5 5
1 2 3 4 5
5 4 3 2 1
6 3
1 2 3 4 5 6
9 8 7
5 5
7 7 6 7 7
7 7 7 7 7
Sample Output:
6
3
7
0
-1
-1
7
Question Input File:
• Input: https://shorturl.at/HS7mo

PRACTICE CHECK

Try your answer.

The linked final-input download could not be retrieved (checked 28 October 2026). This checks the complete published sample, not the unavailable final input.

Run your program in your own editor, then paste its output below. This checks the stated output or checkpoint; it does not assess your full program. Practice attempts do not affect competition scores.

Use all seven published sample cases. Enter one minimum energy per line.

Reveal worked answer

Your output

6
3
7
0
-1
-1
7

First greedily match requirements without insertion. Otherwise try supplying each requirement with the new core; match the remaining ordered requirements against existing cores and minimise the supplied requirement value.

Source: Girls in Code SEA 2025 Fall Competition, 29 November 2025. Booklet created by Emily Xu and the GIC question authors. Shared for non-commercial educational use with attribution, as permitted in the booklet.