# Humanity's Heritage: Official Solution

*English translation by SOTA – AI Community of the Russian original. Organisers who would like this translation removed can email sota.ai.community@gmail.com.*

All-Russian School Olympiad in Informatics 2025–2026, Final Stage<br>
“Artificial Intelligence” profile, Tour 2, Moscow, 25 March 2026<br>
Task D

*Translator's note: the official solution is the authors' Jupyter notebook exported to PDF. Code cells are marked “In [n]”, their results “Out [n]”, and printed output follows the cell. Lines that the PDF wrapped are joined again. Comments, docstrings and messages are translated; the code itself is unchanged. Figures are described in words; see the original PDF for the images.*

In [1]:

```python
# Step 0. Imports
import csv
import json
from pathlib import Path

import numpy as np
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.linear_model import LogisticRegression
from sklearn.metrics.pairwise import cosine_similarity
from sklearn.preprocessing import StandardScaler

# Fix the random number generator for reproducibility
rng = np.random.default_rng(42)
```

## 1.12 Step-by-step walkthrough of the solution

The solutions go in order and become more elaborate step by step:

1. Solution 0: IOU/Jaccard over words.
2. Solution 1: unigram TF-IDF.
3. Solution 2: word+char TF-IDF.
4. Solution 3: solution 2 + greedy one-to-one.
5. Solution 4: solution 3 + logreg-reranker.
6. Solution 5: solution 4 + greedy one-to-one.

### 1.12.1 Step 1. Loading train/test/ytest

We read `train.json` and `test.json` and restore the train pairs, while `true_test` and the `Public/Private` split are built from `ytest.csv` via the correspondences `left_id` $\leftrightarrow$ `right_id` and the column `Usage`.

In [2]:

```python
# Step 1. Loading train/test/ytest (even more compact)
base_dir = Path("/Users/aguschin/Git/uni/vsosh/zakl/nlp")
train_json_path, test_json_path, ytest_csv_path = (
    base_dir / "train.json",
    base_dir / "test.json",
    base_dir / "ytest.csv",
)

def split_poem(text):
    lines = [line.strip() for line in text.split("\n") if line.strip()]
    cut = min(8, len(lines) - 1)
    if cut < 1:
        return None, None
    left, right = "\n".join(lines[:cut]).strip(), "\n".join(lines[cut:]).strip()
    return (left, right) if left and right else (None, None)

# train: from full texts -> pairs of halves -> shuffle the right halves
train_pairs = [split_poem(text) for text in json.loads(train_json_path.read_text(encoding="utf-8"))]
train_pairs = [(left, right) for left, right in train_pairs if left and right]
left_parts = [left for left, _ in train_pairs]
right_parts = [right for _, right in train_pairs]
train_idx = np.arange(len(left_parts), dtype=int)
perm_train = np.random.default_rng(123).permutation(len(left_parts))
left_train = left_parts
right_train_shuffled = [right_parts[i] for i in perm_train]
true_train = np.empty(len(left_parts), dtype=int)
true_train[perm_train] = np.arange(len(left_parts))
n_train = len(left_train)

# test: ready-made left/right
test_data = json.loads(test_json_path.read_text(encoding="utf-8"))
left_items, right_items = test_data["left"], test_data["right"]
left_test = [item["left_text"] for item in left_items]
left_ids = [item["left_id"] for item in left_items]
right_test_shuffled = [item["right_text"] for item in right_items]
right_ids = [item["right_id"] for item in right_items]
n_test = len(left_test)

# ytest: left_id -> right_id and Usage
with open(ytest_csv_path, "r", encoding="utf-8") as f:
    ytest_rows = [row for row in csv.DictReader(f)]

left_to_right = {}
left_to_usage = {}
for row in ytest_rows:
    left_id = (row.get("left_id") or "").strip()
    right_id = (row.get("right_id") or "").strip()
    usage = (row.get("Usage") or "Private").strip().title()
    if not left_id or not right_id:
        continue
    if usage not in {"Public", "Private"}:
        usage = "Private"
    left_to_right[left_id] = right_id
    left_to_usage[left_id] = usage

right_id_to_pos = {rid: j for j, rid in enumerate(right_ids)}
true_test = np.array([right_id_to_pos[left_to_right[lid]] for lid in left_ids], dtype=int)
usage_test = np.array([left_to_usage.get(lid, "Private") for lid in left_ids], dtype=object)
public_mask = usage_test == "Public"
private_mask = usage_test == "Private"

# checks and service variables
assert all(lid in left_to_right for lid in left_ids), "Not all left_id values from test are present in ytest.csv"
assert all(left_to_right[lid] in right_id_to_pos for lid in left_ids), "Some right_id values from ytest.csv are missing from test.json"
vowels = set("аеёиоуыэюя")  # the Russian vowel letters
test_idx = np.arange(n_test, dtype=int) + 10_000_000
overlap = len(set(train_idx.tolist()) & set(test_idx.tolist()))
assert overlap == 0, "train/test overlap detected"

print(f"Source train: {train_json_path}")
print(f"Source test : {test_json_path}")
print(f"Source gt   : {ytest_csv_path}")
print(f"Total pairs: Train: {n_train} | Test: {n_test}")
print(f"Usage split: Public={int(public_mask.sum())} | Private={int(private_mask.sum())}")
print(f"Split fairness: overlap(train,test)={overlap}\n")
```

```text
Source train: /Users/aguschin/Git/uni/vsosh/zakl/nlp/train.json
Source test : /Users/aguschin/Git/uni/vsosh/zakl/nlp/test.json
Source gt   : /Users/aguschin/Git/uni/vsosh/zakl/nlp/ytest.csv
Total pairs: Train: 2000 | Test: 640
Usage split: Public=320 | Private=320
Split fairness: overlap(train,test)=0
```

### 1.12.2 Solution 0: IOU/Jaccard over words

Base score: for each pair of halves, we compute the intersection of the words and divide it by the union. Scoring/choice of the pair: top1 via `argmax` (greedy matching is not used).

In [3]:

```python
# Step 2. Solution 0: IOU/Jaccard via split()

# Solution 0: a base score from the intersection of words

def _masked_acc(pred_idx: np.ndarray, true_idx: np.ndarray, mask: np.ndarray):
    return float((pred_idx[mask] == true_idx[mask]).mean()) if mask.any() else float("nan")

# Function: computes a single score via argmax (Overall/Public/Private)
def evaluate_similarity_argmax(sim: np.ndarray, true_idx: np.ndarray):
    pred = sim.argmax(axis=1)
    score = float((pred == true_idx).mean())
    score_public = _masked_acc(pred, true_idx, public_mask)
    score_private = _masked_acc(pred, true_idx, private_mask)
    return {
        "score": score,
        "score_public": score_public,
        "score_private": score_private,
    }

# Function: turns each text into a set of tokens
def _token_sets(texts):
    return [set(text.split()) for text in texts]

# Function: builds the Jaccard/IOU matrix for all left-right pairs
def _jaccard_matrix(left_sets, right_sets):
    n_left = len(left_sets)
    n_right = len(right_sets)
    sim = np.zeros((n_left, n_right), dtype=np.float32)
    for i, lset in enumerate(left_sets):
        for j, rset in enumerate(right_sets):
            union = lset | rset
            if union:
                sim[i, j] = len(lset & rset) / len(union)
    return sim

word_train_l = _token_sets(left_train)
word_train_r = _token_sets(right_train_shuffled)
word_test_l = _token_sets(left_test)
word_test_r = _token_sets(right_test_shuffled)

sim0_test = _jaccard_matrix(word_test_l, word_test_r)
metrics0 = evaluate_similarity_argmax(sim0_test, true_test)
print(
    f"0_iou_argmax: "
    f"score={metrics0['score']:.4f} (pub={metrics0['score_public']:.4f}, priv={metrics0['score_private']:.4f})"
)
```

```text
0_iou_argmax: score=0.1734 (pub=0.1594, priv=0.1875)
```

### 1.12.3 Solution 1: unigram TF-IDF

We improve solution 0: we replace the plain intersection of words with a TF-IDF representation of the words and cosine similarity.

In [4]:

```python
# Step 2. Solution 1: unigram TF-IDF

# Solution 1: improve solution 0 with TF-IDF features
vec1 = TfidfVectorizer(ngram_range=(1, 1), min_df=5, max_df=0.95, sublinear_tf=False)
vec1.fit(left_train + right_train_shuffled)
sim1_test = cosine_similarity(vec1.transform(left_test), vec1.transform(right_test_shuffled))
metrics1 = evaluate_similarity_argmax(sim1_test, true_test)
print(
    f"1_unigram_tfidf: "
    f"score={metrics1['score']:.4f} (pub={metrics1['score_public']:.4f}, priv={metrics1['score_private']:.4f})"
)
```

```text
1_unigram_tfidf: score=0.2734 (pub=0.2562, priv=0.2906)
```

### 1.12.4 Solution 2: word+char TF-IDF

We improve solution 1: we blend the similarity from word TF-IDF and char TF-IDF and then compute the `argmax` metrics.

In [5]:

```python
# Step 3. Solution 2: word+char TF-IDF

# Function: builds a blended similarity from word and char TF-IDF
def _build_tfidf_blend(left_train, right_train, left_eval, right_eval, cfg, alpha):
    vec_word = TfidfVectorizer(analyzer="word", **cfg["word"] )
    vec_char = TfidfVectorizer(analyzer="char_wb", **cfg["char"] )
    vec_word.fit(left_train + right_train)
    vec_char.fit(left_train + right_train)
    sim_word = cosine_similarity(vec_word.transform(left_eval), vec_word.transform(right_eval))
    sim_char = cosine_similarity(vec_char.transform(left_eval), vec_char.transform(right_eval))
    return alpha * sim_word + (1.0 - alpha) * sim_char

cfg2b = {
    "word": dict(ngram_range=(1, 2), min_df=2, max_df=0.95, sublinear_tf=True),
    "char": dict(ngram_range=(2, 5), min_df=1, max_df=0.99, sublinear_tf=True),
}
alpha2b = 0.25

# Solution 2: improve solution 1 by blending word/char features
sim2b_train = _build_tfidf_blend(left_train, right_train_shuffled, left_train, right_train_shuffled, cfg2b, alpha2b)
sim2b_test = _build_tfidf_blend(left_train, right_train_shuffled, left_test, right_test_shuffled, cfg2b, alpha2b)
metrics2 = evaluate_similarity_argmax(sim2b_test, true_test)
print(
    f"2_word_char_tfidf: "
    f"score={metrics2['score']:.4f} (pub={metrics2['score_public']:.4f}, priv={metrics2['score_private']:.4f})"
)
```

```text
2_word_char_tfidf: score=0.4938 (pub=0.4969, priv=0.4906)
```

### 1.12.5 Solution 3: TF-IDF + greedy one-to-one

We take the score matrix of solution 2 and add a greedy one-to-one matching to increase `one2one`.

In [6]:

```python
# Function: builds a greedy one-to-one correspondence
def greedy_one2one_matching(sim: np.ndarray):
    n = sim.shape[0]
    flat_order = np.argsort(sim, axis=None)[::-1]
    pred = np.full(n, -1, dtype=int)
    used_left = np.zeros(n, dtype=bool)
    used_right = np.zeros(n, dtype=bool)
    matched = 0
    for idx in flat_order:
        i, j = divmod(idx, n)
        if (not used_left[i]) and (not used_right[j]):
            pred[i] = j
            used_left[i] = True
            used_right[j] = True
            matched += 1
            if matched == n:
                break
    return pred

# Function: computes a single score via greedy
def evaluate_similarity_greedy(sim: np.ndarray, true_idx: np.ndarray):
    pred = greedy_one2one_matching(sim)
    score = float((pred == true_idx).mean())
    score_public = _masked_acc(pred, true_idx, public_mask)
    score_private = _masked_acc(pred, true_idx, private_mask)
    return {
        "score": score,
        "score_public": score_public,
        "score_private": score_private,
    }

# Solution 3: add greedy to solution 2
metrics3 = evaluate_similarity_greedy(sim2b_test, true_test)
print(
    f"3_tfidf_greedy: "
    f"score={metrics3['score']:.4f} (pub={metrics3['score_public']:.4f}, priv={metrics3['score_private']:.4f})"
)
```

```text
3_tfidf_greedy: score=0.5062 (pub=0.5094, priv=0.5031)
```

### 1.12.6 Solution 4: logreg reranker

We improve solution 3: we add pairwise features and a logistic regression that re-scores the candidates before `argmax`.

In [7]:

```python
# In short: compute statistics of the halves and assemble a pairwise-feature cube
def _half_stats(texts):
    stats = []
    for text in texts:
        lines = [line.strip() for line in text.split("\n") if line.strip()] or [text.strip()]
        words = ["".join(ch for ch in w if ch.isalpha()) for w in text.replace("\n", " ").split()]
        words = [w for w in words if w]
        letters = [ch for ch in text if ch.isalpha()]
        v_all = [sum(1 for ch in line.lower() if ch in vowels) for line in lines]
        v_edge = [sum(1 for ch in line.lower() if ch in vowels) for line in lines[-4:]]
        cap_ratio = (sum(1 for w in words if w[0].isupper()) / len(words)) if words else 0.0
        latin_ratio = (sum(1 for ch in letters if 'a' <= ch.lower() <= 'z') / len(letters)) if letters else 0.0
        stats.append([len(lines), np.mean([len(line) for line in lines]), np.mean(v_all), np.mean(v_edge), cap_ratio, latin_ratio])
    return np.asarray(stats, dtype=np.float32)

# In short: turn the difference of a scalar feature into a similarity
def _pair_sim(left_vals, right_vals):
    diff = np.abs(left_vals[:, None] - right_vals[None, :])
    norm = np.maximum(left_vals[:, None], right_vals[None, :])
    return 1.0 - diff / (norm + 1e-12)

# In short: form the training pairs (true + hard negatives + random negatives)
def _sample_pairs(cube, true_idx, hard_source_sim, hard_k=8, rand_k=8, random_state=42):
    rng_local = np.random.default_rng(random_state)
    n = cube.shape[0]
    rows, labels = [], []
    for i in range(n):
        j_true = true_idx[i]
        rows.append(cube[i, j_true]); labels.append(1)
        hard_neg = [j for j in np.argsort(-hard_source_sim[i]) if j != j_true][:hard_k]
        forbidden = set(hard_neg + [j_true])
        pool = np.array([j for j in range(n) if j not in forbidden], dtype=int)
        rand_neg = rng_local.choice(pool, size=min(rand_k, len(pool)), replace=False).tolist() if len(pool) else []
        for j in hard_neg + rand_neg:
            rows.append(cube[i, j]); labels.append(0)
    return np.asarray(rows, dtype=np.float32), np.asarray(labels, dtype=np.int32)

left_train_feat = _half_stats(left_train)
right_train_feat = _half_stats(right_train_shuffled)
left_test_feat = _half_stats(left_test)
right_test_feat = _half_stats(right_test_shuffled)

train_maps = [sim2b_train] + [_pair_sim(left_train_feat[:, k], right_train_feat[:, k]) for k in range(left_train_feat.shape[1])] + [_jaccard_matrix(word_train_l, word_train_r).astype(np.float32)]
test_maps = [sim2b_test] + [_pair_sim(left_test_feat[:, k], right_test_feat[:, k]) for k in range(left_test_feat.shape[1])] + [_jaccard_matrix(word_test_l, word_test_r).astype(np.float32)]
cube_train = np.stack(train_maps, axis=2).astype(np.float32)
cube_test = np.stack(test_maps, axis=2).astype(np.float32)

x_train, y_train = _sample_pairs(cube_train, true_train, sim2b_train, hard_k=8, rand_k=8, random_state=42)
scaler = StandardScaler()
model = LogisticRegression(C=0.03, max_iter=2000, class_weight="balanced", solver="lbfgs", random_state=42)
model.fit(scaler.fit_transform(x_train), y_train)
flat_scores = model.predict_proba(scaler.transform(cube_test.reshape(-1, cube_test.shape[-1])))[:, 1]
test_scores_4 = flat_scores.reshape(cube_test.shape[0], cube_test.shape[1])

alpha4 = 0.82
sim4_test = alpha4 * test_scores_4 + (1.0 - alpha4) * sim2b_test
metrics4 = evaluate_similarity_argmax(sim4_test, true_test)
print(
    f"4_logreg_rerank: "
    f"score={metrics4['score']:.4f} (pub={metrics4['score_public']:.4f}, priv={metrics4['score_private']:.4f})"
)
```

```text
4_logreg_rerank: score=0.5203 (pub=0.5031, priv=0.5375)
```

### 1.12.7 Solution 5: logreg reranker + greedy

The final improvement: to the score matrix of solution 4 we again apply greedy one-to-one matching for the maximum `one2one`.

In [8]:

```python
# Solution 5: add greedy to the scores of solution 4
metrics5 = evaluate_similarity_greedy(sim4_test, true_test)
print(
    f"5_logreg_rerank_greedy: "
    f"score={metrics5['score']:.4f} (pub={metrics5['score_public']:.4f}, priv={metrics5['score_private']:.4f})"
)
```

```text
5_logreg_rerank_greedy: score=0.5656 (pub=0.5687, priv=0.5625)
```

In [10]:

```python
# Save the author's submission from the best solution
sim_test = sim4_test
pred_idx = sim_test.argmax(axis=1)

author_submission_path = base_dir / "author_submission.csv"
with open(author_submission_path, "w", newline="", encoding="utf-8") as f:
    writer = csv.writer(f)
    writer.writerow(["left_id", "right_id"])
    for i, lid in enumerate(left_ids):
        writer.writerow([lid, right_ids[int(pred_idx[i])]])

print(f"Saved {author_submission_path}")
```

```text
Saved /Users/aguschin/Git/uni/vsosh/zakl/nlp/author_submission.csv
```

### 1.12.8 Step 5. Matching results

We show only examples of matching for the best current solution: the best and the worst pairs.

In [12]:

```python
# Step 5. Matching results by quantiles for the best solution

def _preview_text(text, max_chars=220, max_lines=8):
    lines = [line.strip() for line in text.split("\n") if line.strip()][:max_lines]
    preview = "\n".join(lines)
    return preview[:max_chars] + ("..." if len(preview) > max_chars else "")

sim_test = sim4_test
pred_idx = sim_test.argmax(axis=1)

quantiles_to_show = [0.99, 0.75, 0.5, 0.25, 0.0]  # can be changed by hand
if not quantiles_to_show or any(q < 0 or q > 1 for q in quantiles_to_show):
    raise ValueError("Quantiles must lie in [0, 1], and the list must not be empty")

match_scores = sim_test[np.arange(len(left_test)), pred_idx]
used = set()

def pick_idx_for_quantile(q):
    target = float(np.quantile(match_scores, q))
    order = np.argsort(np.abs(match_scores - target))
    idx = next((int(i) for i in order if int(i) not in used), int(order[0]))
    used.add(idx)
    return idx, target

print(f"Matching for the best solution")
print(f"Quantiles: {quantiles_to_show}")
print()

for q in quantiles_to_show:
    i, target = pick_idx_for_quantile(q)
    j = int(pred_idx[i])
    print(f"=== q={q:.2f} | target={target:.4f} | sim={match_scores[i]:.4f} ===")
    print(f"left={i} -> pred_right={j} | true={true_test[i]} | correct={j == true_test[i]}")
    print("LEFT :", _preview_text(left_test[i]))
    print("RIGHT:", _preview_text(right_test_shuffled[j]))
    print()
```

*(Translator's note: the poem fragments below are the Russian data of the task and are left untranslated.)*

```text
Matching for the best solution
Quantiles: [0.99, 0.75, 0.5, 0.25, 0.0]

=== q=0.99 | target=0.9055 | sim=0.9076 ===
left=383 -> pred_right=628 | true=628 | correct=True
LEFT : Человек живет на белом свете.
Где - не знаю. Суть совсем не в том.
Я - лежу в пристрелянном кювете,
Он - с мороза входит в теплый дом.
Человек живет на белом свете,
Он - в квартиру поднялся уже.
Я - лежу в пристрелянном ...
RIGHT: Человек живет на белом свете
Он - в квартире зажигает свет
Я - лежу в пристрелянном кювете,
Я - вмерзаю в ледяной кювет.
Снег не тает. Губы, щеки, веки
Он засыпал. И велит дрожать...
С думой о далеком человеке
Легче до а...

=== q=0.75 | target=0.7871 | sim=0.7870 ===
left=208 -> pred_right=508 | true=508 | correct=True
LEFT : Бронепоезда взвывают вдруг,
Стылый ветер грудью разрывая.
Бронепоезда идут на юг
Вдоль твоих перронов,
Лозовая!
Звезды первую звезду зовут.
Дым заката холоден и розов.
Над бронеплощадками плывут
RIGHT: Бескозырки черные матросов.
Говорит, гремит, вздыхает бронь
Отдаленно
и громоподобно.
И горит на станции огонь,
Керосиновый огонь бездомный.
Лист осенний, запоздавший лист,
Братьев в путь-дорогу созывает.

=== q=0.50 | target=0.7115 | sim=0.7113 ===
left=342 -> pred_right=350 | true=350 | correct=True
LEFT : Славянка тихая, сколь ток приятен твой,
Когда, в осенний день, в твои глядятся воды
Холмы, одетые последнею красой
Полуотцветшия природы.
Спешу к твоим брегам... свод неба тих и чист;
При свете солнечном прохлада повевае...
RIGHT: Иду под рощею излучистой тропой;
Что шаг, то новая в глазах моих картина;
То вдруг сквозь чащу древ мелькает предо мной,
Как в дыме, светлая долина;
То вдруг исчезло все... окрест сгустился лес;
Все дико вкруг меня, и су...

=== q=0.25 | target=0.6497 | sim=0.6498 ===
left=532 -> pred_right=415 | true=415 | correct=True
LEFT : Посвящается Феллини
Мертвец играл на дудочке,
По городу гулял,
И незнакомой дурочке
Он руку предлагал.
А дурочка, как Золушка,
Ему в глаза глядит,—
Он говорит о золоте,
RIGHT: О славе говорит.
Мертвец, певец и умница,
Его слова просты —
Пусты ночные улицы,
И площади пусты.
«Мне больно, мне невесело,
Мне холодно зимой,
Возьми меня невестою,

=== q=0.00 | target=0.1137 | sim=0.1137 ===
left=533 -> pred_right=373 | true=329 | correct=False
LEFT : Нет.
Это неправда.
Нет!
И ты?
Любимая,
за что,
за что же?!
Хорошо -
RIGHT: Что нашу грусть —
В листы,
И груз — в цветы
Всего за только всхруст
Руки
В руке:
Игру.
Индус, а может Златоуст
```