1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Largest Subsequence
Contest: Codeforces Round 915 (Div. 2)
Difficulty rating: 1400
Tags: greedy, strings

Given is a string $$$s$$$ of length $$$n$$$. In one operation you can select the lexicographically largest$$$^\dagger$$$ subsequence of string $$$s$$$ and cyclic shift it to the right$$$^\ddagger$$$.

Your task is to calculate the minimum number of operations it would take for $$$s$$$ to become sorted, or report that it never reaches a sorted state.

$$$^\dagger$$$A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- In the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

$$$^\ddagger$$$By cyclic shifting the string $$$t_1t_2\ldots t_m$$$ to the right, we get the string $$$t_mt_1\ldots t_{m-1}$$$.

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 a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the string $$$s$$$.

The second line of each test case contains a single string $$$s$$$ of length $$$n$$$, consisting of lowercase English letters.

It is guaranteed that 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 number of operations required to make $$$s$$$ sorted, or $$$-1$$$ if it's impossible.

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

Note:
In the first test case, the string $$$s$$$ is already sorted, so we need no operations.

In the second test case, doing one operation, we will select cb and cyclic shift it. The string $$$s$$$ is now abc which is sorted.

In the third test case, $$$s$$$ cannot be sorted.

In the fourth test case we will perform the following operations:

- The lexicographically largest subsequence is zca. Then $$$s$$$ becomes abzc.
- The lexicographically largest subsequence is zc. Then $$$s$$$ becomes abcz. The string becomes sorted.

Thus, we need $$$2$$$ operations.

Example input:
6
5
aaabc
3
acb
3
bac
4
zbca
15
czddeneeeemigec
13
cdefmopqsvxzz

Example output:
0
1
-1
2
6
0

Editorial:
We can notice that this operation will ultimately reverse the lexicographically largest subset of the initial string.
Thus, we can easily check if the string is sortable, and for finding the number of operations we will subtract the length of the largest prefix of equal values of the subset from its length.
This solution works in $$$O(n)$$$ time.
Cyclic MEX
Contest: Codeforces Round 915 (Div. 2)
Difficulty rating: 2000
Tags: data structures, implementation, math, two pointers

For an array $$$a$$$, define its cost as $$$\sum_{i=1}^{n} \operatorname{mex} ^\dagger ([a_1,a_2,\ldots,a_i])$$$.

You are given a permutation$$$^\ddagger$$$ $$$p$$$ of the set $$$\{0,1,2,\ldots,n-1\}$$$. Find the maximum cost across all cyclic shifts of $$$p$$$.

$$$^\dagger\operatorname{mex}([b_1,b_2,\ldots,b_m])$$$ is the smallest non-negative integer $$$x$$$ such that $$$x$$$ does not occur among $$$b_1,b_2,\ldots,b_m$$$.

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

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the length of the permutation $$$p$$$.

The second line of each test case contain $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$0 \le p_i < n$$$) — the elements of the permutation $$$p$$$.

It is guaranteed that sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, output a single integer — the maximum cost across all cyclic shifts of $$$p$$$.

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

Note:
In the first test case, the cyclic shift that yields the maximum cost is $$$[2,1,0,5,4,3]$$$ with cost $$$0+0+3+3+3+6=15$$$.

In the second test case, the cyclic shift that yields the maximum cost is $$$[0,2,1]$$$ with cost $$$1+1+3=5$$$.

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

Example output:
15
5
31
1

Editorial:
Let's analyze how the values of each prefix mex changes upon performing a cyclic shift to the left:
• The first prefix mex is popped.
• Each prefix mex with a value less than $$$p_1$$$ doesn't change.
• Each prefix mex with a value greater than $$$p_1$$$ becomes $$$p_1$$$.
• $$$n$$$ is appended to the back.
Let's keep our prefix mexes compressed ( meaning that we keep the value and its frequency instead of keeping multiple same values ). After that, we can simulate the above process naively with a deque, because the potential will decrease by the number of performed operations.
This solution works in $$$O(n)$$$ time.
Prime Deletion
Contest: Educational Codeforces Round 154 (Rated for Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, math

A prime number is a positive integer that has exactly two different positive divisors: $$$1$$$ and the integer itself. For example, $$$2$$$, $$$3$$$, $$$13$$$ and $$$101$$$ are prime numbers; $$$1$$$, $$$4$$$, $$$6$$$ and $$$42$$$ are not.

You are given a sequence of digits from $$$1$$$ to $$$9$$$, in which every digit from $$$1$$$ to $$$9$$$ appears exactly once.

You are allowed to do the following operation several (maybe zero) times: choose any digit from the sequence and delete it. However, you cannot perform this operation if the sequence consists of only two digits.

Your goal is to obtain a sequence which represents a prime number. Note that you cannot reorder the digits in the sequence.

Print the resulting sequence, or report that it is impossible to perform the operations so that the resulting sequence is a prime number.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases.

Each test case consists of one line containing a string of $$$9$$$ digits (without any characters between them). Each digit from $$$1$$$ to $$$9$$$ appears in this string exactly once.

Output format:
For each test case, print the answer on a separate line as follows:

- if it is impossible to perform the described operations, print $$$-1$$$;
- otherwise, print any sequence that represents a prime number, which can be obtained from the given string performing several (maybe zero) operations described in the statement. If there are multiple such sequences, you can print any one of them.

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

Example input:
4
123456789
987654321
243567918
576318429

Example output:
167
53
3571
57638429

Editorial:
There are many possible approaches to this problem.
For example, you could use brute force to solve it: iterate on every integer from $$$1$$$, check that it is a prime number by iterating on its divisors, and check that it appears as a subsequence in the given digit sequence. If you find the answer, break the loop and print the number you found.
But that's a bit lengthy to code. Let's try something different.
We can try looking for a small set of primes such that at least one of the primes from that set appears in the given sequence. Let's try short primes, they are easier to work with.
If there exist two prime numbers of length $$$2$$$ consisting of digits $$$x$$$ and $$$y$$$, one of them is $$$xy$$$, and the other of them is $$$yx$$$, then one of them will definitely appear in our sequence. If $$$x$$$ comes earlier than $$$y$$$, then $$$xy$$$ appears in the sequence, otherwise it's $$$yx$$$.
Thankfully, it's possible to find these two primes. For example, you can use $$$13$$$ and $$$31$$$; one of them will definitely appear in the sequence.
So, the easiest solution is to find whether $$$1$$$ is earlier than $$$3$$$ in the sequence. If $$$1$$$ is earlier, then $$$13$$$ is the answer, otherwise it's $$$31$$$.
Inna and Pink Pony
Contest: Codeforces Round 220 (Div. 2)
Difficulty rating: 2000
Tags: greedy, implementation

Dima and Inna are doing so great! At the moment, Inna is sitting on the magic lawn playing with a pink pony. Dima wanted to play too. He brought an n × m chessboard, a very tasty candy and two numbers a and b.

Dima put the chessboard in front of Inna and placed the candy in position (i, j) on the board. The boy said he would give the candy if it reaches one of the corner cells of the board. He's got one more condition. There can only be actions of the following types:

- move the candy from position (x, y) on the board to position (x - a, y - b);
- move the candy from position (x, y) on the board to position (x + a, y - b);
- move the candy from position (x, y) on the board to position (x - a, y + b);
- move the candy from position (x, y) on the board to position (x + a, y + b).

Naturally, Dima doesn't allow to move the candy beyond the chessboard borders.

Inna and the pony started shifting the candy around the board. They wonder what is the minimum number of allowed actions that they need to perform to move the candy from the initial position (i, j) to one of the chessboard corners. Help them cope with the task!

Input format:
The first line of the input contains six integers n, m, i, j, a, b (1 ≤ n, m ≤ 106; 1 ≤ i ≤ n; 1 ≤ j ≤ m; 1 ≤ a, b ≤ 106).

You can assume that the chessboard rows are numbered from 1 to n from top to bottom and the columns are numbered from 1 to m from left to right. Position (i, j) in the statement is a chessboard cell on the intersection of the i-th row and the j-th column. You can consider that the corners are: (1, m), (n, 1), (n, m), (1, 1).

Output format:
In a single line print a single integer — the minimum number of moves needed to get the candy.

If Inna and the pony cannot get the candy playing by Dima's rules, print on a single line "Poor Inna and pony!" without the quotes.

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

Note:
Note to sample 1:

Inna and the pony can move the candy to position (1 + 2, 3 + 2) = (3, 5), from there they can move it to positions (3 - 2, 5 + 2) = (1, 7) and (3 + 2, 5 + 2) = (5, 7). These positions correspond to the corner squares of the chess board. Thus, the answer to the test sample equals two.

Example input:
5 7 1 3 2 2

Example output:
2

Example input:
5 5 2 3 1 1

Example output:
Poor Inna and pony!

Editorial:
Inna and Nine
Contest: Codeforces Round 220 (Div. 2)
Difficulty rating: 1500
Tags: combinatorics, greedy

Inna loves digit 9 very much. That's why she asked Dima to write a small number consisting of nines. But Dima must have misunderstood her and he wrote a very large number a, consisting of digits from 1 to 9.

Inna wants to slightly alter the number Dima wrote so that in the end the number contained as many digits nine as possible. In one move, Inna can choose two adjacent digits in a number which sum equals 9 and replace them by a single digit 9.

For instance, Inna can alter number 14545181 like this: 14545181 → 1945181 → 194519 → 19919. Also, she can use this method to transform number 14545181 into number 19991. Inna will not transform it into 149591 as she can get numbers 19919 and 19991 which contain more digits nine.

Dima is a programmer so he wants to find out how many distinct numbers containing as many digits nine as possible Inna can get from the written number. Help him with this challenging task.

Input format:
The first line of the input contains integer a (1 ≤ a ≤ 10100000). Number a doesn't have any zeroes.

Output format:
In a single line print a single integer — the answer to the problem. It is guaranteed that the answer to the problem doesn't exceed 263 - 1.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

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

Note:
Notes to the samples

In the first sample Inna can get the following numbers: 369727 → 99727 → 9997, 369727 → 99727 → 9979.

In the second sample, Inna can act like this: 123456789987654321 → 12396789987654321 → 1239678998769321.

Example input:
369727

Example output:
2

Example input:
123456789987654321

Example output:
1

Editorial:
Inna and Dima
Contest: Codeforces Round 220 (Div. 2)
Difficulty rating: 1900
Tags: dfs and similar, dp, graphs, implementation

Inna and Dima bought a table of size n × m in the shop. Each cell of the table contains a single letter: "D", "I", "M", "A".

Inna loves Dima, so she wants to go through his name as many times as possible as she moves through the table. For that, Inna acts as follows:

1. initially, Inna chooses some cell of the table where letter "D" is written;
2. then Inna can move to some side-adjacent table cell that contains letter "I"; then from this cell she can go to one of the side-adjacent table cells that contains the written letter "M"; then she can go to a side-adjacent cell that contains letter "A". Then Inna assumes that she has gone through her sweetheart's name;
3. Inna's next move can be going to one of the side-adjacent table cells that contains letter "D" and then walk on through name DIMA in the similar manner. Inna never skips a letter. So, from the letter "D" she always goes to the letter "I", from the letter "I" she always goes the to letter "M", from the letter "M" she always goes to the letter "A", and from the letter "A" she always goes to the letter "D".

Depending on the choice of the initial table cell, Inna can go through name DIMA either an infinite number of times or some positive finite number of times or she can't go through his name once. Help Inna find out what maximum number of times she can go through name DIMA.

Input format:
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 103).

Then follow n lines that describe Inna and Dima's table. Each line contains m characters. Each character is one of the following four characters: "D", "I", "M", "A".

Note that it is not guaranteed that the table contains at least one letter "D".

Output format:
If Inna cannot go through name DIMA once, print on a single line "Poor Dima!" without the quotes. If there is the infinite number of names DIMA Inna can go through, print "Poor Inna!" without the quotes. Otherwise print a single integer — the maximum number of times Inna can go through name DIMA.

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

Note:
Notes to the samples:

In the first test sample, Inna cannot go through name DIMA a single time.

In the second test sample, Inna can go through the infinite number of words DIMA. For that, she should move in the clockwise direction starting from the lower right corner.

In the third test sample the best strategy is to start from the cell in the upper left corner of the table. Starting from this cell, Inna can go through name DIMA four times.

Example input:
1 2
DI

Example output:
Poor Dima!

Example input:
2 2
MA
ID

Example output:
Poor Inna!

Editorial:
Inna and Sequence
Contest: Codeforces Round 220 (Div. 2)
Difficulty rating: 2000
Tags: binary search, data structures, dp, trees

Dima's spent much time thinking what present to give to Inna and gave her an empty sequence w. Now they want to fill sequence w with numbers zero and one. For that, they decided to play an amusing game.

Before the game begins, Dima chooses m integers a1, a2, ..., am (1 ≤ a1 < a2 < ... < am). Then Inna and Dima start playing, that is, adding numbers to sequence w. Each new number they choose is added to the end of the sequence. At some moments of time Dima feels that the game is going to end too soon (and he wants to play with Inna as long as possible), so he hits a table hard with his fist. At that the a1-th, a2-th, a3-th, ..., ak-th numbers from the beginning simultaneously fall out of the sequence (the sequence gets k numbers less). Here k is such maximum number that value ak doesn't exceed the current length of the sequence. If number a1 is larger than the current length of w, then nothing falls out of the sequence.

You are given the chronological sequence of events in the game. Each event is either adding a number to the end of sequence w or Dima's hit on the table. Calculate the sequence w after all these events happen.

Input format:
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 106) showing how many events took place and how many numbers Dima chose.

The next line contains m distinct integers ai (1 ≤ ai ≤ 106) sorted in the increasing order.

Next n lines describe the events in the chronological order. Each line contains a single integer: -1, 0 or 1. Number -1 means that Dima hits the table. Number 0 means that Inna and Dima add number 0 to the end of the sequence. Number 1 means that Inna and Dima add number 1 to the end of the sequence.

Output format:
In a single line print a sequence of numbers 0 and 1 — the elements of the sequence after all events happen. Print the elements of the sequence in the order from the beginning to the end of the sequence.

If after all events the sequence ends up empty, print "Poor stack!".

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

Example input:
10 3
1 3 6
-1
1
1
0
0
-1
0
1
-1
1

Example output:
011

Example input:
2 1
1
1
-1

Example output:
Poor stack!

Editorial:
Inna and Babies
Contest: Codeforces Round 220 (Div. 2)
Difficulty rating: 2600
Tags: binary search, data structures, dsu, geometry, implementation

Inna, Dima and Sereja are in one room together. It's cold outside, so Sereja suggested to play a board game called "Babies".

The babies playing board is an infinite plane containing n blue babies and m red ones. Each baby is a segment that grows in time. At time moment t the blue baby (x, y) is a blue segment with ends at points (x - t, y + t), (x + t, y - t). Similarly, at time t the red baby (x, y) is a red segment with ends at points (x + t, y + t), (x - t, y - t) of the plane. Initially, at time t = 0 all babies are points on the plane.

The goal of the game is to find the first integer moment of time when the plane contains a rectangle of a non-zero area which sides are fully covered by some babies. A side may be covered by multiple babies. More formally, each point of each side of the rectangle should be covered by at least one baby of any color. At that, you must assume that the babies are closed segments, that is, they contain their endpoints.

You are given the positions of all babies — help Inna and Dima to find the required moment of time.

Input format:
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 2000).

Next n lines contain the coordinates of the blue babies. The i-th line contains integers xi, yi — a baby's coordinates. Next m lines contain the coordinates of m red babies in the similar form.

All coordinates of the input don't exceed 106 in their absolute value. Note that all babies stand in distinct points.

Output format:
In the single line print a single integer — the answer to the problem.

If the rectangle never appears on the plane, print "Poor Sereja!" without the quotes.

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

Example input:
2 2
2 2
5 5
3 7
5 1

Example output:
3

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

Example output:
1

Editorial:
Tokitsukaze and Strange Inequality
Contest: Codeforces Round 789 (Div. 1)
Difficulty rating: 1600
Tags: brute force, data structures, dp

Tokitsukaze has a permutation $$$p$$$ of length $$$n$$$. Recall that a permutation $$$p$$$ of length $$$n$$$ is a sequence $$$p_1, p_2, \ldots, p_n$$$ consisting of $$$n$$$ distinct integers, each of which from $$$1$$$ to $$$n$$$ ($$$1 \leq p_i \leq n$$$).

She wants to know how many different indices tuples $$$[a,b,c,d]$$$ ($$$1 \leq a < b < c < d \leq n$$$) in this permutation satisfy the following two inequalities:

$$$p_a < p_c$$$ and $$$p_b > p_d$$$.

Note that two tuples $$$[a_1,b_1,c_1,d_1]$$$ and $$$[a_2,b_2,c_2,d_2]$$$ are considered to be different if $$$a_1 \ne a_2$$$ or $$$b_1 \ne b_2$$$ or $$$c_1 \ne c_2$$$ or $$$d_1 \ne d_2$$$.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. Each test case consists of two lines.

The first line contains a single integer $$$n$$$ ($$$4 \leq n \leq 5000$$$) — the length of permutation $$$p$$$.

The second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — the permutation $$$p$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output format:
For each test case, print a single integer — the number of different $$$[a,b,c,d]$$$ tuples.

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

Note:
In the first test case, there are $$$3$$$ different $$$[a,b,c,d]$$$ tuples.

$$$p_1 = 5$$$, $$$p_2 = 3$$$, $$$p_3 = 6$$$, $$$p_4 = 1$$$, where $$$p_1 < p_3$$$ and $$$p_2 > p_4$$$ satisfies the inequality, so one of $$$[a,b,c,d]$$$ tuples is $$$[1,2,3,4]$$$.

Similarly, other two tuples are $$$[1,2,3,6]$$$, $$$[2,3,5,6]$$$.

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

Example output:
3
0
28

Editorial:
We can calculate the answer in two steps.
The first step, for each $$$b$$$, let $$$f_b$$$ represents the number of $$$p_d$$$ where $$$p_b > p_d$$$ in the interval $$$[b+1,n]$$$. We can calculate $$$f$$$ in $$$\mathcal{O}(n^2)$$$.
The second step, calculate the answer. First we enumerate $$$c$$$ from $$$1$$$ to $$$n$$$, and then enumerate $$$a$$$ from $$$1$$$ to $$$c-1$$$. When $$$p_a < p_c$$$, add $$$f_b$$$ in the interval $$$[a+1,c-1]$$$ to the answer. Before enumerating $$$a $$$, we can calculate the prefix sum of $$$f$$$ first, so we can add the $$$f_b$$$ in the interval to the answer in $$$\mathcal{O}(1)$$$. The time complexity of this step is $$$\mathcal{O}(n^2)$$$. However, this will add the result of $$$d$$$ in the interval $$$[a+1,c-1]$$$ to the answer, which is illegal because $$$c < d$$$ is required. So we need to maintain $$$f$$$ while enumerating $$$c$$$: enumerate $$$b$$$ from $$$1$$$ to $$$c-1$$$, if $$$p_b > p_c$$$, $$$f_b$$$ minus $$$1$$$. $$$p_c$$$ is actually regarded as $$$p_d$$$, that is, subtract the case where $$$c$$$ is equal to $$$d$$$, so as to subtract the illegal case. The time complexity of this step is also $$$\mathcal{O}(n^2)$$$.
Time complexity:$$$\mathcal{O}(n^2)$$$.