Beat the Feat

You can now download tests for this problem here.

IMPORTANT: Do not postpone reading this statement. Each output file can be submitted only during its own three-minute window, and some of these windows may already have closed.

A group of attackers has created malware that targets audio archives. Instead of deleting recordings or encrypting them, it quietly corrupts WAV files by cutting each recording into equal-sized pieces and shuffling those pieces in a random order. The original permutations are lost forever, and the only remaining hope is a miracle: reconstructing the recordings from the corrupted audio itself. Your task is to perform that miracle. This is a secret task and a matter of the highest national importance, so do not tell anyone!

All original audio files are WAV files in 16-bit, 44.1 kHz, mono LPCM format. Each file has a duration of exactly $d = 40960$ milliseconds. Since 44.1 kHz means 44.1 samples per millisecond, each file contains

$$\text{size} = 44.1d = 1806336$$

amplitude samples. We represent each audio file as the sequence of amplitude samples

$$a_0, a_1, \ldots, a_{\text{size}-1}.$$

To corrupt an audio file, the malware splits it into equal-sized chunks and concatenates those chunks in a random non-identity order.

Competition Format

You need to restore 48 original audio files. Restoring one original audio file is called a stage. In each stage, you work with 10 corrupted records generated from that original file.

Each record is a new corrupted version of the stage's original audio file, produced using the chunk size for that record. The permutation used in each record is generated independently and is guaranteed not to be the identity permutation.

The records within a stage go from hardest to easiest:

The number of chunks halves after each record, so later records contain longer chunks.

Contest Schedule

During the contest, stages are released sequentially. Stage 1 occupies the first 30 minutes, stage 2 occupies the next 30 minutes, and so on until stage 48. The full schedule lasts 24 hours, which is the whole contest duration.

The stage schedule is:

Within each stage, records are released sequentially. Record 1 becomes available when the stage starts, and then a new record becomes available every 3 minutes. For each record, the submission window lasts exactly 3 minutes, and you may submit at most one answer for that record.

For a stage with two-digit number SS, the schedule inside the stage is:

Equivalently, stage $s$ starts $30(s - 1)$ minutes after the contest starts. For record $r$ in that stage, the submission window is open from $30(s - 1) + 3(r - 1)$ to $30(s - 1) + 3r$ minutes after the contest starts.

Once the submission window for a record ends, you can no longer submit an answer for that record. Records are independent for submission purposes: even if you restore the original audio while solving an earlier record, you still need to submit a separate file for every record where you want to receive points.

Required Permutation

Consider one record. Let $n$ be the number of chunks in that record, and let $\text{chunk\_size}$ be the number of samples in one chunk. If the corrupted audio is

$$b_0, b_1, \ldots, b_{\text{size}-1},$$

then chunk $i$ of the corrupted audio is

$$\text{chunk}_i = [b_{\text{chunk\_size}\cdot i}, b_{\text{chunk\_size}\cdot i + 1}, \ldots, b_{\text{chunk\_size}\cdot (i + 1) - 1}].$$

Your answer must be a permutation

$$p_0, p_1, \ldots, p_{n-1}$$

of the integers from $0$ to $n - 1$. The meaning of this permutation is:

$$\text{chunk}_{p_0} \circ \text{chunk}_{p_1} \circ \ldots \circ \text{chunk}_{p_{n-1}}$$

should be the original audio file. Here $\circ$ denotes sequence concatenation. In other words, $p_j$ is the index of the corrupted chunk that you place at position $j$ in the restored audio.

Note: There may be equal chunks. You receive the maximum score for any permutation that reconstructs the original audio file exactly.

Record Data

At the start of the submission window for a record, the corrupted audio file for that record becomes available. The record number determines the number of chunks and the chunk size using the table above. You can download the corrupted audio from the contest system or obtain its download URL through the API.

You may also have downloaded the full test archive in advance from Discord. Use the password 41274070-9BF9-4780-989A-F5CA830E843B to open it. The test archive contains all corrupted audio files. Each file is stored in a separate inner archive, protected by its own password. The password for the currently active record is shown in the contest system and is also available through the API.

Submission Format

The output file for stage $s$ and record $r$ must be named SS-RR.txt, where SS is the two-digit stage number and RR is the two-digit record number. For example, the file for stage 1, record 1 is 01-01.txt, and the file for stage 48, record 10 is 48-10.txt.

Before the record's submission window ends, submit a text file containing exactly $n$ space-separated integers:

$$p_0, p_1, \ldots, p_{n-1}.$$

The submitted sequence must be a permutation of the integers from $0$ to $n - 1$.

The contest platform supports submitting answers through the API. Since this problem has many records and short submission windows, it may be useful to automate submissions through it.

Scoring

Record Scoring

For a permutation $p$, let $S(p)$ be the sequence of chunks obtained by applying this permutation:

$$S(p) = (\text{chunk}_{p_0}, \text{chunk}_{p_1}, \ldots, \text{chunk}_{p_{n-1}}).$$

Let $S^{(\text{original})}$ be the sequence of chunks in the original audio file, and let $S^{(\text{output})} = S(p^{(\text{output})})$ be the sequence of chunks produced by your submitted permutation. In this section, two chunks are equal if their sequences of amplitude samples are exactly equal. Therefore, exchanging two equal chunks does not change $S^{(\text{output})}$ or your score.

Two similarity measures are used:

• $\text{lccs}(S^{(1)}, S^{(2)})$ is the maximum length of a contiguous block of chunks that appears in both sequences in the same order.
• $\text{ncp}(S^{(1)}, S^{(2)})$ is the number of adjacent ordered chunk pairs shared by the two sequences, counted with multiplicity. Formally, it is the size of the intersection of the multiset of pairs $(S_i^{(1)}, S_{i+1}^{(1)})$ over all $0 \le i < n - 1$ and the multiset of pairs $(S_i^{(2)}, S_{i+1}^{(2)})$ over all $0 \le i < n - 1$.

If you do not submit an answer in time, or if your submitted sequence is not a permutation of the integers from $0$ to $n - 1$, you receive 0 points for the record.

Otherwise, your points per record are

$$0.5 \cdot \frac{\text{lccs}(S^{(\text{original})}, S^{(\text{output})}) - 1}{n - 1} + 0.5 \cdot \frac{\text{ncp}(S^{(\text{original})}, S^{(\text{output})})}{n - 1}.$$

A perfect answer receives 1 point for the record. In particular, any submitted permutation that reconstructs the original audio file exactly receives 1 point. Only the first submission for each record is scored.

Stage Scoring

Let $\text{points}_1, \text{points}_2, \ldots, \text{points}_{10}$ be the points obtained for records $1$ through $10$ of one stage. The stage points are

$$\sum_{i=1}^{10} 2^{10-i} \cdot \text{points}_i.$$

Thus, earlier records have larger weights. The maximum possible points per stage is $1023$.

For each stage, the stage points are transformed into stage scores. If your stage points are $\text{your\_stage}$ and the best points achieved by any team for this stage is $\text{best\_stage}$, then your stage score is

$$50 \cdot \frac{\text{your\_stage}}{\text{best\_stage}}.$$

Your total score for the problem is the sum of your normalized stage scores over all 48 stages.

Updated at Jul 4, 2026, 6:39 PM: In case you missed it, an endpoint to download past files in problem B has been added: https://finals.midnightcodecup.org/api-docs#tag/problems/GET/api/v1/problems/{slug}/scheduled-groups/past-tests