# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3741 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3489 |
7 | Radewoosh | 3483 |
8 | Kevin114514 | 3442 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 166 |
2 | atcoder_official | 163 |
3 | Um_nik | 162 |
3 | maomao90 | 162 |
5 | adamant | 157 |
5 | -is-this-fft- | 157 |
5 | djm03178 | 157 |
8 | awoo | 155 |
9 | TheScrasse | 154 |
10 | Dominater069 | 153 |
Name |
---|
Good article. However, learning matroid didn't give me any power solving greedy tasks :(
hahaha, i kinda wonder if these theories are useful in any way lol. given that a red coder also thinks like me :)
There once was a time matroid-intersection tasks popped up.
USACO Guide Link?
Me neither :(. But I think it is a nice way to generalize scattered ideas into one coherent theory, and maybe internalizing some examples can help in unexpected situations where greedy doesn't make sense.
Thanks for helping the community!
Really helpful, thanks for the blog!!
another nor sir blog to star :prayge:
Soon top 10 contributors :prayge:
donee
nor I don't understand the second claim of the proof of theorem 1 part 1, mind clarifying?
Also, should Theorem 3 have $$$w:2^S\to\mathbb R$$$? That is, $$$w$$$ maps subsets of $$$S$$$ to reals.
Indeed, thanks for catching the typo.
Seems like I messed up the claim while writing up the sketch.
The second claim makes sense now, but I don't get third claim. Is it really a continuation of the first claim? Why would $$$sa\in L$$$ imply $$$st'\in L$$$? Isn't the latter string longer?
The part that it is a continuation is an error from when I mentioned the first claim elsewhere in the first draft, and the second claim was the first claim back then. It is also very poorly phrased in retrospect (in quite a lot of ways); it is actually connected to the subsequence $$$t'$$$ in the second claim. Here's what I meant when I wrote that (paraphrasing from my notes):
Let's say we have $$$st, sa \in L$$$. Consider the $$$t'$$$ from the second claim, and the positions of the subsequence that was shifted by 1. If we move $$$a$$$ in that subsequence while preserving the order of the other elements, then the resulting $$$t"$$$ will satisfy $$$st" \in L$$$. (Looking at it in another way, we are shifting one part of the remaining subsequence to before $$$a$$$, while keeping the order of the remaining elements the same, which is essentially what the claim says).
If we consider the previous example, where $$$s = pqr$$$, $$$t = uvwxyz$$$ and $$$t' = avwuyx$$$, we can move around the sequence $$$a$$$ within the characters $$$a, u, x$$$, while preserving the relative position of $$$u$$$ and $$$x$$$, any number of times to get $$$t"$$$ such that $$$st"$$$ is in $$$L$$$. Thus $$$t"$$$ can be $$$uvwayx$$$, $$$uvwxya$$$ and of course $$$t'$$$.
nor Regarding local forest greedoids:
Wouldn't $$$\{x\}$$$ be such a set? Why is this set unique (and what path does it induce)?Never mind, I confused these with matroids.
Actually, I'm still confused about this property. There doesn't seem to be a unique set for the directed branching greedoid, is there?
Now I'm not sure how this issue can be resolved either. Looking through my references, I was referring to this and this for directed branching greedoids in the context of local forest greedoids, and the first link gives the claim for branching greedoids.
Also, I just noticed there are other definitions of directed branching greedoids, so I probably inadvertently mixed them up — for instance, this paper gives the definition that I used in the examples above. For the purposes of proving the correctness of certain greedy algorithms on rooted graphs, however, the two definitions "should" both lead to correct proofs.
Is it true that for any $$$L$$$ there is a corresponding $$$F$$$? If not, it doesn't seem correct to refer to these definitions as equivalent.
Yes, this is true.
How do you show that this is true?
Simply map a $$$w \in L$$$ to the set of its characters, call this mapping $$$f$$$. We claim that $$$f$$$ is the required mapping to go from $$$L$$$ to $$$F$$$. $$$|s| > |t|$$$ in $$$L$$$ implies, since $$$L$$$ is a simple language, that $$$f(s) \setminus f(t)$$$ is the set of characters that are in $$$s$$$ but not in $$$t$$$, and there can be at most one occurrence of any character in $$$S$$$ in the list of characters in $$$s$$$ but not in $$$t$$$ (with multiplicity). So for every $$$tx$$$ for $$$x \in s$$$ and $$$x \not \in t$$$, we have a unique element $$$f(t) \cup \{x\}$$$ in $$$F$$$. Now for any $$$A, B$$$ in $$$F$$$ with $$$|A| > |B|$$$, we can use any preimage of $$$A$$$ and any preimage of $$$B$$$ in $$$L$$$ to be able to claim that there is a $$$x$$$ in $$$A \setminus B$$$ such that $$$A \cup \{x\} \in F$$$. Abuse of notation: we will also denote the map from $$$L$$$ to the set of sets as $$$f$$$.
For the other direction, considered an unordered greedoid $$$(S, F)$$$, and the maximal simple hereditary language $$$L$$$ such that $$$f(L) \subseteq F$$$. It is easy to check that $$$L$$$ is an ordered greedoid. Let's call this mapping $$$g$$$.
Note that $$$f$$$ and $$$g$$$ applied in this order will map $$$L$$$ to itself — this can be shown by induction on word size.
Since this gives an explicit natural bijection, we can use either definition for a greedoid. Most sources (such as Wikipedia) use an unordered version, but I find the ordered version to be much more intuitive for greedy algorithms.
Mind explaining the induction?
Let's denote $$$g(f(L))$$$ as $$$L'$$$. In whatever follows, we'll implicitly use the fact that $$$L$$$ and $$$L'$$$ are simple languages.
All characters of $$$L$$$ are present as singleton sets in $$$f(L)$$$ (and they are the only singletons), so all words of size $$$1$$$ in $$$L'$$$ are in $$$L$$$ too.
It'll be more concise to use well-ordering instead of induction here to show that $$$L'$$$ is a subset of $$$L$$$ (same thing since they're equivalent). Consider a smallest word $$$w$$$ in $$$L'$$$ that is not in $$$L$$$ (if it exists). $$$w$$$ has size at least $$$2$$$. Since $$$L'$$$ is hereditary, $$$w[:-1]$$$ is in $$$L'$$$. But since $$$w$$$ is the smallest word in $$$L'$$$ that is not in $$$L$$$, $$$w[:-1]$$$ is in $$$L$$$ as well. Note that $$$f(L')$$$ is a subset of $$$f(L)$$$, so there is a word $$$w'$$$ in $$$L$$$ such that $$$f(w')$$$ = $$$f(w)$$$. Since $$$L$$$ is a greedoid, apply the exchange lemma on $$$w'$$$ and $$$w[:-1]$$$. This shows $$$w$$$ is in $$$L$$$, contradiction.
So $$$L'$$$ is a subset of $$$L$$$, which means $$$L$$$ and $$$L'$$$ are identical, owing to the maximality of $$$L'$$$.