1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Paths
Contest: Technocup 2018 - Elimination Round 2
Difficulty rating: 2700
Tags: data structures, number theory

You are given a positive integer n. Let's build a graph on vertices 1, 2, ..., n in such a way that there is an edge between vertices u and v if and only if $${ \mathrm { g c d } } ( u, v ) \neq 1$$. Let d(u, v) be the shortest distance between u and v, or 0 if there is no path between them. Compute the sum of values d(u, v) over all 1 ≤ u < v ≤ n.

The gcd (greatest common divisor) of two positive integers is the maximum positive integer that divides both of the integers.

Input format:
Single integer n (1 ≤ n ≤ 107).

Output format:
Print the sum of d(u, v) over all 1 ≤ u < v ≤ n.

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

Note:
All shortest paths in the first example:

- $$2 \rightarrow 6 \rightarrow 3$$
- $$2 \rightarrow 4$$
- $$2 \rightarrow 6$$
- $$3 \rightarrow 6 \rightarrow 4$$
- $$3 \rightarrow 6$$
- $$\overrightarrow{4} \to \overrightarrow{6}$$

There are no paths between other pairs of vertices.

The total distance is 2 + 1 + 1 + 2 + 1 + 1 = 8.

Example input:
6

Example output:
8

Example input:
10

Example output:
44

Editorial:
Integer 1 ≤ x ≤ n is bad is x = 1 or x is prime and x > n / 2. Otherwise integer is good.
primex for 1 < x ≤ n is minimal prime divisor of x.
Path between two vertices doesn't exist if at least one of them is bad.
Distance equals to zero if this two vertices are the same.
Distance equals to one if their numbers have common divisor.
Distance between vertices u and v equals to two if primeu·primev ≤ n.
Otherwise distance is three because path $$u \rightarrow 2 \cdot prime_u \rightarrow 2 \cdot prime_v \rightarrow v$$ always exists.
It is easy to find number of pairs of vertices between which there is no path.
Number of pairs with distance 1 equals to sum over all good x of expressions x - 1 - φ(x).
Number of pairs with distance 3 can be found if we subtract number of pairs without path and number of pairs with distances 0 and 1 from number of all pairs.
So it only remains to find number of pairs with distance 2. Let's divide such pairs on three types
1) Pairs of coprime composite numbers.
2) Good prime p and good number x such as primep·primex ≤ n and x is not divided by p.
3) Two different good prime numbers, product of which is less or equal than n.
Number of pairs with distance 2 equals to number of pairs of the first and the second types minus number of pairs of the third type.
Number of pairs of the first type equals to sum over all composite 1 ≤ x ≤ n of expressions φ(x) - ((number of noncomposite numbers which are less than x) - number of unique prime divisors of x).
For the second type we should sum up over all prime p number of good numbers x such that primep·primex ≤ n and subtract number of such numbers divided by p. The first we can calculate with some additional precalculations, for the second we can just check all numbers divided by p.
Number of the pairs of the third type can be found trivially.
For other details please see the author's code.
Vasya and Book
Contest: Educational Codeforces Round 55 (Rated for Div. 2)
Difficulty rating: 1200
Tags: implementation, math

Vasya is reading a e-book. The file of the book consists of $$$n$$$ pages, numbered from $$$1$$$ to $$$n$$$. The screen is currently displaying the contents of page $$$x$$$, and Vasya wants to read the page $$$y$$$. There are two buttons on the book which allow Vasya to scroll $$$d$$$ pages forwards or backwards (but he cannot scroll outside the book). For example, if the book consists of $$$10$$$ pages, and $$$d = 3$$$, then from the first page Vasya can scroll to the first or to the fourth page by pressing one of the buttons; from the second page — to the first or to the fifth; from the sixth page — to the third or to the ninth; from the eighth — to the fifth or to the tenth.

Help Vasya to calculate the minimum number of times he needs to press a button to move to page $$$y$$$.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of testcases.

Each testcase is denoted by a line containing four integers $$$n$$$, $$$x$$$, $$$y$$$, $$$d$$$ ($$$1\le n, d \le 10^9$$$, $$$1 \le x, y \le n$$$) — the number of pages, the starting page, the desired page, and the number of pages scrolled by pressing one button, respectively.

Output format:
Print one line for each test.

If Vasya can move from page $$$x$$$ to page $$$y$$$, print the minimum number of times he needs to press a button to do it. Otherwise print $$$-1$$$.

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

Note:
In the first test case the optimal sequence is: $$$4 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 5$$$.

In the second test case it is possible to get to pages $$$1$$$ and $$$5$$$.

In the third test case the optimal sequence is: $$$4 \rightarrow 7 \rightarrow 10 \rightarrow 13 \rightarrow 16 \rightarrow 19$$$.

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

Example output:
4
-1
5

Editorial:
It is easy to understand that the optimal answer is achieved in one of three cases:
1. Vasya is trying to visit page $$$y$$$ without visiting pages $$$1$$$ and $$$n$$$;
2. Vasya first goes to the page $$$1$$$, and then to the page $$$y$$$;
3. Vasya first goes to the $$$n$$$ page, and then to the $$$y$$$ page.
In the first case, Vasya can go directly to the $$$y$$$ page from the $$$x$$$ page if $$$|x-y|$$$ is divided by $$$d$$$.
In the second case, Vasya can get to page $$$y$$$ through page $$$1$$$, if $$$y - 1$$$ is divided by $$$d$$$. The required number of actions will be equal to $$$\lceil \frac{x - 1}{d} \rceil + \frac{y - 1}{d}$$$.
Similarly, in the third case, Vasya can go to the page $$$y$$$ through the page $$$n$$$ if $$$n - y$$$ is divided by $$$d$$$. The required number of actions will be equal to $$$\lceil\frac{n - x}{d} \rceil + \frac{n - y}{d}$$$.
If none of the three options described above is appropriate, then there is no answer.
Vova and Trophies
Contest: Educational Codeforces Round 55 (Rated for Div. 2)
Difficulty rating: 1600
Tags: greedy

Vova has won $$$n$$$ trophies in different competitions. Each trophy is either golden or silver. The trophies are arranged in a row.

The beauty of the arrangement is the length of the longest subsegment consisting of golden trophies. Vova wants to swap two trophies (not necessarily adjacent ones) to make the arrangement as beautiful as possible — that means, to maximize the length of the longest such subsegment.

Help Vova! Tell him the maximum possible beauty of the arrangement if he is allowed to do at most one swap.

Input format:
The first line contains one integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of trophies.

The second line contains $$$n$$$ characters, each of them is either G or S. If the $$$i$$$-th character is G, then the $$$i$$$-th trophy is a golden one, otherwise it's a silver trophy.

Output format:
Print the maximum possible length of a subsegment of golden trophies, if Vova is allowed to do at most one swap.

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

Note:
In the first example Vova has to swap trophies with indices $$$4$$$ and $$$10$$$. Thus he will obtain the sequence "GGGGGGGSGS", the length of the longest subsegment of golden trophies is $$$7$$$.

In the second example Vova can make no swaps at all. The length of the longest subsegment of golden trophies in the sequence is $$$4$$$.

In the third example Vova cannot do anything to make the length of the longest subsegment of golden trophies in the sequence greater than $$$0$$$.

Example input:
10
GGGSGGGSGG

Example output:
7

Example input:
4
GGGG

Example output:
4

Editorial:
Let $$$r_i$$$ be the maximal segment of gold cups that begins in the cup $$$i$$$. Let $$$l_i$$$ be the maximum segment of gold cups that ends in the cup $$$i$$$. Also, let the total number of gold cups be $$$cntG$$$.
Note that it makes no sense to change the cups of the same color. Then let's consider the silver cup, which will change with the gold cup, let its number be $$$i$$$. Then if $$$r_{i + 1} + l_{i - 1} < cntG$$$, then we will update the answer with the value $$$r_{i + 1} + l_{i - 1} + 1$$$, and otherwise with the value $$$r_{i + 1} + l_{i - 1}$$$. This will not work if all the cups are golden. In this case, the answer is $$$n$$$.
Multi-Subject Competition
Contest: Educational Codeforces Round 55 (Rated for Div. 2)
Difficulty rating: 1600
Tags: greedy, sortings

A multi-subject competition is coming! The competition has $$$m$$$ different subjects participants can choose from. That's why Alex (the coach) should form a competition delegation among his students.

He has $$$n$$$ candidates. For the $$$i$$$-th person he knows subject $$$s_i$$$ the candidate specializes in and $$$r_i$$$ — a skill level in his specialization (this level can be negative!).

The rules of the competition require each delegation to choose some subset of subjects they will participate in. The only restriction is that the number of students from the team participating in each of the chosen subjects should be the same.

Alex decided that each candidate would participate only in the subject he specializes in. Now Alex wonders whom he has to choose to maximize the total sum of skill levels of all delegates, or just skip the competition this year if every valid non-empty delegation has negative sum.

(Of course, Alex doesn't have any spare money so each delegate he chooses must participate in the competition).

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le m \le 10^5$$$) — the number of candidates and the number of subjects.

The next $$$n$$$ lines contains two integers per line: $$$s_i$$$ and $$$r_i$$$ ($$$1 \le s_i \le m$$$, $$$-10^4 \le r_i \le 10^4$$$) — the subject of specialization and the skill level of the $$$i$$$-th candidate.

Output format:
Print the single integer — the maximum total sum of skills of delegates who form a valid delegation (according to rules above) or $$$0$$$ if every valid non-empty delegation has negative sum.

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

Note:
In the first example it's optimal to choose candidates $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, so two of them specialize in the $$$2$$$-nd subject and other two in the $$$3$$$-rd. The total sum is $$$6 + 6 + 5 + 5 = 22$$$.

In the second example it's optimal to choose candidates $$$1$$$, $$$2$$$ and $$$5$$$. One person in each subject and the total sum is $$$6 + 6 + 11 = 23$$$.

In the third example it's impossible to obtain a non-negative sum.

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

Example output:
22

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

Example output:
23

Editorial:
At first, it's optimal to take candidates with maximal levels for a fixed subject.
At second, if we fix number of participants in each subject for some delegation, then it's always optimal to choose all subjects with positive sum of levels.
It leads us to a following solution. Let's divide all candidates by it's $$$s_i$$$ and sort each group in non-increasing order.
In result we can just iterate over all prefix sums for each group and update global answer of current length with current sum if it has a positive value.
Maximum Diameter Graph
Contest: Educational Codeforces Round 55 (Rated for Div. 2)
Difficulty rating: 1800
Tags: constructive algorithms, graphs, implementation

Graph constructive problems are back! This time the graph you are asked to build should match the following properties.

The graph is connected if and only if there exists a path between every pair of vertices.

The diameter (aka "longest shortest path") of a connected undirected graph is the maximum number of edges in the shortest path between any pair of its vertices.

The degree of a vertex is the number of edges incident to it.

Given a sequence of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ construct a connected undirected graph of $$$n$$$ vertices such that:

- the graph contains no self-loops and no multiple edges;
- the degree $$$d_i$$$ of the $$$i$$$-th vertex doesn't exceed $$$a_i$$$ (i.e. $$$d_i \le a_i$$$);
- the diameter of the graph is maximum possible.

Output the resulting graph or report that no solution exists.

Input format:
The first line contains a single integer $$$n$$$ ($$$3 \le n \le 500$$$) — the number of vertices in the graph.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n - 1$$$) — the upper limits to vertex degrees.

Output format:
Print "NO" if no graph can be constructed under the given conditions.

Otherwise print "YES" and the diameter of the resulting graph in the first line.

The second line should contain a single integer $$$m$$$ — the number of edges in the resulting graph.

The $$$i$$$-th of the next $$$m$$$ lines should contain two integers $$$v_i, u_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$v_i \neq u_i$$$) — the description of the $$$i$$$-th edge. The graph should contain no multiple edges — for each pair $$$(x, y)$$$ you output, you should output no more pairs $$$(x, y)$$$ or $$$(y, x)$$$.

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

Note:
Here are the graphs for the first two example cases. Both have diameter of $$$2$$$.

$$$d_1 = 1 \le a_1 = 2$$$$$$d_2 = 2 \le a_2 = 2$$$$$$d_3 = 1 \le a_3 = 2$$$

$$$d_1 = 1 \le a_1 = 1$$$$$$d_2 = 4 \le a_2 = 4$$$$$$d_3 = 1 \le a_3 = 1$$$$$$d_4 = 1 \le a_4 = 1$$$

Example input:
3
2 2 2

Example output:
YES 2
2
1 2
2 3

Example input:
5
1 4 1 1 1

Example output:
YES 2
4
1 2
3 2
4 2
5 2

Editorial:
Let's construct the graph the following manner. Take all the vertices with $$$a_i > 1$$$ and build a bamboo out of them. Surely, all but the end ones will have degree $$$2$$$, the diameter now is the number of vertices minus 1.
One can show that building the graph any other way won't make the diameter greater.
How should we distribute the other vertices? Two of them can be used to increase diameter. And all the others won't matter, they can be paired with any of the vertices with degrees to spare. If no loops are added then the diameter won't change — the path that was the longest won't become any shorter.
All those facts imply that the graph should be a tree and the sum of $$$a_i$$$ should be at least $$$2n - 2$$$.
Overall complexity: $$$O(n)$$$.
Increasing Frequency
Contest: Educational Codeforces Round 55 (Rated for Div. 2)
Difficulty rating: 2000
Tags: binary search, dp, greedy

You are given array $$$a$$$ of length $$$n$$$. You can choose one segment $$$[l, r]$$$ ($$$1 \le l \le r \le n$$$) and integer value $$$k$$$ (positive, negative or even zero) and change $$$a_l, a_{l + 1}, \dots, a_r$$$ by $$$k$$$ each (i.e. $$$a_i := a_i + k$$$ for each $$$l \le i \le r$$$).

What is the maximum possible number of elements with value $$$c$$$ that can be obtained after one such operation?

Input format:
The first line contains two integers $$$n$$$ and $$$c$$$ ($$$1 \le n \le 5 \cdot 10^5$$$, $$$1 \le c \le 5 \cdot 10^5$$$) — the length of array and the value $$$c$$$ to obtain.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 5 \cdot 10^5$$$) — array $$$a$$$.

Output format:
Print one integer — the maximum possible number of elements with value $$$c$$$ which can be obtained after performing operation described above.

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

Note:
In the first example we can choose any segment and $$$k = 0$$$. The array will stay same.

In the second example we can choose segment $$$[1, 3]$$$ and $$$k = -4$$$. The array will become $$$[2, -2, 2]$$$.

Example input:
6 9
9 9 9 9 9 9

Example output:
6

Example input:
3 2
6 2 6

Example output:
2

Editorial:
Let $$$cnt(l, r, x)$$$ be a number of occurrences of number $$$x$$$ in subsegment $$$[l, r]$$$.
The given task is equivalent to choosing $$$[l, r]$$$ and value $$$d$$$ such that $$$ans = cnt(1, l - 1, c) + cnt(l, r, d) + cnt(r + 1, n, c)$$$ is maximum possible. But with some transformations $$$ans = cnt(1, n, c) + (cnt(l, r, d) - cnt(l, r, c))$$$ so we need to maximize $$$cnt(l, r, d) - cnt(l, r, c)$$$.
Key observation is the next: if we fix some value $$$d$$$ then we can shrink each segment between consecutive occurrences of $$$d$$$ in one element with weight equal to $$$-cnt(l_i, r_i, c)$$$. Then we need just to find subsegment with maximal sum — the standard task which can be solved in $$$O(cnt(1, n, d))$$$.
Finally, total complexity is $$$\sum\limits_{d}{O(cnt(1, n, d))} = O(n)$$$.
Cards
Contest: Codeforces Round 233 (Div. 1)
Tags: constructive algorithms, implementation

User ainta loves to play with cards. He has a cards containing letter "o" and b cards containing letter "x". He arranges the cards in a row, and calculates the score of the deck by the formula below.

1. At first, the score is 0.
2. For each block of contiguous "o"s with length x the score increases by x2.
3. For each block of contiguous "x"s with length y the score decreases by y2.

For example, if a = 6, b = 3 and ainta have arranged the cards in the order, that is described by string "ooxoooxxo", the score of the deck equals 22 - 12 + 32 - 22 + 12 = 9. That is because the deck has 5 blocks in total: "oo", "x", "ooo", "xx", "o".

User ainta likes big numbers, so he wants to maximize the score with the given cards. Help ainta make the score as big as possible. Note, that he has to arrange all his cards.

Input format:
The first line contains two space-separated integers a and b (0 ≤ a, b ≤ 105; a + b ≥ 1) — the number of "o" cards and the number of "x" cards.

Output format:
In the first line print a single integer v — the maximum score that ainta can obtain.

In the second line print a + b characters describing the deck. If the k-th card of the deck contains "o", the k-th character must be "o". If the k-th card of the deck contains "x", the k-th character must be "x". The number of "o" characters must be equal to a, and the number of "x " characters must be equal to b. If there are many ways to maximize v, print any.

Please, do not write 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

Example input:
2 3

Example output:
-1
xoxox

Example input:
4 0

Example output:
16
oooo

Editorial:
Painting The Wall
Contest: Codeforces Round 233 (Div. 1)
Tags: dp, probabilities

User ainta decided to paint a wall. The wall consists of n2 tiles, that are arranged in an n × n table. Some tiles are painted, and the others are not. As he wants to paint it beautifully, he will follow the rules below.

1. Firstly user ainta looks at the wall. If there is at least one painted cell on each row and at least one painted cell on each column, he stops coloring. Otherwise, he goes to step 2.
2. User ainta choose any tile on the wall with uniform probability.
3. If the tile he has chosen is not painted, he paints the tile. Otherwise, he ignores it.
4. Then he takes a rest for one minute even if he doesn't paint the tile. And then ainta goes to step 1.

However ainta is worried if it would take too much time to finish this work. So he wants to calculate the expected time needed to paint the wall by the method above. Help him find the expected time. You can assume that choosing and painting any tile consumes no time at all.

Input format:
The first line contains two integers n and m (1 ≤ n ≤ 2·103; 0 ≤ m ≤ min(n2, 2·104)) — the size of the wall and the number of painted cells.

Next m lines goes, each contains two integers ri and ci (1 ≤ ri, ci ≤ n) — the position of the painted cell. It is guaranteed that the positions are all distinct. Consider the rows of the table are numbered from 1 to n. Consider the columns of the table are numbered from 1 to n.

Output format:
In a single line print the expected time to paint the wall in minutes. Your answer will be considered correct if it has at most 10 - 4 absolute or relative error.

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

Example input:
5 2
2 3
4 1

Example output:
11.7669491886

Example input:
2 2
1 1
1 2

Example output:
2.0000000000

Editorial:
Tree and Array
Contest: Codeforces Round 233 (Div. 1)
Tags: constructive algorithms

User ainta likes trees. This time he is going to make an undirected tree with n vertices numbered by integers from 1 to n. The tree is weighted, so each edge of the tree will have some integer weight.

Also he has an array t: t[1], t[2], ..., t[n]. At first all the elements of the array are initialized to 0. Then for each edge connecting vertices u and v (u < v) of the tree with weight c, ainta adds value c to the elements t[u], t[u + 1], ..., t[v - 1], t[v] of array t.

Let's assume that d(u, v) is the total weight of edges on the shortest path between vertex u and vertex v. User ainta calls a pair of integers x, y (1 ≤ x < y ≤ n) good if and only if d(x, y) = t[x] + t[x + 1] + ... + t[y - 1] + t[y].

User ainta wants to make at least $$\left\lfloor \frac{n}{2} \right\rfloor$$ good pairs, but he couldn't make a proper tree. Help ainta to find such a tree.

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

Output format:
Print n - 1 lines containing the description of the edges. The i-th line should contain three space-separated integers ui, vi, ci (1 ≤ ui < vi ≤ n; 1 ≤ ci ≤ 105) — two vertices connected by the edge, and the weight of the edge.

Next print $$\left\lfloor \frac{n}{2} \right\rfloor$$ lines containing the good pairs. The k-th line should contain two space-separated integers xk and yk (1 ≤ xk < yk ≤ n). Of course, xk, yk must be a good pair. All pairs should be distinct — that is, for all j, k $$( 1 \leq j < k \leq [ \frac { n } { 2 } ] )$$, xj ≠ xk or yj ≠ yk must be satisfied.

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

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

Note:
⌊x⌋ is the largest integer not greater than x.

You can find the definition of a tree by the following link: http://en.wikipedia.org/wiki/Tree_(graph_theory)

You can also find the definition of the shortest path by the following link: http://en.wikipedia.org/wiki/Shortest_path_problem

The tree and the array t in the sample output look like this:

Example input:
7

Example output:
1 4 1
1 2 2
2 3 5
3 5 3
2 6 2
6 7 3
4 5
5 6
5 7

Editorial: