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?

Share your thoughts!

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

Can anyone look into those issues and update the website?

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!

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

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.

This is the edge coloring of graph, and I will talk about this now.

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.

• Codeforces: Edge coloring of Bipartite graphs
• AGC 037 D. Sorting a Grid
• OpenCup 2019/2020 GP of Wroclaw G: Choreography
• Codeforces: Privatization
• Codeforces: Football
• COCI 2018/2019 Round 1 #5. Teoreticar

References

• All the practice problems
• https://www.tau.ac.il/~nogaa/PDFS/lex2.pdf
• https://arxiv.org/pdf/0909.3346.pdf

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

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!

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

Things I might try solving:

• USACO JAN20 Bronze, Silver, Gold Division
• Some old POI tasks (Fire Extinguisher, Fire Brigade, Trees)
• Some random Baekjoon OJ tasks if I really have any time left after this

The stream will end if I get sleepy.

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

See you!

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 nong. Code

Problem E was authored by ckw1140. Code

Problem F was authored by ko_osaga. Code

Problem G was authored by ko_osaga. Code

새해 복 많이 받으세요, 코드포스! (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.

Some information about the round:

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

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

More credits for the contest:

• Coordinator: 300iq
• Testers: kdh9949 kriii OnionPringles molamola. evenharder jihoon DongwonShin xiaowuc1 998kover KAN Diuven
• Great Codeforces and Polygon: MikeMirzayanov

UPD: Editorial. Thank you for your participation!

UPD2: Winners:

1. mnbvmar
2. TLE
3. Benq
4. tourist
5. gamegame
6. never_giveup
7. dario2994
8. yosupo
9. Marcin_smu
10. kczno1

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.

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

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

See you!

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!

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.

• Contest link: http://official.contest.yandex.ru/opencupXX/contest/14556/enter (Only visible for users with OpenCup login)
• Contest time: 2019/10/13 Sunday, 17:00 Korea Standard Time (UTC+9).
• Problemsetters: ainta, Cauchy_Function, jh05013, ko_osaga, kriii, .o.. Thank you!
• Testers: All problemsetters, kdh9949, Konijntje, jqdai0815, tzuyu_chou, xiaowuc1, chenjb. Thank you!

List of relevant previous contests:

• XVIII Open Cup. GP of Korea
• KAIST RUN Spring Contest 2018
• XIX Open Cup. GP of Korea
• XIX Open Cup. GP of Daejeon

Enjoy!

From Friday 14:00 UTC+9 Korea Standard Time, I will stream solving ICPC World Finals 2018 J, Uncrossed Knight's Tour.

Stream link is https://www.twitch.tv/gs14004. Sorry for changing it from my previous account (I'm somehow unable to login with my previous account. I think it is hacked.)

I'll stream until I solve it, or I give up and sleep.

See you!

Hello!

International Olympiad in Informatics (IOI), the most prestigious programming contest in the world, is held in a beautiful city of Baku, Azerbaijan this year.

Wish the best luck to every contestant!

Day1: The contest had started on time, but the scoreboard is broken. It seems there is no mirror this year.

Day1 Contest Overview: Benq solved all Day1 problems in only 3.5 hours, congratulations! Full scorers for each tasks: 23(rect) / 170(shoes) / 6(split)

Day2 Contest Overview: The winner for Day2 is duality, but Benq still secures his consecutive IOI win. Congratulations! Full scorers for each tasks: 0(line) / 47(vision) / 2(walk)

Contest Results

1. Benq 547.09
2. 300iq 511.22
3. duality 494.33
4. TLE 491.46
5. FizzyDavid 482.39

Country Ranking

• 1 Russia 4G
• 2 China 3G1S
• 2 United States of America 3G1S
• 4 Republic of Korea 2G1S1B
• 4 Vietnam 2G1S1B

Congratulations to everyone who competed, and especially to our super awesome team gina0605 GyojunYoun Onjo blackbori !

Useful Links:

• Scoreboard (Mirror by snarknews)
• Youtube live stream
• List of contestants

If there are any errors, please write it in the comment.

Hi all!

Did you know that SRM 763 is scheduled in 15:00 July 17, 2019 UTC+0? I didn't, and I bet you also didn't, so here is a helpful reminder.

Let's wait for hmehta to announce the writers.

And, don't forget the TCO19 Round 3B!

Hi! I was migrating KAIST RUN Spring Contest 2019 into CF Gym, and encountered following error:

For problem C, E, I made a copy of the original problem, as Gym system can't interpret test groups. Otherwise, they are all sane. They are packaged with verification, and user codeforces has write rights for all problems.

I believe this is beyond my scope to handle, MikeMirzayanov, could you please help?

Update 2019/06/12: Me and MikeMirzayanov managed to upload the Div.2 contest into Gym. Huge thanks him for the great system, and also a kind help!

However, I decided not to just open it, but to give a training contest. The contest is scheduled in June 14 Friday, 09:00 UTC. Even considering some obvious bias from the setter, I'm personally very proud of the Div.2 contest :D I hope you participate and share the same joy with us! (and of course, please don't cheat!)

.

.

.

.

.

.

.

.

Update 2019/06/05: I managed to upload the Div.1 contest into Gym. Have fun! https://codeforces.com/gym/102201

Open Cup GP of Daejeon is scheduled at 2019/05/05 Sunday, 11:00 MSK. Daejeon is a city where KAIST is.

Division 1 problem set is identical with MIPT PreFinals Camp 2019 Day 6. It was held on March 15.

Division 2 problem set is identical with KAIST RUN Spring Contest 2019. It was held on May 1 locally. Like last year, it was an IOI-style contest, but as we are doing in OpenCup, subtask will be disabled. Some problems between Div1 and Div2 are shared.

Problems were created by ainta, Konijntje, ko_osaga, kriii, kdh9949. Some problems in Div1 were borrowed by Diuven, imeimi.

Problems were tested by arknave, dotorya, Namnamseo, tzuyu_chou, .o..

List of relevant previous contests:

• XVIII Open Cup. GP of Korea
• KAIST RUN Spring Contest 2018
• XIX Open Cup. GP of Korea

Enjoy!

To jump on a bandwagon, I'll run a boring stream, where I'll virtual participate JOI Spring Camp 2019 Day2 (or Day1 if that's harder). The time will be 3/21 Thursday 7:30 PM UTC+9 (KST)

https://www.twitch.tv/koosaga

If this works out well, I'll maybe continue streaming after WF. I'll try to solve problems that is both hard and annoying, something like this.

See you!

Hmm.. Am I the only one not appearing in the scoreboard?!?

http://hsin.hr/coci

40 minutes left. Enjoy!

Update 2019/01/02: The problemset is finally uploaded to CF Gym. If you didn't participated before, this is a great chance to practice on one of Petr's best problem candidates. I hope you enjoy the contest. Happy New Year!

Division 1 Link

Division 2 Link .

.

.

OpenCup GP of Korea (third edition) is scheduled at 2018/10/14 Sunday, 11:00 MSK.

Both Div1 / Div2 problemset will feature Korean problems.

Problemsetters: ainta alex9801 Cauchy_Function Konijntje jh05013 ko_osaga OnionPringles jo_on .o.

Enjoy!

Hello Codeforces!

In 2018/05/26 21:30 Korea Standard Time (UTC+9) we will hold an online mirror of 2018 KAIST RUN Spring Contest. This is an annual individual contest held by KAIST's algorithm club RUN.

Problems are available in English, and you should individually solve 11 problems in 5 hours. The problems will be prepared in Gym, so this contest is unrated. Grading rules are ICPC-style. There are no prizes in this contest, but if any top scorers come to KAIST, we will bring you to our favorite restaurants or pubs ( ͡° ͜ʖ ͡°)

This online mirror might not reflect the onsite contest fully, due to some technical limits. For example, the grading rules in main contests were IOI-style, every problems were 100 points with subtasks and we had no penalties, but we had some difficulties implementing it on CF environment :/

Problems were prepared by ko_osaga, Konijntje, alex9801, etaehyun4, platinant. alex9801's rating is 2399, so he hopes to be called as "semi-red", not orange.

Special thanks to Konijntje, who hoped to upload this contest to gym (and actually worked on it), and MikeMirzayanov, who is the maintainer of this great community and system!

In the online mirror for Korean participants (including some famous red/nutella coders), nobody was able to solve all problems — I challenge you to beat them! :D

The contest is now finished! Congratulation to winners!

1. sunset
2. Reyna
3. Bedge
4. gamegame
5. the_art_of_war

Local open contest scoreboard

Tests, checkers, solutions (warning, over 400MB!)

Editorial

Problemsetters :

• Konijntje : P (Puyo Puyo), Y (Yut Nori)
• ko_osaga : Q (QueryreuQ), T (Touch The Sky), U (United States of Eurasia), V (Voronoi Diagram), W (Winter Olympic Games), Z (Zigzag)
• alex9801 : X (Xtreme NP-Hard Problem?!)
• platinant : R (Recipe)
• etaehyun4 : S (Segmentation)

Thanks to everyone who participated!

Update 2018.11.01: Rezwan.Arefin01 made a very cool webapp which contains identical problemset, but with more usability. Thank you very much! You can check it here.

Note: There was some updates in 2018.10.05. See here for changes!

Hello! APIO 2018 is near the end, and IOI 2018 is in this September. I hope you are preparing it well!

I'm here to present my OI problem checklist :

I used this to train myself in IOI 2015~2016, and to train Korean IOI 2017 Team (probably 2018 too). For long it was in the "beta" phase, but I think it's now good enough to share!

This problemset contains about 300 ~ 400 hard and interesting problems, with appropriate judge links given. (If there is problem in judging, maybe ojuz can help that..)

Google Docs Link

I hope this can help anyone preparing for future OIs, and a complete answer to the question "How to excel at IOI-style contests" :D

Hello!

According to the official site, BOI 2018 will be held in this weekend. Good luck to all participants!

I wonder if the organizers are planning any online contests. I actually found this Kattis site, but I think this is for official participants. Any ideas?