Checklist OAI 2025 Stage I · Task 5

Hidden Subsequences

Polish title: Ukryte Podciągi

Learn a small neural regressor that predicts the value of a binary string, defined as the sum of weights of hidden patterns occurring in it as subsequences.

Sequence regression
Polish original · English translation

Download the English notebook Open the task notebook (Polish)

The task

A string T is a subsequence of S if T can be obtained by selecting characters of S at strictly increasing (not necessarily consecutive) positions. For a binary string S and a hidden set W of pairs (pattern T, integer weight v), the value φ(S) is the sum of the weights of all patterns in W that are subsequences of S; for example, with W = {(1111, 1), (1010, 2)}, φ(01101100) = 3, because both 1111 and 1010 are subsequences of it.

The training data consist of strings S and their values φ(S); W is hidden. The contestant builds an nn.Module that approximates φ, accepting input of shape (batch, n) and returning (batch, 1) or (batch,).

Hints: all strings have the same fixed length; every pattern is shorter than the strings; there are three hidden patterns, each with an integer value; a string may contain any number of them; strings are represented as lists over the binary alphabet.

Abridged and translated by SOTA from the official Polish materials. The official statement has the exact rules, and it wins wherever this summary differs.

In English

This task was published in Polish. SOTA translated its 2 files into English on 16 September 2026. Only the words changed in the notebooks: markdown, code comments, messages and printed output. The code, file names and paths are the original's, so a translated notebook runs with the original data.

Read the task notebook in English 1197 words and 14 code cells

Hidden Subsequences

Image generated using the DALL-E model.

Introduction

From ancient soothsayers interpreting the arrangement of the stars to modern cryptographers tracking down traces of hidden messages, humanity has always searched for meaning in seemingly chaotic data. Sometimes key information hides in small sequences of symbols, and its value is revealed only after careful analysis.

In this task you will take on the role of a detective searching for structural dependencies in a set of binary sequences. You will have at your disposal a dataset containing example sequences and their correctly computed values. Your goal will be to develop a method of analysing the hidden patterns that makes it possible to determine, as precisely as possible, the values of sequences that do not appear in the dataset.

We say that a sequence $T$ is a subsequence of $S$ , and write $T \subseteq S$ , if

T = S_{i_1}S_{i_2} \dots S_{i_k}

where

1 \leq i_1 < i_2 < \dots < i_k \leq n

for $k$ and $n$ being the lengths of the sequences $T$ and $S$ respectively, and the indices ( $i_1 < i_2 < \dots < i_k$ ) forming a strictly increasing sequence of natural numbers (not necessarily consecutive).

The solution for a given binary sequence $S \in \{0,1\}^{n}$ and a defined set containing, in turn, a pattern and its weight, $W = \{(T, v):T \in \{0,1\}^{k}, k \le n, v \in Z\}$ , is the number

\phi(S) = \sum_{(T_{i}, v_{i}) \in W} v_{i} \cdot \text{I} (T_{i})

where $\text{I}(T_{i}) = \begin{cases} 1, & T_{i} \subseteq S \\ 0, & T_{i} \subsetneq S \end{cases}$

In other words, $\phi(S)$ is the sum of the values of all the sequences from the set $W$ that are subsequences of $S$ .

Example: For the set $W = \{(1111, 1), (1010, 2)\}$ we have:

$\phi$ (01111000) = 1
$\phi$ (11000100) = 2
$\phi$ (01101100) = 3, because
- 1111 $\subseteq$ 01101100
- 1010 $\subseteq$ 01101100
$\phi$ (01100000) = 0, because 1111, 1010 $\subsetneq$ 01100000.

Task

Create a model (an object of type nn.Module) that will find the value of $\phi$ for the sequences from the dataset. The training data consist of sequences $S$ and their corresponding values $\phi(S)$ . Note, therefore, that the pattern $W$ is hidden, and your task is to approximate $\phi$ without knowing it.

Your model must take input data of shape $(\text{batch}, n)$ , and it must return output values of shape $(\text{batch}, 1)$ or $(\text{batch},)$ , where $\text{batch}$ is the number of samples.

Data

The data available to you in this task are:

train_dataset.csv- a file with the data on which you will train your model
val_dataset.csv- a file with the data on which you will test your model

Scoring Criterion

The task will be scored using the MSE (Mean Squared Error) metric, which is one of the most commonly used metrics for assessing the quality of regression.

MSE = \frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{y}_i)^2

where $y_i$ is the true value and $\hat{y}_i$ is the value predicted by the model. The value $i$ is the sample index, and $n$ is the total number of samples.

We have already implemented this metric in this notebook.

Ultimately, your solution will be scored on a secret test set using the MSE metric. The test set does not differ significantly from the validation set.

If the MSE of your model is 64 (or more), you will receive 0 points for the task
If the MSE of your model is 64 (or less), you will receive X points for the task, where X is defined as follows:

\text{X} = \frac{64 - MSE}{64} \times 100

Constraints

Your solution should contain an ML/DL model with trainable parameters. Purely algorithmic solutions will not be accepted.
Your solution will be tested on the Contest Platform without internet access and in an environment with a GPU.
The evaluation of your final solution on the Contest Platform must not take longer than 4 minutes with a GPU.
Your model may be trained for at most 4000 iterations, which corresponds to a single pass over the variable dl (see the example solution).
Your model may not have more than 50000 parameters.

Notes and Hints

All sequences have the same, fixed length.
Each of the subsequences being sought is shorter than the source sequences.
We consider three subsequences. Each of them has an assigned value, which is an integer.
Each sequence contains any number of the subsequences (including none of them).
The sequences and subsequences come from a binary alphabet and are represented as lists.

Submission Files

This notebook, completed with your solution (see the YourModel class and the model training).

Evaluation

Remember that during checking the FINAL_EVALUATION_MODE flag will be set to True.

You can score between 0 and 100 points for this task. The number of points you receive will be calculated on the (secret) test set on the Contest Platform using the formula given above, rounded to an integer. If your solution does not meet the above criteria or does not run correctly, you will receive 0 points for the task.

Starter Code

In this section we initialise the environment by importing the required libraries and functions. The prepared code will make it easier for you to work with the data efficiently and to build a proper solution.

######################### DO NOT CHANGE THIS CELL WHEN SUBMITTING ##########################

FINAL_EVALUATION_MODE = False # During checking we will set this flag to True.

######################### DO NOT CHANGE THIS CELL ##########################

import os
import gdown
import pandas
import torch
import numpy as np
import torch.optim as optim
import torch.nn as nn

######################### DO NOT CHANGE THIS CELL ##########################

def seed_everything(seed: int) -> None:
    """
    Sets the seed for reproducibility of results in Python, NumPy and PyTorch.

    The function sets the seed for the random number generators of Python, NumPy and PyTorch,
    and also configures PyTorch to work in deterministic mode.

    Parameters:
        seed (int): The seed value to set.
    """
    os.environ["PYTHONHASHSEED"] = str(seed)
    np.random.seed(seed)
    torch.manual_seed(seed)
    torch.backends.cudnn.deterministic = True
    torch.backends.cudnn.benchmark = False

######################### DO NOT CHANGE THIS CELL ##########################

seed_everything(12345)

device = 'cuda'
assert torch.cuda.is_available(), "CUDA is not available!"

Loading the Data

Using the code below, we load the data containing the sequences together with their values.

######################### DO NOT CHANGE THIS CELL ##########################

class CSVDataloader(torch.utils.data.DataLoader):
    """
    The CSVDataloader class is used to load data from CSV files and return it in batches.

    Takes:
        csv_file (str): Path to the CSV file.
        batch_size (int): Batch size.
        shuffle (bool): Whether to shuffle the data.
    """
    def __init__(self, csv_file, batch_size=128, shuffle=True):

        class CSVDataset(torch.utils.data.Dataset):
            """
            The CSVDataset class is used to store data from CSV files as individual samples.
            """
            def __init__(self, csv_file: str):
                data = pandas.read_csv(csv_file).values
                self.x = torch.tensor(data[:, :-1], dtype=torch.float32)  # Features
                self.y = torch.tensor(data[:, -1], dtype=torch.float32)  # Labels

            def __len__(self) -> int:
                return len(self.x)

            def __getitem__(self, idx: int) -> tuple:
                return self.x[idx].long(), self.y[idx]

        dataset = CSVDataset(csv_file)
        self.seq_len = dataset.x.shape[1]
        super().__init__(dataset, batch_size=batch_size, shuffle=shuffle)

######################### DO NOT CHANGE THIS CELL ##########################

# Initialise the training dataset
train_dataset_path = "train_dataset.csv"
val_dataset_path = "val_dataset.csv"

if not os.path.exists(train_dataset_path):
    url = "https://drive.google.com/uc?id=1INeYNpPA_YwojuQbMizlsFsERJ-PJX-E"
    gdown.download(url, train_dataset_path, quiet=True)

if not os.path.exists(val_dataset_path):
    url = "https://drive.google.com/uc?id=1oQcOMyDWVX0x76LOyp4TcFip1koRuodN"
    gdown.download(url, val_dataset_path, quiet=True)

dl = CSVDataloader("train_dataset.csv")
val_dl = CSVDataloader("val_dataset.csv")

Scoring Criterion Code

Code similar to the code below will be used to evaluate the solution on the test set.

######################### DO NOT CHANGE THIS CELL ##########################

def mse_criterium(
        estimations: torch.Tensor,
        answers: torch.Tensor
    ) -> torch.Tensor:
    """
    Computes the value of the mean squared error (MSE) function between the predictions and the true values.

    Parameters:
        estimations (torch.Tensor): The model's predictions.
        answers (torch.Tensor): The true values.

    Returns:
        torch.Tensor: The value of the mean squared error function.
    """
    return torch.mean((estimations.view(-1) - answers.view(-1)) ** 2)


def validate_model(
        model: torch.nn.Module,
        val_dl: torch.utils.data.DataLoader,
    ) -> float:
    """
    Validates the model on the validation set. Returns the averaged value
    of the mean squared error function over all samples.

    Parameters:
        model (torch.nn.Module): The model to evaluate.
        val_dl (torch.utils.data.DataLoader): A DataLoader with the validation data.

    Returns:
        float: The averaged value of the mean squared error function
    """
    model = model.eval().to(device)
    values = []
    for x, y in val_dl:
        x = x.to(device)
        y = y.to(device)
        y_pred = model(x)

        mse = mse_criterium(y_pred, y).cpu().item()
        values.append(mse)

    final_value = torch.tensor(values).mean().item()

    return final_value

def estimate_points(mse: float) -> int:
    """
    A function that determines the number of points for the task from the value of the mean squared error function.

    Parameters:
        mse (float): The value of the mean squared error function.

    Returns:
        int: The number of points for the task (0 - 100).
    """
    points = max((100 * (64 - mse)) / 64, 0)
    return int(round(points))

Example Solution

Below we present a simplified solution that serves as an example demonstrating the basic functionality of the notebook. It can serve as a starting point for developing your solution.

A solution based on a multilayer neural network (Multi-layered perceptron, MLP) can serve as a simple example. In this case we treat the sequences of zeros and ones as the input to our network, while its output models the value of the given sequence. By minimising the mean squared error (MSE), we teach the network to estimate the value of the sequence correctly from its elements.

The illustration below shows how we teach our model to evaluate the values of sequences correctly.

######################### DO NOT CHANGE THIS CELL ##########################

class MLP(nn.Module):
    """
    A class representing an MLP network model with four hidden layers.

    Parameters:
        input_length (int): The length of the network input (the sequence length).
    """
    def __init__(self, input_length: int):
        super(MLP, self).__init__()
        neurons_num = [256, 128, 64, 32]

        self.fc_layers = nn.Sequential(
            nn.Linear(input_length, neurons_num[0]),
            nn.ReLU(),
            nn.Linear(neurons_num[0], neurons_num[1]),
            nn.ReLU(),
            nn.Linear(neurons_num[1], neurons_num[2]),
            nn.ReLU(),
            nn.Linear(neurons_num[2], neurons_num[3]),
            nn.ReLU(),
            nn.Linear(neurons_num[3], 1),
        )

        print("Number of parameters:", sum(p.numel() for p in self.parameters()))

    def forward(self, x: torch.Tensor) -> torch.Tensor:
        """
        A function that takes data sequences and returns predictions of their values using the MLP network.

        Parameters:
            x (torch.Tensor): A data sequence.

        Returns:
            torch.Tensor: Predictions of the sequence values.
        """
        x = x.float()
        x = self.fc_layers(x)
        return x

Training the Example Model

######################### DO NOT CHANGE THIS CELL ##########################

if not FINAL_EVALUATION_MODE:
	model = MLP(dl.seq_len).to(device)

	optimizer = optim.Adam(model.parameters(), lr=0.005)
	criterion = nn.MSELoss()

	model.train()
	for batch in iter(dl): # a single pass over dl - 4000 batches
		inputs, targets = batch
		inputs, targets = inputs.to(device).long(), targets.to(device).float().unsqueeze(1)

		optimizer.zero_grad()
		outputs = model(inputs)

		loss = criterion(outputs, targets)
		loss.backward()
		optimizer.step()

Evaluation of the Example Solution

######################### DO NOT CHANGE THIS CELL ##########################

# validation of the example solution
if not FINAL_EVALUATION_MODE:
    score = validate_model(model, val_dl)
    print(f"Mean squared error: {score:.2f}")

Your Solution

Place your solution in this section. Make changes only here!

# an example model that you can modify

class YourModel(nn.Module):
    def __init__(self, sequence_len):
        super(YourModel, self).__init__()
        self.layer = nn.Linear(sequence_len, 1)

    def forward(self, x):
        """
        A function that takes data sequences and returns predictions of their values.

        Parameters:
            x (torch.Tensor): A data sequence.

        Returns:
            torch.Tensor: Predictions of the sequence values.
        """
        return self.layer(x.float())

Training Your Model

Implement the training of your model here.

your_model = YourModel(dl.seq_len).to(device)

# ...

your_model = your_model.eval()

Evaluation

Running the cell below will let you check how many points your solution would score on the validation data. Before submitting, make sure that the whole notebook runs from start to finish without errors and without any user intervention after choosing the "Run All" option.

# ######################### DO NOT CHANGE THIS CELL ##########################

if not FINAL_EVALUATION_MODE:
    assert sum(p.numel() for p in your_model.parameters()) < 50000, "The model has too many parameters"

    mse = validate_model(your_model, val_dl)
    score = estimate_points(mse)

    print(f"Mean squared error: {mse:.2f}")
    print(f"Estimated points for the task: {score}")

During checking, the model will be saved as your_model.pkl and evaluated on the test set.

######################### DO NOT CHANGE THIS CELL ##########################

if FINAL_EVALUATION_MODE:
    import cloudpickle

    OUTPUT_PATH = "file_output"
    FUNCTION_FILENAME = "your_model.pkl"
    FUNCTION_OUTPUT_PATH = os.path.join(OUTPUT_PATH, FUNCTION_FILENAME)

    if not os.path.exists(OUTPUT_PATH):
        os.makedirs(OUTPUT_PATH)

    your_model = your_model.eval()

    with open(FUNCTION_OUTPUT_PATH, "wb") as f:
        cloudpickle.dump(your_model, f)

Translated by SOTA. The Polish original is the official version and wins wherever the two differ. In the official solution, the saved plot images still show the original Polish titles and axis labels; the plotting code has been translated, so re-running it produces English labels. If you organise this olympiad and would like the translation removed, email [email protected] and we will take it down.

At a glance

You get: train_dataset.csv and val_dataset.csv, downloaded from Google Drive.
You submit: This notebook with the YourModel class and its training; saved to your_model.pkl during checking.
Scoring: MSE on the hidden test set. Points = max(100 × (64 − MSE)/64, 0), rounded to an integer (0 points for MSE ≥ 64).
Rules: The solution must be an ML/DL model with learnable parameters; purely algorithmic solutions are not accepted.
Tested without Internet access, with a GPU; evaluation must take at most 4 minutes.
At most 4,000 training iterations (one pass over the provided data loader).
At most 50,000 model parameters.
Format: Stage I (online), 17 February – 22 March 2025; up to 100 points per task (500 in total). Evaluated automatically on the Competition Platform (Platforma Konkursowa) on a hidden test set; points are rounded to an integer, and a notebook that fails the requirements or does not run scores 0.

Details

Olympiad: Polish Olympiad in Artificial Intelligence (Olimpiada Sztucznej Inteligencji)
Year: 2025, Online
Round: Stage I · Task 5
Language: Polish; English translation by SOTA
License: Not stated by the source

Hidden Subsequences

The task

In English

Hidden Subsequences

Introduction

Task

Data

Scoring Criterion

Constraints

Notes and Hints

Submission Files

Evaluation

Starter Code

Loading the Data

Scoring Criterion Code

Example Solution

Training the Example Model

Evaluation of the Example Solution

Your Solution

Training Your Model

Evaluation

At a glance

Links

In English (SOTA)

Notebook

Solutions

Results

Source files

Details