EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
ICPC 2025
ICPC 2025

F. Herding Cats

You are opening a cat cafe in Baku and would like to take a promotional photograph of all the cats sitting in the front window. Unfortunately, getting cats to do what you want is a famously hard problem. But you have a plan: you have bought a collection of...

Updated May 21, 2026
Track ICPC
Year 2025
Statement Text + PDF
TeXC++Statement textStatement PDF
Problem statement

Problem Statement

Formatted from the contest statement text, with sample tests broken out into copyable blocks.

Statement text Statement PDF
Time limit 2 seconds

You are opening a cat cafe in Baku and would like to take a promotional photograph of all the cats sitting in the front window. Unfortunately, getting cats to do what you want is a famously hard problem. But you have a plan: you have bought a collection of m catnip plants, each of a different variety, knowing that each cat likes some of these varieties. There is a row of m pots in the window, numbered 1 to m in order, and you will place one plant in each pot. Each cat will then be persuaded (by means of a toy on a string) to walk along the row of pots from 1 to m. As soon as a cat reaches a pot with a catnip plant that it likes, it will stop there, even if there already are other cats at that plant.

Figure F.1: One possible plant ordering for the first sample test case.

You know which pot you would like each cat to stop beside. Can you find a way in which to place the plants in the pots to achieve this?

Input

The first line of input contains an integer t (1 ≤ t ≤ 10 000), which is the number of test cases. The descriptions of t test cases follow. The first line of each test case contains two integers n and m, where n (1 ≤ n ≤ 2 · 105 ) is the number of cats, and m (1 ≤ m ≤ 2 · 105 ) is the number of catnip plants (and also the number of pots). Catnip plants are numbered from 1 to m. The following n lines each describe one cat. The line starts with two integers p and k, where p (1 ≤ p ≤ m) is the pot at which the cat should stop, and k (1 ≤ k ≤ m) is the number of catnip plants the cat likes. The remainder of the line contains k distinct integers, which are the numbers of the plants that the cat likes. Over all test cases, the sum of n is at most 2 · 105 , the sum of m is at most 2 · 105 , and the sum of all k is at most 5 · 105 .

Output

For each test case, output either yes if it is possible to arrange the catnip plants as described above, or no if not.

Sample Tests

Sample 1
Sample Input 
 2
 3   5
 2   2   1 5
 2   3   1 4 5
 4   2   3 4
 3   5
 2   2   1 5
 2   3   1 4 5
 5   2   3 4
Sample Output 
yes
no

In the first test case, a possible ordering of the plants is [2, 1, 5, 3, 4]. This way, cat 1 will stop at pot 2, as it is the first pot with a plant variety that it likes. Cat 2 will stop there as well. Cat 3 will continue all the way to pot 4, as shown in Figure F.1.

Editorial

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Key Observations

  • For a plant variety $v$, define \[ LB[v] = \max \{p_i : \text{cat } i \text{ likes } v\}. \] If we placed $v$ before $LB[v]$, then some cat that likes $v$ would stop too early. So $v$ may only appear at position $LB[v]$ or later.

  • Therefore a necessary prefix condition is: among the first $j$ pots, we must have at least $j$ plant varieties with $LB[v] \le j$.

  • Now look at a fixed position $j$ with one or more cats assigned to stop there. The plant placed at pot $j$ must be liked by all of those cats, and it must satisfy $LB[v]=j$. If $LB[v] < j$, then some cat that likes $v$ would have been able to stop earlier than $j$. If $LB[v] > j$, then that plant cannot legally be placed at $j$ at all.

  • These two conditions are also sufficient: choose one common plant with $LB=j$ for every occupied position $j$, then place all remaining plants in the still-empty positions in nondecreasing order of $LB$.

Algorithm

  1. Read all cats and compute $LB[v]$ for every plant $v$.

  2. Check the prefix condition by counting how many plants have each lower bound and accumulating these counts from left to right.

  3. Group cats by their target position. For each occupied position $j$, count how many cats at $j$ like each plant. We need at least one plant that is liked by all cats of that group and also satisfies $LB[v]=j$.

  4. If both checks pass, output yes; otherwise output no.

Correctness Proof

We prove that the algorithm returns the correct answer.

Lemma 1.

In any valid arrangement, every plant $v$ must be placed at a position at least $LB[v]$.

Proof.

By definition of $LB[v]$, there exists a cat that likes $v$ and is supposed to stop at position $LB[v]$. If $v$ were placed earlier, that cat would encounter a liked plant before its designated stop and would stop too soon. □

Lemma 2.

For every occupied position $j$, the plant placed at $j$ must be liked by all cats assigned to $j$ and must satisfy $LB[v]=j$.

Proof.

If the plant at $j$ were not liked by some cat assigned to $j$, that cat would continue past pot $j$. If $LB[v] < j$, then some cat that likes $v$ is supposed to stop earlier, so placing $v$ at $j$ would not be the first liked plant for all cats that need to stop at $j$. If $LB[v] > j$, Lemma 1 forbids putting $v$ at $j$. Thus the condition is necessary. □

Lemma 3.

If the prefix condition and the position-wise common-plant condition both hold, then a valid arrangement exists.

Proof.

Fix one valid common plant with $LB=j$ for every occupied position $j$. These choices already guarantee that every such position stops exactly the cats assigned to it. Now consider the remaining plants and the still-empty positions. By the prefix condition, for every prefix of length $j$ there are at least $j$ plants with $LB \le j$. Since we already used exactly one plant with $LB=j$ for each occupied position $j$, the same prefix condition still holds for the leftovers. Therefore placing the remaining plants in nondecreasing order of $LB$ fills all empty positions without ever violating a lower bound. By Lemma 1 no cat stops too early, and the chosen special plants make the cats at occupied positions stop exactly where required. □

Theorem.

The algorithm outputs the correct answer for every valid input.

Proof.

If the program answers yes, then both checks pass, and Lemma 3 gives a valid arrangement. If the program answers no, then either the prefix condition fails, contradicting Lemma 1, or some occupied position has no valid common plant, contradicting Lemma 2. Hence no valid arrangement exists. □

Complexity Analysis

Let $K$ be the total number of liked-plant entries in the test case. The algorithm runs in $O(m+n+K)$ time and uses $O(m+n+K)$ memory. Over all test cases this matches the input bounds.

Implementation Notes

  • The frequency array for the intersection test is reset only on the plants touched by the current group of cats, which keeps the total work linear in the input size.

  • A plant with $LB[v]=0$ is liked by no cat, so it can be used in any still-empty position.

Implementation

Code

C++ solution used for this page.

C++

Clean code view with a raw-file link when you want the original source.

Raw file 
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;

        vector<int> need_at(m + 1, 0);
        vector<vector<int>> cats_at(m + 1);
        vector<vector<int>> like(n);

        for (int i = 0; i < n; ++i) {
            int p, k;
            cin >> p >> k;
            cats_at[p].push_back(i);
            like[i].resize(k);
            for (int j = 0; j < k; ++j) {
                cin >> like[i][j];
                need_at[like[i][j]] = max(need_at[like[i][j]], p);
            }
        }

        vector<int> bucket(m + 1, 0);
        for (int plant = 1; plant <= m; ++plant) {
            bucket[need_at[plant]]++;
        }

        bool ok = true;
        long long seen = bucket[0];
        for (int pos = 1; pos <= m; ++pos) {
            seen += bucket[pos];
            if (seen < pos) {
                ok = false;
                break;
            }
        }

        vector<int> freq(m + 1, 0), touched;
        for (int pos = 1; pos <= m && ok; ++pos) {
            int group = (int)cats_at[pos].size();
            if (group == 0) {
                continue;
            }
            touched.clear();
            for (int cat : cats_at[pos]) {
                for (int plant : like[cat]) {
                    if (freq[plant] == 0) {
                        touched.push_back(plant);
                    }
                    freq[plant]++;
                }
            }
            bool found = false;
            for (int plant : touched) {
                if (freq[plant] == group && need_at[plant] == pos) {
                    found = true;
                }
                freq[plant] = 0;
            }
            if (!found) {
                ok = false;
            }
        }

        cout << (ok ? "yes" : "no") << '\n';
    }

    return 0;
}
Resources

Source Files and Assets

Raw files are still available here when you want the original TeX, C++, or statement assets.

Show raw files
TeX write-upcompetitive_programming/icpc/2025/F-herding-cats/solution.texC++ implementationcompetitive_programming/icpc/2025/F-herding-cats/solution.cppStatement textcompetitive_programming/icpc/2025/F-herding-cats/statement.txtStatement PDFcompetitive_programming/icpc/2025/F-herding-cats/statement.pdfMetadatacompetitive_programming/icpc/2025/F-herding-cats/meta.jsonYear packetcompetitive_programming/icpc/2025/contest_problems.pdf