Background

Fujian Province Youth Informatics Programming Level Certification 2021, Problem 4.

Problem Description

A lottery event is taking place. Each participant receives $n$ sequences. Each sequence contains $d$ positive integers, and there is also a number $k$, meaning that among these positive integers, there exist $k$ lucky numbers.

Each participant chooses several consecutive sequences from their own sequences to form an interval, called a candidate interval. If every sequence in the candidate interval contains at least one lucky number, then this interval is called a lucky interval. Of course, there may be more than one lucky interval. The rules say that the lucky interval containing the most sequences (i.e., with the greatest total length) is called the super lucky interval.

For example, when $d=2,k=3$, the sequences are:

• Sequence $0$: 115 120.
• Sequence $1$: 50 80.
• Sequence $2$: 199 30.
• Sequence $3$: 40 40.
• Sequence $4$: 30 30.
• Sequence $5$: 25 40.

The interval from sequence $0$ to sequence $2$ is a lucky interval, because each sequence from $0$ to $2$ contains $120$, $50$, or $30$, for a total of $3$ lucky numbers. The interval from sequence $1$ to sequence $5$ is also a lucky interval, because all sequences from $1$ to $5$ contain $80$, $30$, or $40$, and it contains $5$ sequences, so it is the super lucky interval with the greatest total length.

Each participant wants to know what their super lucky interval is. The programming task is: for each participant, output the index of the first element and the index of the last element of the super lucky interval with the greatest total length. If there are multiple intervals with the same maximum length, output the one with the smallest first index. Note that indices start from $0$.

Input Format

The first line contains an integer $T$, representing the number of participants who received sequences.

Then follow $T$ groups of data, each describing one participant’s sequence information.

The first line of each group contains three positive integers $n,d,k$, as described above. The next line contains $n\times d$ integers: the first $d$ integers represent sequence $0$, the next $d$ represent sequence $1$, and so on.

Output Format

For each participant, output one line: Case #x: y z, where $x$ is the $\text{case}$ number (starting from $1$), and $y$ and $z$ are the indices of the first and last elements of the answer interval.

(There is one space between Case and #; there is no space between # and x; there is one space after : before y; there is one space between y and z.)

4
8 1 2
1 2 3 2 4 5 4 6
4 3 2
1 2 3 4 5 6 7 8 9 10 11 12
6 2 3
10 20 50 60 70 30 40 40 30 30 20 40
10 1 3
2 4 3 1 4 5 3 1 1 2

Case #1: 1 3
Case #2: 0 1
Case #3: 1 5
Case #4: 1 4

Hint

Constraints

For $45\%$ of the testdata, $n\le1000$.

For $50\%$ of the testdata, $k=2$.

The first two parts together account for $70\%$.

For $100\%$ of the testdata, $2\le k\le 3$.

The input file is within $\text{4.8M}$, $T=10,1\le d\le 4,1\le$ each number in each sequence $\le10^5$.

For at most $6$ $\text{case}$, $1\le n\le 10^5$; for all other $\text{case}$, $1\le n\le 10^3$.

Translated by ChatGPT 5