1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Garage
Contest: COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 1500
Tags: binary search, geometry, math

Pak Chanek plans to build a garage. He wants the garage to consist of a square and a right triangle that are arranged like the following illustration.

Define $$$a$$$ and $$$b$$$ as the lengths of two of the sides in the right triangle as shown in the illustration. An integer $$$x$$$ is suitable if and only if we can construct a garage with assigning positive integer values for the lengths $$$a$$$ and $$$b$$$ ($$$a<b$$$) so that the area of the square at the bottom is exactly $$$x$$$. As a good friend of Pak Chanek, you are asked to help him find the $$$N$$$-th smallest suitable number.

Input format:
The only line contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^9$$$).

Output format:
An integer that represents the $$$N$$$-th smallest suitable number.

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

Note:
The $$$3$$$-rd smallest suitable number is $$$7$$$. A square area of $$$7$$$ can be obtained by assigning $$$a=3$$$ and $$$b=4$$$.

Example input:
3

Example output:
7

Editorial:
Let $$$c$$$ be the bottom side of the right triangle (the side that is not $$$a$$$ or $$$b$$$). From Pythagorean theorem, we know that $$$a^2+c^2 = b^2$$$, so $$$c^2 =b^2-a^2$$$. We can see that the area of the square at the bottom is $$$c^2$$$. So an integer is suitable if and only if it can be expressed as $$$b^2-a^2$$$ for some positive integers $$$a$$$ and $$$b$$$ ($$$a<b$$$).
Consider the case if $$$b=a+1$$$. Then $$$b^2-a^2 = (a+1)^2-a^2 = a^2+2a+1-a^2 = 2a+1$$$. Since $$$a$$$ must be a positive integer, then all possible results for this case are all odd integers that are greater than or equal to $$$3$$$.
Consider the case if $$$b=a+2$$$. Then $$$b^2-a^2 = (a+2)^2-a^2 = a^2+4a+4-a^2 = 4a+4$$$. Since $$$a$$$ must be a positive integer, then all possible results for this case are all integers that are multiples of $$$4$$$ that are greater than or equal to $$$8$$$.
Let's consider an integer that has a remainder of $$$2$$$ when divided by $$$4$$$. We can get that such an integer can never be expressed as $$$b^2-a^2$$$. This is because of the fact that any square number when divided by $$$4$$$ must have a remainder of either $$$0$$$ or $$$1$$$.
Using a simple brute force, we can get that $$$1$$$ and $$$4$$$ cannot be expressed as $$$b^2-a^2$$$.
Using all of the information above, we can see that all suitable numbers are only all odd integers that are greater than or equal to $$$3$$$ and all integers that are multiples of $$$4$$$ that are greater than or equal to $$$8$$$.
In order to find the $$$N$$$-th smallest suitable number, we can do a binary search on a value $$$d$$$. In each iteration of the binary search, we check whether there are at least $$$N$$$ suitable numbers that are less than or equal to $$$d$$$.
Alternatively, we can use a mathematical formula to find the $$$N$$$-th smallest suitable number in $$$O(1)$$$ time complexity.
Time Complexity: $$$O(\log N)$$$ or $$$O(1)$$$
Great Sequence
Contest: Codeforces Round 773 (Div. 1)
Difficulty rating: 1200
Tags: brute force, greedy, sortings

A sequence of positive integers is called great for a positive integer $$$x$$$, if we can split it into pairs in such a way that in each pair the first number multiplied by $$$x$$$ is equal to the second number. More formally, a sequence $$$a$$$ of size $$$n$$$ is great for a positive integer $$$x$$$, if $$$n$$$ is even and there exists a permutation $$$p$$$ of size $$$n$$$, such that for each $$$i$$$ ($$$1 \le i \le \frac{n}{2}$$$) $$$a_{p_{2i-1}} \cdot x = a_{p_{2i}}$$$.

Sam has a sequence $$$a$$$ and a positive integer $$$x$$$. Help him to make the sequence great: find the minimum possible number of positive integers that should be added to the sequence $$$a$$$ to make it great for the number $$$x$$$.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 20\,000$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$, $$$x$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$2 \le x \le 10^6$$$).

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

Output format:
For each test case print a single integer — the minimum number of integers that can be added to the end of $$$a$$$ to make it a great sequence for the number $$$x$$$.

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

Note:
In the first test case, Sam got lucky and the sequence is already great for the number $$$4$$$ because you can divide it into such pairs: $$$(1, 4)$$$, $$$(4, 16)$$$. Thus we can add $$$0$$$ numbers.

In the second test case, you can add numbers $$$1$$$ and $$$14$$$ to the sequence, then you can divide all $$$8$$$ integers into such pairs: $$$(1, 2)$$$, $$$(1, 2)$$$, $$$(2, 4)$$$, $$$(7, 14)$$$. It is impossible to add less than $$$2$$$ integers to fix the sequence.

Example input:
4
4 4
1 16 4 4
6 2
1 2 2 2 4 7
5 3
5 2 3 5 15
9 10
10 10 10 20 1 100 200 2000 3

Example output:
0
2
3
3

Editorial:
Let's look at the minimal integer in our multiset. Since it can be matched with only one integer, we need to create such pair. Thus, we can maintain the current multiset. We need to take the minimal element out of it (and delete it from it), find a pair for it, and delete it from the multiset if such pair exists, or add 1 to the answer if there is no such pair.
Two Arrays
Contest: Codeforces Round 773 (Div. 1)
Difficulty rating: 2700
Tags: bitmasks, brute force, combinatorics, greedy, hashing, math, two pointers

Sam changed his school and on the first biology lesson he got a very interesting task about genes.

You are given $$$n$$$ arrays, the $$$i$$$-th of them contains $$$m$$$ different integers — $$$a_{i,1}, a_{i,2},\ldots,a_{i,m}$$$. Also you are given an array of integers $$$w$$$ of length $$$n$$$.

Find the minimum value of $$$w_i + w_j$$$ among all pairs of integers $$$(i, j)$$$ ($$$1 \le i, j \le n$$$), such that the numbers $$$a_{i,1}, a_{i,2},\ldots,a_{i,m}, a_{j,1}, a_{j,2},\ldots,a_{j,m}$$$ are distinct.

Input format:
The first line contains two integers $$$n$$$, $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \le m \le 5$$$).

The $$$i$$$-th of the next $$$n$$$ lines starts with $$$m$$$ distinct integers $$$a_{i,1}, a_{i,2}, \ldots, a_{i,m}$$$ and then $$$w_i$$$ follows ($$$1\leq a_{i,j} \leq 10^9$$$, $$$1 \leq w_{i} \leq 10^9$$$).

Output format:
Print a single number — the answer to the problem.

If there are no suitable pairs $$$(i, j)$$$, print $$$-1$$$.

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

Note:
In the first test the minimum value is $$$5 = w_3 + w_4$$$, because numbers $$$\{2, 3, 4, 5\}$$$ are distinct.

In the second test case, there are no suitable pair $$$(i, j)$$$.

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

Example output:
5

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

Example output:
-1

Editorial:
Let's maintain a set of arrays of length $$$m$$$, add new arrays there, delete arrays from this set and understand if the set has a suitable pair for some array. To do this, let's consider a pair of sorted arrays $$$a$$$ and $$$b$$$ of length $$$m$$$. Let's write out all subsets of the array $$$a$$$. Then we start a counter $$$count$$$, and for each subset of the array $$$b$$$ we add one to $$$count$$$, if the subset occurs in $$$a$$$ and contains an odd number of elements, and subtract one if the subset occurs in $$$a$$$ and contains an even number of elements. Note that if $$$a$$$ and $$$b$$$ have at least one element in common, then $$$count$$$ will be equal to $$$1$$$, otherwise it will be equal to $$$0$$$. Thus, we can maintain a trie that contains all the subsets of each array in the set. Now any request to this trie is trivially done for $$$2^m$$$.
Now let's sort the arrays by $$$w$$$ and use our structure to find the first array that has a suitable pair. We can simply find the pair and maintain 2 pointers, $$$l$$$ is equal to the first array in the pair, $$$r$$$ is equal to the second array in the pair. Note that now we are only interested in pairs $$$l_{1}, r_{1}$$$ such that $$$l < l_{1} < r_{1} < r$$$. Therefore, we will move $$$l$$$ to the left only. When we moved it once again, we will see if there is a pair for it among $$$l < i < r$$$. If so, then we will move $$$r$$$ to the left until there is a pair for $$$l$$$ among $$$l < i \leq r$$$. After that we can update the answer with $$$w_{l} + w_{r}$$$. The solution works in $$$O(n\cdot 2^m)$$$.
It is also possible to solve this problem in $$$O(\frac{n^2 \cdot m}{32})$$$ using std::bitset.
Substring and Subsequence
Contest: VK Cup 2012 Round 2
Difficulty rating: 1700
Tags: dp

One day Polycarpus got hold of two non-empty strings s and t, consisting of lowercase Latin letters. Polycarpus is quite good with strings, so he immediately wondered, how many different pairs of "x y" are there, such that x is a substring of string s, y is a subsequence of string t, and the content of x and y is the same. Two pairs are considered different, if they contain different substrings of string s or different subsequences of string t. Read the whole statement to understand the definition of different substrings and subsequences.

The length of string s is the number of characters in it. If we denote the length of the string s as |s|, we can write the string as s = s1s2... s|s|.

A substring of s is a non-empty string x = s[a... b] = sasa + 1... sb (1 ≤ a ≤ b ≤ |s|). For example, "code" and "force" are substrings or "codeforces", while "coders" is not. Two substrings s[a... b] and s[c... d] are considered to be different if a ≠ c or b ≠ d. For example, if s="codeforces", s[2...2] and s[6...6] are different, though their content is the same.

A subsequence of s is a non-empty string y = s[p1p2... p|y|] = sp1sp2... sp|y| (1 ≤ p1 < p2 < ... < p|y| ≤ |s|). For example, "coders" is a subsequence of "codeforces". Two subsequences u = s[p1p2... p|u|] and v = s[q1q2... q|v|] are considered different if the sequences p and q are different.

Input format:
The input consists of two lines. The first of them contains s (1 ≤ |s| ≤ 5000), and the second one contains t (1 ≤ |t| ≤ 5000). Both strings consist of lowercase Latin letters.

Output format:
Print a single number — the number of different pairs "x y" such that x is a substring of string s, y is a subsequence of string t, and the content of x and y is the same. As the answer can be rather large, print it modulo 1000000007 (109 + 7).

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

Note:
Let's write down all pairs "x y" that form the answer in the first sample: "s[1...1] t[1]", "s[2...2] t[1]", "s[1...1] t[2]","s[2...2] t[2]", "s[1...2] t[1 2]".

Example input:
aa
aa

Example output:
5

Example input:
codeforces
forceofcode

Example output:
60

Editorial:
Lemmings
Contest: VK Cup 2012 Round 2
Difficulty rating: 2000
Tags: binary search

As you know, lemmings like jumping. For the next spectacular group jump n lemmings gathered near a high rock with k comfortable ledges on it. The first ledge is situated at the height of h meters, the second one is at the height of 2h meters, and so on (the i-th ledge is at the height of i·h meters). The lemmings are going to jump at sunset, and there's not much time left.

Each lemming is characterized by its climbing speed of vi meters per minute and its weight mi. This means that the i-th lemming can climb to the j-th ledge in $$\frac{j \cdot h}{v_i}$$ minutes.

To make the jump beautiful, heavier lemmings should jump from higher ledges: if a lemming of weight mi jumps from ledge i, and a lemming of weight mj jumps from ledge j (for i < j), then the inequation mi ≤ mj should be fulfilled.

Since there are n lemmings and only k ledges (k ≤ n), the k lemmings that will take part in the jump need to be chosen. The chosen lemmings should be distributed on the ledges from 1 to k, one lemming per ledge. The lemmings are to be arranged in the order of non-decreasing weight with the increasing height of the ledge. In addition, each lemming should have enough time to get to his ledge, that is, the time of his climb should not exceed t minutes. The lemmings climb to their ledges all at the same time and they do not interfere with each other.

Find the way to arrange the lemmings' jump so that time t is minimized.

Input format:
The first line contains space-separated integers n, k and h (1 ≤ k ≤ n ≤ 105, 1 ≤ h ≤ 104) — the total number of lemmings, the number of ledges and the distance between adjacent ledges.

The second line contains n space-separated integers m1, m2, ..., mn (1 ≤ mi ≤ 109), where mi is the weight of i-th lemming.

The third line contains n space-separated integers v1, v2, ..., vn (1 ≤ vi ≤ 109), where vi is the speed of i-th lemming.

Output format:
Print k different numbers from 1 to n — the numbers of the lemmings who go to ledges at heights h, 2h, ..., kh, correspondingly, if the jump is organized in an optimal way. If there are multiple ways to select the lemmings, pick any of them.

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

Note:
Let's consider the first sample case. The fifth lemming (speed 10) gets to the ledge at height 2 in $$\frac{1}{5}$$ minutes; the second lemming (speed 2) gets to the ledge at height 4 in 2 minutes; the fourth lemming (speed 2) gets to the ledge at height 6 in 3 minutes. All lemmings manage to occupy their positions in 3 minutes.

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

Example output:
5 2 4

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

Example output:
4 3 1

Editorial:
Large Refrigerator
Contest: VK Cup 2012 Round 2
Difficulty rating: 2900
Tags: brute force

Vasya wants to buy a new refrigerator. He believes that a refrigerator should be a rectangular parallelepiped with integer edge lengths. Vasya calculated that for daily use he will need a refrigerator with volume of at least V. Moreover, Vasya is a minimalist by nature, so the volume should be no more than V, either — why take up extra space in the apartment? Having made up his mind about the volume of the refrigerator, Vasya faced a new challenge — for a fixed volume of V the refrigerator must have the minimum surface area so that it is easier to clean.

The volume and the surface area of a refrigerator with edges a, b, c are equal to V = abc and S = 2(ab + bc + ca), correspondingly.

Given the volume V, help Vasya find the integer lengths for the refrigerator's edges a, b, c so that the refrigerator's volume equals V and its surface area S is minimized.

Input format:
The first line contains a single integer t (1 ≤ t ≤ 500) — the number of data sets.

The description of t data sets follows. Each set consists of a single integer V (2 ≤ V ≤ 1018), given by its factorization as follows.

Let V = p1a1p2a2... pkak, where pi are different prime numbers and ai are positive integer powers.

Then the first line describing a data set contains a single positive integer k — the number of different prime divisors of V. Next k lines contain prime numbers pi and their powers ai, separated by spaces. All pi are different, all ai > 0.

Output format:
Print t lines, on the i-th line print the answer to the i-th data set as four space-separated integers: the minimum possible surface area S and the corresponding edge lengths a, b, c. If there are multiple variants of the lengths of edges that give the minimum area, you are allowed to print any of them. You can print the lengths of the fridge's edges in any order.

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

Note:
In the first data set of the sample the fridge's volume V = 23 = 8, and the minimum surface area will be produced by the edges of equal length.

In the second data set the volume V = 17, and it can be produced by only one set of integer lengths.

Example input:
3
1
2 3
1
17 1
3
3 1
2 3
5 1

Example output:
24 2 2 2
70 1 1 17
148 4 6 5

Editorial:
e-Government
Contest: VK Cup 2012 Round 2
Difficulty rating: 2800
Tags: data structures, dfs and similar, dp, strings, trees

The best programmers of Embezzland compete to develop a part of the project called "e-Government" — the system of automated statistic collecting and press analysis.

We know that any of the k citizens can become a member of the Embezzland government. The citizens' surnames are a1, a2, ..., ak. All surnames are different. Initially all k citizens from this list are members of the government. The system should support the following options:

- Include citizen ai to the government.
- Exclude citizen ai from the government.
- Given a newspaper article text, calculate how politicized it is. To do this, for every active government member the system counts the number of times his surname occurs in the text as a substring. All occurrences are taken into consideration, including the intersecting ones. The degree of politicization of a text is defined as the sum of these values for all active government members.

Implement this system.

Input format:
The first line contains space-separated integers n and k (1 ≤ n, k ≤ 105) — the number of queries to the system and the number of potential government members.

Next k lines contain the surnames a1, a2, ..., ak, one per line. All surnames are pairwise different.

Next n lines contain queries to the system, one per line. Each query consists of a character that determines an operation and the operation argument, written consecutively without a space.

Operation "include in the government" corresponds to the character "+", operation "exclude" corresponds to "-". An argument of those operations is an integer between 1 and k — the index of the citizen involved in the operation. Any citizen can be included and excluded from the government an arbitrary number of times in any order. Including in the government a citizen who is already there or excluding the citizen who isn't there changes nothing.

The operation "calculate politicization" corresponds to character "?". Its argument is a text.

All strings — surnames and texts — are non-empty sequences of lowercase Latin letters. The total length of all surnames doesn't exceed 106, the total length of all texts doesn't exceed 106.

Output format:
For any "calculate politicization" operation print on a separate line the degree of the politicization of the given text. Print nothing for other operations.

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

Example input:
7 3
a
aa
ab
?aaab
-2
?aaab
-3
?aaab
+2
?aabbaa

Example output:
6
4
3
6

Editorial:
Substrings Sort
Contest: Kotlin Heroes: Practice 6
Tags: *special, sortings

You are given $$$n$$$ strings. Each string consists of lowercase English letters. Rearrange (reorder) the given strings in such a way that for every string, all strings that are placed before it are its substrings.

String $$$a$$$ is a substring of string $$$b$$$ if it is possible to choose several consecutive letters in $$$b$$$ in such a way that they form $$$a$$$. For example, string "for" is contained as a substring in strings "codeforces", "for" and "therefore", but is not contained as a substring in strings "four", "fofo" and "rof".

Input format:
The first line contains an integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of strings.

The next $$$n$$$ lines contain the given strings. The number of letters in each string is from $$$1$$$ to $$$100$$$, inclusive. Each string consists of lowercase English letters.

Some strings might be equal.

Output format:
If it is impossible to reorder $$$n$$$ given strings in required order, print "NO" (without quotes).

Otherwise print "YES" (without quotes) and $$$n$$$ given strings in required order.

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

Note:
In the second example you cannot reorder the strings because the string "abab" is not a substring of the string "abacaba".

Example input:
5
a
aba
abacaba
ba
aba

Example output:
YES
a
ba
aba
aba
abacaba

Example input:
5
a
abacaba
ba
aba
abab

Example output:
NO

Editorial:
Firstly, sort all the strings by their lengths (if there are several strings of the same length, their order does not matter because if the answer is "YES" then all the strings of the same length should be equal). Then for each $$$i \in [1..n - 1]$$$ check that $$$s_i$$$ is a substring of $$$s_{i + 1}$$$. If it doesn't hold for some $$$i$$$ then the answer is "NO". Otherwise the answer is "YES" and the sorted array is the correct order of strings.
Oleg and shares
Contest: Tinkoff Challenge - Elimination Round
Difficulty rating: 900
Tags: implementation, math

Oleg the bank client checks share prices every day. There are n share prices he is interested in. Today he observed that each second exactly one of these prices decreases by k rubles (note that each second exactly one price changes, but at different seconds different prices can change). Prices can become negative. Oleg found this process interesting, and he asked Igor the financial analyst, what is the minimum time needed for all n prices to become equal, or it is impossible at all? Igor is busy right now, so he asked you to help Oleg. Can you answer this question?

Input format:
The first line contains two integers n and k (1 ≤ n ≤ 105, 1 ≤ k ≤ 109) — the number of share prices, and the amount of rubles some price decreases each second.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the initial prices.

Output format:
Print the only line containing the minimum number of seconds needed for prices to become equal, of «-1» if it is impossible.

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

Note:
Consider the first example.

Suppose the third price decreases in the first second and become equal 12 rubles, then the first price decreases and becomes equal 9 rubles, and in the third second the third price decreases again and becomes equal 9 rubles. In this case all prices become equal 9 rubles in 3 seconds.

There could be other possibilities, but this minimizes the time needed for all prices to become equal. Thus the answer is 3.

In the second example we can notice that parity of first and second price is different and never changes within described process. Thus prices never can become equal.

In the third example following scenario can take place: firstly, the second price drops, then the third price, and then fourth price. It happens 999999999 times, and, since in one second only one price can drop, the whole process takes 999999999 * 3 = 2999999997 seconds. We can note that this is the minimum possible time.

Example input:
3 3
12 9 15

Example output:
3

Example input:
2 2
10 9

Example output:
-1

Editorial:
Let's notice that as prices can only decrease and answer should be minimum possible, all prices should become equal to minimum among given prices.
Formally, answer is $$\sum_{i=1}^{n}\frac{a_i - \min a_1, \ldots, a_n}{k}$$, if exists no such i that $$(a_i - \min a_1, \ldots, a_n) \bmod k \neq 0$$, otherwise answer is « - 1».