1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Vasya and Isolated Vertices
Contest: Educational Codeforces Round 52 (Rated for Div. 2)
Difficulty rating: 1300
Tags: constructive algorithms, graphs

Vasya has got an undirected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. This graph doesn't contain any self-loops or multiple edges. Self-loop is an edge connecting a vertex to itself. Multiple edges are a pair of edges such that they connect the same pair of vertices. Since the graph is undirected, the pair of edges $$$(1, 2)$$$ and $$$(2, 1)$$$ is considered to be multiple edges. Isolated vertex of the graph is a vertex such that there is no edge connecting this vertex to any other vertex.

Vasya wants to know the minimum and maximum possible number of isolated vertices in an undirected graph consisting of $$$n$$$ vertices and $$$m$$$ edges.

Input format:
The only line contains two integers $$$n$$$ and $$$m~(1 \le n \le 10^5, 0 \le m \le \frac{n (n - 1)}{2})$$$.

It is guaranteed that there exists a graph without any self-loops or multiple edges with such number of vertices and edges.

Output format:
In the only line print two numbers $$$min$$$ and $$$max$$$ — the minimum and maximum number of isolated vertices, respectively.

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

Note:
In the first example it is possible to construct a graph with $$$0$$$ isolated vertices: for example, it should contain edges $$$(1, 2)$$$ and $$$(3, 4)$$$. To get one isolated vertex, we may construct a graph with edges $$$(1, 2)$$$ and $$$(1, 3)$$$.

In the second example the graph will always contain exactly one isolated vertex.

Example input:
4 2

Example output:
0 1

Example input:
3 1

Example output:
1 1

Editorial:
Vasya can decrease number of isolated vertices up to $$$2$$$ using one edge and pairing them. So minimum number of isolated vertices is $$$max(0, n - 2m)$$$.
To calculate maximum number of isolated vertices let's keep number of non-isolated vertices knowing that each pair connected by edge (i.e. size of clique). Let we have size of clique $$$cur$$$ and $$$rem$$$ edges remained unassigned at current step. If $$$rem = 0$$$ then answer is $$$n - cur$$$. Otherwise we need to increase clique with one vertex. Maximum number of edges we can add to connect this vertex is $$$add = min~(rem, cur)$$$. So, subtract it from $$$rem$$$ and increase $$$cur$$$ by one. Repeat this step while $$$rem$$$ greater than zero. Answer is $$$n - cur$$$.
One corner case is next: if $$$cur = 1$$$, then answer is $$$n$$$, not $$$n - cur$$$.
Make It Equal
Contest: Educational Codeforces Round 52 (Rated for Div. 2)
Difficulty rating: 1600
Tags: greedy

There is a toy building consisting of $$$n$$$ towers. Each tower consists of several cubes standing on each other. The $$$i$$$-th tower consists of $$$h_i$$$ cubes, so it has height $$$h_i$$$.

Let's define operation slice on some height $$$H$$$ as following: for each tower $$$i$$$, if its height is greater than $$$H$$$, then remove some top cubes to make tower's height equal to $$$H$$$. Cost of one "slice" equals to the total number of removed cubes from all towers.

Let's name slice as good one if its cost is lower or equal to $$$k$$$ ($$$k \ge n$$$).

Calculate the minimum number of good slices you have to do to make all towers have the same height. Of course, it is always possible to make it so.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$n \le k \le 10^9$$$) — the number of towers and the restriction on slices, respectively.

The second line contains $$$n$$$ space separated integers $$$h_1, h_2, \dots, h_n$$$ ($$$1 \le h_i \le 2 \cdot 10^5$$$) — the initial heights of towers.

Output format:
Print one integer — the minimum number of good slices you have to do to make all towers have the same heigth.

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

Note:
In the first example it's optimal to make $$$2$$$ slices. The first slice is on height $$$2$$$ (its cost is $$$3$$$), and the second one is on height $$$1$$$ (its cost is $$$4$$$).

Example input:
5 5
3 1 2 2 4

Example output:
2

Example input:
4 5
2 3 4 5

Example output:
2

Editorial:
Let's iterate over height $$$pos$$$ of slice in decreasing order. All we need to know is a number of towers with height more than $$$pos$$$ (name it $$$c$$$) and sum of its heights $$$sum$$$.
Current slice on height $$$pos$$$ is good if $$$k \ge sum - c \cdot pos$$$. Let's greedily decrease value $$$pos$$$ while slice on $$$pos$$$ is good keeping correct values $$$c$$$ and $$$sum$$$. When we found minimal good slice we can perform it increasing answer by one and "changing tower heights" just by setting new value to $$$sum$$$ equal to $$$c \cdot pos$$$.
Finish algorithm when $$$pos$$$ becomes equal to minimal height of towers and make final slice.
Display Size
Contest: Codeforces Round 387 (Div. 2)
Difficulty rating: 800
Tags: brute force, math

A big company decided to launch a new series of rectangular displays, and decided that the display must have exactly n pixels.

Your task is to determine the size of the rectangular display — the number of lines (rows) of pixels a and the number of columns of pixels b, so that:

- there are exactly n pixels on the display;
- the number of rows does not exceed the number of columns, it means a ≤ b;
- the difference b - a is as small as possible.

Input format:
The first line contains the positive integer n (1 ≤ n ≤ 106) — the number of pixels display should have.

Output format:
Print two integers — the number of rows and columns on the display.

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

Note:
In the first example the minimum possible difference equals 2, so on the display should be 2 rows of 4 pixels.

In the second example the minimum possible difference equals 0, so on the display should be 8 rows of 8 pixels.

In the third example the minimum possible difference equals 4, so on the display should be 1 row of 5 pixels.

Example input:
8

Example output:
2 4

Example input:
64

Example output:
8 8

Editorial:
We can iterate through the values of a from 1 to n. For each i if n mod i = 0 and if abs(i - n / i) is less than already found different we need to update answer with values min(i, n / i) and max(i, n / i) (because a must be less than b).
Mammoth's Genome Decoding
Contest: Codeforces Round 387 (Div. 2)
Difficulty rating: 900
Tags: implementation, strings

The process of mammoth's genome decoding in Berland comes to its end!

One of the few remaining tasks is to restore unrecognized nucleotides in a found chain s. Each nucleotide is coded with a capital letter of English alphabet: 'A', 'C', 'G' or 'T'. Unrecognized nucleotides are coded by a question mark '?'. Thus, s is a string consisting of letters 'A', 'C', 'G', 'T' and characters '?'.

It is known that the number of nucleotides of each of the four types in the decoded genome of mammoth in Berland should be equal.

Your task is to decode the genome and replace each unrecognized nucleotide with one of the four types so that the number of nucleotides of each of the four types becomes equal.

Input format:
The first line contains the integer n (4 ≤ n ≤ 255) — the length of the genome.

The second line contains the string s of length n — the coded genome. It consists of characters 'A', 'C', 'G', 'T' and '?'.

Output format:
If it is possible to decode the genome, print it. If there are multiple answer, print any of them. If it is not possible, print three equals signs in a row: "===" (without quotes).

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

Note:
In the first example you can replace the first question mark with the letter 'A', the second question mark with the letter 'G', the third question mark with the letter 'T', then each nucleotide in the genome would be presented twice.

In the second example the genome is already decoded correctly and each nucleotide is exactly once in it.

In the third and the fourth examples it is impossible to decode the genom.

Example input:
8
AG?C??CT

Example output:
AGACGTCT

Example input:
4
AGCT

Example output:
AGCT

Editorial:
Let n is the length of the given string. The number of each letter in the resulting string must be equals to n / 4. If n mod 4 does not equal to 0 — there is no solution.
If some letter meets in the given string more than n / 4 times — there is no solution.
After that we always can build the answer. We need to iterate through the given string and change question symbols on any letter, which meets in the current string less than n / 4 times.
Igor and Interesting Numbers
Contest: Codeforces Round 387 (Div. 2)
Difficulty rating: 2500
Tags: brute force, combinatorics, dp, math

Igor likes hexadecimal notation and considers positive integer in the hexadecimal notation interesting if each digit and each letter in it appears no more than t times. For example, if t = 3, then integers 13a13322, aaa, abcdef0123456789 are interesting, but numbers aaaa, abababab and 1000000 are not interesting.

Your task is to find the k-th smallest interesting for Igor integer in the hexadecimal notation. The integer should not contain leading zeros.

Input format:
The first line contains the two integers k and t (1 ≤ k ≤ 2·109, 1 ≤ t ≤ 10) — the number of the required integer and the maximum number of times some integer or letter can appear in interesting integer.

It can be shown that the answer always exists for such constraints.

Output format:
Print in the hexadecimal notation the only integer that is the k-th smallest interesting integer for Igor.

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

Note:
The first 20 interesting integers if t = 1: 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, 10, 12, 13, 14, 15. So the answer for the first example equals 12.

Example input:
17 1

Example output:
12

Example input:
1000000 2

Example output:
fca2c

Editorial:
Let's use dynamic programming and dp[i][j] — the number of valid numbers with length i and maximal digit in this numbers is j. Let iterate by nj from j + 1 and brute len (how many times we will take digit nj). Than new length ni - i + len, number will ends to nj repeated len times. Then dp[ni][nj] = dp[i][j] * (ni! / (i! * len!)).
After that we need to find the length of the answer number lenAns. Let iterate by lenAns from 1 and calculate the number of numbers with length lenAns. It can be done with help of dp (brute maximum digit and calculate dp for len - 1).
Array GCD
Contest: AIM Tech Round (Div. 1)
Difficulty rating: 2300
Tags: dp, greedy, number theory

You are given array ai of length n. You may consecutively apply two operations to this array:

- remove some subsegment (continuous subsequence) of length m < n and pay for it m·a coins;
- change some elements of the array by at most 1, and pay b coins for each change.

Please note that each of operations may be applied at most once (and may be not applied at all) so you can remove only one segment and each number may be changed (increased or decreased) by at most 1. Also note, that you are not allowed to delete the whole array.

Your goal is to calculate the minimum number of coins that you need to spend in order to make the greatest common divisor of the elements of the resulting array be greater than 1.

Input format:
The first line of the input contains integers n, a and b (1 ≤ n ≤ 1 000 000, 0 ≤ a, b ≤ 109) — the length of the array, the cost of removing a single element in the first operation and the cost of changing an element, respectively.

The second line contains n integers ai (2 ≤ ai ≤ 109) — elements of the array.

Output format:
Print a single number — the minimum cost of changes needed to obtain an array, such that the greatest common divisor of all its elements is greater than 1.

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

Note:
In the first sample the optimal way is to remove number 3 and pay 1 coin for it.

In the second sample you need to remove a segment [17, 13] and then decrease number 6. The cost of these changes is equal to 2·3 + 2 = 8 coins.

Example input:
3 1 4
4 2 3

Example output:
1

Example input:
5 3 2
5 17 13 5 6

Example output:
8

Editorial:
At least one of ends (a1 or an) is changed by at most 1. It means that if gcd > 1 then it divides on of prime divisors of either a1 - 1, a1, a1 + 1, an - 1, an or an + 1. We will iterate over these primes.
Suppose prime p is fixed. For each number we know that it's either divisible by p or we can pay b to fix it or it should be in the subarray to change for a
We can use dynamic programming dp[number of numbers considered][subarray to change not started/started/finished] = minimal cost
Complexity is O(Nd) = O(Nlog(max(ai)), where d is the number of primes to check.
Electric Charges
Contest: AIM Tech Round (Div. 1)
Difficulty rating: 2900
Tags: binary search, dp

Programmer Sasha is a student at MIPT (Moscow Institute of Physics and Technology) and he needs to make a laboratory work to pass his finals.

A laboratory unit is a plane with standard coordinate axes marked on it. Physicists from Moscow Institute of Physics and Technology charged the axes by large electric charges: axis X is positive and axis Y is negative.

Experienced laboratory worker marked n points with integer coordinates (xi, yi) on the plane and stopped the time. Sasha should use "atomic tweezers" to place elementary particles in these points. He has an unlimited number of electrons (negatively charged elementary particles) and protons (positively charged elementary particles). He can put either an electron or a proton at each marked point. As soon as all marked points are filled with particles, laboratory worker will turn on the time again and the particles will come in motion and after some time they will stabilize in equilibrium. The objective of the laboratory work is to arrange the particles in such a way, that the diameter of the resulting state (the maximum distance between the pairs of points of the set) is as small as possible.

Since Sasha is a programmer, he naively thinks that all the particles will simply "fall" into their projections on the corresponding axes: electrons will fall on axis X, while protons will fall on axis Y. As we are programmers too, we will consider the same model as Sasha. That is, a particle gets from point (x, y) to point (x, 0) if it is an electron and to point (0, y) if it is a proton.

As the laboratory has high background radiation and Sasha takes care of his laptop, he did not take it with him, and now he can't write a program that computes the minimum possible diameter of the resulting set. Therefore, you will have to do it for him.

Print a square of the minimum possible diameter of the set.

Input format:
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of points marked on the plane.

Each of the next n lines contains two integers xi and yi ( - 108 ≤ xi, yi ≤ 108) — the coordinates of the i-th point. It is guaranteed that no two points coincide.

Output format:
Print a single integer — the square of the minimum possible diameter of the set.

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

Note:
In the first sample Sasha puts electrons at all points, all particles eventually fall at a single point (1, 0).

In the second sample Sasha puts an electron at point (1, 10), and a proton at point (10, 1). The result is a set of two points (1, 0) and (0, 1), which has a diameter of $$\sqrt{2}$$.

Example input:
3
1 10
1 20
1 30

Example output:
0

Example input:
2
1 10
10 1

Example output:
2

Editorial:
Birthday
Contest: AIM Tech Round (Div. 1)
Difficulty rating: 2700
Tags: greedy, math, probabilities

A MIPT student named Misha has a birthday today, and he decided to celebrate it in his country house in suburban Moscow. n friends came by, and after a typical party they decided to play blind man's buff.

The birthday boy gets blindfolded and the other players scatter around the house. The game is played in several rounds. In each round, Misha catches exactly one of his friends and has to guess who it is. The probability of catching the i-th friend does not change between rounds and is equal to pi percent (as we know, it is directly proportional to the amount of alcohol consumed by the i-th friend) and p1 + p2 + ... + pn = 100 holds. Misha has no information about who he caught. After Misha makes an attempt to guess the caught person, the round ends. Even then, Misha isn't told whether he guessed correctly, and a new round begins.

The game ends when Misha guesses every friend at least once, that is, there exists such set of rounds k1, k2, ..., kn, that during round number ki Misha caught the i-th friend and guessed him. Misha wants to minimize the expectation of the number of rounds of the game. Despite the fact that at any point in the game Misha has no information about who he has already guessed, his friends are honest, and if they see that the condition for the end of the game is fulfilled, the game ends immediately. Find the expectation of the number of rounds in the game if Misha plays optimally.

Input format:
The first line of the input contains a single integer n (1 ≤ n ≤ 100) — the number of Misha's friends.

The second line contains n integers pi ($$p_i > 0, \sum_{i=1}^{n} p_i = 100$$), giving the probability to catch the i-th friend in one particular round in percent.

Output format:
Print a single real value — the expectation of the number of rounds provided that Misha plays optimally. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$.

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

Note:
The optimal strategy in the first sample is to guess friends alternately.

Example input:
2
50 50

Example output:
5.0000000000

Example input:
4
50 20 20 10

Example output:
39.2846263444

Editorial:
Transforming Sequence
Contest: AIM Tech Round (Div. 1)
Difficulty rating: 3300
Tags: combinatorics, dp, fft, math

Let's define the transformation P of a sequence of integers a1, a2, ..., an as b1, b2, ..., bn, where bi = a1 | a2 | ... | ai for all i = 1, 2, ..., n, where | is the bitwise OR operation.

Vasya consequently applies the transformation P to all sequences of length n consisting of integers from 1 to 2k - 1 inclusive. He wants to know how many of these sequences have such property that their transformation is a strictly increasing sequence. Help him to calculate this number modulo 109 + 7.

Input format:
The only line of the input contains two integers n and k (1 ≤ n ≤ 1018, 1 ≤ k ≤ 30 000).

Output format:
Print a single integer — the answer to the problem modulo 109 + 7.

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

Example input:
1 2

Example output:
3

Example input:
2 3

Example output:
30

Editorial:
Minimum Integer
Contest: Educational Codeforces Round 58 (Rated for Div. 2)
Difficulty rating: 1000
Tags: math

You are given $$$q$$$ queries in the following form:

Given three integers $$$l_i$$$, $$$r_i$$$ and $$$d_i$$$, find minimum positive integer $$$x_i$$$ such that it is divisible by $$$d_i$$$ and it does not belong to the segment $$$[l_i, r_i]$$$.

Can you answer all the queries?

Recall that a number $$$x$$$ belongs to segment $$$[l, r]$$$ if $$$l \le x \le r$$$.

Input format:
The first line contains one integer $$$q$$$ ($$$1 \le q \le 500$$$) — the number of queries.

Then $$$q$$$ lines follow, each containing a query given in the format $$$l_i$$$ $$$r_i$$$ $$$d_i$$$ ($$$1 \le l_i \le r_i \le 10^9$$$, $$$1 \le d_i \le 10^9$$$). $$$l_i$$$, $$$r_i$$$ and $$$d_i$$$ are integers.

Output format:
For each query print one integer: the answer to this query.

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

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

Example output:
6
4
1
3
10

Editorial:
There are two basic cases we have to consider: either the element we want to find is less than $$$l_i$$$, or it is greater than $$$r_i$$$.
In the first case, we are interested in $$$d_i$$$ itself: it is the minimum positive number divisible by $$$d_i$$$, and if it is less than $$$l_i$$$, then it is the answer.
In the second case, we have to find minimum element that is greater than $$$r_i$$$ and is divisible by $$$d_i$$$. This can be done as follows: we calculate the number of elements divisible by $$$d_i$$$ that are not greater than $$$r_i$$$ as $$$c = \lfloor \frac{r_i}{d_i} \rfloor$$$, and then we take $$$(c+1)$$$-th element, which is $$$d_i(c + 1)$$$.
Accordion
Contest: Educational Codeforces Round 58 (Rated for Div. 2)
Difficulty rating: 1300
Tags: greedy, implementation

An accordion is a string (yes, in the real world accordions are musical instruments, but let's forget about it for a while) which can be represented as a concatenation of: an opening bracket (ASCII code $$$091$$$), a colon (ASCII code $$$058$$$), some (possibly zero) vertical line characters (ASCII code $$$124$$$), another colon, and a closing bracket (ASCII code $$$093$$$). The length of the accordion is the number of characters in it.

For example, [::], [:||:] and [:|||:] are accordions having length $$$4$$$, $$$6$$$ and $$$7$$$. (:|:), {:||:}, [:], ]:||:[ are not accordions.

You are given a string $$$s$$$. You want to transform it into an accordion by removing some (possibly zero) characters from it. Note that you may not insert new characters or reorder existing ones. Is it possible to obtain an accordion by removing characters from $$$s$$$, and if so, what is the maximum possible length of the result?

Input format:
The only line contains one string $$$s$$$ ($$$1 \le |s| \le 500000$$$). It consists of lowercase Latin letters and characters [, ], : and |.

Output format:
If it is not possible to obtain an accordion by removing some characters from $$$s$$$, print $$$-1$$$. Otherwise print maximum possible length of the resulting accordion.

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

Example input:
|[a:b:|]

Example output:
4

Example input:
|]:[|:]

Example output:
-1

Editorial:
No cases. No any special thoughts. Just greedy.
The solution consists of six steps:
1. Remove the prefix of the string until the position of leftmost '[' character. If there is no such character, print -1;
2. Remove the prefix of the string until the position of leftmost ':' character. If there is no such character, print -1;
3. Reverse the string;
4. Remove the prefix of the string until the position of leftmost ']' character. If there is no such character, print -1;
5. Remove the prefix of the string until the position of leftmost ':' character. If there is no such character, print -1;
6. Print the number of '|' characters in the remaining string plus four.