1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Sifid and Strange Subsequences
Contest: Codeforces Round 722 (Div. 2)
Difficulty rating: 1100
Tags: greedy, math, sortings

A sequence $$$(b_1, b_2, \ldots, b_k)$$$ is called strange, if the absolute difference between any pair of its elements is greater than or equal to the maximum element in the sequence. Formally speaking, it's strange if for every pair $$$(i, j)$$$ with $$$1 \le i<j \le k$$$, we have $$$|a_i-a_j|\geq MAX$$$, where $$$MAX$$$ is the largest element of the sequence. In particular, any sequence of length at most $$$1$$$ is strange.

For example, the sequences $$$(-2021, -1, -1, -1)$$$ and $$$(-1, 0, 1)$$$ are strange, but $$$(3, 0, 1)$$$ is not, because $$$|0 - 1| < 3$$$.

Sifid has an array $$$a$$$ of $$$n$$$ integers. Sifid likes everything big, so among all the strange subsequences of $$$a$$$, he wants to find the length of the longest one. Can you help him?

A sequence $$$c$$$ is a subsequence of an array $$$d$$$ if $$$c$$$ can be obtained from $$$d$$$ by deletion of several (possibly, zero or all) elements.

Input format:
The first line contains an 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 an integer $$$n$$$ $$$(1\le n\le 10^5)$$$ — the length of the array $$$a$$$.

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

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

Output format:
For each test case output a single integer — the length of the longest strange subsequence of $$$a$$$.

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

Note:
In the first test case, one of the longest strange subsequences is $$$(a_1, a_2, a_3, a_4)$$$

In the second test case, one of the longest strange subsequences is $$$(a_1, a_3, a_4, a_5, a_7)$$$.

In the third test case, one of the longest strange subsequences is $$$(a_1, a_3, a_4, a_5)$$$.

In the fourth test case, one of the longest strange subsequences is $$$(a_2)$$$.

In the fifth test case, one of the longest strange subsequences is $$$(a_1, a_2, a_4)$$$.

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

Example output:
4
5
4
1
3
4

Editorial:
It's easy to prove that a strange subsequence can't contain more than one positive element.
So it's optimal to pick all of the non-positive elements, now we can pick at most one positive element.
Assume $$$x$$$ is the minimum positive element in the array. We can pick $$$x$$$ if no two elements in the already picked set such as $$$a$$$ and $$$b$$$ exist in a way that $$$|a - b| < x$$$.
To check this, we just have to sort the already picked elements and see the difference between adjacent pairs.
complexity: $$$\mathcal{O}(n\log n)$$$
Yogurt Sale
Contest: Codeforces Round 938 (Div. 3)
Difficulty rating: 800
Tags: math

The price of one yogurt at the "Vosmiorochka" store is $$$a$$$ burles, but there is a promotion where you can buy two yogurts for $$$b$$$ burles.

Maxim needs to buy exactly $$$n$$$ yogurts. When buying two yogurts, he can choose to buy them at the regular price or at the promotion price.

What is the minimum amount of burles Maxim should spend to buy $$$n$$$ yogurts?

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

The first and only line of each test case contains three integers $$$n$$$, $$$a$$$, and $$$b$$$ ($$$1 \le n \le 100$$$, $$$1 \le a, b \le 30$$$) — the number of yogurts Maxim wants to buy, the price for one yogurt, and the price for two yogurts on promotion.

Output format:
For each test case, print in a separate line the minimum cost of buying $$$n$$$ yogurts at "Vosmiorochka".

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

Note:
In the third test case of the example, it is more advantageous to buy three yogurts for $$$15$$$ burles than two for $$$11$$$ and one for $$$5$$$.

In the fourth test case of the example, you need to buy four yogurts, each for $$$5$$$ burles.

Example input:
4
2 5 9
3 5 9
3 5 11
4 5 11

Example output:
9
14
15
20

Editorial:
You can always buy yogurts one by one without using the promotion, then the answer is $$$n \cdot a$$$.
Suppose it is more advantageous to buy yogurts on promotion than one by one, that is, $$$b < 2 \cdot a$$$. If $$$n$$$ is even, the answer is $$${n \over 2} \cdot b$$$, otherwise $$${(n - 1) \over 2} \cdot b + a$$$.
Now you just need to choose whether to buy yogurts one by one or on promotion, taking the minimum of the two options.
Progressive Square
Contest: Codeforces Round 938 (Div. 3)
Difficulty rating: 1000
Tags: constructive algorithms, data structures, implementation, sortings

A progressive square of size $$$n$$$ is an $$$n \times n$$$ matrix. Maxim chooses three integers $$$a_{1,1}$$$, $$$c$$$, and $$$d$$$ and constructs a progressive square according to the following rules:

$$$$$$a_{i+1,j} = a_{i,j} + c$$$$$$

$$$$$$a_{i,j+1} = a_{i,j} + d$$$$$$

For example, if $$$n = 3$$$, $$$a_{1,1} = 1$$$, $$$c=2$$$, and $$$d=3$$$, then the progressive square looks as follows:

$$$$$$ \begin{pmatrix} 1 & 4 & 7 \\ 3 & 6 & 9 \\ 5 & 8 & 11 \end{pmatrix} $$$$$$

Last month Maxim constructed a progressive square and remembered the values of $$$n$$$, $$$c$$$, and $$$d$$$. Recently, he found an array $$$b$$$ of $$$n^2$$$ integers in random order and wants to make sure that these elements are the elements of that specific square.

It can be shown that for any values of $$$n$$$, $$$a_{1,1}$$$, $$$c$$$, and $$$d$$$, there exists exactly one progressive square that satisfies all the rules.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le {10} ^ 4$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$c$$$, and $$$d$$$ ($$$2 \le n \le 500$$$, $$$1 \le c, d \le 10^6$$$) — the size of the square and the values of $$$c$$$ and $$$d$$$ as described in the statement.

The second line of each test case contains $$$n \cdot n$$$ integers $$$b_1, b_2, \dots, b_{n \cdot n}$$$ ($$$1 \le b_i \le 10^9$$$) — the elements found by Maxim.

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

Output format:
For each test case, output "YES" in a separate line if a progressive square for the given $$$n$$$, $$$c$$$, and $$$d$$$ can be constructed from the array elements $$$a$$$, otherwise output "NO".

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

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

Example input:
5
3 2 3
3 9 6 5 7 1 10 4 8
3 2 3
3 9 6 5 7 1 11 4 8
2 100 100
400 300 400 500
3 2 3
3 9 6 6 5 1 11 4 8
4 4 4
15 27 7 19 23 23 11 15 7 3 19 23 11 15 11 15

Example output:
NO
YES
YES
NO
NO

Editorial:
Since $$$c > 0$$$ and $$$d > 0$$$, the elements of the square increase starting from the top left corner. Thus, $$$a_{1,1}$$$ is the minimum element in the square, and consequently in the found elements.
Given $$$n$$$, $$$c$$$, $$$d$$$, and the found $$$a_{1,1}$$$, we will reconstruct the square. It remains to check that the given numbers in the input form the same square. The easiest way is to sort both arrays of numbers and check for equality. The complexity of the solution is $$$O(n ^ 2 \cdot \log{n})$$$.
Oh Sweet Beaverette
Contest: ABBYY Cup 3.0 - Finals
Difficulty rating: 1400

— Oh my sweet Beaverette, would you fancy a walk along a wonderful woodland belt with me?

— Of course, my Smart Beaver! Let us enjoy the splendid view together. How about Friday night?

At this point the Smart Beaver got rushing. Everything should be perfect by Friday, so he needed to prepare the belt to the upcoming walk. He needed to cut down several trees.

Let's consider the woodland belt as a sequence of trees. Each tree i is described by the esthetic appeal ai — some trees are very esthetically pleasing, others are 'so-so', and some trees are positively ugly!

The Smart Beaver calculated that he needed the following effects to win the Beaverette's heart:

- The first objective is to please the Beaverette: the sum of esthetic appeal of the remaining trees must be maximum possible;
- the second objective is to surprise the Beaverette: the esthetic appeal of the first and the last trees in the resulting belt must be the same;
- and of course, the walk should be successful: there must be at least two trees in the woodland belt left.

Now help the Smart Beaver! Which trees does he need to cut down to win the Beaverette's heart?

Input format:
The first line contains a single integer n — the initial number of trees in the woodland belt, 2 ≤ n. The second line contains space-separated integers ai — the esthetic appeals of each tree. All esthetic appeals do not exceed 109 in their absolute value.

- to get 30 points, you need to solve the problem with constraints: n ≤ 100 (subproblem A1);
- to get 100 points, you need to solve the problem with constraints: n ≤ 3·105 (subproblems A1+A2).

Output format:
In the first line print two integers — the total esthetic appeal of the woodland belt after the Smart Beaver's intervention and the number of the cut down trees k.

In the next line print k integers — the numbers of the trees the Beaver needs to cut down. Assume that the trees are numbered from 1 to n from left to right.

If there are multiple solutions, print any of them. It is guaranteed that at least two trees have equal esthetic appeal.

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

Example input:
5
1 2 3 1 2

Example output:
8 1
1

Example input:
5
1 -2 3 1 -2

Example output:
5 2
2 5

Editorial:
Shave Beaver!
Contest: ABBYY Cup 3.0 - Finals
Difficulty rating: 1700

The Smart Beaver has recently designed and built an innovative nanotechnologic all-purpose beaver mass shaving machine, "Beavershave 5000". Beavershave 5000 can shave beavers by families! How does it work? Very easily!

There are n beavers, each of them has a unique id from 1 to n. Consider a permutation a1, a2, ..., an of n these beavers. Beavershave 5000 needs one session to shave beavers with ids from x to y (inclusive) if and only if there are such indices i1 < i2 < ... < ik, that ai1 = x, ai2 = x + 1, ..., aik - 1 = y - 1, aik = y. And that is really convenient. For example, it needs one session to shave a permutation of beavers 1, 2, 3, ..., n.

If we can't shave beavers from x to y in one session, then we can split these beavers into groups [x, p1], [p1 + 1, p2], ..., [pm + 1, y] (x ≤ p1 < p2 < ... < pm < y), in such a way that the machine can shave beavers in each group in one session. But then Beavershave 5000 needs m + 1 working sessions to shave beavers from x to y.

All beavers are restless and they keep trying to swap. So if we consider the problem more formally, we can consider queries of two types:

- what is the minimum number of sessions that Beavershave 5000 needs to shave beavers with ids from x to y, inclusive?
- two beavers on positions x and y (the beavers ax and ay) swapped.

You can assume that any beaver can be shaved any number of times.

Input format:
The first line contains integer n — the total number of beavers, 2 ≤ n. The second line contains n space-separated integers — the initial beaver permutation.

The third line contains integer q — the number of queries, 1 ≤ q ≤ 105. The next q lines contain the queries. Each query i looks as pi xi yi, where pi is the query type (1 is to shave beavers from xi to yi, inclusive, 2 is to swap beavers on positions xi and yi). All queries meet the condition: 1 ≤ xi < yi ≤ n.

- to get 30 points, you need to solve the problem with constraints: n ≤ 100 (subproblem B1);
- to get 100 points, you need to solve the problem with constraints: n ≤ 3·105 (subproblems B1+B2).

Note that the number of queries q is limited 1 ≤ q ≤ 105 in both subproblem B1 and subproblem B2.

Output format:
For each query with pi = 1, print the minimum number of Beavershave 5000 sessions.

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

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

Example output:
2
1
3
5

Editorial:
The Great Julya Calendar
Contest: ABBYY Cup 3.0 - Finals
Difficulty rating: 1100

Yet another Armageddon is coming! This time the culprit is the Julya tribe calendar.

The beavers in this tribe knew math very well. Smart Beaver, an archaeologist, got a sacred plate with a magic integer on it. The translation from Old Beaverish is as follows:

"May the Great Beaver bless you! May your chacres open and may your third eye never turn blind from beholding the Truth! Take the magic number, subtract a digit from it (the digit must occur in the number) and get a new magic number. Repeat this operation until a magic number equals zero. The Earth will stand on Three Beavers for the time, equal to the number of subtractions you perform!"

Distinct subtraction sequences can obviously get you different number of operations. But the Smart Beaver is ready to face the worst and is asking you to count the minimum number of operations he needs to reduce the magic number to zero.

Input format:
The single line contains the magic integer n, 0 ≤ n.

- to get 20 points, you need to solve the problem with constraints: n ≤ 106 (subproblem C1);
- to get 40 points, you need to solve the problem with constraints: n ≤ 1012 (subproblems C1+C2);
- to get 100 points, you need to solve the problem with constraints: n ≤ 1018 (subproblems C1+C2+C3).

Output format:
Print a single integer — the minimum number of subtractions that turns the magic number to a zero.

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

Note:
In the first test sample the minimum number of operations can be reached by the following sequence of subtractions:

24 → 20 → 18 → 10 → 9 → 0

Example input:
24

Example output:
5

Editorial:
Escaping on Beaveractor
Contest: ABBYY Cup 3.0 - Finals
Difficulty rating: 2400

Don't put up with what you're sick of! The Smart Beaver decided to escape from the campus of Beaver Science Academy (BSA). BSA is a b × b square on a plane. Each point x, y (0 ≤ x, y ≤ b) belongs to BSA. To make the path quick and funny, the Beaver constructed a Beaveractor, an effective and comfortable types of transport.

The campus obeys traffic rules: there are n arrows, parallel to the coordinate axes. The arrows do not intersect and do not touch each other. When the Beaveractor reaches some arrow, it turns in the arrow's direction and moves on until it either reaches the next arrow or gets outside the campus. The Beaveractor covers exactly one unit of space per one unit of time. You can assume that there are no obstacles to the Beaveractor.

The BSA scientists want to transport the brand new Beaveractor to the "Academic Tractor" research institute and send the Smart Beaver to do his postgraduate studies and sharpen pencils. They have q plans, representing the Beaveractor's initial position (xi, yi), the initial motion vector wi and the time ti that have passed after the escape started.

Your task is for each of the q plans to determine the Smart Beaver's position after the given time.

Input format:
The first line contains two integers: the number of traffic rules n and the size of the campus b, 0 ≤ n, 1 ≤ b. Next n lines contain the rules. Each line of the rules contains four space-separated integers x0, y0, x1, y1 — the beginning and the end of the arrow. It is guaranteed that all arrows are parallel to the coordinate axes and have no common points. All arrows are located inside the campus, that is, 0 ≤ x0, y0, x1, y1 ≤ b holds.

Next line contains integer q — the number of plans the scientists have, 1 ≤ q ≤ 105. The i-th plan is represented by two integers, xi, yi are the Beaveractor's coordinates at the initial time, 0 ≤ xi, yi ≤ b, character wi, that takes value U, D, L, R and sets the initial direction up, down, to the left or to the right correspondingly (the Y axis is directed upwards), and ti — the time passed after the escape started, 0 ≤ ti ≤ 1015.

- to get 30 points you need to solve the problem with constraints n, b ≤ 30 (subproblem D1);
- to get 60 points you need to solve the problem with constraints n, b ≤ 1000 (subproblems D1+D2);
- to get 100 points you need to solve the problem with constraints n, b ≤ 105 (subproblems D1+D2+D3).

Output format:
Print q lines. Each line should contain two integers — the Beaveractor's coordinates at the final moment of time for each plan. If the Smart Beaver manages to leave the campus in time ti, print the coordinates of the last point in the campus he visited.

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

Example input:
3 3
0 0 0 1
0 2 2 2
3 3 2 3
12
0 0 L 0
0 0 L 1
0 0 L 2
0 0 L 3
0 0 L 4
0 0 L 5
0 0 L 6
2 0 U 2
2 0 U 3
3 0 U 5
1 3 D 2
1 3 R 2

Example output:
0 0
0 1
0 2
1 2
2 2
3 2
3 2
2 2
3 2
1 3
2 2
1 3

Editorial:
Deja Vu
Contest: ABBYY Cup 3.0 - Finals
Difficulty rating: 2900

Everybody knows that we have been living in the Matrix for a long time. And in the new seventh Matrix the world is ruled by beavers.

So let's take beaver Neo. Neo has so-called "deja vu" outbursts when he gets visions of events in some places he's been at or is going to be at. Let's examine the phenomenon in more detail.

We can say that Neo's city is represented by a directed graph, consisting of n shops and m streets that connect the shops. No two streets connect the same pair of shops (besides, there can't be one street from A to B and one street from B to A). No street connects a shop with itself. As Neo passes some streets, he gets visions. No matter how many times he passes street k, every time he will get the same visions in the same order. A vision is a sequence of shops.

We know that Neo is going to get really shocked if he passes the way from some shop a to some shop b, possible coinciding with a, such that the list of visited shops in the real life and in the visions coincide.

Suggest beaver Neo such path of non-zero length. Or maybe you can even count the number of such paths modulo 1000000007 (109 + 7)?..

Input format:
The first line contains integers n and m — the number of shops and the number of streets, correspondingly, 1 ≤ n ≤ 50, $$0 \leq m \leq \frac{n(n-1)}{2}$$. Next m lines contain the descriptions of the streets in the following format: xi yi ki v1 v2 ... vk, where xi and yi (1 ≤ xi, yi ≤ n, xi ≠ yi) are indices of shops connected by a street, ki (0 ≤ ki ≤ n) is the number of visions on the way from xi to yi; v1, v2, ..., vk (1 ≤ vi ≤ n) describe the visions: the numbers of the shops Neo saw. Note that the order of the visions matters.

It is guaranteed that the total number of visions on all streets doesn't exceed 105.

- to get 50 points, you need to find any (not necessarily simple) path of length at most 2·n, that meets the attributes described above (subproblem E1);
- to get 50 more points, you need to count for each length from 1 to 2·n the number of paths that have the attribute described above (subproblem E2).

Output format:
Subproblem E1. In the first line print an integer k (1 ≤ k ≤ 2·n) — the numbers of shops on Neo's path. In the next line print k integers — the number of shops in the order Neo passes them. If the graph doesn't have such paths or the length of the shortest path includes more than 2·n shops, print on a single line 0.

Subproblem E2. Print 2·n lines. The i-th line must contain a single integer — the number of required paths of length i modulo 1000000007 (109 + 7).

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

Note:
The input in both samples are the same. The first sample contains the answer to the first subproblem, the second sample contains the answer to the second subproblem.

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

Example output:
4
6 1 2 3

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

Example output:
1
2
1
1
2
1
1
2
1
1
2
1

Editorial:
Deja Vu
Contest: ABBYY Cup 3.0 - Finals
Difficulty rating: 3100
Tags: constructive algorithms, dp

Everybody knows that we have been living in the Matrix for a long time. And in the new seventh Matrix the world is ruled by beavers.

So let's take beaver Neo. Neo has so-called "deja vu" outbursts when he gets visions of events in some places he's been at or is going to be at. Let's examine the phenomenon in more detail.

We can say that Neo's city is represented by a directed graph, consisting of n shops and m streets that connect the shops. No two streets connect the same pair of shops (besides, there can't be one street from A to B and one street from B to A). No street connects a shop with itself. As Neo passes some streets, he gets visions. No matter how many times he passes street k, every time he will get the same visions in the same order. A vision is a sequence of shops.

We know that Neo is going to get really shocked if he passes the way from some shop a to some shop b, possible coinciding with a, such that the list of visited shops in the real life and in the visions coincide.

Suggest beaver Neo such path of non-zero length. Or maybe you can even count the number of such paths modulo 1000000007 (109 + 7)?..

Input format:
The first line contains integers n and m — the number of shops and the number of streets, correspondingly, 1 ≤ n ≤ 50, $$0 \leq m \leq \frac{n(n-1)}{2}$$. Next m lines contain the descriptions of the streets in the following format: xi yi ki v1 v2 ... vk, where xi and yi (1 ≤ xi, yi ≤ n, xi ≠ yi) are numbers of shops connected by a street, ki (0 ≤ ki ≤ n) is the number of visions on the way from xi to yi; v1, v2, ..., vk (1 ≤ vi ≤ n) describe the visions: the numbers of the shops Neo saw. Note that the order of the visions matters.

It is guaranteed that the total number of visions on all streets doesn't exceed 105.

- to get 50 points, you need to find any (not necessarily simple) path of length at most 2·n, that meets the attributes described above (subproblem E1);
- to get 50 more points, you need to count for each length from 1 to 2·n the number of paths that have the attribute described above (subproblem E2).

Output format:
Subproblem E1. In the first line print an integer k (1 ≤ k ≤ 2·n) — the numbers of shops on Neo's path. In the next line print k integers — the number of shops in the order Neo passes them. If the graph doesn't have such paths or the length of the shortest path includes more than 2·n shops, print on a single line 0.

Subproblem E2. Print 2·n lines. The i-th line must contain a single integer — the number of required paths of length i modulo 1000000007 (109 + 7).

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

Note:
The input in both samples are the same. The first sample contains the answer to the first subproblem, the second sample contains the answer to the second subproblem.

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

Example output:
4
6 1 2 3

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

Example output:
1
2
1
1
2
1
1
2
1
1
2
1

Editorial: