1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Building Castle
Contest: 2024 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 2900

A-Ju has a gorgeous castle in which she often enjoys living. However, she gets tired of living in the castle for a long time. Thus, she decides to rebuild her castle into some specific shape to make her it more beautiful.

Let's say we represent A-Ju's castle as a 2D convex polygon$$$^{\text{∗}}$$$ on the 2D plane. A-Ju aims to rebuild her castle into a point symmetric convex polygon. Here, a polygon is point symmetric if there exists a center $$$c$$$ such that for every point $$$p$$$ in the polygon, the reflection $$$p^\prime$$$ of $$$p$$$ across $$$c$$$ is also in the polygon.

While designing an arbitrary point symmetric convex polygon shape is easy, the cost of rebuilding is very high. After some estimation, A-Ju found that the cost of rebuilding is proportional to the area of the symmetric difference$$$^{\text{†}}$$$ between the original castle and the new castle. See the following figure for an example:

In the example above, A-Ju's castle is a shape of the convex polygon formed by points $$$(3, 7) - (2, 1) - (6, 3)$$$. After rebuilding her castle into the shape of the polygon formed by $$$(3, 7) - (\frac{7}{3}, 3) - (\frac{13}{3}, \frac{1}{3}) - (5, \frac{13}{3})$$$, the area of the symmetric difference between these two polygons will be $$$\frac{11}{3}$$$. The difference can be calculated as the sum of the additional area (represented by the green grid region) and the shaved area (represented by the red line region).

Please write a program that helps A-Ju design a blueprint of the new castle, such that the area of the symmetric difference between the original one and the new one is minimized. You only need to output the minimum value since A-Ju wants to estimate her cost first.

Input format:
The first line contains an integer $$$n$$$, representing the number of vertices of the polygon that forms A-Ju's castle.

Then, $$$n$$$ lines follow, the $$$i$$$-th of which contains two integers $$$x_i, y_i$$$, representing the coordinates of the $$$i$$$-th vertex. The vertices are given in a counterclockwise order.

- $$$3\leq n\leq 500$$$
- $$$|x_i|, |y_i|\leq 10^4$$$
- The vertices are given in a counterclockwise order and are guaranteed to form a convex polygon without three collinear points.

Output format:
Print a single real number in one line, representing the minimum area of the symmetric difference between the original castle and the new castle.

Your answer will be accepted if the absolute or relative error does not exceed $$$10^{-4}$$$. Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is considered correct if $$$\frac{|a-b|}{\max(1,|b|)}\le 10^{-4}$$$.

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

Example input:
3
2 1
6 3
3 7

Example output:
3.666666666667

Example input:
4
0 0
5 0
5 5
0 5

Example output:
0.000000000000

Editorial:
Selection Sort
Contest: 2024 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 2000
Tags: binary search, data structures, greedy, two pointers

Every student enrolled in the algorithms course is required to submit an assignment this week. The task is to implement an $$$O(n^2)$$$-time algorithm to sort $$$n$$$ given integers in non-decreasing order. Alice has already completed her assignment, and her implementation is shown below.

While you have access to Alice's code, you prefer not to simply copy it. Instead, you want to use Alice's sorting function as a building block for your own solution. There are two ways as listed below you can utilize her function, but each of them can be applied at most once. The order in which these two operations are invoked can be arbitrary.

- Prefix sort: choose a length $$$i \in \{1, 2, \ldots, n\}$$$ and call $$$\texttt{alicesort(}s, i\texttt{)}$$$. This sorts the first $$$i$$$ elements in the array $$$s$$$.
- Suffix sort: choose a length $$$i \in \{1, 2, \ldots, n\}$$$ and call $$$\texttt{alicesort(}s+n-i, i\texttt{)}$$$. This sorts the last $$$i$$$ elements in the array $$$s$$$.

Due to the time complexity of the sorting algorithm, the cost of performing either a prefix or suffix sort is $$$i^2$$$, where $$$i$$$ is the length of the chosen subarray. Your goal is to determine the minimum cost to sort the input array $$$s$$$ of $$$n$$$ integers in non-decreasing order using Alice's function, following the rules mentioned above.

For example, Let $$$s=[3,2,5,5,4,1]$$$. We can first perform a suffix sort of length $$$4$$$, and the array becomes $$$[3,2,1,4,5,5]$$$. Then, we perform a prefix sort of length $$$3$$$, and the array becomes $$$[1,2,3,4,5,5]$$$, which is a sorted array. The cost is $$$4^2+3^2=25$$$. Here is another example, let $$$s=[4,3,2,1]$$$. We can complete the sorting by performing only a prefix sort of length $$$4$$$, and the cost is $$$4^2=16$$$.

Input format:
The first line contains exactly one integer $$$n$$$ which indicates the number of integers in the array $$$s$$$. The second line contains the $$$n$$$ integers in $$$s=[s_0, s_1, \ldots, s_{n-1}]$$$.

- $$$1 \le n \le 10^6$$$
- For all $$$i$$$ ($$$0\le i < n$$$), $$$0\le s_i < 2^{31}-1$$$.

Output format:
Output an integer on a line, indicating the minimum cost to sort the input array $$$s$$$ of $$$n$$$ integers in non-decreasing order using Alice's function, following the rules mentioned above.

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

Example input:
6
3 2 5 5 4 1

Example output:
25

Example input:
4
4 3 2 1

Example output:
16

Editorial:
Cost of the Array
Contest: Codeforces Round 1002 (Div. 2)
Difficulty rating: 1300
Tags: brute force, constructive algorithms, greedy, math

You are given an array $$$a$$$ of length $$$n$$$ and an even integer $$$k$$$ ($$$2 \le k \le n$$$). You need to split the array $$$a$$$ into exactly $$$k$$$ non-empty subarrays$$$^{\dagger}$$$ such that each element of the array $$$a$$$ belongs to exactly one subarray.

Next, all subarrays with even indices (second, fourth, $$$\ldots$$$, $$$k$$$-th) are concatenated into a single array $$$b$$$. After that, $$$0$$$ is added to the end of the array $$$b$$$.

The cost of the array $$$b$$$ is defined as the minimum index $$$i$$$ such that $$$b_i \neq i$$$. For example, the cost of the array $$$b = [1, 2, 4, 5, 0]$$$ is $$$3$$$, since $$$b_1 = 1$$$, $$$b_2 = 2$$$, and $$$b_3 \neq 3$$$. Determine the minimum cost of the array $$$b$$$ that can be obtained with an optimal partitioning of the array $$$a$$$ into subarrays.

$$$^{\dagger}$$$An array $$$x$$$ is a subarray of an array $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le k \le n \le 2 \cdot 10^5$$$, $$$k$$$ is even) — the length of the array $$$a$$$ and the number of subarrays.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the minimum cost of the array $$$b$$$ that can be obtained.

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

Note:
In the first test case, there are only two possible partitionings: $$$[[1], [1, 1]]$$$ and $$$[[1, 1], [1]]$$$. In either case, $$$b_1 = 1$$$, and $$$b_2 \ne 2$$$, so the cost is $$$2$$$.

In the second test case, there is only one possible partitioning, where $$$b = [1, 2, 3, 4, 0]$$$, so the cost is $$$5$$$ ($$$b_5 = 0 \ne 5$$$).

In the third test case, the following partitioning works: $$$[[1], [1, 1], [2], [2]]$$$. Then $$$b = [1, 1, 2, 0]$$$, and the cost is $$$2$$$.

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

Example output:
2
5
2
1

Editorial:
If $$$k = n$$$, then the partition is unique and the answer can be explicitly found.
In all other cases, the answer does not exceed $$$2$$$. We want the second subarray of our partition to start not with $$$1$$$, while we can ignore all other subarrays, since in this case the answer will be $$$1$$$. We will iterate over the starting position of the second subarray, which can range from $$$2$$$ to $$$n - k + 2$$$. If we encounter only ones in this segment, then the second subarray can consist of $$$2$$$ ones, and the answer will be $$$2$$$.
Scrambled Scrabble
Contest: 2024-2025 ICPC Asia Jakarta Regional Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 1700
Tags: brute force, greedy

You are playing a word game using a standard set of $$$26$$$ uppercase English letters: A — Z. In this game, you can form vowels and consonants as follows.

- The letters A, E, I, O, and U can only form a vowel.
- The letter Y can form either a vowel or a consonant.
- Each of the remaining letters other than A, E, I, O, U, and Y can only form a consonant.
- The string NG can form a single consonant when concatenated together.

Denote a syllable as a concatenation of a consonant, a vowel, and a consonant in that order. A word is a concatenation of one or more syllables.

You are given a string $$$S$$$ and you want to create a word from it. You are allowed to delete zero or more letters from $$$S$$$ and rearrange the remaining letters to form the word. Find the length of the longest word that can be created, or determine if no words can be created.

Input format:
A single line consisting of a string $$$S$$$ ($$$1 \leq |S| \leq 5000$$$). The string $$$S$$$ consists of only uppercase English letters.

Output format:
If a word cannot be created, output 0. Otherwise, output a single integer representing the length of longest word that can be created.

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

Note:
Explanation for the sample input/output #1

A possible longest word is JAKCARTAP, consisting of the syllables JAK, CAR, and TAP.

Explanation for the sample input/output #2

The whole string $$$S$$$ is a word consisting of one syllable which is the concatenation of the consonant NG, the vowel E, and the consonant NG.

Explanation for the sample input/output #3

The whole string $$$S$$$ is a word consisting of one syllable which is the concatenation of the consonant Y, the vowel Y, and the consonant Y.

Explanation for the sample input/output #4

The whole string $$$S$$$ is a word consisting of two syllables: DAN and GAN.

Example input:
ICPCJAKARTA

Example output:
9

Example input:
NGENG

Example output:
5

Editorial:
ICPC Square
Contest: 2024-2025 ICPC Asia Jakarta Regional Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 2000
Tags: math, number theory

ICPC Square is a hotel provided by the ICPC Committee for the accommodation of the participants. It consists of $$$N$$$ floors (numbered from $$$1$$$ to $$$N$$$). This hotel has a very unique elevator. If a person is currently at floor $$$x$$$, by riding the elevator once, they can go to floor $$$y$$$ if and only if $$$y$$$ is a multiple of $$$x$$$ and $$$y - x \leq D$$$.

You are currently at floor $$$S$$$. You want to go to the highest possible floor by riding the elevator zero or more times. Determine the highest floor you can reach.

Input format:
A single line consisting of three integers $$$N$$$ $$$D$$$ $$$S$$$ ($$$2 \leq N \leq 10^{12}; 1 \leq D \leq N - 1; 1 \leq S \leq N$$$).

Output format:
Output a single integer representing the highest floor you can reach by riding the elevator zero or more times.

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

Note:
Explanation for the sample input/output #1

First, ride the elevator from floor $$$3$$$ to floor $$$15$$$. This is possible because $$$15$$$ is a multiple of $$$3$$$ and $$$15 - 3 \leq 35$$$. Then, ride the elevator from floor $$$15$$$ to floor $$$30$$$. This is possible because $$$30$$$ is a multiple of $$$15$$$ and $$$30 - 15 \leq 35$$$. Finally, ride the elevator from floor $$$30$$$ to floor $$$60$$$. This is possible because $$$60$$$ is a multiple of $$$30$$$ and $$$60 - 30 \leq 35$$$.

Example input:
64 35 3

Example output:
60

Example input:
2024 2023 1273

Example output:
1273

Editorial:
Saraga
Contest: 2024-2025 ICPC Asia Jakarta Regional Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 1400
Tags: greedy, strings

The word saraga is an abbreviation of sarana olahraga, an Indonesian term for a sports facility. It is created by taking the prefix sara of the word sarana and the suffix ga of the word olahraga. Interestingly, it can also be created by the prefix sa of the word sarana and the suffix raga of the word olahraga.

An abbreviation of two strings $$$S$$$ and $$$T$$$ is interesting if there are at least two different ways to split the abbreviation into two non-empty substrings such that the first substring is a prefix of $$$S$$$ and the second substring is a suffix of $$$T$$$.

You are given two strings $$$S$$$ and $$$T$$$. You want to create an interesting abbreviation of strings $$$S$$$ and $$$T$$$ with minimum length, or determine if it is impossible to create an interesting abbreviation.

Input format:
The first line consists of a string $$$S$$$ ($$$1 \leq |S| \leq 200\,000$$$).

The second line consists of a string $$$T$$$ ($$$1 \leq |T| \leq 200\,000$$$).

Both strings $$$S$$$ and $$$T$$$ only consist of lowercase English letters.

Output format:
If it is impossible to create an interesting abbreviation, output -1.

Otherwise, output a string in a single line representing an interesting abbreviation of strings $$$S$$$ and $$$T$$$ with minimum length. If there are multiple solutions, output any of them.

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

Note:
Explanation for the sample input/output #1

You can split saga into s and aga, or sa and ga. The abbreviation saraga is interesting, but saga has a smaller length.

Explanation for the sample input/output #2

The abbreviation belhijau is also interesting with minimum length, so it is another valid solution.

Example input:
sarana
olahraga

Example output:
saga

Example input:
berhiber
wortelhijau

Example output:
berhijau

Editorial:
Narrower Passageway
Contest: 2024-2025 ICPC Asia Jakarta Regional Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 2700
Tags: combinatorics, data structures

You are a strategist of The ICPC Kingdom. You received an intel that there will be monster attacks on a narrow passageway near the kingdom. The narrow passageway can be represented as a grid with $$$2$$$ rows (numbered from $$$1$$$ to $$$2$$$) and $$$N$$$ columns (numbered from $$$1$$$ to $$$N$$$). Denote $$$(r, c)$$$ as the cell in row $$$r$$$ and column $$$c$$$. A soldier with a power of $$$P_{r, c}$$$ is assigned to protect $$$(r, c)$$$ every single day.

It is known that the passageway is very foggy. Within a day, each column in the passageway has a $$$50\%$$$ chance of being covered in fog. If a column is covered in fog, the two soldiers assigned to that column are not deployed that day. Otherwise, the assigned soldiers will be deployed.

Define a connected area $$$[u, v]$$$ ($$$u \leq v$$$) as a maximal set of consecutive columns from $$$u$$$ to $$$v$$$ (inclusive) such that each column in the set is not covered in fog. The following illustration is an example of connected areas. The grayed cells are cells covered in fog. There are $$$4$$$ connected areas: $$$[1, 2]$$$, $$$[4, 6]$$$, $$$[9, 9]$$$, and $$$[11, 11]$$$.

The strength of a connected area $$$[u, v]$$$ can be calculated as follows. Let $$$m_1$$$ and $$$m_2$$$ be the maximum power of the soldiers in the first and second rows of the connected area, respectively. Formally, $$$m_r = \max (P_{r, u}, P_{r, u + 1}, \dots, P_{r, v})$$$ for $$$r \in \{ 1, 2\}$$$. If $$$m_1 = m_2$$$, then the strength is $$$0$$$. Otherwise, the strength is $$$\min (m_1, m_2)$$$.

The total strength of the deployment is the sum of the strengths for all connected areas. Determine the expected total strength of the deployment on any single day.

Input format:
The first line consists of an integer $$$N$$$ ($$$1 \leq N \leq 100\,000$$$).

Each of the next two lines consists of $$$N$$$ integers $$$P_{r, c}$$$ ($$$1 \leq P_{r, c} \leq 200\,000$$$).

Output format:
Let $$$M = 998\,244\,353$$$. It can be shown that the expected total strength can be expressed as an irreducible fraction $$$\frac{x}{y}$$$ such that $$$x$$$ and $$$y$$$ are integers and $$$y \not\equiv 0 \pmod{M}$$$. Output an integer $$$k$$$ in a single line such that $$$0 \leq k < M$$$ and $$$k \cdot y \equiv x \pmod{M}$$$.

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

Note:
Explanation for the sample input/output #1

There are $$$8$$$ possible scenarios for the passageway.

Each scenario is equally likely to happen. Therefore, the expected total strength is $$$(0 + 5 + 10 + 5 + 5 + 0 + 5 + 0) / 8 = \frac{15}{4}$$$. Since $$$249\,561\,092 \cdot 4 \equiv 15 \pmod{998\,244\,353}$$$, the output of this sample is $$$249\,561\,092$$$.

Explanation for the sample input/output #2

The expected total strength is $$$\frac{67}{16}$$$.

Example input:
3
8 4 5
5 4 8

Example output:
249561092

Example input:
5
10 20 5 8 5
5 20 7 5 8

Example output:
811073541

Editorial:
Grid Game 3-angle
Contest: 2024-2025 ICPC Asia Jakarta Regional Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 3000
Tags: games, math

Your friends, Anda and Kamu decide to play a game called Grid Game and ask you to become the gamemaster. As the gamemaster, you set up a triangular grid of size $$$N$$$. The grid has $$$N$$$ rows (numbered from $$$1$$$ to $$$N$$$). Row $$$r$$$ has $$$r$$$ cells; the $$$c$$$-th cell of row $$$r$$$ is denoted as $$$(r, c)$$$.

Before the game starts, $$$M$$$ different cells (numbered from $$$1$$$ to $$$M$$$) are chosen: at cell $$$(R_i, C_i)$$$, you add $$$A_i$$$ stones on it. You then give Anda and Kamu an integer $$$K$$$ and commence the game.

Anda and Kamu will take turns alternately with Anda taking the first turn. A player on their turn will do the following.

- Choose a cell $$$(r, c)$$$ with at least one stone on it.
- Remove at least one but at most $$$K$$$ stones from the chosen cell.
- For each cell $$$(x, y)$$$ such that $$$r + 1 \leq x \leq \min(N, r + K)$$$ and $$$c \leq y \leq c + x - r$$$, add zero or more stones but at most $$$K$$$ stones to cell $$$(x, y)$$$.

The following illustrations show all the possible cells in which you can add stones for $$$K = 3$$$. You choose the cell $$$(2, 1)$$$ for the left illustration and the cell $$$(4, 3)$$$ for the right illustration.

A player who is unable to complete their turn (because there are no more stones on the grid) will lose the game, and the opposing player wins. Determine who will win the game if both players play optimally.

Input format:
This problem is a multi-case problem. The first line consists of an integer $$$T$$$ ($$$1 \leq T \leq 100$$$) that represents the number of test cases.

Each test case starts with a single line consisting of three integers $$$N$$$ $$$M$$$ $$$K$$$ ($$$1 \leq N \leq 10^9; 1 \leq M, K \leq 200\,000$$$). Then, each of the next $$$M$$$ lines consists of three integers $$$R_i$$$ $$$C_i$$$ $$$A_i$$$ ($$$1 \leq C_i \leq R_i \leq N; 1 \leq A_1 \leq 10^9$$$). The pairs $$$(R_i, C_i)$$$ are distinct.

The sum of $$$M$$$ across all test cases does not exceed $$$200\,000$$$.

Output format:
For each case, output a string in a single line representing the player who will win the game if both players play optimally. Output Anda if Anda, the first player, wins. Otherwise, output Kamu.

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

Note:
Explanation for the sample input/output #1

For the first case, during the first turn, Anda will remove all the stones from cell $$$(1, 1)$$$ and then add three stones at $$$(2, 1)$$$. The only cell with stones left is now cell $$$(2, 1)$$$ with five stones, so Kamu must remove stones from that cell. No matter how many stones are removed by Kamu, Anda can remove all the remaining stones at $$$(2, 1)$$$ and win the game.

For the second case, Kamu can always mirror whatever move made by Anda until Anda can no longer complete their turn.

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

Example output:
Anda
Kamu
Anda

Editorial:
Missing Separators
Contest: 2024-2025 ICPC Asia Jakarta Regional Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 2200
Tags: dp, sortings, string suffix structures, strings

You have a dictionary, which is a list of distinct words sorted in alphabetical order. Each word consists of uppercase English letters.

You want to print this dictionary. However, there is a bug with the printing system, and all words in the list are printed next to each other without any separators between words. Now, you ended up with a string $$$S$$$ that is a concatenation of all the words in the dictionary in the listed order.

Your task is to reconstruct the dictionary by splitting $$$S$$$ into one or more words. Note that the reconstructed dictionary must consist of distinct words sorted in alphabetical order. Furthermore, you want to maximize the number of words in the dictionary. If there are several possible dictionaries with the maximum number of words, you can choose any of them.

Input format:
A single line consisting of a string $$$S$$$ ($$$1 \leq |S| \leq 5000)$$$. String $$$S$$$ consists of only uppercase English letters.

Output format:
First, output an integer in a single line representing the maximum number of the words in the reconstructed dictionary. Denote this number as $$$n$$$.

Then, output $$$n$$$ lines, each containing a single string representing the word. The words must be distinct, and the list must be sorted alphabetically. The concatenation of the words in the listed order must equal $$$S$$$.

If there are several possible dictionaries with the maximum number of words, output any of them.

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

Example input:
ABACUS

Example output:
4
A
BA
C
US

Example input:
AAAAAA

Example output:
3
A
AA
AAA

Editorial: