### prabowo's blog

By prabowo, history, 3 months ago,

Hello Codeforces community,

We are excited to invite you to TOKI KSN Open Contest 2021 — an online mirror contest for the Indonesia national olympiad in informatics. This national olympiad is one of the stages required for our students to qualify to represent Indonesia in the International Olympiad in Informatics (IOI). You may have seen our past open olympiads (2015, 2016, 2017, 2018, 2019, 2020) and you can check our past problems here.

The contest is similar to IOI: 2 competition days (+ 1 trial session), each consisting of 3 IOI-style (partial, subtasks) problems to be solved in 5 hours. The schedule is as follows:

Each contestant can select any 5-hour window within the time range to do the contest for each competition day. Each contestant may start the contest any time within the time range, by clicking the "start" button. The scoreboard will be hidden until the contest has ended.

All three contests are now available on TLX.
For more detailed information and rules, see our official website.

UPD The official contest has ended, thanks for your participation!

The result of the open contest can be found on our website.

You can upsolve the problems here.

The editorials can be found in the contest link or upsolve link.

If you'd like to give feedback to the KSN Open, you may submit a response in this form.

We thank everyone who are involved:

We hope we can conduct the open OI again, and see you next year!

• +133

By prabowo, history, 9 months ago,

Dear Codeforces community,

The Asia-Pacific Informatics Olympiad (APIO) 2021 is going to take place this month.

We invite everyone to participate in the APIO 2021 Open Contest. The open contest will have the same problemset as APIO 2021 and will be held using CMS. The open contest will be held between Monday, 24 May 2021 (05:00 UTC+0) and Wednesday, 26 May 2021 (05:00 UTC+0). The duration of the contest is 5 hours, and you can participate at any time within that window.

More details are available on https://apio2021.id/open.html. You can register and access the contest on https://open.apio2021.toki.id/.

We wish everyone to enjoy the open contest!

Thanks,
APIO 2021 Scientific Committee

UPD: The practice session is just over. The problems used are coming from Indonesia's past contests:

You may upsolve the problems there. Some of them have editorials that can be found from the left side of the page.

Feel free to join our virtual opening ceremony on Youtube today, and do not forget to register for the open contest!

UPD: The main competition has just ended, and the open contest has just started! We encourage APIO 2021 participants to NOT discuss the competition until the open contest has ended.

Please take note that not all countries are listed when you registered for a new user. This is because the initial list was taken from countries that participated in IOI before. If you would like more representation countries to be added to the list, please contact info.apio2021@toki.id

Good luck with the open contest!

UPD: The open contest has ended! You may now discuss about the competition tasks. Feel free to join the virtual closing ceremony and medal awarding streamed on Youtube soon. The open contest result will soon be published after the ceremony has ended.

UPD: APIO 2021 has officially ended!

• The result for the main competition can be found here.
• The result for the open contest can be found here.
• You can upsolve the problems here.
• The editorial can be found here.

Congratulations to all the medalists!

• +314

By prabowo, history, 13 months ago,

This is not to be confused with DSU on Tree (Sack).

### What can a Reachability Tree do?

Suppose you are given a weighted (connected) undirected graph of $N$ vertices and $M$ edges. Let's define an ordering of the edges, for example, the edges are ordered in the ascending/descending order of their weights. The reachability tree can help you with:

• Find the minimal/maximal weight of the edges when traversing from vertex $u$ to vertex $v$.
• Find the set of vertices that are reachable from a given vertex using the first $x$ edges, for some arbitrary $x$. You can store some information in this set of reachable vertices, such as the maximum value or the sum of values of all the reachable vertices.

### Constructing a Reachability Tree

The reachability tree is a rooted tree that consists of $N + M$ nodes. The tree will have $N$ leaves which represent the original vertices of the graph, and the rest of $M$ internal nodes represent the edges of the original graph.

To build this tree, we start with the $N$ leaves, then iterate the edges of the graph one by one starting from the smallest one to the largest one. When adding an edge that connects $u$ and $v$, add a new node to the tree, then attach the current root(s) of $u$ and $v$ in the trees as the children of the newly added node. Finding these roots can be done using DSU data structure.

You can think of the reachability tree as a DSU but with no path compression, so each subtree of some internal node in the reachability tree is the set of vertices in the connected component that contains the associated edge at the point when you were adding it.

When possible, you may omit the edges that connect two vertices from the same connected component, and the reachability tree you end up with will only have $2N - 1$ nodes.

### Example code

Following is a simplified version of reachability tree code

### Solving example problems

#### CF1416D – Graph and Queries

Given an undirected graph with $N$ vertices and $M$ edges. Each vertex has a value written on it. You have to process two types of queries:

1. Given a vertex $v$, among all vertices currently reachable from $v$, find the vertex with the largest value, output it, then replace its value with $0$.
2. Delete a given edge $e$.
Solution

#### APIO 2020 – Swapping Cities

Given an undirected weighted graph of $N$ vertices and $M$ edges. Given $Q$ queries, in each query, suppose there are two people at vertices $X$ and $Y$. These two people want to switch places ($X$ moves to $Y$, and $Y$ moves to $X$), but they must not meet each other at any point of time when traversing the graph. The cost of a switch is the maximum weight traversed by both people. Compute the minimum cost, or tell that they can't switch places without meeting each other. Queries have to be processed online.

Solution

#### IOI 2018 – Werewolf

Given an undirected graph with $N$ vertices and $M$ edges. Vertices are numbered from $0$ through $N - 1$. You are given $Q$ queries, each represented as four integers $S$, $E$, $L$, $R$ ($L \le S$ and $E \le R$). You want to know whether it is possible to travel from $S$ to $E$ satisfying: suppose you visit the vertices $V_0, V_1, \dots, V_p$ in this order, there exists $q$ such that $L \le V_0, V_1, \dots, V_q$ and $V_q, V_{q + 1}, \dots, V_p \le R$.

Solution

### More example problems

Thank you to the people who provided me with these example problems, here are what I have so far:

If you have more example problems or any suggestions, please let us know.

• +199

By prabowo, history, 16 months ago,

Hello Codeforces community,

Similar to last year, we are excited to invite you to TOKI KSN Open Contest 2020 -- an online mirror contest for Indonesia national olympiad in informatics. This national olympiad is one of the stages required for our students to qualify to represent Indonesia in the International Olympiad in Informatics (IOI).

The contest is similar to IOI: 2 competition days (+ 1 trial session), each consisting of 3 IOI-style (partial, subtasks) problems to be solved in 5 hours. The schedule is as follows:

Each contestant can select any 5-hour window within the time range to do the contest for each competition day. Each contestant may start the contest any time within the time range, by clicking the "start" button.

All three contests are now available on TLX. Please register in those contests. You may need to register for a TLX account if you do not have one.

For more detailed information and rules, see our official website.

UPD Thanks to everyone who participated! Our top 3:

1. rama_pang (564 points)
2. wiwitrifai (559 points)
3. Meijer (556 points)

The rest of the scores can be found here.

You can upsolve the problems here.

We thank everyone who are involved:

We hope we can conduct the open contest again, and see you next year!

• +130

By prabowo, history, 18 months ago,

Dear Codeforces community,

We are excited to invite you to a TOKI Special Open Contest!
In this contest, You will be given various unusual algorithmic tasks. We tried to make the contest have a similar nature to IPSC.

Key details:

We would like to thank hocky, fushar as organizers, and aguss787, ayaze as testers.

Please register for the contest, and we hope you will enjoy this contest!

UPD Contest is over! Our top 10 (the top 3 are actually tie):

And the first solver for each of the hard versions:

Editorial is available here.

You can upsolve the problems here.

Thank you for participating and see you in the next TOKI contest!

• +123

By prabowo, history, 20 months ago,

Dear Codeforces community,

We are excited to invite you to TOKI Regular Open Contest (TROC) #13!

Key details:

Scoring distribution:

• Div 2: 100 — 200 — 300 — 400 — 500
• Div 1: 100 — 200 — 300 — 500 — 500

We would like to thank hocky, fushar as organizers, rapel, jt3698 as testers, and Yoshiyuki as proofreader.

Please register to the contest, and we hope you will enjoy TROC #13!

UPD1: We postponed the contest by two hours so that it no longer clashes with AtCoder

UPD2: Contest is over! Our top 5:

Div 1:

Div 2:

Editorial is available here (English on page 8).

You can upsolve the problems here.

Thank you for participating and see you on the next contest!

• +147

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

Dear Codeforces community,

We're excited to invite you to TOKI Regular Open Contest (TROC) #12!

Key details:

The round uses two divisions system:

• Users with rating less than 2000 or not yet rated should participate in Div 2
• Users with rating at least 2000 should participate in Div 1

Scoring distribution:

• Div 2: 100 — 200 — 350 — 400 — 500
• Div 1: 100 — 200 — 300 — 400 — 400

Please register to the contest, and we hope you will enjoy TROC #12!

UPD1: Contest is over! Our top 5:

Div 1:

Div 2:

Editorial is available here (English on page 10).

You can upsolve the problems here.

We would like to thank hocky, fushar as organizers, and also ayaze, halohalo as testers, and Yoshiyuki as proofreader.

Thank you for participating and see you on the next contest!

• +87

By prabowo, history, 23 months ago,

Dear Codeforces community,

We're excited to invite you to TOKI Regular Open Contest (TROC) #11!

Key details:

The round uses two divisions system:

• Users with rating less than 2000 or not yet rated should participate in Div 2
• Users with rating at least 2000 should participate in Div 1

Scoring distribution:

• Div 2: 100 — 200 — 350 — 400 — 500 — 550
• Div 1: 100 — 200 — 300 — 350 — 450 — 500

Please register to the contest, and we hope you will enjoy TROC #11!

UPD1: Contest is over! Our Top 5:

Div 1:

Div 2:

Editorial is available here (English on page 8).

You can upsolve the problems here.

We would like to thank fushar, hocky as organizers, and also ayaze and Yehezkiel as testers, and Yoshiyuki as proofreader.

Thank you for participating and see you on the next contest!

• +83

By prabowo, history, 2 years ago,

Dear Codeforces community,

We're excited to invite you to TOKI Regular Open Contest (TROC) #10!

Key details:

• Rated
• Contest links: Div 1 and Div 2
• Time: 1 February 2020, 19:05 UTC+7
• Style: full feedback, with penalty (time taken to reach current score) + (4-minute penalty per wrong submission)
• Scoring: You get the score assigned to the problem when you fully solve it
• Writers: hocky Pa.Nic phillotunru1
• Duration: 2 hours
• Problems: 6 for every division
• Allowed languages: C, C++11, Pascal, Java, Python 3

The round uses two divisions system:

• Users with rating less than 2000 or not yet rated should participate in Div 2
• Users with rating at least 2000 should participate in Div 1

Scoring distribution:

• Div 2: 100 — 200 — 300 — 400 — 500 — 500
• Div 1: 100 — 200 — 300 — 300 — 450 — 500

Please register to the contest, and we hope you will enjoy TROC #10!

UPD1: Contest is over! Our Top 5:

Div 1:

1. antontrygubO_o
2. Egor
3. wiwitrifai
4. Yahor Dubovik
5. Pyqe

Div 2:

Editorial is available here (English on page 5).

You can upsolve the problems here.

We would like to thank fushar as technical committee, and also ayaze and IgoRamli as testers.

Thank you for participating and see you on the next contest!

• +71

By prabowo, 2 years ago,

Dear Codeforces community,

We're excited to invite you to TOKI Regular Open Contest (TROC) #9!

Key details:

• Rated
• Contest links: Div 1 and Div 2
• Time: 23 November 2019, 19:35 UTC+7
• Style: full feedback, 8-minute penalty per wrong submission
• Scoring: You get the score assigned to the problem when you fully solve it
• Writers: AMnu
• Duration: 2 hours
• Problems: 5 for every division
• Allowed languages: C, C++11, Pascal, Java, Python 3

The round uses two divisions system:

• Users with rating less than 2000 or not yet rated should participate in Div 2
• Users with rating at least 2000 should participate in Div 1

Please register to the contest, and we hope you will enjoy TROC #9!

UPD1: Scoring distribution:

• Div 2: 100 — 200 — 300 — 400 — 500
• Div 1: 100 — 200 — 300 — 450 — 500

UPD2: Contest is over! Our Top 5:

Div 1:

Div 2:

Editorial is available here (English on page 5).

You can upsolve the problems here.

We would like to thank hocky and fushar as contest coordinators, and also ayaze and Zoroark as testers.

Thank you for participating and see you on the next contest!

• +11

By prabowo, 2 years ago,

Dear Codeforces community,

We're excited to invite you to TOKI Regular Open Contest (TROC) #8!

Key details:

• Rated
• Contest links: Div 1 and Div 2
• Time: 28 September 2019, 19:05 UTC+7
• Style: full feedback, 8-minute penalty per wrong submission
• Scoring: You get the score assigned to the problem when you fully solve it
• Writers: AMnu, faustaadp, halohalo, ..vince
• Duration: 2 hours
• Problems: 5 for every division
• Allowed languages: C, C++11, Pascal, Java, Python 3

The round uses two divisions system:

• Users with rating less than 2000 or not yet rated should participate in Div 2
• Users with rating at least 2000 should participate in Div 1

Please register to the contest, and we hope you will enjoy TROC #8!

UPD1: Scoring distribution:

• Div 2: 100 — 200 — 400 — 500 — 750
• Div 1: 150 — 200 — 400 — 650 — 850

UPD2: Contest is over! Our Top 5:

Div 1:

Div 2:

1. arknave
2. Son
3. Yahor Dubovik
4. robinyu
5. meneketehe

Editorial is available here.

You can upsolve the problems here.

Thank you for participating and see you on the next contest!

• +38

By prabowo, history, 2 years ago,

Dear Codeforces community,

We're excited to invite you to TOKI Regular Open Contest (TROC) #7!

Key details:

• Rated
• Contest links: Div 1 and Div 2
• Time: 1 September 2019, 13:05 UTC+7
• Style: full feedback, 8-minute penalty per wrong submission
• Scoring: You get the score assigned to the problem when you fully solve it
• Writers: AMnu, YogayoG
• Duration: 2 hours
• Problems: 5 for every division
• Allowed languages: C, C++11, Pascal, Java, Python 3

This is the first TROC round that uses two divisions system:

• Users with rating less than 2000 or not yet rated should participate in Div 2
• Users with rating at least 2000 should participate in Div 1

Please register to the contest, and we hope you will enjoy TROC #7!

UPD1: The contest is rescheduled to 1 September 2019, 13:05 UTC+7

UPD2: Scoring distribution:

• Div 2: 100 — 200 — 300 — 550 — 700
• Div 1: 200 — 400 — 500 — 850 — 900

UPD3: Contest is over! Our Top 5:

Div 1:

Div 2:

1. rapel
2. Lucina
3. ollpu
4. jessenanwar
5. vioalbert

Editorial will be available here (currently English is not fully available yet).

You can upsolve the problems here.

Thank you for participating and see you on the next contest!