prabowo's blog

By prabowo, history, 4 months ago, In English

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 03.12.2023 07:35 (Московское время) 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:

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!

Full text and comments »

  • Vote: I like it
  • +184
  • Vote: I do not like it

By prabowo, history, 6 months ago, In English

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?

Full text and comments »

Tags icpc, wf
  • Vote: I like it
  • +179
  • Vote: I do not like it

By prabowo, history, 16 months ago, In English

I can't open this problem: https://codeforces.com/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?

Full text and comments »

  • Vote: I like it
  • +98
  • Vote: I do not like it

By prabowo, history, 20 months ago, In English

IOI 2022 Day 1 has just ended.

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!

Full text and comments »

  • Vote: I like it
  • +150
  • Vote: I do not like it

By prabowo, history, 2 years ago, In English

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.

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:

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

Full text and comments »

  • Vote: I like it
  • +133
  • Vote: I do not like it

By prabowo, history, 3 years ago, In English

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 [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!

Full text and comments »

  • Vote: I like it
  • +314
  • Vote: I do not like it

By prabowo, history, 3 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +199
  • Vote: I do not like it

By prabowo, history, 3 years ago, In English

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.

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:

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

Full text and comments »

  • Vote: I like it
  • +130
  • Vote: I do not like it

By prabowo, history, 4 years ago, In English

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

  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:

Editorial is available here.

You can upsolve the problems here.

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

Full text and comments »

  • Vote: I like it
  • +123
  • Vote: I do not like it

By prabowo, history, 4 years ago, In English

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:

  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!

Full text and comments »

  • Vote: I like it
  • +147
  • Vote: I do not like it

By prabowo, history, 4 years ago, In English

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!

Full text and comments »

  • Vote: I like it
  • +87
  • Vote: I do not like it

By prabowo, history, 4 years ago, In English

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:

  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!

Full text and comments »

  • Vote: I like it
  • +83
  • Vote: I do not like it

By prabowo, history, 4 years ago, In English

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!

Full text and comments »

  • Vote: I like it
  • +71
  • Vote: I do not like it

By prabowo, 4 years ago, In English

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!

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it

By prabowo, 5 years ago, In English

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!

Full text and comments »

  • Vote: I like it
  • +38
  • Vote: I do not like it

By prabowo, history, 5 years ago, In English

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!

Full text and comments »

  • Vote: I like it
  • +41
  • Vote: I do not like it