1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Bowling Frame
Contest: 2024 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 1200
Tags: binary search, brute force, math

Bowling is a national sport in Taiwan; everyone in the country plays the sport on a daily basis since their youth. Naturally, there are a lot of bowling alleys all over the country, and the competition between them is as intense as you can imagine.

Maw-Shang owns one such bowling alley. To stand out from other competitors in the industry and draw attention from customers, he decided to hold a special event every month that features various unorthodox bowling rules. For the event this month, he came up with a new version of the game called X-pin bowling. In the traditional $$$10$$$-pin bowling game, a frame is built out of ten bowling pins forming a triangular shape of side length four. The pin closest to the player forms the first row, and the two pins behind it form the second row, and so on. Unlike the standard version, the game of $$$X$$$-pin bowling Maw-Shang designed allows a much larger number of pins that form a larger frame. The following figure shows a standard $$$10$$$-pin frame on the left, and on the right it shows a $$$21$$$-pin frame that forms a triangular shape of side length six which is allowed in the game of $$$X$$$-pin bowling.

Being the national sport, the government of Taiwan strictly regulates and standardizes the manufacturing of bowling pins. There are two types of bowling pins allowed, one in black and the other in white, and the bowling alley Maw-Shang owns has $$$w$$$ white pins and $$$b$$$ black pins. To make this new game exciting for the customers, Maw-Shang wants to build the largest possible frame from these $$$w+b$$$ pins. However, even though he is okay with using both colors in building the frame, for aesthetic reasons, Maw-Shang still wants the colors of the pins on the same row to be identical. For example, the following figure shows two possible frames of side length six, but only the left one is acceptable to Maw-Shang since the other one has white and black pins mixed in the third row.

The monthly special event is happening in just a few hours. Please help Maw-Shang calculate the side length of the largest frame that he can build from his $$$w+b$$$ pins!

Input format:
The first line of the input contains a single integer $$$t$$$, the number of test cases. Each of the following $$$t$$$ lines contains two integers $$$w$$$ and $$$b$$$, the number of white and black pins, respectively.

- $$$1 \leq t \leq 100$$$
- $$$0 \leq w, b \leq 10^9$$$

Output format:
For each test case, output in a single line the side length $$$k$$$ of the largest pin satisfying Maw-Shang's requirement you can build with the given pins.

Constraints:
Time limit: 1.0 s
Memory limit: 1024.0 MB

Example input:
4
1 2
3 2
3 3
12 0

Example output:
2
2
3
4

Editorial:
Cube
Contest: 2024 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 2000
Tags: bitmasks, dfs and similar, dp

You are given an $$$n\times n\times n$$$ big three-dimensional cube that contains $$$n^3$$$ numbers. You have to choose $$$n$$$ of those numbers so that their sum is as small as possible. It is, however, forbidden to choose two numbers that are located in the same plane. That is, if we identify the positions in the cube by three Cartesian coordinates, then choosing two numbers from positions $$$(x,y,z)$$$ and $$$(x',y',z')$$$ is forbidden if $$$x=x'$$$, $$$y=y'$$$, or $$$z=z'$$$.

Input format:
The input consists of the number $$$n$$$ followed by $$$n^3$$$ numbers in the cube. The numbers are presented as $$$n$$$ two-dimensional matrices, one for each layer of the cube. More precisely, there will be $$$n^2$$$ lines follow, each having $$$n$$$ numbers. For each $$$x, y, z$$$ ($$$1\le x, y, z\le n$$$), the number at the position $$$(x, y, z)$$$ is listed as the $$$z$$$-th number in the $$$((x-1)\times n+y)$$$-th line.

- $$$2 \leq n \leq 12$$$
- All numbers in the cube are integers between $$$0$$$ and $$$2\times 10^7$$$.

Output format:
The output consists of a single number. It is the minimum sum of $$$n$$$ numbers chosen from the cube according to the above rules.

Constraints:
Time limit: 3.0 s
Memory limit: 1024.0 MB

Example input:
3
1 2 3
4 5 6
7 8 9
1 1 1
2 2 2
3 3 3
4 3 0
2 1 4
9 8 9

Example output:
5

Editorial:
Drunken Maze
Contest: 2024 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 1700
Tags: brute force, dfs and similar, graphs, shortest paths

Image generated by ChatGPT 4o.

You are given a two-dimensional maze with a start and end position. Your task is to find the fastest way to get from the start to the end position. The fastest way is to make the minimum number of steps where one step is going left, right, up, or down. Of course, you cannot walk through walls.

There is, however, a catch: If you make more than three steps in the same direction, you lose balance and fall down. Therefore, it is forbidden to make more than three consecutive steps in the same direction. It is okay to walk three times to the right, then one step to the left, and then again three steps to the right. This has the same effect as taking five steps to the right, but is slower.

Input format:
The first line contains two numbers $$$n$$$ and $$$m$$$, which are the height and width of the maze. This is followed by an ASCII-representation of the maze where $$$\tt{\#}$$$ is a wall, $$$\tt{.}$$$ is an empty space, and $$$\tt S$$$ and $$$\tt T$$$ are the start and end positions.

- $$$12 \leq n\times m \leq 200000$$$.
- $$$3\leq n,m \leq 10000$$$.
- Characters are only $$$\tt{.\#ST}$$$ and there is exactly one $$$\tt{S}$$$ and one $$$\tt{T}$$$.
- The outer borders are only $$$\tt{\#}$$$ (walls).

Output format:
The minimum number of steps to reach the end position from the start position or -1 if that is impossible.

Constraints:
Time limit: 2.0 s
Memory limit: 1024.0 MB

Example input:
7 12
############
#S........T#
#.########.#
#..........#
#..........#
#..#..#....#
############

Example output:
15

Example input:
5 8
########
#......#
#.####.#
#...T#S#
########

Example output:
14

Editorial:
Beautiful Array
Contest: 2024 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 1200
Tags: constructive algorithms, math

Image generated by ChatGPT 4o.

A-Ming's birthday is coming and his friend A-May decided to give him an integer array as a present. A-Ming has two favorite numbers $$$a$$$ and $$$b$$$, and he thinks an array is beautiful if its mean is exactly $$$a$$$ and its median is exactly $$$b$$$. Please help A-May find a beautiful array so her gift can impress A-Ming.

The mean of an array is its sum divided by its length. For example, the mean of array $$$[3, -1, 5, 5]$$$ is $$$12 \div 4 = 3$$$.

The median of an array is its middle element after sorting if its length is odd, or the mean of two middle elements after sorting if its length is even. For example, the median of $$$[1, 1, 2, 4, 8]$$$ is $$$2$$$ and the median of $$$[3, -1, 5, 5]$$$ is $$$(3 + 5) \div 2 = 4$$$.

Note that the mean and median are not rounded to an integer. For example, the mean of array $$$[1, 2]$$$ is $$$1.5$$$.

Input format:
The only line contains two integers $$$a$$$ and $$$b$$$.

- $$$-100 \leq a, b \leq 100$$$.
- The length of the array must be between $$$1$$$ and $$$1000$$$.
- The elements of the array must be integers and their absolute values must not exceed $$$10^6$$$.

Output format:
In the first line, print the length of the array.

In the second line, print the elements of the array.

If there are multiple solutions, you can print any. It can be proved that, under the constraints of the problem, a solution always exists.

Constraints:
Time limit: 1.0 s
Memory limit: 1024.0 MB

Example input:
3 4

Example output:
4
3 -1 5 5

Example input:
-100 -100

Example output:
1
-100

Editorial:
Segmentation Folds
Contest: 2024 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 2400
Tags: brute force, dfs and similar, number theory

Peter loves folding segments. There is a segment on a number line occupying the interval $$$[\ell, r]$$$. Since it is the prime time for folding the segments, Peter decides to fold the segment carefully. In each step, he chooses one of the two following operations whenever possible:

1. Operation $$$\tt{LTR}$$$: he folds the segment from left to right, where $$$\ell$$$ coincides with a point $$$x$$$ ($$$\ell < x \le r$$$) such that $$$\ell+x$$$ is a prime number$$$^{\text{∗}}$$$. When Peter chooses this operation, he always chooses the largest possible value $$$x$$$. Note that the segment occupies the interval $$$[\frac{1}{2}(\ell+x), r]$$$ afterwards.
2. Operation $$$\tt{RTL}$$$: he folds the segment from right to left, where $$$r$$$ coincides with a point $$$x$$$ ($$$\ell \le x < r$$$) such that $$$r+x$$$ is a prime number. When Peter chooses this operation, he always chooses the smallest possible value $$$x$$$. Note that the segment occupies the interval $$$[\ell, \frac{1}{2}(r+x)]$$$ afterwards.

A folding sequence refers to a sequence of operations specified above. Peter wants to fold the segment several times, resulting in the shortest possible interval whose length that cannot be further reduced. The length of an interval $$$[\ell, r]$$$ is defined naturally to be $$$r-\ell$$$. Let's consider the following example. Suppose that we are folding a segment initially occupying the interval $$$[1, 30]$$$. There are three folding sequences that lead to the shortest possible resulting interval, as shown in the following figure.

Please help Peter determine the number of folding sequences such that the resulting interval has a shortest possible length. Output the number modulo $$$998244353$$$.

Input format:
The first line contains an integer $$$t$$$, denoting the number of test cases. In each of the following $$$t$$$ lines, there are two integers $$$\ell$$$ and $$$r$$$.

- $$$1 \le t \le 10$$$
- $$$1 \le \ell < r \le 10^{12}$$$
- $$$r - \ell \le 10^5$$$

Output format:
For each test case, please output a line denoting the number of ways to fold the given segment such that the resulting segment has the shortest possible length, modulo $$$998244353$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 1024.0 MB

Example input:
3
1 30
16 18
142857 240135

Example output:
3
1
63

Editorial:
Grid Game
Contest: 2024 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 3100

Claire loves drawing lines. She receives a sheet of paper with an $$$n \times n$$$ grid and begins drawing "lines" on it. Well—the concept of a "line" here is not what we usually think of. Claire refers each line to be a set of consecutive vertical grid cells. When she draws a line, these cells are all covered with black ink. Initially, all the cells are white, and drawing lines turns some of them black. After drawing a few lines, Claire wonders: how many ways she can color an additional white cell black so that the remaining white cells do not form a single connected component.

Two cells are directly connected if they share an edge. Two cells $$$x$$$ and $$$y$$$ are indirectly connected if there exists a sequence of cells $$$c_0, c_1, \ldots, c_k$$$ with $$$k > 1$$$ such that $$$c_0 = x$$$, $$$c_k = y$$$, and for every $$$i \in \{1, 2, \ldots, k\}$$$ the cells $$$c_i$$$ and $$$c_{i-1}$$$ are directly connected. A set of cells forms a single connected component if each pair of cells in the set is either directly or indirectly connected.

The grid has $$$n$$$ rows and $$$n$$$ columns, both indexed from $$$1$$$ to $$$n$$$. Claire will draw $$$q$$$ lines. The $$$i$$$-th line is drawn in the $$$y_i$$$-th column, from the $$$s_i$$$-th row to the $$$f_i$$$-th row, where $$$s_i \leq f_i$$$ for each $$$i \in \{1, 2, \ldots, q\}$$$. Note that the cells that are passed by at least one of the $$$q$$$ lines are colored black. The following figure shows an example of a $$$20\times 20$$$ grid with $$$q=67$$$ lines. The grid cells marked with red star symbols refer to the cells such that, if Claire colors that cell black, all white cells no longer form a single connected component.

You may assume that, after drawing the $$$q$$$ lines, the remaining white cells form a single connected component with at least three white cells.

Input format:
The first line contains exactly one integer $$$t$$$, indicating the number of test cases. For each test case, it begins with a line containing exactly two integers $$$n$$$ and $$$q$$$. This indicates that the grid is $$$n$$$ by $$$n$$$ and that Claire draws $$$q$$$ lines on it. Then $$$q$$$ lines follow. For each $$$i \in \{1, 2, \ldots, q\}$$$, the $$$i$$$-th line among the $$$q$$$ lines contains exactly three integers $$$y_i$$$, $$$s_i$$$, and $$$f_i$$$.

- $$$1\le t \le 125$$$
- $$$2\leq n \leq 10^9$$$
- $$$q\ge 1$$$; the sum of all $$$q$$$ values is at most $$$10^5$$$.
- $$$1\leq y_i \leq n$$$
- $$$1\leq s_i \leq f_i \leq n$$$
- There are at least three white cells and all white cells form a connected component.

Output format:
Print an integer on a line, indicating how many ways Claire can color an additional white cell black so that the remaining white cells do not form a single connected component.

Constraints:
Time limit: 4.0 s
Memory limit: 1024.0 MB

Example input:
2
3 1
2 1 2
5 2
2 1 4
4 2 5

Example output:
5
15

Editorial:
Sheet Music
Contest: 2024 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 2300
Tags: combinatorics, dp, math

Image generated by ChatGPT 4o.

Alice likes singing. As a singing enthusiast, Alice has listened to countless songs and has tried singing them many times. However, occasionally, some songs make Alice feel bored. After some research, Alice believes that this is because even though the songs she chose are all different, due to her instinctive preference, they all turn out to be musically similar to one another.

To thoroughly analyze this, Alice decided to study the sheet music of the songs. For convenience, Alice represented a song of length $$$n$$$ as an integer sequence $$$a_1, a_2, \ldots, a_n$$$, where $$$a_i$$$ is the pitch of the $$$i$$$-th note. Then she defined the musical equivalence between songs. Two songs $$$a_1, a_2, \ldots, a_n$$$ and $$$b_1, b_2, \ldots, b_n$$$ of length $$$n$$$ are musically equivalent if for all $$$1\leq i<n$$$, both $$$a_i, a_{i+1}$$$ and $$$b_{i}, b_{i+1}$$$ have the same pitch relationship. More specifically, $$$a_i, a_{i+1}$$$ and $$$b_i, b_{i+1}$$$ have the same pitch relationship if either

- $$$a_i < a_{i + 1}$$$ and $$$b_i < b_{i + 1}$$$,
- $$$a_i = a_{i + 1}$$$ and $$$b_i = b_{i + 1}$$$, or
- $$$a_i > a_{i + 1}$$$ and $$$b_i > b_{i + 1}$$$.

Having practiced consistently for a long time, Alice is able to sing any note in the range of $$$[1, k]$$$. She wants to know how many different songs of length $$$n$$$ within her range there are, if we treat musically equivalent songs as the same one. Can you help her calculate the number?

Since the answer might be large, print the answer modulo $$$998244353$$$.

Input format:
The only line contains two integers $$$n, k$$$.

- $$$1\leq n\leq 10^6$$$
- $$$1\leq k \leq 10^9$$$

Output format:
Output the number of different songs modulo $$$998244353$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 1024.0 MB

Example input:
3 2

Example output:
7

Example input:
5 3

Example output:
67

Editorial:
Auto Complete
Contest: 2024 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 2300
Tags: binary search, data structures, hashing, implementation, sortings, strings, trees

You are designing a snazzy new text editor, and you want to add a nifty auto-complete feature to help users save time. Here is how it will work: if a user types "App", your editor will magically suggest the word "Application"! Even better, users can personalize the words that auto-complete in your editor.

Your editor will support 4 kinds of operations (Let's say the current text in your editor is $$$t$$$):

1. Add an auto complete pattern $$$p_i$$$.
2. Delete an auto complete pattern $$$p_i$$$.
3. Append a string $$$s$$$ to the end of $$$t$$$.
4. Delete $$$c$$$ characters from the end of $$$t$$$. Note that if $$$c$$$ is larger then the length of $$$t$$$, delete all the characters from $$$t$$$.

After each action, your editor should suggest an auto-complete candidate $$$i$$$ that matches the following criteria:

1. The string $$$p_i$$$ has a prefix equal to $$$t$$$.
2. If there are multiple $$$p_i$$$, pick the longest one.
3. If there are still multiple $$$p_i$$$, pick the one with the smallest lexicographic order.
4. If there are still multiple $$$p_i$$$, pick the one with the smallest ID.

For example, let us say we have three candidates: "alice", "bob", and "charlie", with ID 1, 2, and 3. At first, there is nothing on the screen, so "charlie" (3) should be suggested because it is the longest. Then, let us say the user types "b". You should suggest "bob" (2) because it is the only one that starts with "b". Finally, let us say the user type "body". You should print -1 because there is no matched pattern.

Input format:
The first line contains an integer $$$n$$$, followed by $$$n$$$ lines, with each line containing an action.

There are four types of actions:

1. $$$i$$$ $$$p_i$$$
2. $$$i$$$
3. $$$s$$$
4. $$$c$$$

- $$$1 \leq n \leq 10^6$$$
- The total number of characters in all $$$p_i$$$ and $$$s$$$ does not exceed $$$2\times 10^6$$$.
- $$$1 \leq c \leq 2\times 10^6$$$
- The strings $$$p_i$$$ and $$$s$$$ may contain any printable characters, excluding all space characters (ASCII number in the range from $$$33$$$ to $$$126$$$).
- The ID $$$i$$$ for each add operation is unique.
- The ID $$$i$$$ for each delete is guaranteed to be valid.
- Each ID $$$i$$$ satisfies $$$0\le i \le n$$$.

Output format:
The program should output $$$n$$$ lines. For each action, output an integer $$$i$$$, which means that after the action, $$$p_i$$$ is the suggested auto complete candidate. If there is no $$$p_i$$$ that matches the requirement, output -1.

Constraints:
Time limit: 4.0 s
Memory limit: 1024.0 MB

Example input:
6
add 1 pattern1_alice
add 2 pattern2_bob
add 3 pattern3_charlie
append pattern
append 2_bobabc
backspace 3

Example output:
1
1
3
3
-1
2

Example input:
6
append pattern
add 1 pattern1_alice____
add 2 pattern2_bob______
add 3 pattern3_charlie__
delete 1
delete 2

Example output:
-1
1
1
1
2
3

Editorial:
Bottle Arrangement
Contest: 2024 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 2700
Tags: data structures, divide and conquer, dp, dsu, greedy

Image generated by ChatGPT 4o.

Mayaw works in a renowned Epah (aboriginal Taiwanese millet wine; Epah is the Pangcah term for aboriginal Taiwanese millet wine, named in the language of the Pangcah people, the largest Indigenous group in Taiwan) bar in the Fata'an Village. To showcase the depth of its collections, the bar has a two-row wine rack where each row can fit exactly $$$n$$$ bottles. There are already $$$n$$$ bottles placed on the back row of the rack, where the $$$i$$$-th bottle from left has height $$$a_i$$$. The owner of the bar has another $$$n$$$ bottles with distinct heights $$$b_1, \ldots, b_n$$$ that he would like Mayaw to put on the first row. To ensure that all bottles on the rack are visible, the owner requires that each bottle on the back row should not be blocked by the one put in front of it. That is, if a bottle of height $$$h$$$ is put on the $$$i$$$-th spot (from left) in the first row, then $$$h$$$ must be less than $$$a_i$$$. However, not all such arrangements are good for the owner. To pay tributes to the Maxi Mountain nearby, he additionally demands that the bottles in the front row should display a mountain-like shape. In particular, the heights of the bottles, when listing from left to right, should form a sequence that is first (non-strictly) increasing and then (non-strictly) decreasing.

Unfortunately, sometimes it is impossible to achieve owner's requirements. That is why Mayaw is also allowed to slightly reduce a bottle's height by removing its cap that has a height of $$$1$$$. In other words, after the removal of the cap, the height of the bottle decreases by exactly $$$1$$$. Of course, exposing the Epah inside the bottle to the open air is detrimental to its quality, and therefore it is desirable to remove as few bottle caps as possible.

Can you help Mayaw determine the minimum number of caps needed to be removed so that he can arrange the bottles in a way that satisfies the owner's requirements? Note that the positions of the bottles in the back row are fixed and Mayaw is not allowed to modify them.

Input format:
The first line contains an integer $$$n$$$ which represents the number of bottles in each row. The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$, the height of the bottles in the back row. The third line contains $$$n$$$ distinct integers $$$b_1, \ldots, b_n$$$, the height of the bottles in the front row.

- $$$1 \leq n \leq 5 \times 10^5$$$
- $$$1 \leq a_i, b_i \leq 10^9$$$
- All $$$b_i$$$'s are distinct.

Output format:
Output the minimum number of bottle caps needed to be removed so that Mayaw can arrange the bottles in the desired way. If it is impossible to achieve that (regardless of the number of caps removed), output -1 instead.

Constraints:
Time limit: 5.0 s
Memory limit: 1024.0 MB

Example input:
5
2 4 6 5 4
1 2 3 4 5

Example output:
0

Example input:
5
2 3 6 5 4
1 2 3 4 5

Example output:
0

Editorial: