Kuroni's blog

By Kuroni, history, 5 weeks ago, In English

Hello again Codeforces!

Two weeks ago we held the first round of VNOI Cup 2024! We hope that everyone who joined the contest had a great time and enjoyed our problems!

On Sunday, June 16, at 21:00 GMT+7 , we will hold the mirror contest of the VNOI Cup Qualification Round 2, and we would like to invite you to join the contest. Remember, if you are a Vietnamese national, consider joining the official round.

VNOI Cup is a Competitive Programming competition hosted by VNOI (Vietnam Olympiads in Informatics community), a group of Vietnamese programmers like you, working together to make programming competitions more fun and challenging in Vietnam. We're a non-profit organization dedicated to supporting the growth of competitive programming in Vietnam. This competition is one of the many ways we aim to achieve this goal!

Again, a big shoutout to our awesome problem setters and testers! Thanks to their hard work, we have an exciting contest ready for you.

The contest will feature 7 problems to be solved in 180 minutes. Points for problems increase with difficulty. Each problem may consist of multiple subtasks, and you only earn points for a subtask if you pass all test cases for that subtask. Penalty points are calculated as the time of the last scoring submission plus 5 minutes for each incorrect submission. Contestants are ranked by total points, with ties broken by ascending penalty points.

Remember, the second mirror contest starts on Sunday, June 16, at 21:00 GMT+7. The official contest will start 1 hour sooner, at 20:00 GMT+7.

We're excited to see you in the contest! Good luck, and happy coding! 🚀

Full text and comments »

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

By Kuroni, history, 7 weeks ago, In English

Hello Codeforces!

We're thrilled to announce the third season of the VNOI Cup! 🎉

We invite you to join the mirror round of our programming contest. Remember, if you are a Vietnamese-national, consider joining the official round.

VNOI Cup is a Competitive Programming competition hosted by VNOI (Vietnam Olympiads in Informatics community), a group of Vietnamese programmers like you, working together to make programming competitions more fun and challenging in Vietnam. We're a non-profit organization dedicated to supporting the growth of competitive programming in Vietnam. This competition is one of the many ways we aim to achieve this goal!

A big shoutout to our awesome problem setters and testers! Thanks to their hard work, we have an exciting contest ready for you.

The contest will feature 7 problems to be solved in 180 minutes. Points for problems increase with difficulty. Each problem may consist of multiple subtasks, and you only earn points for a subtask if you pass all test cases for that subtask. Penalty points are calculated as the time of the last scoring submission plus 5 minutes for each incorrect submission. Contestants are ranked by total points, with ties broken by ascending penalty points.

The first mirror contest starts on June 2, 2024, at 21:00 GMT+7. The official contest will start 1 hour sooner, at 20:00 GMT+7.

We're excited to see you in the contest! Good luck, and happy coding! 🚀

Full text and comments »

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

By Kuroni, history, 3 months ago, In English

Xin chào Codeforces (・ω・)ノ

We are pleased to announce the resumption of the Global Rounds. Thanks to XTX Markets for supporting the initiative! In 2024, we will hold 4 such rounds. The series results will take into account the best 3 participations out of 4.

On Apr/06/2024 17:35 (Moscow time) we will host Codeforces Global Round 25.

Codeforces Global Round 25 marks the first round in the 2024 series of Codeforces Global Rounds. These rounds are open and rated for everyone.

The prizes for this round are as follows:

  • The top 30 participants will receive a t-shirt.
  • 20 t-shirts will be randomly distributed among participants ranked between 31 and 500, inclusive.

The prizes for the 4-round series in 2024:

  • In each round, the top-100 participants get points according to the table.
  • A participant's final score will be the sum of the points they earned in their 3 highest-placing rounds.
  • The top 20 participants across the series will receive sweatshirts and placement certificates.

We extend our gratitude to XTX Markets for supporting the global rounds initiative in 2024!

The problems were all marinated and cooked by MofK and Kuroni.

Our sincerest gratitudes go to:

Round Information:

  • Duration: $$$3$$$ hours.
  • Number of problems: $$$9$$$ problems.
  • Score distribution: $$$500 - 1000 - 1500 - 1750 - 2250 - 2750 - 3250 - 3500 - 4000$$$.

A tiny bit of personal note at the end, this is our first round on Codeforces in 3 years, and it feels a bit nostalgic to be back here again :) We eagerly anticipate your participation and let's all make it an awesome contest together!

Blooper

UPD: Added score distribution.

UPD: The round has concluded. Congratulations to the winners!

  1. Geothermal
  2. ecnerwala
  3. Um_nik
  4. maroonrk
  5. jqdai0815
  6. Benq
  7. hos.lyric
  8. antontrygubO_o
  9. cmll02
  10. AlternatingCurrent

Tutorial can be found here, and playlist of songs used in the problem statements can be found here.

Full text and comments »

Announcement of Codeforces Global Round 25
  • Vote: I like it
  • +605
  • Vote: I do not like it

By Kuroni, history, 12 months ago, In English

Hi everyone! On behalf of the VNOI CUP 2023 team, I would like to invite you to participate in VNOI CUP 2023 Final — online mirror, which will be held in parallel with the official onsite division and the open onsite division.

Some important information about the round:

  • Online mirror link.
  • Time: Saturday, 22 July 2023, 03:00 UTC.
  • Duration: 5 hours.
  • Problems: 7 to 10, sorted by difficulty (hopefully!). Each problem contains multiple subtasks.
  • Penalty format: AtCoder style, i.e. timestamp of last submission that increased your score + 5 minutes per submission before the best submission for each problem.

To get a flavor of our problems, we recommend you checking out this year's qualifier rounds in the following links: Round 1, Round 2, and Round 3. You can also check out last year's final round online mirror here.

I would like to introduce and thank the following people for making the cup happen:

We will have a Vietnamese live commentary of the official final round hosted by Kuroni and I_love_Hoang_Yen on VNOI's Facebook page. Editorials in both languages will also be provided after the contest.

EDIT: The mirror has concluded. Thank you everyone for participating!

Here are the English statement, Vietnamese statement, English editorial, and Vietnamese editorial.

Full text and comments »

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

By Kuroni, history, 3 years ago, In English

"Love" is a violent word.
"I love that about you..." Doesn't that just mean "If that changed, I wouldn't love you anymore?"
"Love" is a word that binds you.
— Touko Nanami —

Hi Codeforces!

Ari and I are pleased to invite you to participate in Codeforces Round 715 (Div. 1) and Codeforces Round 715 (Div. 2), which will be held at Apr/16/2021 17:35 (Moscow time). Each division will have 6 problems and 2 hours and 15 minutes to solve them.

Big thanks to the following people:

The round will be themed around Yagate Kimi ni Naru, which is a romantic anime/manga series. If you haven't picked up the series yet, I highly recommend you to do so after the round ;)

Please do read all of the problems, stay hydrated during the round, and solve as many as you can! Good luck have fun to everyone!

Here are the scoring distributions:

  • Div. 2: 500 — 1000 — 1500 — 2250 — 2500 — 3000
  • Div. 1: 750 — 1000 — 1500 — 2250 — 2250 — 4000

UPD1: The round has concluded! Congratulations to the winners from both divisions:

  • Div. 1:
  1. ecnerwala
  2. ksun48
  3. tourist
  4. Radewoosh
  5. maroonrk
  • Div. 2:
  1. wannahavealife (solved all problems!)
  2. traxex2
  3. _su1sen
  4. I_love_Ilya_Krasnov
  5. tsugu

UPD2: Editorial is up!

Thanks to everyone for participating in this contest, this has been a wild ride from start to finish. See you all next time!

Full text and comments »

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

By Kuroni, 4 years ago, In English

Special thanks to Ari for helping me proof-reading this blog :D

Hi everyone! Some years ago I read zscoder's tutorial on slope trick. Initially, I found the blog a bit difficult to understand, so I came up with a different explanation and system for my personal use. Today, I finally have the courage to share it with you guys. So without further ado, let's get started!

Formulation and properties

Slope trick is a way to represent a function. Here, I denote that a function is slope-trick-able (sorry for the lack of creativity) if the function satisfies 3 conditions:

  1. It is continuous.

  2. It can be divided into multiple sections, where each section is a linear function with an integer slope.

  3. It is a convex/concave function. In other words, the slope of each section is non-decreasing or non-increasing when scanning the function from left to right.

For example, the function $$$y = f(x) = |x|$$$ is a slope-trick-able function because it can be divided into two sections of linear functions with integer slopes ($$$y = -x$$$ for $$$x \in (-\infty, 0)$$$, and $$$y = x$$$ for $$$x \in [0, \infty)$$$), and the slope is non-decreasing going from left to right.

Let's define some other terms. I define a slope changing point to be the value $$$x_{change}$$$ such that when going from the left of $$$x_{change}$$$ to the right of $$$x_{change}$$$, the function changes its slope. Taking the example above, $$$x_{change} = 0$$$ is a slope changing point, the slope is $$$-1$$$ to the left of $$$x = 0$$$ and is $$$1$$$ to the right of $$$x = 0$$$. Note that a function can have multiple slope changing points. For example, this artificial function

$$$ y = g(x) = \begin{cases} 2 &\quad\text{when } x < 2\\ x &\quad\text{when } 2 \leq x < 8\\ 4x-24 &\quad\text{when } 8 \leq x\\ \end{cases} $$$

has $$$x = 2$$$ and $$$x = 8$$$ as slope changing points.

Let's come up with a way to represent this kind of function smoothly. I can represent this function by storing the linear function of the rightmost section, and the multiset $$$\text{S}$$$ all the slope changing points where the slope changes its value by $$$1$$$ (here I use the multiset with its mathematical definition, i.e. a set where we can repeat elements). This also means that if there is a slope changing point where the slope changes its value by more than $$$1$$$, we simply store that point as many times as the change in the slope value.

Using this, we see that the function $$$f(x) = |x|$$$ can be represented in slope trick language as $$$[y=x, \text{ S = {0, 0}}]$$$ ($$$x$$$ is the function of the rightmost function, and $$$0$$$ is stored twice because the slope increases by $$$2$$$ (from $$$-1$$$ to $$$1$$$). Likewise, the artificial function above can be represented as $$$[y=4x-24, \text{ S = {2, 8, 8, 8}}]$$$.

We note that just by storing these values, we can reconstruct every segment and therefore the whole function itself. Let's take the artificial function as an example. Using the multiset of slope changing point, we see that there are 3 sections $$$(-\infty, 2)$$$, $$$[2, 8)$$$, and $$$[8, \infty)$$$. The last section has the function of $$$y = 4x - 24$$$. The second-to-last section has the function of $$$y = x + b$$$ (because the slope changes by $$$3$$$ at $$$x = 8$$$), and we can solve $$$x + b = 4x - 24$$$ at $$$x = 8$$$ to yield $$$b = 0$$$, hence the second-to-last section has the function of $$$y = x$$$. Finally, the first section has the function of $$$y = c$$$ (the slope changes by $$$1$$$ at $$$x = 2$$$), and $$$c = x$$$ at $$$x = 2$$$ yields $$$c = 2$$$, therefore the function for the first section is $$$y = 2$$$.

Here comes the single most important property of slope-trick-able functions: they are mergable! In other words, if both $$$f(x)$$$ and $$$g(x)$$$ are slope-trick-able functions, then $$$h(x)=f(x)+g(x)$$$ is also a slope-trick-able function. Note that we only consider addition of the same type of slope-trick-able functions, i.e. both convex functions or concave functions. Even more beautifully, the slope trick representation of $$$h(x)$$$ is also easily deductable: the rightmost function is equals to the sum of two rightmost functions of $$$f(x)$$$ and $$$g(x)$$$, and the multiset $$$S_h = S_f \cup S_g$$$. To see how this union operation works, if you are familiar with how sweep line works, we can view the slope changing points as the event points where the slope changes, and so when adding two functions, we can simply union all the event points together.

Now we are done with all the definitions, let's get this new knowledge to work! As we will see in the next few examples, the essence of slope trick lies in the flexibility of transforming our functions just from modifying the slope changing points and the rightmost function.

713C - Sonya and Problem Wihtout a Legend

TL;DR: You are given an array, each operation you are allowed to increase or decrease an element's value by $$$1$$$. Find the minimum number of operations to make the array strictly increasing.

We first need to transform this problem a bit by changing the condition from strictly increasing to non-decreasing. To do that, simply do a[i] -= i for all elements.

Let's denote the function $$$f_i(x)$$$ to be the mininum number of operations to make the first $$$i$$$ elements of the array non-decreasing, with the condition that $$$a_i \leq x$$$. We see that the answer to our problem is simply $$$f_n(\infty)$$$. Here, I will prove that $$$f_i(x)$$$ is a convex slope-trick-able function for all $$$i$$$ using induction.

Firstly, we see that $$$f_0(x)$$$ is a convex slope-trick-able function, it is simply $$$f_0(x) = 0$$$.

Let's suppose $$$f_{i - 1}(x)$$$ is a convex slope-trick-able function. Denote $$$g_i(x)$$$ to be the mininum number of operations to make the first $$$i$$$ elements of the array non-decreasing, with the condition that $$$a_i = x$$$ (note that $$$g_i(x)$$$ is almost similar to $$$f_i(x)$$$, but with $$$=$$$ instead of $$$\leq$$$ condition for $$$a_i$$$). We can see that $$$g_i(x) = f_{i - 1}(x) + |x - a_i|$$$. Since $$$|x - a_i|$$$ is a convex slope-trick-able function (similar to the first example function), and $$$f_{i - 1}(x)$$$ is a convex slope-trick-able function due to our induction hypothesis, $$$g_i(x)$$$ is also convex slope-trick-able.

Now comes to our finale: We observe that $$$f_i(x)$$$ is a prefix-min function to $$$g_i(x)$$$ (i.e. $$$f_i(x) = \min(g_i(t), \forall t \leq x)$$$). We see that for a convex slope-trick-able function, its value is non-increasing up until the point where the slope becomes $$$1$$$, and non-decreasing from that point on. So, in order to make $$$f_i(x)$$$, we simply "cut" $$$g_i(x)$$$ at the point where the slope becomes $$$1$$$, and "extend" that point rightward. I give you this absolutely amazing doodle to demonstrate what I've just said:

Since the "cut" and "extend" operation is simply simultaneously removing the largest slope changing point along with modifying the rightmost function until the slope of the rightmost function becomes $$$0$$$, $$$f_i(x)$$$ is also a convex slope-trick-able function. Additionally, you can inductively prove that the slope of the rightmost function of $$$g_i(x)$$$ is $$$1$$$, and therefore we only have to remove the largest slope changing point of $$$g_i(x)$$$ to obtain $$$f_i(x)$$$.

Therefore, we can continously maintain $$$f_i(x)$$$ with increasing $$$i$$$, using a priority_queue as the data structure backing our slope changing multiset, and simply output $$$f_n(\infty)$$$ as our answer. The complexity is $$$O(n \log n)$$$.

Singapore NOI 2018 — Task 5

TL;DR: You are given an array of $$$n$$$ non-negative integers, each operation you are allowed to increase or decrease an element's value by $$$1$$$ (you must keep all elements non-negative at all times). Find the minimum number of operations to make the array satisfy $$$|a_i - a_{i + 1}| \leq h$$$ for $$$1 \leq i < n$$$, where $$$h$$$ is a given value.

We first observe that the restriction to keep all elements non-negative is unnecessary, because in an optimal construction, we would never have a negative element in the array (we can simply make the negative elements equal to $$$0$$$ to use less operations and still satisfy the condition).

We denote $$$f_i(x)$$$ to be the minimum number of operations to make the first $$$i$$$ elements satisfiable, while ensuring that $$$a_i = x$$$. We will once again prove that this function is convex slope-trick-able for all $$$i$$$.

It is easy to see that $$$f_1(x) = |a_1 - x|$$$, and therefore $$$f_1(x)$$$ is convex slope-trick-able.

Suppose $$$f_{i - 1}(x)$$$ is convex slope-trick-able. Denote $$$g_i(x)$$$ as the minimum number of operations to make the first $$$i$$$ elements satisfiable, with $$$|a_i - x| \leq h$$$. We see that $$$g_i(x)$$$ is some sort of a "local-minimum" function of $$$f_i(x)$$$, where $$$g_i(x) = \min(f_i(t), |t - x| \leq h)$$$. Let's transform $$$f_{i - 1}$$$ into $$$g_{i - 1}$$$. Here, let's focus on three parts: the section where the slope is 0, the left of that section, and the right of that section.

  1. The section where the slope is 0 remains the same, because as we have stated in the previous problem, this section contains the minimum value of $$$f_{i - 1}$$$.
  2. The part to the left of the 0-section "shifts" to the left by $$$h$$$. That is because this left part is non-increasing, therefore $$$g_{i - 1}(x)$$$ will always try to take the minimum value of $$$f_{i - 1}(t)$$$ where $$$x \leq t \leq x + h$$$.
  3. The part to the right of the 0-section "shifts" to the right by $$$h$$$. Same explanation.

Again, an amazing doodle:

Here, we can maintain the slope changing points by subtracting every slope changing points up until the 0-section by $$$h$$$, and adding $$$h$$$ to every other slope changing points (we need to also recalculate the rightmost function). Therefore, $$$g_{i - 1}(x)$$$ is convex slope-trick-able. Finally, we see that $$$f_i(x) = g_{i - 1}(x) + |a_i - x|$$$, and therefore $$$f_i(x)$$$ is convex slope-trick-able.

A sidenote when implementing, we can use 2 priority_queue's to maintain the slope changing points of our left and right part, and rather than maintaining the rightmost function, we can maintain the function of the minimum section itself. Complexity is $$$O(n \log n)$$$.

Full text and comments »

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

By Kuroni, history, 4 years ago, In English

Hello everyone, this is the editorial for Codeforces Round 616 (Div. 1) and Codeforces Round 616 (Div. 2)! Along with the solution to each problem, we will have the theme and easter egg solution as well! I hope you all enjoyed our problems ( ´ ▽ ` )b

1291A - Even But Not Even

Author: 265918

Tutorial
Implementation

1291B - Array Sharpening

Author: hugopm

Tutorial
Implementation

1290A - Mind Control

Author: Ari

Tutorial
Implementation (quadratic)
Implementation (linear)

1290B - Irreducible Anagrams

Author: Ari

Tutorial
Implementation

1290C - Prefix Enlightenment

Author: hugopm

Tutorial
Implementation (preprocess with DFS)
Implementation (dynamic bipartite DSU)

1290D - Coffee Varieties (hard version)

Author: hugopm

Tutorial
Implementation

1290E - Cartesian Tree

Author: gamegame

Tutorial
Implementation

1290F - Making Shapes

Author: Kuroni

Tutorial
Implementation

Theme and easter eggs

Spoilers

Full text and comments »

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

By Kuroni, history, 4 years ago, In English

Hello Codeforces o(≧∇≦o) I'm glad to introduce you to Codeforces Round 616 (Div. 1) and Codeforces Round 616 (Div. 2), which will take place on Feb/02/2020 17:05 (Moscow time).

Each division will contain 6 problems, and you will have 2.5 hours to solve them. There might be interactive problems, feel free to learn about them here. The problems were created by 265918, Ari, Kuroni, gamegame, and hugopm.

Now, here are some people I would love to mention:

The statements were made as clear as possible for your best experiences. Moreover, we sneakily included a theme in the problemset, and each problem will have an easter egg that is the clue to the theme. If you have AC'd every problem, be sure to search for the theme(*´▽`*)

Additionally, most of us are in a Discord server dedicated to competitive programming called "AC" (this is also the motto of this contest). We will be on the server after the contest to discuss the problems with you. You can find the server here!

I wish you all have good luck and high ratings ( ´ ▽ ` )ノ

UPD1: Here is the score distribution:

  • Div. 2: 500 1000 1500 2000 2750 3000

  • Div. 1: 500 1000 1750 2500 3000 3250

UPD2: Here is the editorial, including easter egg solutions!

UPD3: Thank you everyone for participating :D Here are the final standings:

Div. 1:

  1. tourist

  2. fateice

  3. ksun48

  4. Um_nik

  5. WZYYN

Div. 2:

  1. IZONE

  2. Infoshoc

  3. CouponKaka-ChutteNahiHai

  4. lzh12139

  5. liqing

Thank you everyone and I hope to see you again!

Full text and comments »

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

By Kuroni, history, 5 years ago, In English

Disclaimer: Please don't try this at home. I just find this occasion quite hilarious and want to share with you guys :D

So yesterday I was hanging out with my folks, and there were some mild alcohol here and there (I drank some apple cider, please don't call the police I just reached 18) and I was a bit drowsy but definitely not drunk. I was just chilling when I checked on my phone and realized it was a mere 7 minutes until Codeforces Round 573 (Div. 1). If it was for any normal human being, they would probably skipped the contest and continue the fun. However, because I am not drunk at all, I decided that I should run home and participate. So I excused myself out of the party and sprinted as fast as I can.

On the path back home, there were 2 paths, one is clear and nicely lighted but a little bit further, and one involved running through a badly-lighted park but it was shorter in distance. As a programmer, I applied the Dijkstra algorithm immediately and sprinted through the park with maximum power. Little did I know, the shorter path does not always have the lower weight. There was a giant boulder in the middle of the park, and since the park was a little dark and I am definitely not drunk, I scratched my knee onto the boulder. It kinda hurt, but I just shrugged and ran through the rest of the park. Upon reaching home, I was greeted with this (mild bleeding warning).

However, it turns out my dedication was paid off, since I probably peaked my all-time performance, solving 4 problems in div 1 for the first time and at one point even reached the 8th place with a +221 predicted delta. There's not much to say afterwards, I regained my grandmaster status with no failed system test :D

So you could say I literally traded my red blood for my red grandmaster status. Please don't do this unless you are definitely not drunk.

Full text and comments »

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

By Kuroni, history, 5 years ago, In English

Hello everyone, this is the editorial for Codeforces Round 558 (Div. 2). I hope you enjoy the problem as well as I did!

1163A - Eating Soup

Author: ArguteOnAir

Tutorial
Implementation

1163B2 - Cat Party (Hard Edition)

Author: Shirone

Tutorial
Implementation

1163C2 - Power Transmission (Hard Edition)

Author: GreymaneSilverfang

Tutorial
Implementation

1163D - Mysterious Code

Author: Kuroni

Tutorial
Implementation

1163E - Magical Permutation

Author: Kuroni

Tutorial
Implementation
Implementation with DFS

1163F - Indecisive Taxi Fee

Author: Kuroni

Tutorial
Implementation

Full text and comments »

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

By Kuroni, history, 5 years ago, In English

Hi Codeforces!

I'm glad to introduce you to Codeforces Round 558 (Div. 2), which will take place on 09.05.2019 18:05 (Московское время).

You will have 6 problems and 2 hours to solve them. Two problems will have subtasks. Round will be rated for everyone with rating below 2100. Participants from the first division can also participate out of competition as usual.

The problems were prepared by me, ArguteOnAir, Shirone, and GreymaneSilverfang. I would like to thank cdkrot for his immense help during the round preparation, 300iq, mohammedehab2002, and Um_nik for testing them, and of course MikeMirzayanov for the Codeforces and Polygon platforms.

In the contest, you will meet Kuro, Shiro, Katie, and Selena, the four naughty but smart cats who love playing and asking questions. I hope you will find our problems interesting.

I will be in the community Discord server after the contest to discuss the problems with you. You can find the server here!

Good luck!

UPD1: Problem B and C will have 2 subtasks. The scoring distribution will be 500 — (750 + 500) — (1000 + 750) — 2250 — 2750 — 3250.

UPD2: The contest will be delayed by 15 minutes due to technical reasons. Sorry for the inconvenience :(

UPD3: Final standings!

Div. 1:

  1. ainta (the only contestant to finish all problems!)

  2. dreamoon_love_AA

  3. hank55663

  4. tfg

  5. pmnox

Div. 2:

  1. xht37

  2. Ekoos

  3. beka_asd

  4. bbao69

  5. OIerDb

The editorial is available here. Thank you for participating!

Full text and comments »

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