### ko_osaga's blog

By ko_osaga, history, 4 weeks ago,

In today 6pm KST, I will stream solving problems related to Chordal Graphs and Tree decompositions. Stream link is here.

Even if the problem has some special structure, I will ignore it and only assume that it is a Chordal Graph or a graph with bounded treewidth.

Stream will end if someone asks me to play League together. I think it will probably last about 4 hours.

Enjoy!

• +148

By ko_osaga, history, 4 weeks ago,

I recently solved some problems that involved the concept of Lyndon decomposition. Honestly, most of them were too hard to understand for me. I'm just trying to think out loud about things I've read, so I can learn ideas or better takes from smarter people?

Note that I will omit almost all proofs as I can't do that. I believe all unproven claims below are facts, but it is always great to have doubts about anything.

## 1. Lyndon decomposition, definition, and algorithms

A string is called simple (or a Lyndon word), if it is strictly smaller than any of its own nontrivial suffixes. Examples of simple strings are $a, b, ab, aab, abb, abcd, abac$.

It can be shown that a string is simple, if and only if it is strictly smaller than all its nontrivial cyclic shifts. As a corollary, it can be observed that simple words are never periodic (it is not a repetition of some words for $2$ or more times).

The Lyndon decomposition of string $s$ is a factorization $s = w_1 w_2 \ldots w_k$, where all strings $w_i$ are simple, and are in non-increasing order $w_1 \geq w_2 \geq \ldots \geq w_k$.

Alternatively, the Lyndon decomposition of string $s$ can be represented as $s = w_1^{p_1} w_2^{p_2} \ldots w_k^{p_k}$. Here, $p_i$ are positive integers, and $w^p_i$ denotes the string $w$ repeated for $p_i$ times. All strings $w_i$ are simple, and are in decreasing order $w_1 > w_2 > \ldots > w_k$. The only difference is that the group of identical factors is grouped as a chunk such as $w^p_i$.

It is claimed that for any string such a factorization exists and it is unique. However, I can't prove it.

### 1.1 Algorithm

There are two algorithms that compute the Lyndon decomposition in linear time. The first algorithm is the well-known Duval algorithm. E-maxx has a good explanation on this, so I won't discuss it here.

Another algorithm is conceptually much simpler. Given a string $S$, consider the greedy algorithm that repeatedly removes the smallest suffix from $S$. By definition, the greedy algorithm always removes a simple word, so the algorithm will return a decomposition consisting of simple words. We believe that the Lyndon decomposition is unique, thus algorithm returns a Lyndon decomposition.

Let's compute the time complexity, the algorithm will iterate at most $O(N)$ times, and it can find the smallest suffix naively in $O(N^2)$ time, so the naive implementation will take $O(N^3)$ time. However, the smallest suffix is just the first entry of the suffix array, so using the fastest suffix array algorithm can optimize each phase to $O(N)$, giving an $O(N^2)$ algorithm.

Should we compute the suffix array from scratch in each phase? The removal of a suffix does change the ordering in the suffix array. For example, $abac < ac$, but $aba > a$.

However, this issue doesn't apply to our application, where we remove the smallest suffix. Therefore, given a suffix array $SA_0, \ldots, SA_{N - 1}$ for the string $S$, one can simply iterate from $SA_0$ to $SA_{N - 1}$, and cut the string as long as it is the leftmost position we encountered. As the suffix array can be solved in $O(N)$, this gives an $O(N)$ solution to the Lyndon decomposition. I can't prove why this is true. But this looks like a folklore algorithm, so I believe it's true.

## 2. Computing Lyndon decomposition for each substring

For a string of size $N$, the Lyndon decomposition may have at most $O(N)$ size, in which case the above algorithms are already optimal. Hence, in this section, we only discuss finding the smallest suffix for each substring in near-constant time, since it may

• lead to an algorithm for computing Lyndon decomposition in near-linear time on output size, by the above greedy algorithm.
• yield some small implicit structure (tree) that captures the Lyndon decomposition for all interesting substrings

### 2.1. Lyndon decomposition for all suffixes

The removal of a prefix does not change the ordering in the suffix array. To find the smallest suffix in $S[x ...]$, just find the first entry in the suffix array such that $SA_i \geq x$.

### 2.2. Lyndon decomposition for all prefixes

Duval's algorithm is basically incremental since it repeatedly adds a letter $s[j]$ to the existing structure. This hints that the Lyndon decomposition can be computed for all prefixes, although it's not entirely straightforward.

I came up with the algorithm to compute all min suffixes for all prefixes. There are other algorithms to compute the min suffixes, such as the one ecnerwala described in this comment.

Duval algorithm maintains a pre-simple string in each iteration. Consider a pre-simple string $t = ww\ldots w\overline{w}$ for the current prefix. Except for the last string $\overline{w}$, every other string are simple. And if we take the Lyndon decomposition of $\overline{w}$, the first element of it is the prefix of $\overline{w}$, which is obviously less than $w$. As we know that Lyndon decomposition is unique, we can see that the last element of Lyndon decomposition of $\overline{w}$ is exactly the smallest suffix of the current prefix.

Thus, the naive algorithm is the following:

• If $\overline{w}$ is empty, $w$ is the smallest suffix of the given prefix.
• Otherwise, the smallest suffix of $\overline{w}$ is the smallest suffix for the given prefix.

However, we don't have to recompute the smallest suffix of $\overline{w}$ every time. In the decomposition algorithm, we fix the string $s_1 = s[0 : i)$ and compute the decomposition for the suffix $s[i \ldots]$. For each relevant $i$, we use dynamic programming. Let $MinSuf[j]$ be the length of smallest suffix of $S[i \ldots j)$ for $j > i$. If $\overline{w}$ is empty the smallest suffix is $w$. Otherwise, since $\overline{w}$ is exactly the string $S[i \ldots i + |\overline{w}|)$, $MinSuf[j] = MinSuf[i + |\overline{w}|]$. Therefore we can obtain a simple recursive formula.

### 2.3 Lyndon decomposition for all substrings?

This paper contains some ideas, so if you are interested, give it a try :)

## 3. The Runs Theorem

Run is a concept that is useful for solving problems related to repeats. Even if you never heard of the name, anyone who solved some challenging suffix array problems will be familiar with it.

Given a string $S$, the tuple $(l, r, p)$ is a run of string $S$ if

• $0 \le l < r \le |S|$
• $1 \le p \le |S|$
• $r - l \geq 2p$
• $p$ is the smallest positive integer where $S[i] = S[i + p]$ holds for all $l \le i < r - p$
• The above four properties doesn't hold for tuple $(l - 1, r, p)$ and $(l, r + 1, p)$

Let $-S$ be the string where all elements are inverted: Specifically, we assign s[i] = 'a' + 'z' - s[i] for all elements of $S$, so that the usual comparison order is reverted, except the empty character which has the lowest priority.

Given a string $S$, a Lyndon prefix is the longest prefix that is a Lyndon word. Given a suffix array of $S$, this Lyndon prefix can be easily computed. Recall an algorithm that computes the Lyndon decomposition given a suffix array. Let $Rank_i$ be the inverse of the suffix array. Then, we can see that the length of the Lyndon prefix is the smallest $i$ such that $Rank_i < Rank_0$ (or $|S|$ if such does not exist). Similarly, we can also compute this for all suffixes $S[i \ldots]$: find the smallest $j > 0$ such that $Rank_{i + j} < Rank_i$.

For each suffix of $S$ and $-S$, we compute the Lyndon prefix $[i, j)$ and take them as a "seed". Start from the tuple $(i, j, j - i)$, and extend the tuple in both direction as long as $S[i] = S[i + p]$ holds. Specifically, Let $k$ be the maximum number such that $S[i, i + k) = S[j, j + k)$ and $l$ be the maximum number such that $S[i - l, i) = S[j - l, j)$. Then we obtain a run $(i - l, j + k, j - i)$. Both $k, l$ can be computed in $O(\log N)$ time with suffix arrays.

It's easy to verify that those elements are actually the run of the string. If we remove all duplicated runs, the following fact holds:

Fact 1. Those we computed are exactly the set of all Runs.

Fact 2. There are at most $n$ runs.

Fact 3. The sum of $(j - i) / p$ for all runs are at most $3n$.

Fact 4. The sum of 2-repeats ($j - i - 2p + 1$) obtained from runs are at most $n \log n$.

Fact 3 is useful when we want to enumerate all repeats. Suppose that we have to enumerate all possible repeats. A string "aaaa" can be considered as a repeat of "a" 4 times, but it is also a repeat of "aa" 2 times. In this case, we have to enumerate all multiples of $p$ — but by Fact 3, that does not affect the overall complexity.

Fact 1, 2, 3 can be found on this paper. I think Fact 4 is not hard to prove, but that doesn't mean I've done it, nor do I have a reference that states this fact.

## 4. Lexicographically minimum substring reverse

Given a string $S$, you can select $0$ or more non-overlapping substrings, and reverse them. What is the lexicographically minimum result you can obtain from the single iteration of this operation?

Let $S^R$ be the reverse of $S$. The answer is to take the Lyndon decomposition for $S^R$, and reverse each substring from that respective position.

I don't know why this works.

Intuitively, we are replacing each prefix of $S$ to the minimum suffix of $S^R$. Replacing each prefix to the minimum possible suffix seems like a good trade. Do you agree or disagree? XD

## 5. Minimal Rotation from Lyndon decomposition

Given a string $S$, what is the lexicographically minimum result you can obtain by taking a cyclic shift of $S$?

The answer can be found by finding the smallest suffix of length $> |S|$ for string $S + S$, and rotating at the respective position. This suffix can be found with Lyndon decomposition. Therefore we can solve this in $O(n)$ time, which is great.

What about just reversing a minimum suffix of $S$? Unfortunately, cases like "acabab", "dacaba" are the countercase. If we can reduce this problem into a minimum suffix instance, we can solve this problem for all prefixes, suffixes, and possibly substrings, so that's really unfortunate...

.. or maybe not. For a string $S$, consider it's Lyndon factorization $S = w_1^{p_1} w_2^{p_2} w_3^{p_3} \ldots w_k^{p_k}$. Clearly, taking the middle of periods is a bad idea. And taking only $w_k^{p_k}$ as a candidate is wrong.

Then what about trying to crack the tests? Let $SFX_j = w_j^{p_j} w_{j+1}^{p_{j + 1}} \ldots w_k^{p_k}$. Then, we can try all $SFX_j$ in range $k - 69 \le j \le k + 1$ as a candidate. It looks really hard to create an anti-test for this approach.

Lemma. Minimum rotation exists in the last $\log_2 |S|$ candidates of $SFX_j$. (Observation 6)

This provides an algorithm for computing the minimum rotation in $O(Q(n) \log n)$ time, where $Q(n)$ is time to compute the minimum suffix.

## Practice problems

### Minimum rotation for each substring

• +105

By ko_osaga, history, 3 months ago,

Hello!

XXII Open Cup. Grand Prix of Seoul will be held in 2022/07/17 Sunday, 17:00 KST (UTC+9).

The contest was used as a Day 2 Contest for ByteDance Summer Camp 2022.

Problems were authored by jh05013, molamola., jihoon, ainta, pichulia, chaeyihwan, evenharder, TLEwpdus, applist, Cauchy_Function.

Special thanks to myself for translating the statements and editorials.

Enjoy!

• +136

By ko_osaga, history, 7 months ago,

Hello!

XXII Open Cup. Grand Prix of Daejeon will be held in 2022/03/27 Sunday, 17:00 KST (UTC+9). The date of March 27 is final.

Daejeon is home to KAIST, but the contest itself has little to do with it, it just inherits the spirit of 2019 Daejeon GP.

The contest was used as a Day 2 Contest for Petrozavodsk Winter Camp 2022. I'm sorry for the camp participants over the lack of editorial. I will work to publish the full editorials right after the GP.

Problems were authored by ko_osaga, GyojunYoun, nell_jwk, Diuven, queued_q, jh05013. Special thanks to xiaowuc1 for reviewing the statements.

For external accounts, the contest is ready now.

Note that the old opencup.ru link is not accessible now. (snarknews is trying to find servers outside of Russia.)

List of relevant previous contests:

Enjoy!

• +100

By ko_osaga, history, 11 months ago,

Update (2021.10.28): Editorial, Division 1 Gym, Division 2 Gym are prepared.

Hello!

For external accounts, the contest is ready now.

List of relevant previous contests:

Enjoy!

• +188

By ko_osaga, history, 14 months ago,

Since hmehta didn't wrote anything..

For easy, I spend eternity to realize that every cards starts with their face down. I have so many things to talk about easy, but at this point, it seems worthless.

• +122

By ko_osaga, history, 16 months ago,

Will there be a mirror in the near future?

• +87

By ko_osaga, history, 19 months ago,

TL;DR: IOI 2021 was planned to held on-site with strong safety measures. Today, IC announced to turn it into an on-line contest (I guess due to travel difficulties). The IC is exploring the possibility of an optional on-site contest.

Dear Friends of IOI,

I hope you are doing well as COVID-19 is still rampaging all over the world. But as vaccines are becoming available, I hope we can all soon get back to our normal life before the pandemic.

The IC held the Winter meeting in late February. We have the following important information regarding IOI 2021 to share with the community.

First, IOI 2021, organized by Singapore, will still be an online competition much like the previous year. The competition week will fall between mid to late June.

Second, competition aside, in an effort to bring back some normalcy, IOI business will be conducted as usual. This includes collection of registration fees and election of new committee members.

Third, the host and the IC are still exploring possibilities to socially host some teams who can and are willing to travel to Singapore, subject to various Air Travel requirements and COVID-19 safe management measures. Such teams would still sit the contest online from within Singapore, using their own computers. Detailed plans will be announced by the host as they become available.

I hope this information will allow you to start making plans for selecting teams to participate in IOI 2021. The IC and the host team will continue to held online meetings leading up to the IOI in June. We will keep you all updated as things develop further. If you have any questions, please contact the IOI Secretariat at secretary.ioinformatics@gmail.com.

Stay safe and best wishes, Greg Lee IOI President

• +271

By ko_osaga, history, 19 months ago,

Hello!

I uploaded 2020 Petrozavodsk Summer Camp, Korean Contest to the CF Gym. It is a collection of Korean problems per the request of snarknews.

Problems are collected from:

• UCPC 2020 (Local ICPC Contest. 2019 version was used in XX Open Cup. GP of Korea)
• Semi-Game Cup (Contest authored by Seoul Science High School students. YeongTree is selected to IOI 2021 Korea team)
• IOI 2020 Korean TST (Problem B)
• Random educational problem from rkm0959

Problems are authored by:

And unfortunately there are no editorials.

List of relevant previous contests:

Enjoy!

• +81

By ko_osaga, history, 20 months ago,

Hello! I'm happy to announce XXI Open Cup. Grand Prix of Suwon. Gyeonggi Science High School is located in Suwon, Korea.

This contest was used as a Day 9 Contest from Petrozavodsk Winter 2021 Camp.

List of relevant previous contests:

Enjoy!

• +155

By ko_osaga, history, 21 month(s) ago,

Hi!

Tomorrow at 22:00 KST I will stream solving New Year Prime Contest 2021. It is an ongoing contest, but Prime Contest is special, so I think it's okay to stream.

My goal is to implement the task "Gardening Game". gs18115 said it is very interesting. Let's give it a try!

If I have time left, I will try to implement "Evacuation" with SMAWK.

The stream will end if Prime Contest 2021 ends.

See you!

• +226

By ko_osaga, history, 22 months ago,

Hi! Tomorrow at 21:00 KST I will stream solving judge.yosupo.jp. In the stream, I will try to implement Edmond's Directed MST algorithm with this lecture note.

I will solve the following problems in the stream. Recommendations are welcome, preferably ones that's not just "Find Directed MST".

Since this is not a regular data structure stream, I will keep it short. The stream will last about 3 hours.

This event isn't that well-prepared like others, please don't expect too much :)

Thanks!

• +117

By ko_osaga, history, 2 years ago,

Hello! I'm happy to announce XXI Open Cup. Grand Prix of Korea.

Special thanks to xiaowuc1 for revising our English.

List of relevant previous contests:

Enjoy!

• +279

By ko_osaga, history, 2 years ago,

Thanks to vintage_Vlad_Makeev for the information.

According to Wikipedia, RP is a class of decision problem which admits a randomized polynomial-time algorithm such that:

• If the correct answer is NO, it always returns NO
• If the correct answer is YES, then it returns YES with probability at least 1/2 (otherwise, it returns NO).

The Amazing Power of Randomness: NP=RP authored by Andras Farago claims that NP=RP. This means, there is a randomized polynomial time solution to NP problems, such as:

• 3-SAT
• Traveling Salesperson Problem
• Minimum Vertex Cover
• Graph Coloring
• Among others

What does it mean? Is the paper wrong? Should we start studying randomized algorithm instead of machine learning? Will all cryptographic system collapse?

• +769

By ko_osaga, history, 2 years ago,

Currently, Jury archives for NERC 2019 is missing, unlike the other years.

Can anyone look into those issues and update the website?

• +35

By ko_osaga, history, 2 years ago,

In 2020/05/24 14:00 KST, I will stream solving 全国統一プログラミング王決定戦本戦.

I'll also experiment with my new tablets, so there will be some explanation of my thinking process.

Even if you can't read Japanese, don't worry. I can't read it either, and I'll have a hard time with the translator too.

The stream will end if I solve everything or if it's too late.

Stream link is https://www.twitch.tv/gs14004 as usual.

See you!

• +33

By ko_osaga, history, 2 years ago,

I uploaded 2020 Petrozavodsk Winter Camp, Jagiellonian U Contest to the CF Gym.

The problemset was used in 2020 Petrozavodsk Winter Camp, and North America Programming Camp 2020. Both ghosts are in scoreboard, so it's a good opportunity to test your skills.

In the version used in PtzCamp and NAPC, problem K had a weak test and the model solution failed in my simple handcrafted tests. I just added that test, and changed the problem limit leniently to allow model solution to pass. I guess this made the problem much easier now.

Thanks to the problemsetters (I don't know who are them). Enjoy!

Editorial

• +77

By ko_osaga, history, 3 years ago,

You are given a graph $G$, and for each vertex $v$ you have to assign a positive integer color such that every adjacent pair of vertices (vertices directly connected by edge) have different color assigned. You have to minimize the maximum color assigned: In other words, you have to minimize the number of distinct assigned colors.

But that's graph coloring (vertex coloring). It's hard. Ok, one more time:

You are given a graph $G$, and for each edge $e$ you have to assign a positive integer color such that every adjacent pair of edges (edges sharing same endpoints) have different color assigned. You have to minimize the maximum color assigned: In other words, you have to minimize the number of distinct assigned colors.

Note that this can be interpreted as "graph coloring (vertex coloring) of line graphs". In that sense, you can consider in a similar spirit to "graph coloring of interval graphs", "graph coloring of permutation graphs", blah-blah.

## General graph

Let $D = max_{v \in V(G)}deg(v)$ be the maximum degree of a graph. Since every vertex should be incident to edges with different colors, the edges can't be colored with less than $D$ colors.

So if we somehow find the way to color the edges with $D$ colors, the case is closed. This is obviously not true: Consider a 3-cycle, then $D = 2$, but you need 3 colors.

Still, Vizing discovered that this is approximately true:

• Theorem (Vizing, 1964). Every simple graph can be edge-colored with $D+1$ colors.
• Proof: If you are interested then see here.

Note that:

• Theorem doesn't hold if the graph has multiple edges connecting same vertices.
• It's NP-hard to determine if the graph can be colored with $D$ colors, so optimal coloring is still NP-hard.

Wikipedia discusses the $O(nm)$ algorithm to find a $D+1$ edge coloring of simple graph, which you can find the implementation here. Sometimes, people asks you to solve just that exact same problem, and sometimes you can just cheese problems without thinking too much. Anyway, this is not our main point. let's jump to more interesting part.

## Bipartite Graphs

To find an optimal edge coloring, we have to prove that the edges can be colored with $D$ colors. In general graph this was a little (one color!) bit of fail, but as the countercase had an odd cycle, maybe in bipartite graph this is true?

• Theorem. Every bipartite graph can be edge-colored with $D$ colors.

• Proof. We use induction on $D$.

• If $D = 0$, the proposition is trivial.

• Otherwise, we will partition the graph $G$ with a matching $M$ and a graph $G\setminus M$ with maximum degree $D - 1$. We transform the graph $G$ in such a way that the left/right bipartition have equal number of vertices (just add dummy nodes of degree 0), and every node have degree $D$ (repeatedly pick two nodes with degree $<D$ and add a dummy edge. If this procedure fails, then two bipartition have different sum of degrees, which is impossible).

Let $L, R$ be a bipartition of this new graph. Now we assume every node of $G$ have degree $D$. Suppose there is no perfect matching in $G$. Then by Hall's theorem, there exists a subset of vertices $S \subseteq L$ such that $|N(S)| < |S|$. Then there exists $|S| \times D$ edges connecting between $N(S)$ and $S$. On the other hand, there can't exist more than $|N(S)| \times D$ edges incident to $N(S)$. Contradiction. Thus the perfect matching exists.

Now remove the dummy edges from the perfect matching. Note that the dummy edges don't connect any node which originally had degree $D$. So the edges left from the matching still covers all nodes with degree $D$. Denote this matching $M$. Then $G \setminus M$ have maximum degree $D - 1$. Color the edges in $M$ with color $D$, and color $G \setminus M$ by inductive hypothesis.

• Remark. Theorem still holds when the graph has multiple edges.

This also gives an algorithm to find a edge coloring of bipartite graphs. We just want to find any matching that covers all nodes with maximum degree $D$. If all nodes have degree $D$, then simple bipartite matching works. In general case, since we have to cover some nodes, we have to model this as flow and enforce some edges to have capacity 1. This can be modeled with maximum flow with demands. In any case, if you use Dinic's algorithm or Hopcroft/Karp, time complexity is $O(D \times MN^{0.5})$.

So that's great, we can optimally solve edge coloring of bipartite graph in polynomial time. On the other hand, using matching or even flow with demands is pretty tiring and complicated, can we get rid of flows at all?

There is an implementation of edge coloring in $O(NM)$ with short code and good constant factor, which doesn't rely on flow argument. You can read about this algorithm here (problem F). Here is the implementation I use, which is copied from waterfalls' submission here.

## Faster

Can we do this faster? Let's go back to Dinic's algorithm. Here's a simple yet elegant trick to reduce the time complexity from $O(D \times MN^{0.5})$ to $O(MN^{0.5} \log D)$.

The idea is, as you can guess from the $\log$ factor, divide-and-conquer. If $D$ is odd, you can just use the naive method to reduce the degree to $D - 1$. If $D$ is even, it partitions the graph into two pieces with maximum degree $\frac{D}{2}$. But how?

Let's revisit the following well-known fact related to even degrees:

• Lemma (Euler Circuit). For connected graphs where every node has even degree, there is a circuit which visits every edges exactly once.

And also, there exists an algorithm to compute the Euler circuits in linear time.

So now, let's add some dummy edges again to connect the vertices with odd degree. Obviously, there exists even number of vertices with odd degree, so we can add any kind of matchings between them. Now, every connected component has an Euler circuit, so we can compute them for linear time.

Now, note that the Euler circuit obviously have even length in bipartite graphs, let's denote the circuit as $C = {e_1, e_2, \ldots, e_{2k}}$. Let's color the odd-numbered edges ($e_1, e_3, e_5 \ldots$) as blue, and even-numbered edges as red. Then, for each vertex $v$, we can see it is adjacent to $\frac{deg(v)}{2}$ blue nodes and $\frac{deg(v)}{2}$ red nodes! This is because, if the circuit entered the vertex with some color, it leaves the vertex with different colors.

Thus, just take the Euler circuit for each component, and divide the edges into blue and red sets. Remove dummy edges, and you still have max degree $\frac{D}{2}$ for each color. So you can recurse from that point! Since every edges are considered at at most $O(\log D)$ recursion stage, and they contribute to at most $N^{0.5}$ overhead, the time complexity is $O(MN^{0.5} \log D)$.

## More faster!!

Now let's look for something genuinely fast: Fast enough that it doesn't involve any flow and have $O(M\log M \log D)$ solution!

Going back to the original proof, we know that it is easier to assume that the graph is regular: Every node has degree of $D$. Naive strategy of adding edges, as described in proof, adds too much edges and is inefficient. But we can improve it by "merging" small-degree nodes: If two node have sum of degree at most $D$, then we can merge(contract) two nodes, and any coloring in this new graph still works in the original one.

So, for each side of biparitition, while there is at least 2 nodes with $deg(v) \le \frac{D}{2}$, find them and contract it. After the end of this procedure, we are left with at most 2 nodes (one for each bipartition) with $deg(v) \le \frac{D}{2}$. Now, even if we apply the naive way of adding dummy nodes and edges, we end up adding at most $O(cM)$ edges where $c \le 3$ in my naive calculation.

Now let's assume the graph is regular. Thanks to regularity, we don't have to find flows anymore but can simply calculate a perfect matching in this regular graph. It doesn't look easy to find this faster than $O(M^{1.5})$, but there is an algorithm to compute a perfect matching of regular graph in $O(M \log M)$, which was discovered in 2010: https://arxiv.org/pdf/0909.3346.pdf

To briefly explain what's going on, the algorithm is actually not very different from finding a bipartite matching with flows. We construct a usual flow graph with source and sinks, and find an augmenting path. There are just two notable difference:

• If the edge is in matching, rather than reversing it, we just contract two endpoint of such edge. You can see this doesn't make the situation different.
• We don't use DFS to find path: We use random walk from source, which means we will sample any outgoing edges with random probability, and halt until it reaches the sink.

Intuitively, the second heuristic will run very fast in the initial stage of augmenting path finding. At the first stage the length of path will be length 3, and it will remain so until a certain period. Random walk procedure is much faster than DFS in such case, because it's time complexity is just it's walk length. Now, the paper claims the following:

• Lemma 6 (from paper). If we found $m < n$ matchings in a current graph, then the expected number of steps taken by the random walk is at most $2 + \frac{n}{n - m}$.

Then, we can simply do this for all $0 \le m \le n - 1$, and get $2n + n \sum_{i=1}^{n}\frac{1}{i} = O(n \log n)$!

Lastly, note that this problem can be solved in $O(M \log M)$ time. Interested readers can find it in the second reference link.

## Challenge

The $O(mn)$ algorithm is very simple to implement and it usually don't find long Kempe chains. I doubt that is true for any fast algorithm I mentioned. Plus, it won't be cache oblivious. Can anyone implement any $o(mn)$ algorithm for bipartite edge coloring which runs faster than $O(mn)$ algorithm?

## Practice problem

I added some practice problem for this topic. Some of them are directly related to my article, some of them checks your creativity at reducing different problems to bipartite edge coloring.

## References

Also special thanks to 300iq for introducing me the paper for perfect matching.

• +361

By ko_osaga, history, 3 years ago,

From Sunday 14:00 UTC-4 Eastern Daylight Time, I will stream solving problems in Chinese OJ. Specifically, I'll try to

• Read these two papers (paper1 paper2) and try to learn them
• Write it in Chinese OJ (problem1 problem2). Huge thanks to TLE for making this stream more authentic.

Stream link is https://www.twitch.tv/gs14004. Stream will be in English.

I'm not sure about the exact plan, but I'll stream at least 4 hours.

See you!

• +151

By ko_osaga, 3 years ago,

About 4 hours later (2020/01/27 20:30 KST), I will stream solving random OI problems.

Things I might try solving:

The stream will end if I get sleepy.

Stream link is https://www.twitch.tv/gs14004 as usual.

See you!

• +39

By ko_osaga, history, 3 years ago,

Since the Polygon tutorial system is currently broken, I will replace the editorial with PDF format. Sorry for the inconvenience!

Solution PDF

Problem A was authored by ko_osaga. Code

Problem B was authored by ko_osaga. Code

Problem C was authored by ko_osaga. Code

Problem D was authored by no_ng. Code

Problem E was authored by ckw1140. Code

Problem F was authored by ko_osaga. Code

Problem G was authored by ko_osaga. Code

Tutorial of Hello 2020

• +191

By ko_osaga, 3 years ago,

새해 복 많이 받으세요, 코드포스! (Happy new year, Codeforces!)

Welcome to the first Codeforces Round of the new decade, Hello 2020! The round will be held on Jan/04/2020 15:05 MSK.

• Div 1, 2 combined
• 2.5 hours!
• 7 problems!
• Score distribution: 500-1250-1750-2500-2750-4000-4000
• Yes, it is rated!

This round is prepared by ko_osaga no_ng ckw1140. I am personally very thrilled to deliver my first Codeforces contest as such a memorable one!

More credits for the contest:

UPD: Editorial. Thank you for your participation!

UPD2: Winners:

Announcement of Hello 2020

• +1231

By ko_osaga, history, 3 years ago,

From Friday 14:00 UTC+9 Korea Standard Time, I will stream solving problems in Baekjoon OJ. All problems will be only about doing some queries on sequences or graphs.

Problem list

My goal is to stream until Saturday 0:00 (10 hours), including meals and some other breaks.

See you!

• +141

By ko_osaga, history, 3 years ago,

Hi! In Korea Regional ICPC homepage, news about ICPC East Asia Pacific Semifinal has appeared. I didn't found any other articles about this, so I'll upload this to get some contribution.

There will be a semi-final competition in the East Asia-Pacific region between the Regional Contest and the World Final. The official title is undecided, but the semifinals will be held in Vietnam on December 21-23, 2020. Up to this year, we are selecting teams to advance to the world competitions, but starting next year, some will be selected at the regional competitions and some will be selected at the semifinals. Unlike the World Championships, the semifinals are expected to allow multiple teams, with an upper limit on the number of teams in each university. The East Asia-Pacific region includes Korea, Taiwan, Japan, Southeast Asia such as Vietnam, the Philippines and Indonesia, and Oceania such as Australia and New Zealand.

Original post

Great to see some fair team selection in East Asia!

• +67

By ko_osaga, history, 3 years ago,

Update 2019/11/07. The contest is now in Gym. Thanks to MikeMirzayanov for uploading it. Have fun!

Hello! I'm happy to announce XX Open Cup. Grand Prix of Korea.

List of relevant previous contests:

Enjoy!