1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Elections
Contest: Codeforces Round 503 (by SIS, Div. 1)
Difficulty rating: 1700
Tags: brute force, greedy

As you know, majority of students and teachers of Summer Informatics School live in Berland for the most part of the year. Since corruption there is quite widespread, the following story is not uncommon.

Elections are coming. You know the number of voters and the number of parties — $$$n$$$ and $$$m$$$ respectively. For each voter you know the party he is going to vote for. However, he can easily change his vote given a certain amount of money. In particular, if you give $$$i$$$-th voter $$$c_i$$$ bytecoins you can ask him to vote for any other party you choose.

The United Party of Berland has decided to perform a statistical study — you need to calculate the minimum number of bytecoins the Party needs to spend to ensure its victory. In order for a party to win the elections, it needs to receive strictly more votes than any other party.

Input format:
The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 3000$$$) — the number of voters and the number of parties respectively.

Each of the following $$$n$$$ lines contains two integers $$$p_i$$$ and $$$c_i$$$ ($$$1 \le p_i \le m$$$, $$$1 \le c_i \le 10^9$$$) — the index of this voter's preferred party and the number of bytecoins needed for him to reconsider his decision.

The United Party of Berland has the index $$$1$$$.

Output format:
Print a single number — the minimum number of bytecoins needed for The United Party of Berland to win the elections.

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

Note:
In the first sample, The United Party wins the elections even without buying extra votes.

In the second sample, The United Party can buy the votes of the first and the fourth voter. This way The Party gets two votes, while parties $$$3$$$, $$$4$$$ and $$$5$$$ get one vote and party number $$$2$$$ gets no votes.

In the third sample, The United Party can buy the votes of the first three voters and win, getting three votes against two votes of the fifth party.

Example input:
1 2
1 100

Example output:
0

Example input:
5 5
2 100
3 200
4 300
5 400
5 900

Example output:
500

Editorial:
Let's iterate over final number of votes for The United Party of Berland. We can see that all opponents should get less votes than our party, and our party should get at least our chosen number of votes.
We can sort all voters by their costs, and solve the problem in two passes. First, if we need to get $$$x$$$ votes, we should definitely buy all cheap votes for parties that have at least $$$x$$$ votes. Second, if we don't have $$$x$$$ votes yet, we should by the cheapest votes to get $$$x$$$ votes. We can see that this solution is optimal: consider the optimal answer, and see how many votes The United Party got. We tried such number of votes, and we tried to achieve this number of votes by cheapest way, so we couldn't miss the optimal answer. This can be implemented in $$$O(n^2 \log n)$$$ or even $$$O(n \log n)$$$.
Large Triangle
Contest: Codeforces Round 503 (by SIS, Div. 1)
Difficulty rating: 2700
Tags: binary search, geometry, sortings

Students from many different parts of Russia and abroad come to Summer Informatics School. You marked the hometowns of the SIS participants on a map.

Now you decided to prepare an interesting infographic based on this map. The first thing you chose to do is to find three cities on this map, such that they form a triangle with area $$$S$$$.

Input format:
The first line of input contains two integers $$$n$$$ and $$$S$$$ ($$$3 \le n \le 2000$$$, $$$1 \le S \le 2 \cdot 10^{18}$$$) — the number of cities on the map and the area of the triangle to be found.

The next $$$n$$$ lines contain descriptions of the cities, one per line. Each city is described by its integer coordinates $$$x_i$$$, $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$).

It is guaranteed that all cities are located at distinct points. It is also guaranteed that no three cities lie on the same line.

Output format:
If the solution doesn't exist — print «No».

Otherwise, print «Yes», followed by three pairs of coordinates $$$(x, y)$$$ — the locations of the three cities, which form the triangle of area $$$S$$$.

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

Example input:
3 7
0 0
3 0
0 4

Example output:
No

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

Example output:
Yes
0 0
1 3
2 0

Editorial:
Let's fix one of edge of the triangle. We need to find a third point so the area of triangle is equal to $$$s$$$. Notice that area of triangle is proportional to scalar product of the normal vector to the chosen edge and radius-vector of third point. So, if we had all other points sorted by scalar product with normal to the edge, we could find the third point by binary search. It is the main goal of the solution.
There are $$$O(n^2)$$$ interesting directions — two normal vectors to each of edges, defined by all pairs of points. For each pair of points you can see that for some directions one of points has larger scalar product with this direction, and for some other direction another point has larger scalar product. We can see that points $$$a_i$$$ and $$$a_j$$$ have the same scalar product with vector $$$rotate_{90}(a_i-a_j)$$$ — with normal vector edge defined by these two points. If you look at all directions on unit circle, this vector and the opposite vector change the order of points $$$a_i$$$ and $$$a_j$$$ in sorted order by scalar product. Also, as there are no three points lying on one line, these two points will be neighboring in sorting order by this direction.
So, we can maintain the sorting order. Let's take all events on unit circle as all vectors of type $$$rotate_{90}(a_i - a_j)$$$, and for every such event swap two neighboring points $$$a_i$$$ and $$$a_j$$$ in sorting order. After swap we can do a binary search for third point to find a required triangle with area $$$s$$$. This works in $$$O(n^2 \log n)$$$ time.
AquaMoon and Strange Sort
Contest: Codeforces Round 732 (Div. 1)
Difficulty rating: 1500
Tags: sortings

AquaMoon has $$$n$$$ friends. They stand in a row from left to right, and the $$$i$$$-th friend from the left wears a T-shirt with a number $$$a_i$$$ written on it. Each friend has a direction (left or right). In the beginning, the direction of each friend is right.

AquaMoon can make some operations on friends. On each operation, AquaMoon can choose two adjacent friends and swap their positions. After each operation, the direction of both chosen friends will also be flipped: left to right and vice versa.

AquaMoon hopes that after some operations, the numbers written on the T-shirt of $$$n$$$ friends in the row, read from left to right, become non-decreasing. Also she wants, that all friends will have a direction of right at the end. Please find if it is possible.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of Aquamoon's friends.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$) — the numbers, written on the T-shirts.

It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, if there exists a possible sequence of operations, print "YES" (without quotes); otherwise, print "NO" (without quotes).

You can print each letter in any case (upper or lower).

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

Note:
The possible list of operations in the first test case:

1. Swap $$$a_1$$$ and $$$a_2$$$. The resulting sequence is $$$3, 4, 2, 5$$$. The directions are: left, left, right, right.
2. Swap $$$a_2$$$ and $$$a_3$$$. The resulting sequence is $$$3, 2, 4, 5$$$. The directions are: left, left, right, right.
3. Swap $$$a_1$$$ and $$$a_2$$$. The resulting sequence is $$$2, 3, 4, 5$$$. The directions are: right, right, right, right.

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

Example output:
YES
YES
NO

Editorial:
It's easy to see that each number needs to move an even distance.
For the same number, count how many of them are in the odd position and even position.
Sort the array and count again.
The given array named A, the sorted array named B.
For every number, if the number of its occurrence in the odd position in A is different from its occurrence in the odd position in B, or the number of its occurrence in the even position in A is different from its occurrence in the even position in B, then the answer is NO. Otherwise the answer is YES.
AquaMoon and Chess
Contest: Codeforces Round 732 (Div. 1)
Difficulty rating: 1900
Tags: combinatorics, math

Cirno gave AquaMoon a chessboard of size $$$1 \times n$$$. Its cells are numbered with integers from $$$1$$$ to $$$n$$$ from left to right. In the beginning, some of the cells are occupied with at most one pawn, and other cells are unoccupied.

In each operation, AquaMoon can choose a cell $$$i$$$ with a pawn, and do either of the following (if possible):

- Move pawn from it to the $$$(i+2)$$$-th cell, if $$$i+2 \leq n$$$ and the $$$(i+1)$$$-th cell is occupied and the $$$(i+2)$$$-th cell is unoccupied.
- Move pawn from it to the $$$(i-2)$$$-th cell, if $$$i-2 \geq 1$$$ and the $$$(i-1)$$$-th cell is occupied and the $$$(i-2)$$$-th cell is unoccupied.

You are given an initial state of the chessboard. AquaMoon wants to count the number of states reachable from the initial state with some sequence of operations. But she is not good at programming. Can you help her? As the answer can be large find it modulo $$$998\,244\,353$$$.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — the number of test cases.

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the size of the chessboard.

The second line contains a string of $$$n$$$ characters, consists of characters "0" and "1". If the $$$i$$$-th character is "1", the $$$i$$$-th cell is initially occupied; otherwise, the $$$i$$$-th cell is initially unoccupied.

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

Output format:
For each test case, print the number of states that reachable from the initial state with some sequence of operations modulo $$$998\,244\,353$$$.

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

Note:
In the first test case the strings "1100", "0110" and "0011" are reachable from the initial state with some sequence of operations.

Example input:
6
4
0110
6
011011
5
01010
20
10001111110110111000
20
00110110100110111101
20
11101111011000100010

Example output:
3
6
1
1287
1287
715

Editorial:
We enumerate $$$i$$$ from $$$1$$$ to $$$n$$$. If position $$$i-1$$$ and $$$i$$$ both contain a chess and $$$i-1$$$ is not in other groups, then we divide them into one group.
We can change the operation a little: Each time we can swap the two consecutive $$$1$$$ and the element to their left or right. It's easy to see this operation equals to the initial one.
So that means we can take out the groups (two consecutive $$$1$$$) and insert them to any position of the chessboard. So let the number of groups be $$$m$$$, the number of zeros be $$$n$$$, it's easy to find that the answer is $$$\binom{n+m}{m}$$$(Since inserting one group to the left of some $$$1$$$ or to the right of it are the same).
AquaMoon and Time Stop (easy version)
Contest: Codeforces Round 732 (Div. 1)
Difficulty rating: 3500
Tags: data structures, dp

Note that the differences between easy and hard versions are the constraints on $$$n$$$ and the time limit. You can make hacks only if both versions are solved.

AquaMoon knew through foresight that some ghosts wanted to curse tourists on a pedestrian street. But unfortunately, this time, these ghosts were hiding in a barrier, and she couldn't enter this barrier in a short time and destroy them. Therefore, all that can be done is to save any unfortunate person on the street from the ghosts.

The pedestrian street can be represented as a one-dimensional coordinate system. There is one person hanging out on the pedestrian street. At the time $$$0$$$ he is at coordinate $$$x$$$, moving with a speed of $$$1$$$ unit per second. In particular, at time $$$i$$$ the person will be at coordinate $$$x+i$$$.

The ghosts are going to cast $$$n$$$ curses on the street. The $$$i$$$-th curse will last from time $$$tl_i-1+10^{-18}$$$ to time $$$tr_i+1-10^{-18}$$$ (exclusively) and will kill people with coordinates from $$$l_i-1+10^{-18}$$$ to $$$r_i+1-10^{-18}$$$ (exclusively). Formally that means, that the person, whose coordinate is between $$$(l_i-1+10^{-18},r_i+1-10^{-18})$$$ in the time range $$$(tl_i-1+10^{-18},tr_i+1-10^{-18})$$$ will die.

To save the person on the street, AquaMoon can stop time at any moment $$$t$$$, and then move the person from his current coordinate $$$x$$$ to any coordinate $$$y$$$ ($$$t$$$, $$$x$$$ and $$$y$$$ are not necessarily integers). The movement costs AquaMoon $$$|x-y|$$$ energy. The movement is continuous, so if there exists some cursed area between points $$$x$$$ and $$$y$$$ at time $$$t$$$, the person will die too.

AquaMoon wants to know what is the minimum amount of energy she needs to spend in order to save the person on the street from all $$$n$$$ curses. But she is not good at programming. As her friend, can you help her?

Input format:
The first line contains a single integer $$$n$$$ ($$$1\le n\le 2000$$$) — the number of curses.

The next line contains a single integer $$$x$$$ ($$$1\le x\le 10^6$$$) — the initial coordinate of the person.

The following $$$n$$$ lines contain four integers $$$tl_i$$$, $$$tr_i$$$, $$$l_i$$$, $$$r_i$$$ each ($$$1\le tl_i\le tr_i\le 10^6$$$, $$$1\le l_i\le r_i\le 10^6$$$).

Output format:
Print a single integer — the minimum energy which AquaMoon needs to spent, rounded up to the nearest integer (in case there are two nearest integers you should round the answer to the highest of them).

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

Example input:
2
1
1 2 1 2
2 3 2 3

Example output:
2

Example input:
3
4
1 4 1 2
1 4 4 15
6 7 1 4

Example output:
8

Editorial:
Subtractions
Contest: Codeforces Testing Round 5
Difficulty rating: 900
Tags: math, number theory

You've got two numbers. As long as they are both larger than zero, they go through the same operation: subtract the lesser number from the larger one. If they equal substract one number from the another. For example, one operation transforms pair (4,17) to pair (4,13), it transforms (5,5) to (0,5).

You've got some number of pairs (ai, bi). How many operations will be performed for each of them?

Input format:
The first line contains the number of pairs n (1  ≤  n  ≤  1000). Then follow n lines, each line contains a pair of positive integers ai, bi (1  ≤  ai,  bi  ≤  109).

Output format:
Print the sought number of operations for each pair on a single line.

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

Example input:
2
4 17
7 987654321

Example output:
8
141093479

Editorial:
Dominoes
Contest: Codeforces Testing Round 5
Difficulty rating: 2000
Tags: dfs and similar, graphs

You have a set of dominoes. Each domino is a rectangular tile with a line dividing its face into two square ends. Can you put all dominoes in a line one by one from left to right so that any two dominoes touched with the sides that had the same number of points? You can rotate the dominoes, changing the left and the right side (domino "1-4" turns into "4-1").

Input format:
The first line contains number n (1  ≤  n  ≤  100). Next n lines contains the dominoes. Each of these lines contains two numbers — the number of points (spots) on the left and the right half, correspondingly. The numbers of points (spots) are non-negative integers from 0 to 6.

Output format:
Print "No solution", if it is impossible to arrange the dominoes in the required manner. If the solution exists, then describe any way to arrange the dominoes. You put the dominoes from left to right. In each of n lines print the index of the domino to put in the corresponding position and then, after a space, character "+" (if you don't need to turn the domino) or "–" (if you need to turn it).

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

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

Example output:
2 -
1 -
5 -
3 +
4 -

Editorial:
Berland Traffic
Contest: Codeforces Testing Round 5
Difficulty rating: 2700
Tags: math, matrices

Berland traffic is very different from traffic in other countries. The capital of Berland consists of n junctions and m roads. Each road connects a pair of junctions. There can be multiple roads between a pair of junctions. For each road we know its capacity: value ci is the maximum number of cars that can drive along a road in any direction per a unit of time. For each road, the cars can drive along it in one of two direction. That it, the cars can't simultaneously move in both directions. A road's traffic is the number of cars that goes along it per a unit of time. For road (ai, bi) this value is negative, if the traffic moves from bi to ai. A road's traffic can be a non-integer number.

The capital has two special junctions — the entrance to the city (junction 1) and the exit from the city (junction n). For all other junctions it is true that the traffic is not lost there. That is, for all junctions except for 1 and n the incoming traffic sum equals the outgoing traffic sum.

Traffic has an unusual peculiarity in the capital of Berland — for any pair of junctions (x, y) the sum of traffics along any path from x to y doesn't change depending on the choice of the path. Such sum includes traffic along all roads on the path (possible with the "minus" sign, if the traffic along the road is directed against the direction of the road on the path from x to y).

Your task is to find the largest traffic that can pass trough the city per one unit of time as well as the corresponding traffic for each road.

Input format:
The first line contains a positive integer n — the number of junctions (2 ≤ n ≤ 100). The second line contains integer m (1 ≤ m ≤ 5000) — the number of roads. Next m lines contain the roads' descriptions. Each road contains a group of three numbers ai, bi, ci, where ai, bi are the numbers of junctions, connected by the given road, and ci (1 ≤ ai, bi ≤ n; ai ≠ bi; 0 ≤ ci ≤ 10000) is the largest permissible traffic along this road.

Output format:
In the first line print the required largest traffic across the city. Then print m lines, on each line print the speed, at which the traffic moves along the corresponding road. If the direction doesn't match the order of the junctions, given in the input, then print the traffic with the minus sign. Print the numbers with accuracy of at least five digits after the decimal point.

If there are many optimal solutions, print any of them.

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

Example input:
2
3
1 2 2
1 2 4
2 1 1000

Example output:
6.00000
2.00000
2.00000
-2.00000

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

Example output:
13.00000
2.00000
2.00000
3.00000
6.00000
1.00000
3.00000
4.00000
7.00000
1.00000
2.00000
6.00000

Editorial:
Lucky Permutation Triple
Contest: Codeforces Round 183 (Div. 1)
Difficulty rating: 1300
Tags: constructive algorithms, implementation, math

Bike is interested in permutations. A permutation of length n is an integer sequence such that each integer from 0 to (n - 1) appears exactly once in it. For example, [0, 2, 1] is a permutation of length 3 while both [0, 2, 2] and [1, 2, 3] is not.

A permutation triple of permutations of length n (a, b, c) is called a Lucky Permutation Triple if and only if $$$$. The sign ai denotes the i-th element of permutation a. The modular equality described above denotes that the remainders after dividing ai + bi by n and dividing ci by n are equal.

Now, he has an integer n and wants to find a Lucky Permutation Triple. Could you please help him?

Input format:
The first line contains a single integer n (1 ≤ n ≤ 105).

Output format:
If no Lucky Permutation Triple of length n exists print -1.

Otherwise, you need to print three lines. Each line contains n space-seperated integers. The first line must contain permutation a, the second line — permutation b, the third — permutation c.

If there are multiple solutions, print any of them.

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

Note:
In Sample 1, the permutation triple ([1, 4, 3, 2, 0], [1, 0, 2, 4, 3], [2, 4, 0, 1, 3]) is Lucky Permutation Triple, as following holds:

- $$1 + 1 \equiv 2 \equiv 2 \mod 5$$;
- $$4 + 0 \equiv 4 \equiv 4 \mod 5$$;
- $$3 + 2 \equiv 0 \equiv 0 \mod 5$$;
- $$2 + 4 \equiv 6 \equiv 1 \mod 5$$;
- $$0+3\equiv 3\equiv 3 \mod 5$$.

In Sample 2, you can easily notice that no lucky permutation triple exists.

Example input:
5

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

Example input:
2

Example output:
-1

Editorial:
Rectangle Puzzle II
Contest: Codeforces Round 183 (Div. 1)
Difficulty rating: 1700
Tags: implementation, math

You are given a rectangle grid. That grid's size is n × m. Let's denote the coordinate system on the grid. So, each point on the grid will have coordinates — a pair of integers (x, y) (0 ≤ x ≤ n, 0 ≤ y ≤ m).

Your task is to find a maximum sub-rectangle on the grid (x1, y1, x2, y2) so that it contains the given point (x, y), and its length-width ratio is exactly (a, b). In other words the following conditions must hold: 0 ≤ x1 ≤ x ≤ x2 ≤ n, 0 ≤ y1 ≤ y ≤ y2 ≤ m, $$\frac{x_{2}-x_{1}}{y_{2}-y_{1}}=\frac{a}{b}$$.

The sides of this sub-rectangle should be parallel to the axes. And values x1, y1, x2, y2 should be integers.

If there are multiple solutions, find the rectangle which is closest to (x, y). Here "closest" means the Euclid distance between (x, y) and the center of the rectangle is as small as possible. If there are still multiple solutions, find the lexicographically minimum one. Here "lexicographically minimum" means that we should consider the sub-rectangle as sequence of integers (x1, y1, x2, y2), so we can choose the lexicographically minimum one.

Input format:
The first line contains six integers n, m, x, y, a, b (1 ≤ n, m ≤ 109, 0 ≤ x ≤ n, 0 ≤ y ≤ m, 1 ≤ a ≤ n, 1 ≤ b ≤ m).

Output format:
Print four integers x1, y1, x2, y2, which represent the founded sub-rectangle whose left-bottom point is (x1, y1) and right-up point is (x2, y2).

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

Example input:
9 9 5 5 2 1

Example output:
1 3 9 7

Example input:
100 100 52 50 46 56

Example output:
17 8 86 92

Editorial:
Minimum Modular
Contest: Codeforces Round 183 (Div. 1)
Difficulty rating: 2400
Tags: brute force, graphs, math, number theory

You have been given n distinct integers a1, a2, ..., an. You can remove at most k of them. Find the minimum modular m (m > 0), so that for every pair of the remaining integers (ai, aj), the following unequality holds: $$a_{i} \not\equiv a_{j} \mod m$$.

Input format:
The first line contains two integers n and k (1  ≤ n  ≤ 5000, 0 ≤ k ≤ 4), which we have mentioned above.

The second line contains n distinct integers a1, a2, ..., an (0 ≤ ai ≤ 106).

Output format:
Print a single positive integer — the minimum m.

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

Example input:
7 0
0 2 3 6 7 12 18

Example output:
13

Example input:
7 1
0 2 3 6 7 12 18

Example output:
7

Editorial: