Korea Olympiad of Informatics 2026 Competition

Recently, the 2026 Korea Olympiad of Informatics took place. Those who perform well in the second round of this competition have a chance at becoming a national representative in international competitions, including the Asia-Pacific Informatics Olympiad and the International Olympiad of Informatics.

Last year, I was able to receive gold awards for both the first and second round of the contest, becoming a trainee of sorts. I had to attend many classes for a year and took the selection “exam” in January and February.

Some students move onto a higher level, in which they receive more advanced training and are forever a national trainee/representative (until they start college or become an adult). However, as my results were not as great compared to others (I was the youngest age that students can participate in, and many were much older than me). So, to be selected again, I took part in the 2026 contest.

Round 1

Round 1 consists of two parts. The first are mathematical questions, with some related to algorithms. The second was purely competitive programming problems, featuring data structures and algorithms.

I, sadly, did not perform well on both parts of the round. For the first part, my score was quite lower than I anticipated, but I had thought this may happen. However, I knew that I had to receive as many points as possible during the second part, possibly having to solve all three problems given.

This, however, did not happen at all. I easily solved the first two problems given, but I was completely stuck on the third. I had multiple broad ideas that may work (which were on the right track looking at the intended solution given), but they didn’t seem to go anywhere. Looking back, I should have tried to solve the subtasks given instead of the whole problem, giving me at least a few points. Others who solved the problem mentioned afterward that it was well-known.

Either way, Round 1 did not end well, but I still received a gold award (to my surprise).

Round 2

Looking at the previous round, it may seem all hope is lost. I performed much worse than I should have, looking at the accomplishments I’ve achieved and the progress made.

HOWEVER, Round 2 was completely different.

During the first thirty minutes, I was able to knock out the first two problems (out of a total of four) quite easily, with implementing the actual solutions taking up the most time. This is actual a bit slower than I would have hoped, as I needed time for the last two.

The third problem made me anxious, thinking there was no way I could solve it. After fiddling around with the graphs, I finally realized the complete solution. In less than 2 hours, I implemented and KOed that problem as well. At this point, I sort of knew I would get a gold award at the least, but that first place was calling my name.

When peaking at the last problem, OH BOY. I had no idea what the solution could remotely be. So, I tried to solve the subtasks given to receive as many point as possible. While solving a couple of them, I realized that the problem could actually be solved using the solutions to some of the subtasks! After 20-30 minutes of coding, I had finally and successfully solved all problems!

It wasn’t until today (as of writing this, July 21st) that the results were posted. My last submission time was 3 hours and 52 minutes (approximately) for a 4 hour and 30 minutes contest. Looking at past results, it was unlikely for me to get top two, especially because I heard multiple people had solved all problems, and many strong performers in my age group are very quick. To my surprise, I indeed WAS FIRST PLACE!

In light of this result, I shall be posting the problems and my solutions to Round 2.

Problem 1: Stacking Dice (주사위 탑 쌓기)

Link to the problem: https://jungol.co.kr/problem/21026

Short Translation

You are given some amount of dice, N. Each dice has sides numbered 1 to 6. Each opposing sides have the sum of 7 (so, on every dice, the opposite side of 1 is 6). You can create a tower of dice when the sides where the dice touch are the same. In other words, as you place a dice on top of a tower, the bottom side of this new dice must equal the top side of the top dice on the tower. Note, a tower can be created with any dice, so the first dice of the tower can be placed in any way. As input, each dice is given a top side. This means that when placing a dice on a tower, it’s top side must be equal to the top side given. You must figure out the minimum number of towers you can create when every dice that you have is part of some tower.

Solution

When creating a tower, because of the constraint given, the top sides of the dice must be alternating, and the two different top sides must have the sum of 7. This is because when you lay a specifc dice with a specific top side (this would be a number, which we will call x), the next dice stacked on top must have it’s bottom side as the same number. It’s top side must be 7 - x, because the sum of opposing sides are 7. When you stack one more dice, it’s bottom side must be 7 - x, while it’s top side is 7 - (7 - x), which can be simplified to x. Therefore, the contraints for the problem show that there must only be two alternatig top sides: x and (7 - x).

Since you know how many dice have x as their top side, you can figure out how many towers you need for x and (7 - x). Let’s assume the number of dice with x at the top is larger than or equal to the number of dice with (7 - x) at the top (if its the opposite, the same can be done, just switching the numbers). We can say that the variable y represents the number of dice with x at the top, while the variable z represents the number of dice with (7 - x) at the top. Then, there are two cases to thing about:

1. If y is equal to or larger than z by a maximum of one, we only need one tower. This can be constructed by using one dice with x at the bottom and continue alternating.

2. If y is larger than z by more than one, we need (y - z) towers. Our first tower would have used all of the dice with (7 - x). The leftover dice with x at the top will be (y - z - 1) if we constructed the tower like we did in the first case. Now, we have no other choice but to create new towers with only one dice. Therefore, we would have (y - z - 1 + 1) or (y - z) towers.

With these two cases, we can check each pair and find the corresponding answer by adding all answers to each pair.

Problem 2: Distributing Snacks (간식 분배)

Link to the problem: https://jungol.co.kr/problem/21027

Short Translation

There are snacks numbered from 1 to N. There are also exactly N students. Each student has a set of snacks that they like, which will be given as input. All snacks are in a singular room, and, in some order, each student will go into the room and take all of the snacks they like. If previous students took all the snacks that a student likes, then that students leaves the room with nothing (quite sad). Your mission is simple: order the students in some way to make sure every student takes exactly ONE snack. No more, no less. If there is no way to fulfill this mission, you must say so as well.

Solution

We can say that the following is true: every time a student goes into the room, they must have only one snack they like out of the snacks left in the room. This means that the first few students to go into the room must have only one snack they like (not just in the room, out of all N snacks). Once those students are completed, we can remove these snacks from the rest of the student’s lists (since they can’t take that snack anymore). Now, those with only one snack they like out of the snacks in the room will be able to have their turn.

If there is an answer, then the above solution will always work. This is because at any point in time, there will be students with only one snack they like. They MUST take that snack with them. Therefore, they will go into the room, and others cannot take that snack anymore.

If there is any sort of collision, where a student does not have any snack to take, or there is no student with only one snack the link in the room, there is no answer. If we look at the first case, if a student takes a specific snack, the student who originally took that snack must take another snack and so on. This would continue until we hit a student with exactly one snack the like out of all snacks. They can’t change their answer, so therefore, this student cannot either. We can prove that there is no way for this student to take any snack. For the second case, if this does happen, there is no way for us to edit the past answers so that we can continue this process (which is the same explanation as the first case).

Therefore, this greedy solution works and is the correct answer.

Problem 3: Game (게임)

Link to the problem: https://jungol.co.kr/problem/21028

Short Translation

Alice and Bob are playing a game (no surprise there). There are N towns and M roads. Each road connects two different towns, and there may be multiple roads between two towns. There may also be two towns you could never travel to through these roads. Through some of these towns, Alice can escape and win the game. Bob, of course, is trying to stop this. The game goes like this:

1. Alice is given an integer K and the starting town.

2. In each round, Alice must choose K roads that connect the current town Alice is in and any other town. If there are not enough roads, she must choose all of them. If there are multiple roads from town A to town B, she can choose any number of them.

3. Bob will choose any of the roads that Alice gives for Alice to travel to. Once Bob chooses, Alice will travel through that road.

4. This continues until Alice reaches a town she can escape through. If she can reach at least one, she wins. If she can never reach one, Bob wins. Note: if Alice starts at an escaping town, she wins automatically.

Alice and Bob play many times, with both players trying to win. You want to figure out whether or not Alice can win on a certain game given K and the starting town. Note: you are solving for multiple games played by Alice and Bob.

Solution

For this problem, you need to make a couple observations:

1. Let’s say that there is a value maxK for every town. This value corresponds to the largest K value where Alice can win when she starts at a specific town. If Alice can win when K is equal to X, then she can also win whenever K is less than X. This works because you can choose the same edges that you would choose if K is larger (but less than or equal to maxK) and removing some of them. This still will allow you to win, since Bob has to choose one of the edges, and each edge will let you win for all K <= maxK.

2. The maxK value for an escaping town is infinity, since whatever the K value is, Alice will win. Excluding those town, for every town’s maxK value, it must never be larger than the maxK value of its neighbors (neighbor means a town connected to another town through one or more roads). If we say that such a case exists, and K is equal to maxK, Alice still has to go to one of the neighbors. However, we know that every neighbor’s maxK value is smaller than K, meaning none of them can actually end at an escaping town (knowing that all players work optimally). Therefore, this maxK value can never be larger than all of its neighbors’ maxK values.

3. The maxK value of a town is equal to the largest K where Alice can win. This value is equal to the largest K where there are at least K edges where the opposing towns connected to the current town have a maxK value bigger than or equal to K. This is the only way, as if there is just one edge that connects to a town with a maxK value less than K, Bob will choose that edge. Then, it’s game over for Alice.

Knowing this, we solve the problem using Breadth-First Search (BFS) based on the maxK values. If we start at the towns with the largest maxK values, we know that every town with a higher maxK value has already been visited, and other towns cannot become larger than the current town’s maxK value (due to the observations above).

Now, the problem is updating other towns’ maxK values based on the towns visited. We will have two arrays for each town. The first array will store all the current maxK values we have for this town’s neighbors. This will already be sorted in non-increasing order, since we order the nodes based on maxK value. The second array will store a Segment Tree, where it stores the values of the number of edges connected the current town and another neighbor town.

How this works is that when a town spots a neighbor town with a lower maxK value than it, it will push to both arrays it’s maxK value and the number of edges the pair shares respectively. Then, we will update the value of the neighbor node by Binary Searching for the correct K. For a specific mid point, we check whether or not it could be a valid maxK value. Using the segment tree, we can query the range from the smallest maxK value of it’s neighbors larger than or equal to the midpoint to the largest maxK value. This will calculate the number of edges where the opposing side town’s maxK value is bigger than or equal to the mid point value. If this number is less than the mid point value, we know that this value cannot be the maxK value and can continue searching for values less than this mid point. Otherwise, this value can be the maxK value and can continue searching for values larger than or equal to this mid point.

Now, after the BFS, all town’s have a complete maxK value. For every game instance given (with K and the starting town), we can easily calculate whether or not Alice wins depending whether K is less than, equal to or larger than the maxK value of the starting town.

Problem 4: Sequence Operations (수열 연산)

Link to the problem: https://jungol.co.kr/problem/21029

Short Translation

You are given a sequence A = [A₁, A₂, …, A_N] of length N and a sequence B = [B₁, B₂, …, B_M] of length M. M is always less than or equal to N. Both sequences have unique values (meaning there is no same value in one sequence) and have values from 1 to N. A is a permutation (as it is exactly length N), while B may or may not be one. There are two different operations you can perform on a sequence:

1. Swapping

   You have a sequence X = [X₁, X₂, …, X_K] of length K.

   You can choose an index i (1 <= i < K) where X_i < X_i+1 and swap X_i and X_i+1 values.

2. Combining

   You have a sequence X = [X₁, X₂, …, X_K] of length K.

   You can choose an index i (1 <= i < K), remove values X_i and X_i+1 and insert min(X_i, X_i+1) (the minimum of the two values) value in their place.

   This operation decreases the length of the sequence by 1.

You must perform these operations on sequence A to transform it into sequence B in less than N² operations. If this cannot be done, you must also say so.

Solution

This problem has some cases to think about:

1. If the value 1 does not exist in the sequence B, there is no sequence of operations that will work. We know that 1 exists in sequence A, and we cannot remove this value in the sequence. Operation 2 removes the larger value between adjacent values, but 1 could never be the larger value.

2. If you never have to remove a value (this means that N = M, and you must never perform operation 2), you can greedily solve this problem. In order of the values in B, you can swap values to move that value in A to the correct index in B. If at any point you cannot swap two values, it will never work. Whatever you do, you won’t be able to swap these two values. What if you don’t have to swap these two values? This will never happen, due to the fact that when using the above solution, values in the front of B will be ordered first, meaning if a swap occurs, it is required

Knowing these two, we just need to first remove the values in A but not in B. There are only two ways to do this:

1. In A, let’s say the value in index i needs to be removed. If there exists an index j where i < j and A_i > A_j, you will be able to remove this value. After finding the smallest j that works, we know that all the other indexes x where i < x < j have a larger value than A_i. We can perform operation 1 until the values A_i and A_j are adjacent. Then, as A_j is smaller than A_i, you can use operation 2 and remove A_i.

2. You can move another value in index j where i > j and A_i > A_j. When moving A_j to be adjacent to A_i, we need to make sure that when swapping two values, it must stay within the constraints of operation 1. Additionally, if we swap values A_x and A_x+1, the A_x+1 value must appear BEFORE the A_x value in B. This is due to the fact that if you swap these two values, in the future, you’ll have to swap them back. The constraints of operation 1 does not allow this.

Through these two different ways, you can greedily try both ways one by one to remove all values. From what I have calculated, it doesn’t necessarily matter which one to start with, but for simplicity, we shall try to second option first.

For all values in A that must not be removed (values that are also in B), you can swap values as far as you can before having to stop. This occurs when they encounter a smaller value than themselves, or this new value is infront of the original value in B (we explained above why we cannot swap these two values in this case). It is also crucial to start this process for N to 1 (largest to smallest). Therefore, we move values N, N-1, … and 1 in that order.

One problem we could have is when we could have moved more, but due to other values, we stop at a certain point without removing as many values as we could have. If we complete the process above in the order given, this will either never happen, or it does not matter.

If some value encounters a smaller value than itself, we know that it could never pass that smaller value (due to the constraints of operation 1). Even if this smaller value continues moving to the right in future operations, this current value will have no use, as the smaller value will always remove the values the current value could. So, even though the current value can go further if the smaller value moved first, this doesn’t matter at all.

In the other case, even if some value encounters a larger value than itself and cannot swap (because of the way B is ordered), we know that this larger value had moved first and went as far as it could before stopping (or there was no point in going any further). Therefore, this value doesn’t have to go any further as well.

There are more cases to think about, like adding the above two cases together. However, they can never occur or produce any problems.

Now, for the leftover values to be removed, we can check if there are any smaller values behind them. If there are none for any value, we can say there is no way to transform A into B. The proof will be left as a challenge to the reader. Otherwise, we can remove these values with the operations and leave the rest of the values in the order they were in.

Now, we have removed all non-existing values in B. If you can recall, we solved the case when the length of A and B are the same (and all values in A occur in B). Using that solution, we can transform A into B (or prove that it cannot happen).

Adding all of these processes together solves for the whole problem!

Reflection

Round 2, in my opinion, had some great problems with different intentions, specifically for problem 3 and 4. For problem 3, you had to create observations (or known truths) based on a simple idea (maxK). Problem 4 had to do with case work, and what to do in some certain case. Then, you could add all of them together into a complete solution.

Even though this is a biased opinion (since I won the whole round), this year’s problems were absolutely fun to solve, having to figure out the solution in different ways. Hopefully, the future will provide us with even more difficult problems!