1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Reconstruction
Contest: Codeforces Global Round 26
Difficulty rating: 2500
Tags: brute force, dp, math

There is a hidden array $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$ whose elements are integers between $$$-m$$$ and $$$m$$$, inclusive.

You are given an array $$$b_1, b_2, \ldots, b_n$$$ of length $$$n$$$ and a string $$$s$$$ of length $$$n$$$ consisting of the characters $$$\texttt{P}$$$, $$$\texttt{S}$$$, and $$$\texttt{?}$$$.

For each $$$i$$$ from $$$1$$$ to $$$n$$$ inclusive, we must have:

- If $$$s_i = \texttt{P}$$$, $$$b_i$$$ is the sum of $$$a_1$$$ through $$$a_i$$$.
- If $$$s_i = \texttt{S}$$$, $$$b_i$$$ is the sum of $$$a_i$$$ through $$$a_n$$$.

Output the number of ways to replace all $$$\texttt{?}$$$ in $$$s$$$ with either $$$\texttt{P}$$$ or $$$\texttt{S}$$$ such that there exists an array $$$a_1, a_2, \ldots, a_n$$$ with elements not exceeding $$$m$$$ by absolute value satisfying the constraints given by the array $$$b_1, b_2, \ldots, b_n$$$ and the string $$$s$$$.

Since the answer may be large, output it modulo $$$998\,244\,353$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 2 \cdot 10^3$$$, $$$2 \leq m \leq 10^{9}$$$) — the length of the hidden array $$$a_1, a_2, \ldots, a_n$$$ and the maximum absolute value of an element $$$a_i$$$.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$ consisting of characters $$$\texttt{P}$$$, $$$\texttt{S}$$$, and $$$\texttt{?}$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$|b_i| \leq m \cdot n$$$).

The sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^3$$$.

Output format:
For each test case, output a single integer — the number of ways to replace all $$$\texttt{?}$$$ in $$$s$$$ with either $$$\texttt{P}$$$ or $$$\texttt{S}$$$ that result in the existence of a valid array $$$a_1, a_2, \ldots, a_n$$$, modulo $$$998\,244\,353$$$.

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

Note:
In the first test case, we can see that the following array satisfies all constraints, thus the answer is $$$1$$$:

1. $$$\texttt{P}$$$ — $$${[\color{red}{\textbf{1}},3,4,2]}$$$: sum of $$$1$$$.
2. $$$\texttt{S}$$$ — $$${[1,\color{red}{\textbf{3},4,2}]}$$$: sum of $$$9$$$.
3. $$$\texttt{P}$$$ — $$${[\color{red}{1,3,\textbf{4}},2]}$$$: sum of $$$8$$$.
4. $$$\texttt{P}$$$ — $$${[\color{red}{1,3,4,\textbf{2}}]}$$$: sum of $$$10$$$.

In the second test case, it can be shown that no array $$$a$$$ with all $$$|a_i| \leq m = 10^9$$$ satisfies all constraints.

Example input:
6
4 10
PSPP
1 9 8 10
4 1000000000
????
1 1 1 4000000000
8 1000000000
?P?SSP?P
-857095623 -1424391899 -851974476 673437144 471253851 -543483033 364945701 -178537332
4 7
PPSS
4 2 1 3
9 20
?????????
1 2 3 4 5 6 7 8 9
3 1000000000
P??
-145463248 -974068460 -1287458396

Example output:
1
0
2
1
14
1

Editorial:
Magic Trick II
Contest: Codeforces Global Round 26
Difficulty rating: 3200
Tags: constructive algorithms, implementation, sortings

The secret behind Oscar's first magic trick has been revealed! Because he still wants to impress Lura, he comes up with a new idea: he still wants to sort a permutation $$$p_1, p_2, \ldots, p_n$$$ of $$$[1, 2, \ldots, n]$$$.

This time, he chooses an integer $$$k$$$. He wants to sort the permutation in non-decreasing order using the following operation several times:

1. Pick a continuous subarray of length $$$k$$$ and remove it from $$$p$$$.
2. Insert the continuous subarray back into $$$p$$$ at any position (perhaps, in the very front or the very back).

To be as impressive as possible, Oscar would like to choose the maximal value of $$$k$$$ such that he can sort his permutation. Please help him find the maximal $$$k$$$ as well as a sequence of operations that will sort the permutation. You don't need to minimize the number of operations, but you are allowed to use at most $$$5n^2$$$ operations.

We have a proof that, for the maximal $$$k$$$ such that you can sort the permutation in any number of operations, you can also sort it in at most $$$5n^2$$$ operations.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$5 \leq n \leq 10^3$$$) — the length of the permutation.

The second line of each test case contains a permutation $$$p_1, p_2, \ldots, p_n$$$ of $$$[1, 2, \ldots, n]$$$.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^3$$$.

Output format:
For each test case, first output the chosen value of $$$k$$$ on a new line ($$$1 \leq k \leq n$$$).

Then, output a single integer $$$m$$$ — the number of operations used ($$$0 \leq m \leq 5n^2$$$).

Then, on each of the next $$$m$$$ lines, output the operations denoted by two integers $$$i$$$ and $$$j$$$ ($$$1 \leq i, j \leq n - k + 1$$$), representing an operation where you remove the subarray starting from index $$$i$$$ and replace it back into $$$p$$$ at index $$$j$$$.

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

Note:
In the first test case, it is enough to move the last four numbers to the front.

In the second test case, it can be shown that we cannot have $$$k = 4$$$ or $$$k = 5$$$. With $$$k = 3$$$, we can move the first three numbers to the end, and then the middle three to the front to sort the permutation.

In the third test case, the permutation is already sorted. We can have $$$k = 6$$$ and use no operations.

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

Example output:
4
1
2 1
3
2
1 3
2 1
6
0

Editorial:
Tower Capturing
Contest: Codeforces Global Round 26
Difficulty rating: 3300
Tags: combinatorics, dp, geometry

There are $$$n$$$ towers at $$$n$$$ distinct points $$$(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$$$, such that no three are collinear and no four are concyclic. Initially, you own towers $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$, and you want to capture all of them. To do this, you can do the following operation any number of times:

- Pick two towers $$$P$$$ and $$$Q$$$ you own and one tower $$$R$$$ you don't own, such that the circle through $$$P$$$, $$$Q$$$, and $$$R$$$ contains all $$$n$$$ towers inside of it.
- Afterwards, capture all towers in or on triangle $$$\triangle PQR$$$, including $$$R$$$ itself.

Count the number of attack plans of minimal length. Note that it might not be possible to capture all towers, in which case the answer is $$$0$$$.

Since the answer may be large, output it modulo $$$998\,244\,353$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 250$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$4 \leq n \leq 100$$$) — the number of towers.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^4 \leq x_i, y_i \leq 10^4$$$) — the location of the $$$i$$$-th tower. Initially, you own towers $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$.

All towers are at distinct locations, no three towers are collinear, and no four towers are concyclic.

The sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

Output format:
For each test case, output a single integer — the number of attack plans of minimal length after which you capture all towers, modulo $$$998\,244\,353$$$.

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

Note:
In the first test case, there is only one possible attack plan of shortest length, shown below.

- Use the operation with $$$P =$$$ tower $$$1$$$, $$$Q =$$$ tower $$$2$$$, and $$$R =$$$ tower $$$5$$$. The circle through these three towers contains all towers inside of it, and as a result towers $$$3$$$ and $$$5$$$ are captured.
- Use the operation with $$$P =$$$ tower $$$5$$$, $$$Q =$$$ tower $$$1$$$, and $$$R =$$$ tower $$$4$$$. The circle through these three towers contains all towers inside of it, and as a result tower $$$4$$$ is captured.

In the second case, for example, you can never capture the tower at $$$(3, 10\,000)$$$.

Example input:
3
5
1 1
2 5
3 3
4 2
5 4
6
1 1
3 3
1 2
2 1
3 10000
19 84
7
2 7
-4 -3
-3 6
3 1
-5 2
1 -4
-1 7

Example output:
1
0
10

Editorial:
Planets
Contest: Codeforces Round 823 (Div. 2)
Difficulty rating: 800
Tags: data structures, greedy, sortings

One day, Vogons wanted to build a new hyperspace highway through a distant system with $$$n$$$ planets. The $$$i$$$-th planet is on the orbit $$$a_i$$$, there could be multiple planets on the same orbit. It's a pity that all the planets are on the way and need to be destructed.

Vogons have two machines to do that.

- The first machine in one operation can destroy any planet at cost of $$$1$$$ Triganic Pu.
- The second machine in one operation can destroy all planets on a single orbit in this system at the cost of $$$c$$$ Triganic Pus.

Vogons can use each machine as many times as they want.

Vogons are very greedy, so they want to destroy all planets with minimum amount of money spent. Can you help them to know the minimum cost of this project?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then the test cases follow.

Each test case consists of two lines.

The first line contains two integers $$$n$$$ and $$$c$$$ ($$$1 \le n, c \le 100$$$) — the number of planets and the cost of the second machine usage.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$), where $$$a_i$$$ is the orbit of the $$$i$$$-th planet.

Output format:
For each test case print a single integer — the minimum cost of destroying all planets.

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

Note:
In the first test case, the cost of using both machines is the same, so you can always use the second one and destroy all planets in orbit $$$1$$$, all planets in orbit $$$2$$$, all planets in orbit $$$4$$$, all planets in orbit $$$5$$$.

In the second test case, it is advantageous to use the second machine for $$$2$$$ Triganic Pus to destroy all the planets in orbit $$$2$$$, then destroy the remaining two planets using the first machine.

In the third test case, you can use the first machine twice or the second machine once.

In the fourth test case, it is advantageous to use the first machine twice.

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

Example output:
4
4
2
2

Example input:
1
1 100
1

Example output:
1

Editorial:
To solve the problem, it was enough to count the number of planets with the same orbits $$$cnt_i$$$ and sum up the answers for the orbits separately. For one orbit, it is advantageous either to use the second machine once and get the cost $$$c$$$, or to use only the first one and get the cost equal to $$$cnt_i$$$.
Minimum Notation
Contest: Codeforces Round 823 (Div. 2)
Difficulty rating: 1200
Tags: data structures, greedy, math, sortings

You have a string $$$s$$$ consisting of digits from $$$0$$$ to $$$9$$$ inclusive. You can perform the following operation any (possibly zero) number of times:

- You can choose a position $$$i$$$ and delete a digit $$$d$$$ on the $$$i$$$-th position. Then insert the digit $$$\min{(d + 1, 9)}$$$ on any position (at the beginning, at the end or in between any two adjacent digits).

What is the lexicographically smallest string you can get by performing these operations?

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ of the same length if and only if the following holds:

- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a smaller digit than the corresponding digit in $$$b$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then the test cases follow.

Each test case consists of a single line that contains one string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$) — the string consisting of digits. Please note that $$$s$$$ is just a string consisting of digits, so leading zeros are allowed.

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

Output format:
Print a single string — the minimum string that is possible to obtain.

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

Note:
In the first test case:

- Delete $$$8$$$ and insert $$$9$$$ at the end of the notation. The resulting notation is $$$04299$$$.
- Delete $$$4$$$ and insert $$$5$$$ in the $$$3$$$-rd position of the notation. The resulting notation is $$$02599$$$.

Nothing needs to be done in the second and third test cases.

Example input:
4
04829
9
01
314752277691991

Example output:
02599
9
01
111334567888999

Editorial:
We leave all suffix minimums by the digits $$$mn_i$$$ (digits less than or equal to the minimum among the digits to the right of them), remove the rest and replace them with $$$\min{(d + 1, 9)}$$$ (using the described operations) and add to lexicographically minimum order on the right (due to the appropriate order of operations, this is possible). The suffix minimums $$$mn_i$$$ should be left, because no matter what digit we leave after $$$mn_i$$$, it will be no less than $$$mn_i$$$, and therefore will not improve the answer. The rest must be removed at the end with operations, since there is a number to the right less than this one, i.e. if you remove everything before it (put $$$mn_i$$$ at the current position), the answer will become less than if you leave another digit at this position.
Almost Sorted
Contest: Codeforces Round 823 (Div. 2)
Difficulty rating: 2700
Tags: bitmasks, data structures, dp

You are given a permutation $$$p$$$ of length $$$n$$$ and a positive integer $$$k$$$. Consider a permutation $$$q$$$ of length $$$n$$$ such that for any integers $$$i$$$ and $$$j$$$, where $$$1 \le i < j \le n$$$, we have $$$$$$p_{q_i} \le p_{q_j} + k.$$$$$$

Find the minimum possible number of inversions in a permutation $$$q$$$.

A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

An inversion in a permutation $$$a$$$ is a pair of indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$) such that $$$i < j$$$, but $$$a_i > a_j$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 5000$$$, $$$1 \le k \le 8$$$).

The second line contains $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$).

Output format:
Print the minimum possible number of inversions in the permutation $$$q$$$.

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

Note:
In the first example, the only permutation is $$$q = [1]$$$ ($$$0$$$ inversions). Then $$$p_{q_1} = 1$$$.

In the second example, the only permutation with $$$1$$$ inversion is $$$q = [1, 3, 2]$$$. Then $$$p_{q_1} = 2$$$, $$$p_{q_2} = 1$$$, $$$p_{q_3} = 3$$$.

In the third example, one of the possible permutations with $$$6$$$ inversions is $$$q = [3, 4, 5, 1, 2]$$$. Then $$$p_{q_1} = 3$$$, $$$p_{q_2} = 2$$$, $$$p_{q_3} = 1$$$, $$$p_{q_4} = 5$$$, $$$p_{q_5} = 4$$$.

Example input:
1 1
1

Example output:
0

Example input:
3 1
2 3 1

Example output:
1

Editorial:
Let's build a permutation $$$q$$$ from left to right. If the current prefix contains the number $$$i$$$, let's call the element $$$p_i$$$ used, otherwise — unused. Consider the smallest unused element $$$mn = p_j$$$. All elements greater than $$$mn + k$$$ must also be unused, and all elements less than $$$mn$$$ must be used. Then the current state can be described by the number $$$mn$$$ and the mask, $$$i$$$-th bit of which indicates whether the element with the value $$$mn + i$$$ is used.
Let's solve the problem by dynamic programming: $$$dp[mn][mask]$$$ is the minimum number of inversions. We can continue building a permutation by adding the number $$$i$$$ such that $$$mn \le p_i \le mn + k$$$ and $$$p_i$$$ hasn't been used yet. New inversions can be divided into two types: those formed with indices of elements less than $$$mn$$$ (they can be counted using Fenwick tree) and those formed with indices of elements not less than $$$mn$$$ (but their number is not more than $$$k$$$).
The time complexity is $$$O(n \cdot 2^k \cdot k \cdot (k + \log n))$$$.
Trading Business
Contest: Croc Champ 2012 - Round 2
Difficulty rating: 1200
Tags: greedy, sortings

To get money for a new aeonic blaster, ranger Qwerty decided to engage in trade for a while. He wants to buy some number of items (or probably not to buy anything at all) on one of the planets, and then sell the bought items on another planet. Note that this operation is not repeated, that is, the buying and the selling are made only once. To carry out his plan, Qwerty is going to take a bank loan that covers all expenses and to return the loaned money at the end of the operation (the money is returned without the interest). At the same time, Querty wants to get as much profit as possible.

The system has n planets in total. On each of them Qwerty can buy or sell items of m types (such as food, medicine, weapons, alcohol, and so on). For each planet i and each type of items j Qwerty knows the following:

- aij — the cost of buying an item;
- bij — the cost of selling an item;
- cij — the number of remaining items.

It is not allowed to buy more than cij items of type j on planet i, but it is allowed to sell any number of items of any kind.

Knowing that the hold of Qwerty's ship has room for no more than k items, determine the maximum profit which Qwerty can get.

Input format:
The first line contains three space-separated integers n, m and k (2 ≤ n ≤ 10, 1 ≤ m, k ≤ 100) — the number of planets, the number of question types and the capacity of Qwerty's ship hold, correspondingly.

Then follow n blocks describing each planet.

The first line of the i-th block has the planet's name as a string with length from 1 to 10 Latin letters. The first letter of the name is uppercase, the rest are lowercase. Then in the i-th block follow m lines, the j-th of them contains three integers aij, bij and cij (1 ≤ bij < aij ≤ 1000, 0 ≤ cij ≤ 100) — the numbers that describe money operations with the j-th item on the i-th planet. The numbers in the lines are separated by spaces.

It is guaranteed that the names of all planets are different.

Output format:
Print a single number — the maximum profit Qwerty can get.

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

Note:
In the first test case you should fly to planet Venus, take a loan on 74 units of money and buy three items of the first type and 7 items of the third type (3·6 + 7·8 = 74). Then the ranger should fly to planet Earth and sell there all the items he has bought. He gets 3·9 + 7·9 = 90 units of money for the items, he should give 74 of them for the loan. The resulting profit equals 16 units of money. We cannot get more profit in this case.

Example input:
3 3 10
Venus
6 5 3
7 6 5
8 6 10
Earth
10 9 0
8 6 4
10 9 3
Mars
4 3 0
8 4 12
7 2 5

Example output:
16

Editorial:
Word Cut
Contest: Croc Champ 2012 - Round 2
Difficulty rating: 1700
Tags: dp

Let's consider one interesting word game. In this game you should transform one word into another through special operations.

Let's say we have word w, let's split this word into two non-empty parts x and y so, that w = xy. A split operation is transforming word w = xy into word u = yx. For example, a split operation can transform word "wordcut" into word "cutword".

You are given two words start and end. Count in how many ways we can transform word start into word end, if we apply exactly k split operations consecutively to word start.

Two ways are considered different if the sequences of applied operations differ. Two operation sequences are different if exists such number i (1 ≤ i ≤ k), that in the i-th operation of the first sequence the word splits into parts x and y, in the i-th operation of the second sequence the word splits into parts a and b, and additionally x ≠ a holds.

Input format:
The first line contains a non-empty word start, the second line contains a non-empty word end. The words consist of lowercase Latin letters. The number of letters in word start equals the number of letters in word end and is at least 2 and doesn't exceed 1000 letters.

The third line contains integer k (0 ≤ k ≤ 105) — the required number of operations.

Output format:
Print a single number — the answer to the problem. As this number can be rather large, print it modulo 1000000007 (109 + 7).

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

Note:
The sought way in the first sample is:

ab  →  a|b  →  ba  →  b|a  →  ab

In the second sample the two sought ways are:

- ababab  →  abab|ab  →  ababab
- ababab  →  ab|abab  →  ababab

Example input:
ab
ab
2

Example output:
1

Example input:
ababab
ababab
1

Example output:
2

Editorial:
Playing with Superglue
Contest: Croc Champ 2012 - Round 2
Difficulty rating: 2000
Tags: combinatorics, constructive algorithms

Two players play a game. The game is played on a rectangular board with n × m squares. At the beginning of the game two different squares of the board have two chips. The first player's goal is to shift the chips to the same square. The second player aims to stop the first one with a tube of superglue.

We'll describe the rules of the game in more detail.

The players move in turns. The first player begins.

With every move the first player chooses one of his unglued chips, and shifts it one square to the left, to the right, up or down. It is not allowed to move a chip beyond the board edge. At the beginning of a turn some squares of the board may be covered with a glue. The first player can move the chip to such square, in this case the chip gets tightly glued and cannot move any longer.

At each move the second player selects one of the free squares (which do not contain a chip or a glue) and covers it with superglue. The glue dries long and squares covered with it remain sticky up to the end of the game.

If, after some move of the first player both chips are in the same square, then the first player wins. If the first player cannot make a move (both of his chips are glued), then the second player wins. Note that the situation where the second player cannot make a move is impossible — he can always spread the glue on the square from which the first player has just moved the chip.

We will further clarify the case where both chips are glued and are in the same square. In this case the first player wins as the game ends as soon as both chips are in the same square, and the condition of the loss (the inability to move) does not arise.

You know the board sizes and the positions of the two chips on it. At the beginning of the game all board squares are glue-free. Find out who wins if the players play optimally.

Input format:
The first line contains six integers n, m, x1, y1, x2, y2 — the board sizes and the coordinates of the first and second chips, correspondingly (1 ≤ n, m ≤ 100; 2 ≤ n × m; 1 ≤ x1, x2 ≤ n; 1 ≤ y1, y2 ≤ m). The numbers in the line are separated by single spaces.

It is guaranteed that the chips are located in different squares.

Output format:
If the first player wins, print "First" without the quotes. Otherwise, print "Second" without the quotes.

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

Example input:
1 6 1 2 1 6

Example output:
First

Example input:
6 5 4 3 2 1

Example output:
First

Editorial: