Test Case Compression Problem

Обмеження: 10 сек., 1024 МіБ

With the continuous iteration of the DUT (Device Under Test), the interaction between features becomes increasingly complex. To ensure the quality of new features, new test cases must be developed. Additionally, new versions must be tested to ensure forward compatibility (i.e., later versions must support the functionalities and features of previous versions). Consequently, the number of test cases grows continuously, leading to increased test workload and quality risks. Therefore, we aim to develop a streamlined method to reduce testing workload while maintaining test case coverage.

Test Action, Flow and Pipeline

We model a specific test action (e.g., "execute software X in condition Y and expect result Z") as a graph vertex. Each vertex has a cost attribute $cost_i$.

A test flow is defined as a directed path visiting two or more test actions, specifying the execution order and serving as a basic component of a full test pipeline.

A test pipeline is a sequence of one or more test flows, allowing duplicates since some bugs require repeated execution to be reproduced. In a pipeline, the last vertex of each flow (except the last one) matches the first vertex of the next one.

For example given test flows 0 → 1 → 4, 2 → 1 → 4, 2 → 3, 3 → 3, 3 → 2, 4 → 2, 4 → 5, 3 → 5, the following pipelines are valid:

(0 → 1 → 4) + (4 → 2) + (2 → 3) + (3 → 2) + (2 → 3) + (3 → 3) + (3 → 2) + (2 → 1 → 4) + (4 → 5),

(0 → 1 → 4) + (4 → 2) + (2 → 3) + (3 → 5).

However, (0 → 1 → 4) + (2 → 3) is invalid.

Each vertex has a location attribute $loc_i$:

\[\text{$loc$}_i = \begin{cases} 0, & \text{if vertex $i$ must be at the beginning of any pipeline it appears in}, \\ 1, & \text{if vertex $i$ must be a middle node (neither beginning nor end)}, \\ 2, & \text{if vertex $i$ must be at the end of any pipeline it appears in}. \end{cases}\]

A pipeline set is a set of pipelines, which satisfies some requirements.

Pipeline Set Requirements

There are two constraints on the pipeline set which you have to respect:

Flow occurrence requirement. Each test flow has a minimal necessary number of occurences in a pipeline set. The flow $j$ must appear at least $w_j$ times in a pipeline set in order for the flow occurence requirement to be considered satisfied.
Precondition requirement. Each vertex $i$ has a precondition set $P_i$. In order for a pipeline set to satisfy the precondition requirement, for each vertex $i$, and each vertex $v \in P_i$ there should be at least one pipeline in the set, where there is a path from the vertex $v$ to the vertex $i$.

Optimization Objectives

Given a set of test flows and a set of pipelines $U^{full}$ created from the given test flows, which satisfies all requirements. Your task is:

Generate $U^{sub}$ – a subset of ${U^{full}}$ that satisfies all requirements while minimizing the total cost of pipelines in the subset.
Generate $U^{new}$ – a new pipeline set that satisfies all requirements while minimizing the total cost of pipelines in the subset.

The description of the pipeline cost as well as other scoring details are described in the Scoring section below.

Вхідні дані

The first line of the input contains three integers $n$, $m$ and $k$ — the number of vertices, the number of flows and the number of pipelines in $U^{full}$.

The next $n$ lines describe information about vertices, one line per vertex. Each line starts with three integer values $cost_i$, $loc_i$ and $P^{len}_i$ — cost of the vertex, location attribute and the size of the precondition set of the $i$-th vertex. The next $P_i$ integers in the line are the elements of the precondition set $P_{i, r}$. If $P^{len}_i = 0$ there is no precondition requirements.

The following $m$ lines describe the test flows. In the $j$-th following line, the first integer is $w_j$ — the flow occurence requirement. The second integer is the length of the test flow $F_j^{len}$. The following $F_j^{len}$ numbers $F_{j, t}$ are the test actions passed by the flow $F_j$, in order that they appear in the flow.

The last $k$ lines describe the pipelines in $U^{full}$. The $p$-th line starts with an integer $U_p^{full}$, which denotes the length of the pipelines, followed by $U_p^{full}$ integers $U_{p, s}^{full}$ — the IDs of the flows used in $p$-th pipeline of $U^{full}$. It is guaranteed that if flows $x$ and $y$ are adjacent in $U^{full}_p$, the last vertex of one equals the first vertex of the other. Also, the location rules, precondition rules and flow occurrence requirement hold true for $U^{full}$.

Вихідні дані

In the first line output a single integer $c$ — the number of pipelines in $U^{sub}$. In the second line output $c$ zero-indexed integers $sub_z$ — the indices of pipelines from $U^{full}$ that are a part of your $U^{sub}$.

In the third line output a single integer $h$ — the number of pipelines in $U^{new}$. Each of the next $h$ lines should describe the pipelines in $U^{new}$, one per line. The $p$-th lines should start with an integer $U^{new}_p$ which indicate the number of flows in the $p$-th pipelines of $U^{new}$ followed by $U^{new}_p$ integers $U^{full}_{p, s}$ — indexes of the flows used in the pipeline, in order.

Обмеження

$1 \le n \le 5 \cdot 10^4$,

$1 \le m \le 10^6$,

$1 \le k \le 10^5$,

$1 \le cost_i \le 2^{16} - 1$,

$0 \le loc_i \le 2$,

$1 \le P_i^{len} \le 1000$,

$0 \le P_{i, r} \le n - 1$,

$1 \le w_j \le 2^{16} - 1$,

$2 \le F_j^{len} \le 100$,

$0 \le F_{j, t} \le n - 1$,

$1 \le U_p^{full} \le 1000$,

$0 \le U_{p, s}^{full} \le m - 1$.

Приклади

Вхідні дані (stdin)	Вихідні дані (stdout)
6 8 4 4 0 0 5 1 0 8 1 1 3 7 1 2 1 4 11 1 0 7 2 0 1 3 0 1 4 1 3 2 1 4 2 2 2 3 3 2 3 3 2 2 3 2 1 2 4 2 1 2 4 5 1 2 3 5 9 0 5 2 4 2 3 4 1 6 4 0 5 2 7 6 0 5 2 4 2 7 6 0 5 2 3 3 7	3 0 2 3 2 8 0 5 2 4 2 4 1 6 9 0 5 2 3 3 3 4 2 7

Примітки

Scoring

Your output for a test is considered to be incorrect if any of the following holds:

the output has a format inconsistent with the one described in the Output section of this statement,
one of the following constraints is violated:
- $1 \le c \le k$,
- $0 \le sub_z \le k-1$,
- $sub_z \neq sub_{z'} \text{ for all } z \neq z'$,
- $1 \le h \le 10^5$,
- $1 \le U^{new}_p \le 1000$,
- $0 \le U^{new}_{p, s} \le m-1$.
flow occurence requirement is not satisfied for $U^{sub}$ of $U^{new}$,
precondition requirement is not satisfied for $U^{sub}$ of $U^{new}$,
location attribute is not respected for any of the vertices in $U^{new}$,
any two consecutive flows in a pipeline in $U^{new}$ do not share the last/first vertex.

You get 0 points for a test with an incorrect output. Otherwise, the total score for a testcase is a combination of the scores of the two tasks:

$score_1$ – the score of the minimum subset accounts for 20%,
$score_2$ – the score of the optimal subset accounts for 80%.

\[\begin{split} score &= \left \lfloor (0.2 \cdot score_1 + 0.8 \cdot score_2) \cdot 10^7 \right \rfloor, \\ score_1 &= \max \left( \frac{cost(U^{full}) - cost(U^{sub})}{cost(U^{full})}, 0 \right), \\ score_2 &= \max \left( \frac{cost(U^{full}) - cost(U^{new})}{cost(U^{full})}, 0 \right). \\ \end{split}\]

The cost of a pipeline set is the sum of costs of all pipelines in the set. The cost of a pipeline is the sum of costs of all vertices it traverses. Note that vertices shared between consecutive flows in a pipeline are counted only once. For example:

cost((0 → 1 → 4) + (4 → 2) + (2 → 3) + (3 → 5)) = $cost_0 + cost_1 + cost_4 + cost_2 + cost_3 + cost_5$.

cost((0 → 1 → 4) + (4 → 2) + (2 → 3) + (3 → 3) + (3 → 2) + (2 → 3) + (3 → 5)) = $cost_0 + cost_1 + cost_4 + cost_2 + cost_3 + cost_3 + cost_2 + cost_3 + cost_5$.

\[cost(U) = \sum_{p = 0}^{|U|-1} \left( first(U_{p, 0}) + \sum_{s = 0}^{U_p - 1} flow(U_{p, s}) \right),\]

where $first(j)$ is the cost of the first vertex in flow $j$, $flow(j)$ is the cost of all vertices of the flow $j$ except the first one:

\[\begin{split} first(j) &= cost_{F_{j, 0}}, \\ flow(j) &= \sum_{t = 0}^{F_{j}^{len} - 1} cost_{F_{j, t}}. \\ \end{split}\]

Submissions

The execution time limit is 10 seconds per test case, and the memory limit is 1024 mebibytes.
The code size limit is 64 kibibytes.
The compilation time limit is 1 minute.
There are 47 provisional test cases. Your submissions will be evaluated on the provisional set during the submission phase.
You can submit your code no more than once every 30 minutes, and you will get feedback with your score for each of the provisional tests.
There will be 240 test cases in the final testing after the submission phase is over. Please note that provisional tests are not included in the final testing. The final results will be announced in one week.

Quick start

Check the sample solution, which reads the data, iterates through the pipelines and removes them from the pipeline set if none of the constraints is violated. In this solution, $U^{new}$ is the same as $U^{sub}$.

Tests

There are two types of test cases:

Real test cases. Data from production enviroments is anonymized and adapted for the purposes of the problem.
Synthetic test cases. Generated by a generator.

Please check out a sample test cases set which consists of 4 real and 20 synthetic tests here: hot-2025-1-sample-dataset.zip (Google Drive, ~200 Mb, ~500 Mb when extracted). You can use those for exploring the specifics of the tests or for local testing. If you have any troubles downloading, please contact us through the Clarifications section.

Each of the three test sets (sample, provisional and final) contain approximately $16\%$ of real test cases. The real test cases are split randomly into the three sets without any bias or handpicking. The synthetic test cases are all generated by the same generator using random initial seeds. Synthetic test cases are generated without any bias or handpicking as well.

Checker and scorer

The checker verifies the correctness of your output for the test. It checks if the data in your output file is valid. If there is an issue with your solution the checker prints a message which describes the problem to standard output. If your output is correct, the checker prints nothing.

The scorer calculates the score of your output. Please note that the scorer doesn’t check for the validity of the output and assumes that the output is correct, i.e. the checker was run prior to the scorer and didn’t report any issues.

The checker and the scorer both use an Algotester Library. You can use the checker and the scorer for local testing by taking a few simple steps:

Save the library source code to a file named algotester.h
Save the checker source code to a file named checker.cpp
Save the scorer source code to a file named scorer.cpp

Compile the source codes:

g++ checker.cpp -O2 -o checker
g++ scorer.cpp -O2 -o scorer

Run the checker and provide it with the test case and your output for this test case:
```
./checker <input-file> <your-output-file>
```
This will report any issues with your output for the test case to standard output.
Run the scorer and provide it with the test case and your output for this test case:
```
./scorer <input-file> <your-output-file>
```
This will print your score for the test case to standard output.

Element Type	Створено	Хто	Задача	Компілятор	Результат	Час (сек.)	Пам'ять (МіБ)	№	Дії

Element Type	Is Unofficial	Місце	Хто	Група	Group Id	Розширена група	Group Ex Id	Бали	Штраф	Results	Is Current User	№	Дії	2025-2026 - R1

2025-2026 - R1. Test Case Compression Problem | HOT • Practice