rama_pang's blog

By rama_pang, history, 4 months ago, In English

Hello Codeforces community,

We are excited to invite you to TOKI Indonesian NOI Open Contest 2022 — an online mirror contest for the Indonesian 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, 2021), 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 at any time within the time range by clicking the "start" button. There will be no additional time given if a contestant starts the contest less than 5 hours before the contest ends. The scoreboard will be hidden until the contest has ended.

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: The official contest has ended, thanks for your participation!

Congratulations to errorgorn for winning the contest! 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 contest, you may submit a response in this form.

We thank everyone who is involved:

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

Full text and comments »

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

By rama_pang, 5 months ago, In English

errorgorn just passed 3000 rating after Round #819, making him probably the first LGM in the ASEAN region.

Many congratulations to Sir Ashley.

P.S. minum susu gaming

EDIT: round unrated igmrrorgorn forever 😭

Full text and comments »

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

By rama_pang, history, 17 months ago, In English

Dear Codeforces community,

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

Key details:

Many thanks to:

  • prabowo for making sure no problems are in OEIS coordinating the contest. 🤣 👋
  • steven.novaryo for helping with problem preparation for the very first (!) time. 🥳 🎉
  • AMnu for testing the problems.
  • fushar for the TLX platform.

Please register for the contest, and we hope you will enjoy TROC #22! Good luck! 🏆 🥇 🥈 🥉

P.S. Please note the unusual duration 😱, read all problems 😎, and solve them in any order 💯.

UPD: Contest is over!

Congratulations to our top 5:

  1. Maripium
  2. tourist
  3. maroonrk
  4. errorgorn
  5. noimi

Congratulations to our first solvers:

Rating has been updated.

You can upsolve the problems here.

Editorial is available in the upsolve link.

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

Full text and comments »

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

By rama_pang, history, 23 months ago, In English

Happy Pi Day, Codeforces community!

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

Key details:

Scoring distribution: 100 — 200 — 350 — 400 — 550 — 600 — 800

Many thanks to:

  • prabowo for being a brilliant coordinator.
  • hocky for helping with problem preparation.
  • nirvana and bukanYohandi for testing the problems and giving invaluable feedback.
  • fushar for the amazing TLX platform.

Please register for the contest, and we hope you will enjoy TROC #20!

UPD: Contest over!

Congratulations to our top 5:

  1. tourist
  2. LayCurse
  3. maroonrk
  4. antontrygubO_o
  5. riantkb

Congratulations to our first solvers:

Editorial is available here.

You can upsolve the problems here.

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

P.S. We apologize that G is apparently OEIS-able :"(

Full text and comments »

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

By rama_pang, history, 2 years ago, In English

Hello everyone! I discovered a new (?) trick on how to apply lazy propagation on the Li Chao Tree and decided to write a blog about it. I've personally never seen it before (outside of myself), nor have I seen a problem that needs the Extended Li Chao Tree specifically, but it can overkill some problems. Of course, I might not be looking hard enough...

You can learn about the basics of Li Chao Tree from cp-algorithms or this simple blog.

The Extended Li Chao Tree can do the following problems (and other variations):

Problem 1

There is an array $$$A$$$ of size $$$N$$$. There are $$$Q$$$ online operations:

  • Range Line Insertion. Given $$$l$$$, $$$r$$$, $$$a$$$, $$$b$$$, do $$$A_i = \max(A_i, a \cdot i + b)$$$, $$$\forall i \in [l, r]$$$ in $$$O(\log^2 N)$$$
  • Range Line Addition. Given $$$l$$$, $$$r$$$, $$$a$$$, $$$b$$$, do $$$A_i += a \cdot i + b$$$, $$$\forall i \in [l, r]$$$ in $$$O(\log^2 N)$$$.
  • Point Query. Given $$$i$$$, return $$$A_i$$$ in $$$O(\log N)$$$.

Problem 2

There is an array $$$A$$$ of size $$$N$$$. There are $$$Q$$$ online operations:

  • Range Line Insertion. Given $$$l$$$, $$$r$$$, $$$a$$$, $$$b$$$, do $$$A_i = \max(A_i, a \cdot i + b)$$$, $$$\forall i \in [l, r]$$$ in $$$O(\log^2 N)$$$
  • Range Sum Addition. Given $$$l$$$, $$$r$$$, $$$b$$$, do $$$A_i += b$$$, $$$\forall i \in [l, r]$$$ in $$$O(\log^2 N)$$$.
  • Range Maximum Query. Given $$$l$$$, $$$r$$$, return $$$\max\limits_{\forall i \in [l, r]} A_i$$$ in $$$O(\log N)$$$.

Prerequisites

Some things you should know beforehand:

  • The Li Chao Tree can work with any functions, as long as that for all pairs of functions $$$f$$$ and $$$g$$$, there is a point $$$p$$$ where $$$f(x) \leq g(x)$$$ for $$$x \leq p$$$ and $$$f(x) \geq g(x)$$$ for $$$x \geq p$$$. However, for this discussion, I will assume that $$$f$$$ is always a line equation $$$f(x) = a \cdot x + b$$$.
  • We can also insert a line $$$f(x)$$$ only to a certain range $$$[l, r]$$$. Just as in the usual segment tree, we first split the interval $$$[l, r]$$$ into $$$O(\log N)$$$ segments. After that, we can do the "global" Li Chao Tree insertion on the subtree of those segments.

Example code for a basic version of the Li Chao Tree (with line insertions on a certain range).

code

The Extension

Let's focus on the Li Chao Tree that solves Problem 1. Range line insertion and point query can be implemented as usual.

Now we need to implement a lazy propagation method. But implementing it naively won't work. As an example, let the current node be $$$[1, N]$$$ with line $$$f$$$, and we want to do a range addition on the interval $$$[2, N - 1]$$$. What happens in a usual segment tree is that we directly recurse to $$$[1, M]$$$ and $$$[M + 1, N]$$$ with $$$M = \lfloor \frac{L + R}{2} \rfloor$$$. But let's say that we do a range sum addition with value $$$-\infty$$$ to the range $$$[2, N - 1]$$$. Since line $$$f$$$ on node $$$[1, N]$$$ is not affected by the update, when we query point $$$x = 2$$$, we will get $$$f(2)$$$ instead of $$$-\infty$$$.

How can we affect $$$f$$$ as well? Since $$$f$$$ must also be affected, then we can just push it downwards. In other words, we do a global line insertion on the intervals $$$[1, M]$$$ and $$$[M + 1, N]$$$ with the line $$$f$$$, then reset $$$[1, N]$$$ to have no line. After that, we can safely recurse to $$$[1, M]$$$ and $$$[M + 1, N]$$$, and all lines which might be optimal on the range $$$[2, N - 1]$$$ will be affected.

Since the global line insertion runs in $$$O(\log N)$$$ time, and we need to traverse $$$O(\log N)$$$ nodes when splitting the update interval, this takes $$$O(\log^2 N)$$$ time.

Example code for the Extended Li Chao Tree.

code

Problem 2 can be implemented in the same way, except that we store the range maximum as well. Note that we cannot do a range line addition this way (since the optimal $$$x$$$ which yields the maximum value might change). However, it might be possible in another way.

Optimizing Dijkstra in Line Graphs

TROC #13 — Mall and Transportation

Problem. Given a line graph with $$$H$$$ nodes. You can travel from $$$u$$$ to $$$v$$$ in $$$|u - v| \cdot S$$$ time. There are also $$$N$$$ nodes $$$D_1, D_2, ..., D_N$$$, where you can travel from $$$D_u$$$ to any nodes $$$v \in [A_u, B_u]$$$ in $$$|D_u - v| \cdot T_u + Q_u$$$ time. You initially start at $$$D_X$$$ for a given $$$X$$$. Find the minimum time to get to floors $$$D_1, D_2, ..., D_N$$$.

Solution. This is a blatant shortest path problem. Note that for a given $$$t$$$, all nodes reachable in $$$\leq t$$$ time form a segment $$$[l, r]$$$. Thus, after we reached all nodes $$$\in [l, r]$$$, the next node must be either $$$l - 1$$$ or $$$r + 1$$$. Now we only need to be able to update distance quickly. This can be easily done by modeling the update as a line equation insertion, which is solvable using the basic Li Chao Tree.

OII 2020 — Candele

Problem. Given $$$N$$$ segments $$$A_i, B_i$$$.

  • If $$$A_i < B_i$$$, then there exist edges $$$(u, u + 1), A_i \leq u < B_i$$$.
  • If $$$A_i > B_i$$$, then there exist edges $$$(u, u - 1), B_i < u \leq A_i$$$.

Find the shortest path from $$$A_1$$$ to $$$A_2, A_3, ..., A_N$$$!

Solution. The solution is the same as the previous one. Also, variation 3 is almost exactly the same problem.

For the original problem, since all line equations $$$f(x) = a \cdot x + b$$$ inserted has the property $$$a \in {1, -1}$$$, we can store $$$2$$$ segment trees instead: one for $$$a = 1$$$ and one for $$$a = -1$$$. That way, we can simply maximize $$$b$$$ with a classic segment tree which takes only $$$O(\log N)$$$ time per operation.

Overkilling Data Structure Problems

Singapore NOI 2020 — Progression

Problem. Given an array $$$A$$$ of size $$$N$$$. There are $$$Q$$$ operations:

  • Given $$$L$$$, $$$R$$$, $$$S$$$, $$$C$$$, $$$\forall i \in [L, R]$$$ do $$$A_i += S + (i - L) \cdot C$$$.
  • Given $$$L$$$, $$$R$$$, $$$S$$$, $$$C$$$, $$$\forall i \in [L, R]$$$ do $$$A_i = S + (i - L) \cdot C$$$.
  • Given $$$L$$$, $$$R$$$, find the maximum $$$j - i + 1$$$ where $$$L \leq i \leq j \leq R$$$ and $$$\forall x,y \in [i, j - 1]$$$, $$$A_{x + 1} - A_{x} = A_{y + 1} - A_{y}$$$.

Solution. Operation $$$1$$$ and $$$2$$$ are both supported by an Extended Li Chao Tree, so we can maintain the values of $$$A$$$. To check for operation $$$3$$$, we need to maintain a segment tree of the array $$$B$$$, where $$$B_i = A_i - A_{i-1}$$$.

  • For operation $$$1$$$, $$$B_i += C$$$, $$$\forall i \in [L + 1, R]$$$, while $$$B_L$$$ and $$$B_{R + 1}$$$ changes. We can do a range sum addition on the segment tree of $$$B$$$, then easily update $$$B_L$$$ and $$$B_{R + 1}$$$ since we can maintain the values of $$$A$$$.
  • For operation $$$2$$$, we set $$$B_i = C$$$, $$$\forall i \in [L + 1, R]$$$. We can do a range set update on the segment tree of $$$B$$$, then update $$$B_L$$$ and $$$B_{R + 1}$$$ accordingly.
  • For operation $$$3$$$, we need to find the maximum length subarray of $$$B[L+1 \dots R]$$$ where all elements in that subarray are equal. This is similar to a classic segment tree problem on finding a subsegment with the maximal sum for a given subarray, described at cp-algorithms. We can do a range sum addition and range set update through normal lazy propagation.

ABC177F — I hate Shortest Path Problem

Problem. There is an $$$(H + 1) \times W$$$ grid. We start at any cell on the top row and can move either down or right in a single step. However, for the $$$i$$$-th row, we cannot move downwards for the cells $$$(i, A_i), (i, A_i + 1), \dots, (i, B_i)$$$. Find the minimum steps to reach a cell in the $$$i$$$-th row, $$$\forall i \in [2, H + 1]$$$.

Solution. We can maintain the shortest path for all $$$W$$$ columns of some row $$$i$$$ in an array $$$A$$$ of size $$$W$$$. We can simulate moving from row $$$i$$$ to $$$i + 1$$$ quickly with the following operations:

  • Do $$$A_i += 1$$$, $$$\forall i \in [1, W]$$$.
  • Do $$$A_i = \infty$$$, $$$\forall i \in [l, r]$$$.
  • Do $$$A_i = \min(A_i, a \cdot i + b)$$$, $$$\forall i \in [l, r]$$$.
  • Find $$$\min\limits_{\forall i \in [1, W]} A_i$$$.

Everything can be done with an Extended Li Chao Tree.

Naively Maintaining Slope Trick

CF713C — Sonya and Problem Wihtout a Legend

Problem. Given an array $$$A$$$ of size $$$N$$$. In one operation, you can choose any element and increase or decrease it by $$$1$$$. Find the minimum number of operations to make the array strictly increasing.

Solution. See the solution described at:

However, instead of using a priority queue to store the slope changing points, you could store the lines themselves with the Extended Li Chao Tree. Since slope trick problems require the function to be convex (or concave), we can ternary search to find the value where the slope is $$$0$$$. Code.

Convex Hull Trick Again

The Extended Li Chao Tree is more powerful than a standard line container, so it can also solve all problems solvable by it (and also trivializes some).

The Motivation Behind

IOI 2018 — Meetings

Problem. Given an array $$$H$$$ of size $$$N$$$. You are given $$$Q$$$ queries $$$[ql, qr]$$$. For each query, find $$$\min\limits_{\forall x \in [ql, qr]}(\sum\limits_{y = ql}^{x-1} \max\limits_{\forall z \in [y, x]} H_z + \sum\limits_{y = x}^{qr} \max\limits_{\forall z \in [x, y]} H_z)$$$.

Solution. First, we build a Cartesian Tree over the array $$$H$$$ (for all comparisons, we use a pair $$$(H_i, i)$$$ to ensure all elements are distinct). Let us assume we are at the node which denotes the segment $$$[L, R]$$$, where the maximum value is $$$(H_M, M)$$$, and its children denotes the segment $$$[L, M - 1]$$$ and $$$[M + 1, R]$$$. All queries on this segment must satisfy $$$L \leq ql \leq M \leq qr \leq R$$$ and $$$\max\limits_{ql \leq i \leq qr} (H_i, i) = (H_M, M)$$$. Consider a query $$$[ql, qr]$$$ on this segment.

Let $$$opt_{l, r}$$$ be the answer for the query $$$[l, r]$$$. Assume we have values $$$opt_{L, M - 1}, opt_{L + 1, M - 1}, \dots, opt_{M - 1, M - 1}$$$ and $$$opt_{L, L}, opt_{L, L + 1}, \dots, opt_{L, M - 1}$$$ from the node $$$[L, M - 1]$$$, and values $$$opt_{M + 1, R}, opt_{M + 2, R}, \dots, opt_{R, R}$$$ and $$$opt_{M + 1, M + 1}$$$, $$$opt_{M + 1, M + 2}$$$, \dots, $$$opt_{M + 1, R}$$$ from the node $$$[M + 1, R]$$$.

If we have such values, for a query $$$[ql, qr]$$$, the answer is $$$\min(opt_{ql, M - 1} + (qr - M + 1) \cdot H_M, opt_{M + 1, qr} + (M - ql + 1) \cdot H_M)$$$. This is true since $$$H_M$$$ is the maximum value on segment $$$[L, R]$$$. Now we only need to calculate $$$opt_{L, L}, opt_{L, L + 1}, \dots, opt_{L, R}$$$ and $$$opt_{L, R}, opt_{L + 1, R}, \dots, opt_{R, R}$$$ and we're done.

Consider $$$opt_{L, L}, opt_{L, L + 1}, \dots, opt_{L, M - 1}$$$ and $$$opt_{M + 1, M + 1}, opt_{M + 1, M + 2}, \dots, opt_{M + 1, R}$$$. Notice that for $$$x \in [M + 1, R]$$$, then $$$opt_{L, x} = \min(opt_{L, M - 1} + (x - M + 1) \cdot H_M, opt_{M + 1, x} + (M - L + 1) \cdot H_M )$$$. The second one is simply pasting $$$opt_{M + 1, x}$$$ to $$$opt_{L, x}$$$ then doing a range sum addition. After that, then we can handle the first part by taking the minimum with $$$opt_{L, M - 1} + (x - M + 1) \cdot H_M$$$. Notice that it is simply a line insertion on the range $$$[M + 1, R]$$$. The same thing can be done for $$$opt_{M + 1, R}, opt_{M + 2, R}, \dots, opt_{R, R}$$$ and $$$opt_{L, M - 1}, opt_{L + 1, M - 1}, \dots, opt_{M - 1, M - 1}$$$.

At first glance, we will need an Extended Li Chao Tree, but you don't actually need to. Since we do the range addition updates in a specific "bottom-up" manner, when traversing a node in the segment tree, we do not have to split the line and do a global insert to its children simply because there is no line yet. Thus we can use a basic Li Chao Tree with normal lazy propagation on top.

This problem is the motivation behind the Extended Li Chao Tree — being able to support the needed operations without any specific constraint.

If you spot any mistakes or errors, please let me know! Feel free to ask any questions, suggest other problems, or share any new tricks you found in the comments. :)

Full text and comments »

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