1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Genetic engineering
Contest: Yandex.Algorithm 2011: Round 2
Difficulty rating: 2500
Tags: dp, string suffix structures, trees

"Multidimensional spaces are completely out of style these days, unlike genetics problems" — thought physicist Woll and changed his subject of study to bioinformatics. Analysing results of sequencing he faced the following problem concerning DNA sequences. We will further think of a DNA sequence as an arbitrary string of uppercase letters "A", "C", "G" and "T" (of course, this is a simplified interpretation).

Let w be a long DNA sequence and s1, s2, ..., sm — collection of short DNA sequences. Let us say that the collection filters w iff w can be covered with the sequences from the collection. Certainly, substrings corresponding to the different positions of the string may intersect or even cover each other. More formally: denote by |w| the length of w, let symbols of w be numbered from 1 to |w|. Then for each position i in w there exist pair of indices l, r (1 ≤ l ≤ i ≤ r ≤ |w|) such that the substring w[l ... r] equals one of the elements s1, s2, ..., sm of the collection.

Woll wants to calculate the number of DNA sequences of a given length filtered by a given collection, but he doesn't know how to deal with it. Help him! Your task is to find the number of different DNA sequences of length n filtered by the collection {si}.

Answer may appear very large, so output it modulo 1000000009.

Input format:
First line contains two integer numbers n and m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10) — the length of the string and the number of sequences in the collection correspondently.

Next m lines contain the collection sequences si, one per line. Each si is a nonempty string of length not greater than 10. All the strings consist of uppercase letters "A", "C", "G", "T". The collection may contain identical strings.

Output format:
Output should contain a single integer — the number of strings filtered by the collection modulo 1000000009 (109 + 9).

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

Note:
In the first sample, a string has to be filtered by "A". Clearly, there is only one such string: "AA".

In the second sample, there exist exactly two different strings satisfying the condition (see the pictures below).

Example input:
2 1
A

Example output:
1

Example input:
6 2
CAT
TACT

Example output:
2

Editorial:
Powerful array
Contest: Yandex.Algorithm 2011: Round 2
Difficulty rating: 2200
Tags: data structures, implementation, math, two pointers

An array of positive integers a1, a2, ..., an is given. Let us consider its arbitrary subarray al, al + 1..., ar, where 1 ≤ l ≤ r ≤ n. For every positive integer s denote by Ks the number of occurrences of s into the subarray. We call the power of the subarray the sum of products Ks·Ks·s for every positive integer s. The sum contains only finite number of nonzero summands as the number of different values in the array is indeed finite.

You should calculate the power of t given subarrays.

Input format:
First line contains two integers n and t (1 ≤ n, t ≤ 200000) — the array length and the number of queries correspondingly.

Second line contains n positive integers ai (1 ≤ ai ≤ 106) — the elements of the array.

Next t lines contain two positive integers l, r (1 ≤ l ≤ r ≤ n) each — the indices of the left and the right ends of the corresponding subarray.

Output format:
Output t lines, the i-th line of the output should contain single positive integer — the power of the i-th query subarray.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preferred to use cout stream (also you may use %I64d).

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

Note:
Consider the following array (see the second sample) and its [2, 7] subarray (elements of the subarray are colored):

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

Example output:
3
6

Example input:
8 3
1 1 2 2 1 3 1 1
2 7
1 6
2 7

Example output:
20
20
20

Editorial:
Long sequence
Contest: Yandex.Algorithm 2011: Round 2
Difficulty rating: 2700
Tags: brute force, math, matrices

A sequence a0, a1, ... is called a recurrent binary sequence, if each term ai (i = 0, 1, ...) is equal to 0 or 1 and there exist coefficients $$c_1, c_2, \ldots, c_k \in \{0, 1\}$$ such that

an = c1·an - 1 + c2·an - 2 + ... + ck·an - k (mod 2),

Note that such a sequence can be uniquely recovered from any k-tuple {as, as + 1, ..., as + k - 1} and so it is periodic. Moreover, if a k-tuple contains only zeros, then the sequence contains only zeros, so this case is not very interesting. Otherwise the minimal period of the sequence is not greater than 2k - 1, as k-tuple determines next element, and there are 2k - 1 non-zero k-tuples. Let us call a sequence long if its minimal period is exactly 2k - 1. Your task is to find a long sequence for a given k, if there is any.

Input format:
Input contains a single integer k (2 ≤ k ≤ 50).

Output format:
If there is no long sequence for a given k, output "-1" (without quotes). Otherwise the first line of the output should contain k integer numbers: c1, c2, ..., ck (coefficients). The second line should contain first k elements of the sequence: a0, a1, ..., ak - 1. All of them (elements and coefficients) should be equal to 0 or 1, and at least one ci has to be equal to 1.

If there are several solutions, output any.

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

Note:
1. In the first sample: c1 = 1, c2 = 1, so an = an - 1 + an - 2  (mod 2). Thus the sequence will be:

so its period equals 3 = 22 - 1.

2. In the second sample: c1 = 0, c2 = 1, c3 = 1, so an = an - 2 + an - 3  (mod 2). Thus our sequence is:

and its period equals 7 = 23 - 1.

Periods are colored.

Example input:
2

Example output:
1 1
1 0

Example input:
3

Example output:
0 1 1
1 1 1

Editorial:
Lengthening Sticks
Contest: Codeforces Round 317 [AimFund Thanks-Round] (Div. 1)
Difficulty rating: 2100
Tags: combinatorics, implementation, math

You are given three sticks with positive integer lengths of a, b, and c centimeters. You can increase length of some of them by some positive integer number of centimeters (different sticks can be increased by a different length), but in total by at most l centimeters. In particular, it is allowed not to increase the length of any stick.

Determine the number of ways to increase the lengths of some sticks so that you can form from them a non-degenerate (that is, having a positive area) triangle. Two ways are considered different, if the length of some stick is increased by different number of centimeters in them.

Input format:
The single line contains 4 integers a, b, c, l (1 ≤ a, b, c ≤ 3·105, 0 ≤ l ≤ 3·105).

Output format:
Print a single integer — the number of ways to increase the sizes of the sticks by the total of at most l centimeters, so that you can make a non-degenerate triangle from it.

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

Note:
In the first sample test you can either not increase any stick or increase any two sticks by 1 centimeter.

In the second sample test you can increase either the first or the second stick by one centimeter. Note that the triangle made from the initial sticks is degenerate and thus, doesn't meet the conditions.

Example input:
1 1 1 2

Example output:
4

Example input:
1 2 3 1

Example output:
2

Editorial:
Let's count the number of ways to form a triple which can't represent triangle sides, and then we subtract this value from $$C_{l+3}^{3} = \frac{(l+1)(l+1)(l+2)}{6}$$ — the total number of ways to increase the sticks not more than l in total. This number is obtained from partition of l into 4 summands (la + lb + lc + unusedl = l), or can be counted using a 'for' loop.
Now we consider triples a + la, b + lb, c + lc, where la + lb + lc ≤ l, la, lb, lc ≥ 0. Fix the maximal side, for example it would be a + la. We'll have to do the following algo for b + lb and c + lc in the same way. The triple is not a triangle with maximal side a + la if a + la ≥ b + lb + c + lc. If we iterate over la between 0 and l, we have the following conditions on lb, lc:
To sum up, we need to iterate over the maximal side and over the addition to that side, then write these formulas, and subtract the result from the total number of different additions to the sides. The complexity of the solution is O(l).
Minimization
Contest: Codeforces Round 317 [AimFund Thanks-Round] (Div. 1)
Difficulty rating: 2000
Tags: dp, greedy, sortings

You've got array A, consisting of n integers and a positive integer k. Array A is indexed by integers from 1 to n.

You need to permute the array elements so that value

$$\sum_{i=1}^{n-k}|A[i]-A[i+k]|$$

Input format:
The first line contains two integers n, k (2 ≤ n ≤ 3·105, 1 ≤ k ≤ min(5000, n - 1)).

The second line contains n integers A[1], A[2], ..., A[n] ( - 109 ≤ A[i] ≤ 109), separate by spaces — elements of the array A.

Output format:
Print the minimum possible value of the sum described in the statement.

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

Note:
In the first test one of the optimal permutations is 1 4 2.

In the second test the initial order is optimal.

In the third test one of the optimal permutations is 2 3 4 4 3 5.

Example input:
3 2
1 2 4

Example output:
1

Example input:
5 2
3 -5 3 -5 3

Example output:
0

Editorial:
We can divide all indices [1;n] into groups by their remainder modulo k. While counting $${ \sum _ { i = 1 } ^ { n - k } | a _ { i } - a _ { i + k } | }$$, we can consider each group separately and sum the distances between neighbouring numbers in each group.
Consider one group, corresponding to some remainder i modulo k, i.e. containing aj for $$j \equiv i \mod (k)$$. Let's write down its numbers from left to right: b1, b2, ..., bm. Then this group adds to the overall sum the value
Now consider two groups b1, ..., bm and c1, c2, ..., cl, both sorted in non-decreasing order. We claim that either b1 ≥ cl or bm ≤ c1, i.e. segments [b1, bm] and [c1, cl] can have common points only in their endpoints.
Why is this true? These groups add |bm - b1| + |cl - c1| to the overall sum. We consider the case c1 ≥ b1, the other is symmetric. If c1 < bm, then swapping c1 and bm will not increase the values these groups add to the answer, since the right border of b group moves to the left, and the left border of c group moves to the right. So, c1 ≥ bm in that case, and the assertion is proved.
Now we know that the values in each group should from a continuous segment of the sorted original array. In fact, we have $$k - ( n \mod k )$$ groups of size $$\pi_{k}$$ (so called small groups) and $$( n \mod k )$$ groups of size $$(\frac{n}{k}+1)$$ (so called large groups). Consider the following dynamic programming: dp[L][S] — the minimal sum of values added to the answer by L large groups and S small groups, if we choose the elements for them from the first $$L \cdot \left( \frac{n}{k} + 1 \right) + S \cdot \frac{n}{k}$$ elements of the sorted array A. There are no more than O(k2) states, and each transition can be made in O(1): we choose large or small group to add and obtain the number it adds to the sum by subtracting two elements of the sorted array. The answer for the problem will be in $$dp\left[(n \mod k)\right]\left[k-(n \mod k)\right]$$.
The overall complexity of the solution is $${\mathcal {O}}(n\log n+k^{2})$$. We can note that in pretests $$( n \mod k )$$ was quite small, and some slower solutions could pass, but they failed on final tests.
Geometric Progressions
Contest: Codeforces Round 317 [AimFund Thanks-Round] (Div. 1)
Difficulty rating: 3200
Tags: math

Geometric progression with the first element a and common ratio b is a sequence of numbers a, ab, ab2, ab3, ....

You are given n integer geometric progressions. Your task is to find the smallest integer x, that is the element of all the given progressions, or else state that such integer does not exist.

Input format:
The first line contains integer (1 ≤ n ≤ 100) — the number of geometric progressions.

Next n lines contain pairs of integers a, b (1 ≤ a, b ≤ 109), that are the first element and the common ratio of the corresponding geometric progression.

Output format:
If the intersection of all progressions is empty, then print  - 1, otherwise print the remainder of the minimal positive integer number belonging to all progressions modulo 1000000007 (109 + 7).

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

Note:
In the second sample test one of the progressions contains only powers of two, the other one contains only powers of three.

Example input:
2
2 2
4 1

Example output:
4

Example input:
2
2 2
3 3

Example output:
-1

Editorial:
If intersection of two geometric progressions is not empty, set of common elements indexes forms arithmetic progression in each progression or consists of not more than one element. Let's intersect first progression with every other progression. If some of these intersections are empty then total intersection is empty. If some of these intersection consist of one element, then we could check only this element. Otherwise one could intersect arithmetic progressions of first progression indexes and take minimal element of this intersection. The remaining question is how intersect two geometric progression? Let's factorise all numbers in these two progressions and find set of appropriate indexes for every prime factor in both progressions. These progressions one need intersect both by values and by indexes.
Single Push
Contest: Codeforces Round 600 (Div. 2)
Difficulty rating: 1000
Tags: implementation

You're given two arrays $$$a[1 \dots n]$$$ and $$$b[1 \dots n]$$$, both of the same length $$$n$$$.

In order to perform a push operation, you have to choose three integers $$$l, r, k$$$ satisfying $$$1 \le l \le r \le n$$$ and $$$k > 0$$$. Then, you will add $$$k$$$ to elements $$$a_l, a_{l+1}, \ldots, a_r$$$.

For example, if $$$a = [3, 7, 1, 4, 1, 2]$$$ and you choose $$$(l = 3, r = 5, k = 2)$$$, the array $$$a$$$ will become $$$[3, 7, \underline{3, 6, 3}, 2]$$$.

You can do this operation at most once. Can you make array $$$a$$$ equal to array $$$b$$$?

(We consider that $$$a = b$$$ if and only if, for every $$$1 \le i \le n$$$, $$$a_i = b_i$$$)

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 20$$$) — the number of test cases in the input.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100\ 000$$$) — the number of elements in each array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 1000$$$).

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 1000$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

Output format:
For each test case, output one line containing "YES" if it's possible to make arrays $$$a$$$ and $$$b$$$ equal by performing at most once the described operation or "NO" if it's impossible.

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

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

Note:
The first test case is described in the statement: we can perform a push operation with parameters $$$(l=3, r=5, k=2)$$$ to make $$$a$$$ equal to $$$b$$$.

In the second test case, we would need at least two operations to make $$$a$$$ equal to $$$b$$$.

In the third test case, arrays $$$a$$$ and $$$b$$$ are already equal.

In the fourth test case, it's impossible to make $$$a$$$ equal to $$$b$$$, because the integer $$$k$$$ has to be positive.

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

Example output:
YES
NO
YES
NO

Editorial:
If we set $$$d_i = b_i - a_i$$$, we have to check that $$$d$$$ has the following form: $$$[0, 0, \ldots, 0, k, k, \ldots, k, 0, 0, \ldots, 0]$$$. Firstly check that there is no negative element in $$$d$$$.
Solution 1 : add $$$0$$$ to the beginning and the end of the array $$$d$$$, then check that there is at most two indices $$$i$$$ such that $$$d_i \neq d_{i+1}$$$.
Solution 2 : let $$$l$$$ be the smallest integer such that $$$d_l \neq 0$$$, and $$$r$$$ be the greatest integer such that $$$d_r \neq 0$$$. Check that for all $$$l \le i \le r$$$, $$$d_i = d_l$$$.
Complexity : $$$O(n)$$$ for each test case.
Implementation (solution 1)
Harmonious Graph
Contest: Codeforces Round 600 (Div. 2)
Difficulty rating: 1700
Tags: constructive algorithms, dfs and similar, dsu, graphs, greedy, sortings

You're given an undirected graph with $$$n$$$ nodes and $$$m$$$ edges. Nodes are numbered from $$$1$$$ to $$$n$$$.

The graph is considered harmonious if and only if the following property holds:

- For every triple of integers $$$(l, m, r)$$$ such that $$$1 \le l < m < r \le n$$$, if there exists a path going from node $$$l$$$ to node $$$r$$$, then there exists a path going from node $$$l$$$ to node $$$m$$$.

In other words, in a harmonious graph, if from a node $$$l$$$ we can reach a node $$$r$$$ through edges ($$$l < r$$$), then we should able to reach nodes $$$(l+1), (l+2), \ldots, (r-1)$$$ too.

What is the minimum number of edges we need to add to make the graph harmonious?

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 200\ 000$$$ and $$$1 \le m \le 200\ 000$$$).

The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$), that mean that there's an edge between nodes $$$u$$$ and $$$v$$$.

It is guaranteed that the given graph is simple (there is no self-loop, and there is at most one edge between every pair of nodes).

Output format:
Print the minimum number of edges we have to add to the graph to make it harmonious.

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

Note:
In the first example, the given graph is not harmonious (for instance, $$$1 < 6 < 7$$$, node $$$1$$$ can reach node $$$7$$$ through the path $$$1 \rightarrow 2 \rightarrow 7$$$, but node $$$1$$$ can't reach node $$$6$$$). However adding the edge $$$(2, 4)$$$ is sufficient to make it harmonious.

In the second example, the given graph is already harmonious.

Example input:
14 8
1 2
2 7
3 4
6 3
5 7
3 8
6 8
11 12

Example output:
1

Example input:
200000 3
7 9
9 8
4 5

Example output:
0

Editorial:
For each connected component, let's find the weakest node $$$l$$$ and the biggest node $$$r$$$ in it (with one DFS per connected component).
If we look for all components at their intervals $$$[l\ ;\ r]$$$, we can see that two components should be connected in the resulting graph if and only if their intervals intersect. This leads to a $$$O(n^2 + m)$$$ naive solution : create a second graph where nodes represent components, add an edge between all pairs of components with intersecting intervals, and choose any spanning forest.
To optimize it, generate intervals in increasing order of $$$l$$$ (starting DFS in increasing order of nodes numbers). Look at them in this order, maintaining the biggest end $$$B$$$ seen. If $$$l \le B$$$, it is necessary to connect current interval to the interval ending at $$$B$$$ (hence increment answer).
It is quite easy to prove that doing only these connections is also sufficient (i.e. resulting graph will be harmonious).
Final complexity is $$$O(n + m)$$$.
Implementation
I'm bored with life
Contest: Codeforces Round 422 (Div. 2)
Difficulty rating: 800
Tags: implementation, math, number theory

Holidays have finished. Thanks to the help of the hacker Leha, Noora managed to enter the university of her dreams which is located in a town Pavlopolis. It's well known that universities provide students with dormitory for the period of university studies. Consequently Noora had to leave Vičkopolis and move to Pavlopolis. Thus Leha was left completely alone in a quiet town Vičkopolis. He almost even fell into a depression from boredom!

Leha came up with a task for himself to relax a little. He chooses two integers A and B and then calculates the greatest common divisor of integers "A factorial" and "B factorial". Formally the hacker wants to find out GCD(A!, B!). It's well known that the factorial of an integer x is a product of all positive integers less than or equal to x. Thus x! = 1·2·3·...·(x - 1)·x. For example 4! = 1·2·3·4 = 24. Recall that GCD(x, y) is the largest positive integer q that divides (without a remainder) both x and y.

Leha has learned how to solve this task very effective. You are able to cope with it not worse, aren't you?

Input format:
The first and single line contains two integers A and B (1 ≤ A, B ≤ 109, min(A, B) ≤ 12).

Output format:
Print a single integer denoting the greatest common divisor of integers A! and B!.

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

Note:
Consider the sample.

4! = 1·2·3·4 = 24. 3! = 1·2·3 = 6. The greatest common divisor of integers 24 and 6 is exactly 6.

Example input:
4 3

Example output:
6

Editorial:
Crossword solving
Contest: Codeforces Round 422 (Div. 2)
Difficulty rating: 1000
Tags: brute force, implementation, strings

Erelong Leha was bored by calculating of the greatest common divisor of two factorials. Therefore he decided to solve some crosswords. It's well known that it is a very interesting occupation though it can be very difficult from time to time. In the course of solving one of the crosswords, Leha had to solve a simple task. You are able to do it too, aren't you?

Leha has two strings s and t. The hacker wants to change the string s at such way, that it can be found in t as a substring. All the changes should be the following: Leha chooses one position in the string s and replaces the symbol in this position with the question mark "?". The hacker is sure that the question mark in comparison can play the role of an arbitrary symbol. For example, if he gets string s="ab?b" as a result, it will appear in t="aabrbb" as a substring.

Guaranteed that the length of the string s doesn't exceed the length of the string t. Help the hacker to replace in s as few symbols as possible so that the result of the replacements can be found in t as a substring. The symbol "?" should be considered equal to any other symbol.

Input format:
The first line contains two integers n and m (1 ≤ n ≤ m ≤ 1000) — the length of the string s and the length of the string t correspondingly.

The second line contains n lowercase English letters — string s.

The third line contains m lowercase English letters — string t.

Output format:
In the first line print single integer k — the minimal number of symbols that need to be replaced.

In the second line print k distinct integers denoting the positions of symbols in the string s which need to be replaced. Print the positions in any order. If there are several solutions print any of them. The numbering of the positions begins from one.

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

Example input:
3 5
abc
xaybz

Example output:
2
2 3

Example input:
4 10
abcd
ebceabazcd

Example output:
1
2

Editorial:
Let's consider all the positions i (1 ≤ i ≤ m - n + 1) that denotes the begining of the occurrence of the string s in the string t. Then let's find out how many symbols we should replace if the begining of the occurrence is position i. After the considering of all m - n + 1 positions the optimal answer will be found.
Total complexity is O(nm).