Hello Codeforces!

We will host TOKI Open 2024. This is one of the tests to select the Indonesian team for IOI 2024. Everyone is welcome to take part in this contest.

The contest will be held in two days:

• Day 1: Saturday, 25 May 2024, 09:00 (UTC+7) — Sunday, 26 May 2024, 07:00 (UTC+7)
• Day 2: Sunday, 26 May 2024, 09:00 (UTC+7) — Monday, 27 May 2024, 07:00 (UTC+7)

Some key details of the contest:

• Duration: 5 hours
• Style: IOI
• Allowed language: C++17
• You can start at any time within the 22-hour window.

All contest days are hosted on TLX. Please register for an account if you do not have one. More details on the contest rules are available on the contest page.

The results will be published within one day after each contest day has ended.

We hope that you will enjoy the contest. Good luck and have fun!

UPD. The day 1 contest has ended. We have published both the scoreboard and the editorial, which can be found on the contest page. The day 2 contest window will start soon.

UPD2. All contest days have ended. Thank you for your participation, we hope you enjoyed the problems!

You can upsolve the problems here. The editorial can be found on either the contest page or the upsolve link. The combined scoreboard for both days including the official contestants will be published soon.

We thank everyone who is involved:

• fushar for the TLX platform.
• prabowo Pyqe rama_pang nightlight as Scientific Committee.
• ayaze Zanite Morphymorphymorphy Owmicron rfpermen joelgun14 ArvinCiu as testers.
• Pyqe yz_ wiwitrifai as problem authors.

We hope that we can host TOKI Open again in the future!

UPD3. You can find the complete combined scoreboard of both days here.

Hello Codeforces!

We are going to hold The 2023 ICPC Asia Jakarta Regional Contest.

We invite you to join the online mirror contest 2023-2024 ICPC, Asia Jakarta Regional Contest (Online Mirror, Unrated, ICPC Rules, Teams Preferred) on Codeforces. It will be held on Dec/03/2023 07:35 (Moscow time) and will last for 5 hours.

The mirror will be held using ICPC-style scoring with 10 to 13 problems. The problem statements will only be available in English. We encourage participating as a team using only one computer for coding (as in ICPC contests). The mirror will be unrated.

Some useful links:

• The 2023 ICPC Asia Jakarta homepage
• The regional information in ICPC Global
• The onsite scoreboard

We hope that you will enjoy the contest. Good luck and have fun!

UPD. The mirror has started! You can also see the public scoreboard of the onsite contest (started 90 minutes earlier) from the provided link.

UPD2. The mirror has ended! You can find the editorial here. The onsite scoreboard will be unfrozen after the closing ceremony. Thank you for participating and we hope that you enjoyed the problemset!

Given the escalating situation that is happening near Sharm, I would like to know what the universities/teams for the upcoming ICPC World Finals are thinking about their trips.

Will you:

Travel as planned
Shorten your itinerary
Cancel your trip

Or are there some other measures that your university/team is preparing? Is there any penalty for not coming to this specific WF, and are there any updates from the ICPC itself?

I can't open this problem: https://codeforces.me/problemset/problem/1641/E

Upon opening, it gave this message: Can't read or parse problem descriptor

Maybe there is a problem with the Polygon?

IOI 2022 Day 1 has just ended.

• The tasks for IOI 2022 have been published on the IOI 2022 website.
• Final ranking can be seen from https://ranking.ioi2022.id/
• Live streaming (containing tasks discussion) for day 1 and day 2 from the official IOI 2022 YouTube channel.
• Tasks will soon be available on Codeforces IOI archive (https://ioi.contest.codeforces.com/)
  • Virtual 5 hours with CMS page by ojuz for day 1 and day 2.

UPD. Day 2 has ended.

UPD. The IOI 2022 has officially ended, the editorial is ready on the task page as well.
Thanks to the authors and organizers. Congratulation to all participants!

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:

• Day 0: 7 November 2021 09:00 — 8 November 2021 01:30 UTC (trial session)
• Day 1: 8 November 2021 06:30 — 9 November 2021 01:30 UTC
• Day 2: 9 November 2021 06:30 — 10 November 2021 01:30 UTC

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.

See you on the leaderboard!

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:

• Scientific Committee: prabowo, Yoshiyuki, AMnu, steven.novaryo, vioalbert
• Technical Committee: fushar, faishol27, Samuel
• Authors: fushar, prabowo, AMnu, steven.novaryo, Pyqe
• Testers: rama_pang, hocky, jfcjaya

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

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:

• Problem cards: https://tlx.toki.id/problems/tsoc-cms/B
• Problem defence: https://tlx.toki.id/problems/ksn-2020/1A
• Problem hoax: https://tlx.toki.id/problems/osn-2019/2C

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 [email protected]

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!

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

int getRoot(int u) {
  if (u == dsu[u]) return u;
  return dsu[u] = getRoot(dsu[u]);
}

void addEdge(int u, int v) {
  u = getRoot(u); v = getRoot(v);

  dsu[n] = n;
  dsu[u] = dsu[v] = n;

  adj[n].push_back(u);
  if (u != v) adj[n].push_back(v);

  ++n;
}

void build() {
  for (int i = 0; i < n; ++i) dsu[i] = i;
  for (int i = 0; i < m; ++i) addEdge(U[i], V[i]);
}

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$$$.

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.

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$$$.

More example problems

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

• Codechef CHEFCOMP – Chefina and Strange Tree
• Codechef TULIPS – Tiptoe through the tulips
• AtCoder CODE FESTIVAL 2017 Tournament Round 3 – Black Cats Deployment
• USACO 2014 January Contest Gold – Ski Course Rating

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

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:

• Day 0: 12 October 2020 09:00 — 21:30 UTC (trial session)
• Day 1: 13 October 2020 06:30 — 21:30 UTC
• Day 2: 14 October 2020 06:30 — 21:30 UTC

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.

See you on the leaderboard!

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:

• Yoshiyuki, prabowo, AMnu, hocky, rfpermen, wijayareynaldo as Scientific Committee
• fushar, nathanchrs, aguss787 as Technical Committee
• AMnu, rfpermen, prabowo, AVM.Martin, Yoshiyuki as problem authors
• malfple, Klungs as testers
• ya_ for helping me with this open contest

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

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:

• Unrated
• Contest link: TOKI Special Open Contest: Contest of Salty Tasks
• Time: 1st August 2020, 12.05 UTC
• Writers: afaji321 athin
• Problems: 6, each has an easy and hard version
• Duration: 2 hours

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):

1. Golovanov399
2. nuip
3. Endagorion
4. pwild
5. rfpermen
6. Bedge
7. Itst
8. dorijanlendvaj
9. Pa.Nic
10. Pyqe

And the first solver for each of the hard versions:

• N: Bedge
• O: Bedge
• P: Sadrian
• Q: Bedge
• R: Golovanov399
• S: nuip

Editorial is available here.

You can upsolve the problems here.

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

Dear Codeforces community,

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

Key details:

• Contest links: Div 1 (rating ≥ 2000) and Div 2 (rating ≤ 1999)
• Time: 14 June 2020, 21:05 UTC+7
• Writers: yz_ rama_pang steven.novaryo
• Duration: 2 hours
• Problems: 5 for every division

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:

1. Benq
2. wiwitrifai
3. KrK
4. Egor
5. hitonanode

Div 2:

1. neal
2. tourist
3. zscoder
4. maroonrk
5. risujiroh

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!

Dear Codeforces community,

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

Key details:

• Rated
• Contest links: Div 1 and Div 2
• Time: 2 May 2020, 21: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: Berted Pyqe yz_ Pa.Nic steven.novaryo rama_pang vioalbert
• 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

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:

1. Benq
2. antontrygubO_o
3. malfple
4. jonathanirvings
5. buko

Div 2:

1. nuip
2. MrBrionix
3. kzvd4729
4. hitonanode
5. Littleboy123

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!

Dear Codeforces community,

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

Key details:

• Rated
• Contest links: Div 1 and Div 2
• Time: 1 March 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: Pyqe Berted nabilervatra rama_pang yz_ steven.novaryo prabowo vioalbert
• 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 — 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:

1. jonathanirvings
2. wiwitrifai
3. yogahmad77
4. DystoriaX
5. meneketehe

Div 2:

1. Jeffrey
2. malfple
3. Bohdan
4. nhho
5. alvinvaja

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!

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:

1. Benq
2. nikolapesic2802
3. nirvana
4. buko
5. aropan

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!

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:

1. jonathanirvings
2. YogayoG
3. wiwitrifai
4. Pyqe
5. ollpu

Div 2:

1. YouKn0wWho
2. ipul23
3. Egor
4. farmerboy
5. markus_geger

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!

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:

1. KrK
2. almogwald
3. Pyqe
4. DystoriaX
5. Berted

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!

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:

1. wiwitrifai
2. rais.fathin38
3. faustaadp
4. Pyqe
5. rfpermen

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!