Kuroni's blog

By Kuroni, 4 months 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)$$$.

Read more »

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

By Kuroni, history, 8 months 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

Read more »

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

By Kuroni, history, 8 months 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!

Read more »

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

By Kuroni, history, 14 months 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.

Read more »

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

By Kuroni, history, 16 months 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: _iloveNQ_

Tutorial
Implementation

1163B2 - Cat Party (Hard Edition)

Author: _Shirone_

Tutorial
Implementation

1163C2 - Power Transmission (Hard Edition)

Author: LunarStellarshot

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

Read more »

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

By Kuroni, history, 16 months ago, In English

Hi Codeforces!

I'm glad to introduce you to Codeforces Round #558 (Div. 2), which will take place on May/09/2019 18:05 (Moscow time).

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, _iloveNQ_, _Shirone_, and LunarStellarshot. I would like to thank _kun_ 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!

Read more »

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