IOAI Training: Learn AI by solving problems

The problem in brief

Each example is a short piano excerpt of 100 consecutive notes, given as four lists: when each note starts (in seconds, the first note at 0), how long it lasts, its pitch (MIDI number, 60 = middle C) and its velocity (how hard the key was struck). For 23 929 training excerpts you also know the composer, one of 34 names from Bach to Rachmaninoff; you must name the composer of 10 254 test excerpts. The excerpts look like slices of recorded piano performances (the MAESTRO style of data: real pianists, real timing). This task is from the Swedish AI Olympiad final 2025 (problem by Arvid Kristoffersson); you print one name per test excerpt and Kattis scores the list.

The test labels are hidden, so every number below comes from a held-out part of the training set.

How you are scored

With $x$ the fraction of composers guessed correctly,

\text{Score} = \max\Big(0,\ \min\big(100,\ 165\,(e^{x} - e^{0.14})\big)\Big).

The score is 0 below 14 % accuracy and reaches 100 as soon as $e^x \ge e^{0.14} + 100/165$ , that is $x \ge 56.3\,\%$ . Final ranking uses 70 % of the test set, the other 30 % being shown during the contest.

What to aim for. 56.3 % accuracy gives full marks. The Kattis statistics page shows three full solves (100) and then 93.4 and 76.8.

First look at the data

The classes are very unbalanced: Schubert has 4125 excerpts, Chopin, Beethoven and Liszt about 3300 each, and the last ten composers fewer than 50 each (two of them have 2). Always answering "Franz Schubert" is right 17.5 % of the time, a score of about 7.
Excerpts last about 8 seconds (the median time of the 100th note).
The data reads like many performances cut into pieces. Famous competition pieces (a Chopin ballade, a Liszt étude, a Schubert sonata) are played by many pianists, and each performance yields dozens of excerpts.

That last remark is the important one. If training and test excerpts are drawn at random from the same pool of performances, then a test excerpt very often comes from a piece that is already in the training set, played by someone else or taken from another part of the same recording. Recognising a composer's style is hard; recognising a piece is much easier.

We checked that there is no trivial leak: no test excerpt shares even three consecutive notes with exactly the same durations and velocities as a training excerpt, so the windows do not overlap. Yet 75 % of test excerpts share at least one sequence of 8 consecutive pitches with some training excerpt, and that is far too often to be chance.

A first baseline

A sensible "style" model: summarise each excerpt with 50 global statistics (mean, spread and range of pitch, the 12 pitch-class frequencies, a histogram of melodic intervals, note durations, velocities, note density, the share of chords) and train a classifier.

model on global statistics	validation accuracy	score
always "Schubert"	17.5 %	6.8
gradient boosting, learning rate 0.08, 300 rounds	15.7 %	3.2
gradient boosting, learning rate 0.05, 15 leaves, L2 = 1	60.1 %	100
random forest, 500 trees	64.2 %	100

The first gradient-boosting run is worth a warning: with 34 classes, several of them with a handful of examples, an aggressive learning rate made the multiclass boosting diverge, to below the majority vote. Regularising fixed it.

Already the random forest clears the 56.3 % bar. That is suspiciously good for composer identification from 8 seconds of music, and it hints at the same thing: pitch range, dynamics and tempo are partly a fingerprint of the performance and the piece.

The key idea

Treat the problem as piece retrieval by melody. Index every run of $n$ consecutive pitches (an $n$ -gram) seen in the training excerpts, with the composers it occurred under. For a new excerpt, each of its $n$ -grams found in the index casts one vote, shared among the composers in proportion to how often that $n$ -gram appeared with each of them:

S_c(\text{excerpt}) = \sum_{g \in \text{grams(excerpt)}} \frac{\text{count}(g, c)}{\sum_{c'} \text{count}(g, c')}.

Predict $\arg\max_c S_c$ . The choice of $n$ is a trade-off you can see in the figure. Short $n$ -grams (2 or 3 notes) occur in every piece by every composer: they always match but say little. Long $n$ -grams (10 or more notes) are almost unique to one piece but rarely match, because performers differ by ornaments, chord order and wrong notes. Five notes is the sweet spot: 99.6 % of validation excerpts find a match and 81 % are attributed correctly.

Accuracy and match rate against n-gram length, and the scoring curve

A second index on intervals (differences between consecutive pitches) makes the melody transposition-invariant: the same theme in another key, or a sequence repeated a step higher, still matches. Adding interval 6-grams to pitch 5-grams lifts accuracy further.

The full solution

Parse the four JSON lists of every excerpt into an array of shape (excerpts, 100, 4).
Build one index from pitch 5-grams and interval 6-grams of all training excerpts (each excerpt counts each distinct $n$ -gram once).
Score each test excerpt with the vote $S_c$ above, normalised to sum to 1.
Add the random forest's class probabilities on the global statistics, $S_c + \alpha P_c$ with $\alpha = 1$ . The forest matters for the few excerpts with little or ambiguous melodic evidence.
Write the 10 254 names. Kattis only receives the program's output, so solution.py also generates a 7 KB submission.py with the predictions zlib-compressed and base85-encoded inside it.

The combination weight $\alpha$ (tried at 0.3, 1 and 3) and the $n$ -gram lengths were chosen on one random 5000-excerpt hold-out. The final numbers below come from a different random hold-out of 5000 excerpts, never used for any choice.

Results

Validation accuracy on held-out training excerpts (official test labels are private).

approach	accuracy	score
always "Schubert"	17.5 %	6.8
gradient boosting on statistics (diverged)	15.7 %	3.2
random forest on statistics	64.0 %	100
pitch 12-grams	51.2 %	85.5
pitch 8-grams	68.5 %	100
pitch 5-grams	80.9 %	100
interval 5-grams	79.2 %	100
pitch 5-grams + random forest	82.9 %	100
pitch 5-grams + interval 6-grams + random forest (final, fresh split)	84.3 %	100

The final model is 28 points of accuracy above the full-score threshold, so it should keep 100 on the hidden 70 % unless the test pieces were chosen to be absent from the training set, which the statement does not suggest (it says the test excerpts are a uniform random part of the same data).

What to remember

Before modelling "style", ask how the split was made. When train and test excerpts come from the same recordings or pieces, retrieval of near-duplicates beats any genuine generalisation; in real life you would split by piece to measure what you actually care about.
$n$ -gram length is a precision/recall trade-off: short grams always match but are ambiguous, long grams are precise but rare.
Representations with invariances (intervals instead of absolute pitches) make matching more robust.
Read the scoring curve: here everything above 56.3 % scores the same, so robustness matters more than the last point of accuracy.
Multiclass boosting with tiny classes can diverge: regularise, or check against the majority baseline.

"""SAIO Haydn Seek: guess the composer of a 100-note piano excerpt.

Idea: the test excerpts come from the same pool of pieces as the training excerpts (many
pieces are played several times, by several pianists), so the task is mostly *piece
recognition*. We index every pitch 5-gram and interval 6-gram of the training excerpts and let
each test excerpt vote for the composers whose excerpts share its n-grams, plus a small
random-forest vote on global statistics for excerpts with few or no matches.

  python3 solution.py --validate   # honest hold-out estimate (split never used for tuning)
  python3 solution.py              # fit on all training data, write predictions + Kattis program
Data: data/train.csv, data/test.csv from the problem's data.zip (run from the work folder).
"""
import sys, json, base64, zlib
import numpy as np, pandas as pd
from collections import defaultdict
from sklearn.ensemble import RandomForestClassifier

ALPHA = 1.0          # weight of the random-forest probabilities (chosen on a separate split)


def load(name):
    d = pd.read_csv(f'data/{name}.csv')
    X = np.stack([np.array([json.loads(s) for s in d[c]], dtype=float)
                  for c in ['start', 'duration', 'pitch', 'velocity']], -1)  # (n, 100, 4)
    return X, (d['composer'].values.astype(str) if 'composer' in d else None)


def grams(x):
    """Pitch 5-grams (exact melody) and interval 6-grams (melody up to transposition)."""
    p = x[:, 2].astype(int)
    iv = np.diff(p)
    out = {('p',) + tuple(p[j:j + 5]) for j in range(len(p) - 4)}
    out |= {('i',) + tuple(iv[j:j + 6]) for j in range(len(iv) - 5)}
    return out


def features(X):
    """Global, order-free statistics of an excerpt (for the random-forest fallback)."""
    s, d, p, v = X[..., 0], X[..., 1], X[..., 2], X[..., 3]
    pc = np.stack([(p % 12 == k).mean(1) for k in range(12)], 1)          # pitch classes
    iv = np.diff(p, axis=1)
    ivh = np.stack([(np.clip(iv, -12, 12) == k).mean(1) for k in range(-12, 13)], 1)
    ioi = np.diff(s, axis=1)
    F = [p.mean(1), p.std(1), p.min(1), p.max(1), d.mean(1), np.median(d, 1), d.std(1),
         v.mean(1), v.std(1), s[:, -1], ioi.mean(1), (ioi < 0.02).mean(1), np.abs(iv).mean(1)]
    return np.column_stack(F + [pc, ivh])


def fit_predict(Xa, ya, Xb):
    classes = np.unique(ya)
    ci = {c: k for k, c in enumerate(classes)}
    index = defaultdict(lambda: np.zeros(len(classes)))
    for x, lab in zip(Xa, ya):
        for g in grams(x):
            index[g][ci[lab]] += 1
    S = np.zeros((len(Xb), len(classes)))
    for r, x in enumerate(Xb):
        for g in grams(x):
            if g in index:
                v = index[g]
                S[r] += v / v.sum()           # each shared n-gram casts one (split) vote
    S /= np.maximum(S.sum(1, keepdims=True), 1e-9)
    rf = RandomForestClassifier(500, min_samples_leaf=2, n_jobs=2, random_state=0)
    rf.fit(features(Xa), ya)
    P = np.zeros_like(S)
    P[:, [ci[c] for c in rf.classes_]] = rf.predict_proba(features(Xb))
    return classes[(S + ALPHA * P).argmax(1)], classes[S.argmax(1)], classes[P.argmax(1)]


def score(acc):
    return max(0.0, min(100.0, (np.exp(acc) - np.exp(0.14)) * 165))


if __name__ == '__main__':
    X, y = load('train')
    if '--validate' in sys.argv:
        perm = np.random.default_rng(1).permutation(len(y))   # seed 1: not the tuning split
        va, tr = perm[:5000], perm[5000:]
        both, ng, rf = fit_predict(X[tr], y[tr], X[va])
        for name, p in [('n-grams only', ng), ('random forest only', rf), ('combined', both)]:
            acc = (p == y[va]).mean()
            print(f'{name:20s} accuracy {acc:.4f}  score {score(acc):.1f}')
    else:
        Xt, _ = load('test')
        pred, _, _ = fit_predict(X, y, Xt)
        open('predictions.txt', 'w').write('\n'.join(pred) + '\n')
        names = sorted(set(pred))
        code = base64.b85encode(zlib.compress(bytes(names.index(p) for p in pred), 9)).decode()
        open('submission.py', 'w').write(
            'import zlib,base64\nN=%r\nfor b in zlib.decompress(base64.b85decode(%r)):print(N[b])\n'
            % (names, code))
        print('wrote predictions.txt and submission.py for', len(pred), 'excerpts')