Top Recent Blog Posts
By DeMen100ns, history, 9 days ago,
Before the round starts

1713A - Traveling Salesman Problem

Hint 1
Hint 2
Tutorial
Solution
Feedback

1713B - Optimal Reduction

Hint 1
Hint 2
Hint 3
Tutorial
Solution
Feedback

1713C - Build Permutation

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Solution
Feedback

1713D - Tournament Coundown

Hint 1
Hint 2
Hint 3
Tutorial
Solution
Feedback

1713E - Cross Swapping

Hint 1
Hint 2
Hint 3
Tutorial
Solution
Feedback

1713F - Lost Array

Hint 0
Hint 1
Hint 2
Hint 3
Tutorial
Solution
Feedback

• +255

By Makha, history, 41 hour(s) ago,

The first day of IOI is going to start at 10th of August and I made this blog.

• +36

By Valar.Morghulis, history, 7 hours ago,

# Background

Maybe you have watched the classic Kung Fu Panda movie. Well, today we introduce the Competitive Programming version! Let me present to you the cast...

## jiangly (based off of Master Po)

The hero of our story, jiangly is the prophesied Dragon Warrior, and the bright young future of competitive programming. He has risen to the highest levels of this ancient activity, and has faced many obstacles and enemies on his way.

## Errichto (based off of Master Shifu)

The famous coach and youtuber, Errichto represents a father figure to many young and energetic competitive programmers. Many have learned the ancient ways from his Youtube channel.

## MikeMirzayanov (based off of Mr. Ping, Po's dad)

Mr. Mike runs the establishment known as "Codeforces". Many elite competitive programmers go here to train, hone their craft, or simply to hang out and read blog posts like this.

## Robert Tarjan (based off of Grand Master Oogway)

The esteemed elder of competitive programming, and one of the greatest pure computer scientists of all time. Many of the finest masters literally worship at his shrine (the Linear Offline LCA Temple), and hold sacred his famous analysis of Union Find's inverse ackermann time complexity.

## tourist (based off of Master Tigress)

The leader of the elite group of competitive programmers called the "Furious Five", tourist is famous for his legendary speed, extreme skill, and no-nonsense approach to problem solving. He is widely considered the greatest of them all.

## Benq (based off of Master Mantis)

Benq is a famous master, who uses his sharp mandibles to tear apart 3500 level math problems as if they were nothing!

## Um_nik (based off of Tai Lung)

The villain of our story, Umnik is known for his deep knowledge of data structures written in blackened grimoires of ancient evil! His minions at the Umnik Training Center are deadly foes to the protagonists of our story.

## YOU AND ME (based off of the rabbits)

That's right, WE ALL have a role to play in this epic story! Actaully, your role is to stand there, look cute, and generate revenue for the movie franchise.

• +107

By awoo, history, 3 days ago, translation,

1716A - 2-3 Moves

Idea: vovuh

Tutorial
Solution (vovuh)

1716B - Permutation Chain

Idea: BledDest

Tutorial
Solution (awoo)

1716C - Robot in a Hallway

Idea: BledDest

Tutorial
Solution (awoo)

1716D - Chip Move

Idea: BledDest

Tutorial
Solution (Neon)

1716E - Swap and Maximum Block

Idea: BledDest

Tutorial
Solution (BledDest)

1716F - Bags with Balls

Idea: BledDest

Tutorial
Solution (BledDest)

• +140

By __BaD_mAn__, history, 46 hours ago,

Today I participated in the coding competition Codegoda hosted by Agoda. I'm not going to talk about their weird rules and coding environment. I just want to share some of my experiences regarding the problemset. In a word, worst experience ever. I just want to mention some things here that seem annoying to me and make me feel it was a waste of time participating in the contest.

Most of the problems require no more than 30 seconds of thinking to get the idea. The problemset was not standard. Expected more quality problems in such a big competition. In the problem of probability, it was mentioned to print up to 5 digits after the decimal point. What does it mean actually? Is it exactly 5 digits? Or at most 5 digits? If it is, then printing more than 5 digits should give wrong answer, right? I printed 10 digits and it passed 3 tests and gave wrong in the 4-th test case. I was thinking my idea/solution is wrong. Then wrote the bruteforce solution and wasted almost 1 hour finding out the actual problem. Printing 5 digits after the decimal point got passed all the public tests. Why it didn't give wrong answer verdict in the first 3 cases? Isn't it weird? They could clearly mention that we have to print exactly 5 digits.

The problem of checking whether two companies are from the same group or not is a very common problem of DSU/DFS. Why such a common well-known problem in such a contest? Are they taking speed test?

The problem of digit mapping was so annoying as we cannot copy/paste into the contest editor. It requires writing some similar types of lines multiple times. All you have to type so fast.

The problem of finding the best hotel within a budget range had a confusing statement. It was mentioned nowhere what should be printed if there is no hotel in the budget range given in each query. If it is guaranteed that at least one hotel exists in the budget range, then why it was not mentioned in the statement? Is there any issue in the dataset of this problem or any corner case? My fresh solution didn't pass after 3rd test -_-

I tried these 4 problems and found none of them interesting. Didn't try the other two problems. The problems are so poor compared to their magnificent advertisement. Overall it feels like a waste of time.

• +124

By jerefigo, history, 2 days ago,

We, the Argentine team (jignacioc, lucastarche, jerefigo and uliseslp) just arrived at the Rich Jogja hotel, after two days of international travel.

• +172

By kostka, 7 hours ago,

... will take place in Bolivia! This will be the second time that IOI will be hosted in South America, after IOI 1993 in Argentina!

• +79

By adamant, history, 39 hours ago,

Hi everyone!

There is a well-known result about bipartite graphs which is formulated as follows:

In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.

Knowing it you can easily find the size of a minimum vertex cover in a given bipartite graph. But what about actually recovering such cover? Well... There is an algorithm to it, but it's lengthy and not very motivated, so I constantly forget its details. However, there is a simple alternative, which is easily reproduced from scratch, even if you forget specific details.

Besides, there is another well-known result which is formulated as follows:

A bipartite graph has a perfect matching if and only if every subset $\alpha$ of one part has a neighborhood $\beta$ in the other part such that $|\beta| \geq |\alpha|$.

This result can be proven with a similar approach. It is likely known to those familiar with the topic, but still might be of interest to someone.

• +108

By Ra16bit, history, 3 days ago,

Google Code Jam 2022 Virtual World Finals will take place today. They have published the list of finalists recently. For some reason SpyCheese and duality are not in the list. And there are 26 finalists this year (not 25), here they are:

GCJ Handle CF Handle Country CF Rating Finals before Best place before
Gennady.Korotkevich tourist Belarus 3771 8 Seven times GCJ World Champion (2014-2020)
Benq Benq United States 3513 2 5th @ GCJ 2021
Um_nik Um_nik Ukraine 3539 1 8th @ GCJ 2021
simonlindholm simonlindholm Sweden 2739 3 7th @ GCJ 2017
KalininN KAN Russia 3014 3 7th @ GCJ 2020
jiangly jiangly China 3688 0
ksun48 ksun48 Canada 3452 2 2nd @ GCJ 2020
molamola molamola. South Korea 3082 2 11th @ GCJ 2019
xll114514 MiracleFaFa China 3466 2 6th @ GCJ 2017
yutaka1999 yutaka1999 Japan 3190 2 10th @ GCJ 2020
CauchySheep slime China 3498 1 4th @ GCJ 2021
ImBarD Vercingetorix Russia 2929 0
lumibons lumibons Germany 2976 0
ACRushTC ACRush China 3047 7 Two times GCJ World Champion (2008, 2009)
qwerty787788 qwerty787788 Ukraine 2735 2 12th @ GCJ 2019
mhq mhq Belarus 2967 0
Snuke snuke Japan 3251 1 22nd @ GCJ 2017
ecnerwala ecnerwala United States 3318 3 3rd @ GCJ 2019 and 2020
dacin21 dacin21 Switzerland 2682 3 6th @ GCJ 2019
BigBag BigBag Ukraine 2765 0
Golovanov399 Golovanov399 Russia 2973 1 23rd @ GCJ 2018
NyaanNyaan Nyaan Japan 2720 0
zemen zemen Russia 2945 2 2nd @ GCJ 2017
mnbvmar mnbvmar Poland 3166 2 4th @ GCJ 2019

Best of luck to all the finalists!

• +257

By thanhchauns2, history, 2 hours ago,

Firstly, thanks everyone for participating in our contests! I am delightful with the feedbacks, I can't ever imagine it would be that successful.

This blog is written to discuss about problem 1713D - Tournament Countdown. Specifically, the $2^{n - 1}$ solution.

This solution is NOT correct, we tried to get rid of it, but unluckily the system tests are still not strong enough to eliminate all of its variants.

Take an example:

0 1 0 3 0 2 0 1

This is the output if we only compare the $1^{st}$ with the $3^{rd}$:

0 1 0 3 0 2 0 1

1 3 2 1

1 2

2

We eliminated the participant with most wins. So this attemp is wrong. Why? Because the two participants left is probably not the two with most wins among four participants. That's why there is the "almost every" clause in hint 1, as I worried that there are still a few wrong solutions that would pass system test (and they did).

Unfortunately, the system test is not that strong, I am so sorry for that. By the way if anyone has a solid proof, I would love to hear your opinion.

Yes, hint 1 is not a typo.

But yes, the solution in tutorial is not the only approach, can you solve it by BINARY SEARCH?