1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Happy Line
Contest: Looksery Cup 2015
Difficulty rating: 2200
Tags: constructive algorithms, greedy, sortings

Do you like summer? Residents of Berland do. They especially love eating ice cream in the hot summer. So this summer day a large queue of n Berland residents lined up in front of the ice cream stall. We know that each of them has a certain amount of berland dollars with them. The residents of Berland are nice people, so each person agrees to swap places with the person right behind him for just 1 dollar. More formally, if person a stands just behind person b, then person a can pay person b 1 dollar, then a and b get swapped. Of course, if person a has zero dollars, he can not swap places with person b.

Residents of Berland are strange people. In particular, they get upset when there is someone with a strictly smaller sum of money in the line in front of them.

Can you help the residents of Berland form such order in the line so that they were all happy? A happy resident is the one who stands first in the line or the one in front of who another resident stands with not less number of dollars. Note that the people of Berland are people of honor and they agree to swap places only in the manner described above.

Input format:
The first line contains integer n (1 ≤ n ≤ 200 000) — the number of residents who stand in the line.

The second line contains n space-separated integers ai (0 ≤ ai ≤ 109), where ai is the number of Berland dollars of a man standing on the i-th position in the line. The positions are numbered starting from the end of the line.

Output format:
If it is impossible to make all the residents happy, print ":(" without the quotes. Otherwise, print in the single line n space-separated integers, the i-th of them must be equal to the number of money of the person on position i in the new line. If there are multiple answers, print any of them.

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

Note:
In the first sample two residents should swap places, after that the first resident has 10 dollars and he is at the head of the line and the second resident will have 9 coins and he will be at the end of the line.

In the second sample it is impossible to achieve the desired result.

In the third sample the first person can swap with the second one, then they will have the following numbers of dollars: 4 11 3, then the second person (in the new line) swaps with the third one, and the resulting numbers of dollars will equal to: 4 4 10. In this line everybody will be happy.

Example input:
2
11 8

Example output:
9 10

Example input:
5
10 9 7 10 6

Example output:
:(

Editorial:
Degenerate Matrix
Contest: Looksery Cup 2015
Difficulty rating: 2100
Tags: binary search, math

The determinant of a matrix 2 × 2 is defined as follows:

$$\operatorname*{det}\left(\begin{array}{cc}
a & b \\
c & d
\end{array}\right) = ad - bc$$

A matrix is called degenerate if its determinant is equal to zero.

The norm ||A|| of a matrix A is defined as a maximum of absolute values of its elements.

You are given a matrix $${\boldsymbol{A}}={\begin{pmatrix}a&b\\c&d\end{pmatrix}}$$. Consider any degenerate matrix B such that norm ||A - B|| is minimum possible. Determine ||A - B||.

Input format:
The first line contains two integers a and b (|a|, |b| ≤ 109), the elements of the first row of matrix A.

The second line contains two integers c and d (|c|, |d| ≤ 109) the elements of the second row of matrix A.

Output format:
Output a single real number, the minimum possible value of ||A - B||. Your answer is considered to be correct if its absolute or relative error does not exceed 10 - 9.

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

Note:
In the first sample matrix B is $${ \left( \begin{array} { l l } { 1. 2 } & { 1. 8 } \\ { 2. 8 } & { 4. 2 } \end{array} \right) }$$

In the second sample matrix B is $${ \left( \begin{array} { l l } { 0. 5 } & { 0. 5 } \\ { 0. 5 } & { 0. 5 } \end{array} \right) }$$

Example input:
1 2
3 4

Example output:
0.2000000000

Example input:
1 0
0 1

Example output:
0.5000000000

Editorial:
The rows of degenerate matrix are linear dependent so the matrix B can be written in the following way: $${ \left( \begin{array} { l } { x } \\ { k \cdot x } \end{array} \right) }$$. Suppose $$A = \begin{pmatrix} x_0 & y_0 \\ x_1 & y_1 \end{pmatrix}$$. Let's assume that elements of the first row of matrix A are coordinates of point a0 on two-dimensional plane and the elements of the second row are coordinates of point a1. Assume that the rows of matrix B are also coordinates of points b0 and b1. Let's note that in this case the line that is passing through points b0 and b1 is also passing through point (0, 0).
Let's find the answer — the number d — by using binary search. Suppose we are considering some number d0. We need to check if there is such matrix B that $${ \left| \begin{array} { l l } { x_{ 0 } - x } & { y _ { 0 } - y } \\ { x _ { 1 } - k \cdot x } & { y _ { 1 } - k \cdot y } \end{array} \right| } \leq d _ { 0 }$$. In geometric interpretation it means that point b0 are inside the square which center is point a0 and length of side is 2·d0. In the same way the point b1 are inside the square which center is point a1 and length of side is 2·d0. So we need to check if there is a line that is passing through point (0, 0) and is crossing these squares. In order to do this we should consider every vertex of the first square, build the line that is passing through the chosen vertex and the center of coordinate plane and check if it cross any side of the other square. Afterwards we should swap the squares and check again. Finally if there is a desired line we need to reduce the search area and to expand otherwise.
Fafa and his Company
Contest: Codeforces Round 465 (Div. 2)
Difficulty rating: 800
Tags: brute force, implementation

Fafa owns a company that works on huge projects. There are n employees in Fafa's company. Whenever the company has a new project to start working on, Fafa has to divide the tasks of this project among all the employees.

Fafa finds doing this every time is very tiring for him. So, he decided to choose the best l employees in his company as team leaders. Whenever there is a new project, Fafa will divide the tasks among only the team leaders and each team leader will be responsible of some positive number of employees to give them the tasks. To make this process fair for the team leaders, each one of them should be responsible for the same number of employees. Moreover, every employee, who is not a team leader, has to be under the responsibility of exactly one team leader, and no team leader is responsible for another team leader.

Given the number of employees n, find in how many ways Fafa could choose the number of team leaders l in such a way that it is possible to divide employees between them evenly.

Input format:
The input consists of a single line containing a positive integer n (2 ≤ n ≤ 105) — the number of employees in Fafa's company.

Output format:
Print a single integer representing the answer to the problem.

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

Note:
In the second sample Fafa has 3 ways:

- choose only 1 employee as a team leader with 9 employees under his responsibility.
- choose 2 employees as team leaders with 4 employees under the responsibility of each of them.
- choose 5 employees as team leaders with 1 employee under the responsibility of each of them.

Example input:
2

Example output:
1

Example input:
10

Example output:
3

Editorial:
Let's try all values of l from 1 to n - 1 and check whether the remaining people could be distributed equally over team leaders (that is, l divides n - l). The number of valid values of l is our answer. Complexity: O(n).
The problem is also equivalent to finding the number of ways to divide the n employees into equal teams where each team contains more than one employee. It can also be solved in $$O(\sqrt{n})$$ by finding the number of divisors of n.
Fafa and the Gates
Contest: Codeforces Round 465 (Div. 2)
Difficulty rating: 900
Tags: implementation

Two neighboring kingdoms decided to build a wall between them with some gates to enable the citizens to go from one kingdom to another. Each time a citizen passes through a gate, he has to pay one silver coin.

The world can be represented by the first quadrant of a plane and the wall is built along the identity line (i.e. the line with the equation x = y). Any point below the wall belongs to the first kingdom while any point above the wall belongs to the second kingdom. There is a gate at any integer point on the line (i.e. at points (0, 0), (1, 1), (2, 2), ...). The wall and the gates do not belong to any of the kingdoms.

Fafa is at the gate at position (0, 0) and he wants to walk around in the two kingdoms. He knows the sequence S of moves he will do. This sequence is a string where each character represents a move. The two possible moves Fafa will do are 'U' (move one step up, from (x, y) to (x, y + 1)) and 'R' (move one step right, from (x, y) to (x + 1, y)).

Fafa wants to know the number of silver coins he needs to pay to walk around the two kingdoms following the sequence S. Note that if Fafa visits a gate without moving from one kingdom to another, he pays no silver coins. Also assume that he doesn't pay at the gate at point (0, 0), i. e. he is initially on the side he needs.

Input format:
The first line of the input contains single integer n (1 ≤ n ≤ 105) — the number of moves in the walking sequence.

The second line contains a string S of length n consisting of the characters 'U' and 'R' describing the required moves. Fafa will follow the sequence S in order from left to right.

Output format:
On a single line, print one integer representing the number of silver coins Fafa needs to pay at the gates to follow the sequence S.

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

Note:
The figure below describes the third sample. The red arrows represent the sequence of moves Fafa will follow. The green gates represent the gates at which Fafa have to pay silver coins.

Example input:
1
U

Example output:
0

Example input:
6
RURUUR

Example output:
1

Editorial:
Fafa visits the gates when he stands on the line y = x. This happens only when he makes an equal number of up and right moves. Fafa will pass the gates if he is currently at a gate and will make a move similar to the last one.
So, we can iterate over the moves in order from left to right keeping track of the number of up and right moves till now, and increment the answer if the next move is similar to the current one and the number of up and right moves are equal.
Complexity: O(n).
Fifa and Fafa
Contest: Codeforces Round 465 (Div. 2)
Difficulty rating: 1600
Tags: geometry

Fifa and Fafa are sharing a flat. Fifa loves video games and wants to download a new soccer game. Unfortunately, Fafa heavily uses the internet which consumes the quota. Fifa can access the internet through his Wi-Fi access point. This access point can be accessed within a range of r meters (this range can be chosen by Fifa) from its position. Fifa must put the access point inside the flat which has a circular shape of radius R. Fifa wants to minimize the area that is not covered by the access point inside the flat without letting Fafa or anyone outside the flat to get access to the internet.

The world is represented as an infinite 2D plane. The flat is centered at (x1, y1) and has radius R and Fafa's laptop is located at (x2, y2), not necessarily inside the flat. Find the position and the radius chosen by Fifa for his access point which minimizes the uncovered area.

Input format:
The single line of the input contains 5 space-separated integers R, x1, y1, x2, y2 (1 ≤ R ≤ 105, |x1|, |y1|, |x2|, |y2| ≤ 105).

Output format:
Print three space-separated numbers xap, yap, r where (xap, yap) is the position which Fifa chose for the access point and r is the radius of its range.

Your answer will be considered correct if the radius does not differ from optimal more than 10 - 6 absolutely or relatively, and also the radius you printed can be changed by no more than 10 - 6 (absolutely or relatively) in such a way that all points outside the flat and Fafa's laptop position are outside circle of the access point range.

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

Example input:
5 3 3 1 1

Example output:
3.7677669529663684 3.7677669529663684 3.914213562373095

Example input:
10 5 5 5 15

Example output:
5.0 5.0 10.0

Editorial:
Let p be Fafa's position and c be the flat center. Obviously, the largest wifi circle we can draw will touch the point p and a point on the flat circle border q. The diameter of the circle will be the distance between p and q. To maximize the area of the wifi circle, we will choose q to be the furthest point on the border from p. This point lies on the line connecting p and c. The center of wifi circle w will be the midpoint of the line segment connecting p and q.
If the point p is outside the circle, then the wifi circle will be the flat circle (w = c). If the point p lies on the flat center (p = c), then there are infinite number of solutions as q can be any point on the flat circle border.
Complexity: O(1)
Fafa and Ancient Alphabet
Contest: Codeforces Round 465 (Div. 2)
Difficulty rating: 1900
Tags: math, probabilities

Ancient Egyptians are known to have used a large set of symbols $$\Sigma$$ to write on the walls of the temples. Fafa and Fifa went to one of the temples and found two non-empty words S1 and S2 of equal lengths on the wall of temple written one below the other. Since this temple is very ancient, some symbols from the words were erased. The symbols in the set $$\Sigma$$ have equal probability for being in the position of any erased symbol.

Fifa challenged Fafa to calculate the probability that S1 is lexicographically greater than S2. Can you help Fafa with this task?

You know that $$\sum = m$$, i. e. there were m distinct characters in Egyptians' alphabet, in this problem these characters are denoted by integers from 1 to m in alphabet order. A word x is lexicographically greater than a word y of the same length, if the words are same up to some position, and then the word x has a larger character, than the word y.

We can prove that the probability equals to some fraction $$P / Q$$, where P and Q are coprime integers, and $$Q \not\equiv 0 \pmod{10^9 + 7}$$. Print as the answer the value $$R = P \cdot Q^{-1} \mod (10^9 + 7)$$, i. e. such a non-negative integer less than 109 + 7, such that $$R \cdot Q \equiv P \mod (10^9 + 7)$$, where $$a \equiv b \mod (m)$$ means that a and b give the same remainders when divided by m.

Input format:
The first line contains two integers n and m (1 ≤ n,  m ≤ 105) — the length of each of the two words and the size of the alphabet $$\Sigma$$, respectively.

The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ m) — the symbols of S1. If ai = 0, then the symbol at position i was erased.

The third line contains n integers representing S2 with the same format as S1.

Output format:
Print the value $$P \cdot Q^{-1} \mod (10^9 + 7)$$, where P and Q are coprime and $$P / Q$$ is the answer to the problem.

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

Note:
In the first sample, the first word can be converted into (1) or (2). The second option is the only one that will make it lexicographically larger than the second word. So, the answer to the problem will be $${ \frac { 1 } { 2 } } \mod ( 1 0 ^ { 9 } + 7 )$$, that is 500000004, because $$(500000004 \cdot 2) \bmod (10^9 + 7) = 1$$.

In the second example, there is no replacement for the zero in the second word that will make the first one lexicographically larger. So, the answer to the problem is $${ \frac { 0 } { 1 } } { \bmod { ( 1 0 ^ { 9 } + 7 ) } }$$, that is 0.

Example input:
1 2
0
1

Example output:
500000004

Example input:
1 2
1
0

Example output:
0

Editorial:
Let Suff1(i) and Suff2(i) be the suffixes of S1 and S2 starting from index i, respectively. Also, let P(i) be the probability of Suff1(i) being lexicographically larger than Suff2(i). P(i) is equal to the probability that:
• S1[i] is greater than S2[i], or
• S1[i] is equal to S2[i] and Suff1(i + 1) is lexicographically greater than Suff2(i + 1).
More formally,
The answer to the problem is P(0).
Complexity: O(n)
Fafa and Ancient Mathematics
Contest: Codeforces Round 465 (Div. 2)
Difficulty rating: 2300
Tags: dfs and similar, dp, trees

Ancient Egyptians are known to have understood difficult concepts in mathematics. The ancient Egyptian mathematician Ahmes liked to write a kind of arithmetic expressions on papyrus paper which he called as Ahmes arithmetic expression.

An Ahmes arithmetic expression can be defined as:

- "d" is an Ahmes arithmetic expression, where d is a one-digit positive integer;
- "(E1 op E2)" is an Ahmes arithmetic expression, where E1 and E2 are valid Ahmes arithmetic expressions (without spaces) and op is either plus ( + ) or minus ( - ).

On his trip to Egypt, Fafa found a piece of papyrus paper having one of these Ahmes arithmetic expressions written on it. Being very ancient, the papyrus piece was very worn out. As a result, all the operators were erased, keeping only the numbers and the brackets. Since Fafa loves mathematics, he decided to challenge himself with the following task:

Given the number of plus and minus operators in the original expression, find out the maximum possible value for the expression on the papyrus paper after putting the plus and minus operators in the place of the original erased operators.

Input format:
The first line contains a string E (1 ≤ |E| ≤ 104) — a valid Ahmes arithmetic expression. All operators are erased and replaced with '?'.

The second line contains two space-separated integers P and M (0 ≤ min(P, M) ≤ 100) — the number of plus and minus operators, respectively.

It is guaranteed that P + M =  the number of erased operators.

Output format:
Print one line containing the answer to the problem.

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

Note:
- The first sample will be (1 + 1)  =  2.
- The second sample will be (2 + (1 - 2))  =  1.
- The third sample will be ((1 - (5 - 7)) + ((6 + 2) + 7))  =  18.
- The fourth sample will be ((1 + (5 + 7)) - ((6 - 2) - 7))  =  16.

Example input:
(1?1)
1 0

Example output:
2

Example input:
(2?(1?2))
1 1

Example output:
1

Editorial:
We can represent the arithmetic expression as a binary tree where:
• each leaf node is a digit.
• each non-leaf node is an operator and the left and right subtrees are the operands.
To maximize the value of the sub-expression represented by a subtree rooted at v, we will either:
• put a plus (+) operator at v, and maximize the values of left(v) and right(v) subtrees, or
• put a minus (-) operator at v, and maximize the value of left(v) subtree and minimize the value of right(v) subtree.
We can solve this task using DP keeping in mind the number of remaining operators of each type. The DP state will be (v, rem + , rem - ). However, this state will not fit in time or memory limits. Since min(P, M) ≤ 100, we can drop the larger of the last two parameters and implicitly calculate it from the other parameter and the subtree size.
Fafa and Array
Contest: Codeforces Round 465 (Div. 2)
Difficulty rating: 2600
Tags: data structures, greedy

Fafa has an array A of n positive integers, the function f(A) is defined as $$\sum_{i=1}^{n-1} |a_i - a_{i+1}|$$. He wants to do q queries of two types:

- 1 l r x — find the maximum possible value of f(A), if x is to be added to one element in the range [l,  r]. You can choose to which element to add x.
- 2 l r x — increase all the elements in the range [l,  r] by value x.

Note that queries of type 1 don't affect the array elements.

Input format:
The first line contains one integer n (3 ≤ n ≤ 105) — the length of the array.

The second line contains n positive integers a1, a2, ..., an (0 < ai ≤ 109) — the array elements.

The third line contains an integer q (1 ≤ q ≤ 105) — the number of queries.

Then q lines follow, line i describes the i-th query and contains four integers ti li ri xi $$( t _ { i } \in \{ 1, 2 \}, 1 < l _ { i } \leq r _ { i } < n, 0 < x _ { i } \leq 1 0 ^ { 9 } )$$.

It is guaranteed that at least one of the queries is of type 1.

Output format:
For each query of type 1, print the answer to the query.

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

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

Example output:
2
8

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

Example output:
6
10

Editorial:
Let's have a look at the relation of each element ai with its adjacent elements. Without loss of generality, assume ai has two adjacent elements bi and ci where bi ≤ ci. One of the following cases will hold for ai, bi and ci:
1. ai ≥ bi and ai ≥ ci.
2. ai ≥ bi and ai < ci.
3. ai < bi and ai < ci.
For a query 1 l r x:
• if there exists an element ai, where $$i \in [l, r]$$, such that case 1 holds, then it is the best element on which we can apply the add operation because it will increment f(A) by 2·x.
• if case 1 doesn't exist, then there is at most one element for which case 3 holds (you can prove this by contradiction). Let's assume that this case holds for element ai, where $$i \in [l, r]$$. Then we will either:   increment the element aj where $$j \in [l,r]$$, j ≠ i and j = argmink{ck - ak}. The value of f(A) will be incremented by 2·max(0, x - (ck - ak)).  increment the element ai. The value of f(A) will be incremented by 2·max(0, x - (ci - ai)) - 2·min(bi - ai, x).
• increment the element aj where $$j \in [l,r]$$, j ≠ i and j = argmink{ck - ak}. The value of f(A) will be incremented by 2·max(0, x - (ck - ak)).
• increment the element ai. The value of f(A) will be incremented by 2·max(0, x - (ci - ai)) - 2·min(bi - ai, x).
• if neither case 1 nor case 3 exists, then we can only the second option of the previous case.
For a query 2 l r x: the only affected elements will be al - 1, al, ar, ar + 1.
We can use segment trees to answer queries in O(logn) time.
Complexity: $${\mathcal O}(n+q\cdot\log n)$$
Array Divisibility
Contest: Codeforces Round 956 (Div. 2) and ByteRace 2024
Difficulty rating: 800
Tags: constructive algorithms, math

An array of integers $$$a_1,a_2,\cdots,a_n$$$ is beautiful subject to an integer $$$k$$$ if it satisfies the following:

- The sum of $$$a_{j}$$$ over all $$$j$$$ such that $$$j$$$ is a multiple of $$$k$$$ and $$$1 \le j \le n $$$, itself, is a multiple of $$$k$$$.
- More formally, if $$$\sum_{k | j} a_{j}$$$ is divisible by $$$k$$$ for all $$$1 \le j \le n$$$ then the array $$$a$$$ is beautiful subject to $$$k$$$. Here, the notation $$${k|j}$$$ means $$$k$$$ divides $$$j$$$, that is, $$$j$$$ is a multiple of $$$k$$$.

It can be shown that an answer always exists.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first and only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the size of the array.

Output format:
For each test case, print the required array as described in the problem statement.

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

Note:
In the second test case, when $$$n = 6$$$, for all integers $$$k$$$ such that $$$1 \le k \le 6$$$, let $$$S$$$ be the set of all indices of the array that are divisible by $$$k$$$.

- When $$$k = 1$$$, $$$S = \{1, 2, 3,4,5,6\}$$$ meaning $$$a_1+a_2+a_3+a_4+a_5+a_6=242$$$ must be divisible by $$$1$$$.
- When $$$k = 2$$$, $$$S = \{2,4,6\}$$$ meaning $$$a_2+a_4+a_6=92$$$ must be divisible by $$$2$$$.
- When $$$k = 3$$$, $$$S = \{3,6\}$$$ meaning $$$a_3+a_6=69$$$ must divisible by $$$3$$$.
- When $$$k = 4$$$, $$$S = \{4\}$$$ meaning $$$a_4=32$$$ must divisible by $$$4$$$.
- When $$$k = 5$$$, $$$S = \{5\}$$$ meaning $$$a_5=125$$$ must divisible by $$$5$$$.
- When $$$k = 6$$$, $$$S = \{6\}$$$ meaning $$$a_6=54$$$ must divisible by $$$6$$$.

Example input:
3
3
6
7

Example output:
4 22 18
10 6 15 32 125 54
23 18 27 36 5 66 7

Editorial:
The construction $$$a[i] = i$$$ for all $$$1 \le i \le n$$$ satisfies all the required conditions.