I have been learning about Matroids and Matroid Intersection and I've solved a few problems using the algorithm. However, most resources online, academic or competitive, only list a handful of nontrivial matroids that have a forseeable application in competitive programming. I'd like to make this post for two reasons. The first reason is to ask the community for other interesting matroids they've seen in other problems or come up with on their own and proved the matroid property. The second reason is to compile a list of these matroids for others in the future to use, as well as a list of problems that use matroid intersection for further practicing.

Please, if you have anything to contribute, feel free to comment / dm me on cf or on discord @meaf!

List of common Matroids:

• The Graphic / Forest Matroid: Let $$$X$$$ be the set of edges in a graph, and $$$I$$$ be the set of subsets of $$$X$$$ s.t. the edges do not form a cycle.
• The Linear Matroid: Let $$$X$$$ be a set of vectors, and $$$I$$$ be the set of subsets of $$$X$$$ s.t. all vectors are linearly independent.
• The Colorful Matroid: Let $$$X$$$ be a set of elements, each with their own color. Let $$$I$$$ be the set of subsets of $$$X$$$ s.t. all elements have pairwise distinct color.
• The Extended Colorful Matroid: Let $$$X$$$ be a set of elements, each with their own color. Let $$$C$$$ be a list of nonnegative integers, one for each distinct color. Let $$$I$$$ be the set of subsets of $$$X$$$ s.t. for any color $$$i$$$, the number of elements of color $$$i$$$ does not exceed $$$C_i$$$
• The Matching Matroid: Consider a bipartite graph. Let $$$X$$$ be the set of elements on the right side of the bipartition. Let $$$I$$$ be the set of subsets of $$$X$$$ s.t. there exists a matching which contains exactly these elements.

List of Matroid Intersection problems:

SPOJ: Coin Collecting

CodeChef: Communicating Servers

CodeChef: Faulty System

CF: Pick Your Own Nim

CF: ICPC Kingdom

Kattis: Rainbow Graph

I've recently been working on suffix automaton code and I have an implementation that I believe to be more intuitive and easier to type (certainly shorter) than the implementation I've seen circulating around (mainly adapted from cp-algorithms). It also appears to benchmark a little faster than the cp-algorithms implementation as well, which is a nice perk. Please, let me know if you can find some improvements to make, either making the code shorter, faster, etc.

Edit: The primary purpose of this code is for ICPC-style contests which limit printed material and have no digital materials (unlike codeforces which allows copy/paste during contests). Thus, my primary focus is brevity and speed, not necessarily readability. There's always tradeoffs; for example, if 20 characters would be added to make the code much more readable, than that's a valid consideration, but I want the number of lines and number of characters to be as small as reasonable without making the code completely arcane.

// len is the longest-length substring ending here
// pos is the first index in the string matching here
// term is whether this node is a terminal (aka a suffix)
struct st { int len, pos, term; st *link; map<char, st*> next; };
st *suffixAutomaton(string &str) {
    st *last = new st(), *root = last;
    for(auto c : str) {
        st *p = last, *cur = last = new st{last->len + 1, last->len};
        while(p && !p->next.count(c))
            p->next[c] = cur, p = p->link;
        if (!p) cur->link = root;
        else {
            st *q = p->next[c];
            if (p->len + 1 == q->len) cur->link = q;
            else {
                st *clone = new st{p->len+1, q->pos, 0, q->link, q->next};
                for (; p && p->next[c] == q; p = p->link)
                    p->next[c] = clone;
                q->link = cur->link = clone;
            }
        }
    }
    while(last) last->term = 1, last = last->link;
    return root;
}