1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Square Subsets
Contest: Codeforces Round 448 (Div. 2)
Difficulty rating: 2000
Tags: bitmasks, combinatorics, dp, math

Petya was late for the lesson too. The teacher gave him an additional task. For some array a Petya should find the number of different ways to select non-empty subset of elements from it in such a way that their product is equal to a square of some integer.

Two ways are considered different if sets of indexes of elements chosen by these ways are different.

Since the answer can be very large, you should find the answer modulo 109 + 7.

Input format:
First line contains one integer n (1 ≤ n ≤ 105) — the number of elements in the array.

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

Output format:
Print one integer — the number of different ways to choose some elements so that their product is a square of a certain integer modulo 109 + 7.

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

Note:
In first sample product of elements chosen by any way is 1 and 1 = 12. So the answer is 24 - 1 = 15.

In second sample there are six different ways to choose elements so that their product is 4, and only one way so that their product is 16. So the answer is 6 + 1 = 7.

Example input:
4
1 1 1 1

Example output:
15

Example input:
4
2 2 2 2

Example output:
7

Editorial:
String Mark
Contest: Codeforces Round 448 (Div. 2)
Difficulty rating: 2100
Tags: combinatorics, math, strings

At the Byteland State University marks are strings of the same length. Mark x is considered better than y if string y is lexicographically smaller than x.

Recently at the BSU was an important test work on which Vasya recived the mark a. It is very hard for the teacher to remember the exact mark of every student, but he knows the mark b, such that every student recieved mark strictly smaller than b.

Vasya isn't satisfied with his mark so he decided to improve it. He can swap characters in the string corresponding to his mark as many times as he like. Now he want to know only the number of different ways to improve his mark so that his teacher didn't notice something suspicious.

More formally: you are given two strings a, b of the same length and you need to figure out the number of different strings c such that:

1) c can be obtained from a by swapping some characters, in other words c is a permutation of a.

2) String a is lexicographically smaller than c.

3) String c is lexicographically smaller than b.

For two strings x and y of the same length it is true that x is lexicographically smaller than y if there exists such i, that x1 = y1, x2 = y2, ..., xi - 1 = yi - 1, xi < yi.

Since the answer can be very large, you need to find answer modulo 109 + 7.

Input format:
First line contains string a, second line contains string b. Strings a, b consist of lowercase English letters. Their lengths are equal and don't exceed 106.

It is guaranteed that a is lexicographically smaller than b.

Output format:
Print one integer  — the number of different strings satisfying the condition of the problem modulo 109 + 7.

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

Note:
In first sample from string abc can be obtained strings acb, bac, bca, cab, cba, all of them are larger than abc, but smaller than ddd. So the answer is 5.

In second sample any string obtained from abcdef is larger than abcdeg. So the answer is 0.

Example input:
abc
ddd

Example output:
5

Example input:
abcdef
abcdeg

Example output:
0

Editorial:
Eyes Closed
Contest: Codeforces Round 448 (Div. 2)
Difficulty rating: 2300
Tags: data structures, probabilities

Vasya and Petya were tired of studying so they decided to play a game. Before the game begins Vasya looks at array a consisting of n integers. As soon as he remembers all elements of a the game begins. Vasya closes his eyes and Petya does q actions of one of two types:

1) Petya says 4 integers l1, r1, l2, r2 — boundaries of two non-intersecting segments. After that he swaps one random element from the [l1, r1] segment with another random element from the [l2, r2] segment.

2) Petya asks Vasya the sum of the elements of a in the [l, r] segment.

Vasya is a mathematician so he answers Petya the mathematical expectation of the sum of the elements in the segment.

Your task is to write a program which will answer the second type questions as Vasya would do it. In other words your program should print the mathematical expectation of the sum of the elements of a in the [l, r] segment for every second type query.

Input format:
The first line contains two integers n, q (2 ≤ n ≤ 105, 1 ≤ q ≤ 105)  — the number of elements in the array and the number of queries you need to handle.

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

The next q lines contain Petya's actions of type 1 or 2.

If it is a type 1 action then the line contains 5 integers 1, l1, r1, l2, r2 (1 ≤ l1 ≤ r1 ≤ n, 1 ≤ l2 ≤ r2 ≤ n).

If it is a type 2 query then the line contains 3 integers 2, l, r (1 ≤ l ≤ r ≤ n).

It is guaranteed that there is at least one type 2 query and segments [l1, r1], [l2, r2] don't have common elements.

Output format:
For each type 2 query print one real number — the mathematical expectation of the sum of elements in the segment.

Your answer will be considered correct if its absolute or relative error doesn't exceed 10 - 4  — formally, the answer is correct if $${ \operatorname* { m i n } } ( | x - y |, { \frac { | x - y | } { x } } ) \leq 1 0 ^ { - 4 }$$ where x is jury's answer and y is yours.

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

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

Example output:
3.0000000
3.0000000

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

Example output:
6.0000000
8.0400000

Editorial:
Array Without Local Maximums
Contest: Codeforces Round 518 (Div. 1) [Thanks, Mail.Ru!]
Difficulty rating: 1900
Tags: dp

Ivan unexpectedly saw a present from one of his previous birthdays. It is array of $$$n$$$ numbers from $$$1$$$ to $$$200$$$. Array is old and some numbers are hard to read. Ivan remembers that for all elements at least one of its neighbours ls not less than it, more formally:

$$$a_{1} \le a_{2}$$$,

$$$a_{n} \le a_{n-1}$$$ and

$$$a_{i} \le max(a_{i-1}, \,\, a_{i+1})$$$ for all $$$i$$$ from $$$2$$$ to $$$n-1$$$.

Ivan does not remember the array and asks to find the number of ways to restore it. Restored elements also should be integers from $$$1$$$ to $$$200$$$. Since the number of ways can be big, print it modulo $$$998244353$$$.

Input format:
First line of input contains one integer $$$n$$$ ($$$2 \le n \le 10^{5}$$$) — size of the array.

Second line of input contains $$$n$$$ integers $$$a_{i}$$$ — elements of array. Either $$$a_{i} = -1$$$ or $$$1 \le a_{i} \le 200$$$. $$$a_{i} = -1$$$ means that $$$i$$$-th element can't be read.

Output format:
Print number of ways to restore the array modulo $$$998244353$$$.

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

Note:
In the first example, only possible value of $$$a_{2}$$$ is $$$2$$$.

In the second example, $$$a_{1} = a_{2}$$$ so there are $$$200$$$ different values because all restored elements should be integers between $$$1$$$ and $$$200$$$.

Example input:
3
1 -1 2

Example output:
1

Example input:
2
-1 -1

Example output:
200

Editorial:
Let's find solution with complexity $$$O(n \cdot a^2)$$$. We can count $$$dp[prefix][a][flag]$$$ — quantity of ways to restore element from $$$1$$$ to $$$pref$$$ with last element equalls to $$$a$$$, $$$flag = 0$$$ means that previous element is less then the last or last element is first, $$$flag = 1$$$ — the opposite. So $$$ dp[pref][a][0] = \sum_{i=1}^{a-1} (dp[pref-1][i][1] + dp[pref-1][i][0]) $$$, $$$ dp[pref][a][1] = dp[pref-1][a][0] + \sum_{i=a}^{200} dp[pref-1][i][1] $$$.
Now let's count $$$prefix \_ sums[a][flag] = \sum_{i=1}^{a} dp[pref][i][flag]$$$ on each prefix before counting all $$$dp[pref]$$$, so we can recalculate dp in O(1) time.
Complexity is $$$O(n \cdot a)$$$.
Multihedgehog
Contest: Codeforces Round 518 (Div. 1) [Thanks, Mail.Ru!]
Difficulty rating: 1800
Tags: dfs and similar, graphs, shortest paths

Someone give a strange birthday present to Ivan. It is hedgehog — connected undirected graph in which one vertex has degree at least $$$3$$$ (we will call it center) and all other vertices has degree 1. Ivan thought that hedgehog is too boring and decided to make himself $$$k$$$-multihedgehog.

Let us define $$$k$$$-multihedgehog as follows:

- $$$1$$$-multihedgehog is hedgehog: it has one vertex of degree at least $$$3$$$ and some vertices of degree 1.
- For all $$$k \ge 2$$$, $$$k$$$-multihedgehog is $$$(k-1)$$$-multihedgehog in which the following changes has been made for each vertex $$$v$$$ with degree 1: let $$$u$$$ be its only neighbor; remove vertex $$$v$$$, create a new hedgehog with center at vertex $$$w$$$ and connect vertices $$$u$$$ and $$$w$$$ with an edge. New hedgehogs can differ from each other and the initial gift.

Thereby $$$k$$$-multihedgehog is a tree. Ivan made $$$k$$$-multihedgehog but he is not sure that he did not make any mistakes. That is why he asked you to check if his tree is indeed $$$k$$$-multihedgehog.

Input format:
First line of input contains $$$2$$$ integers $$$n$$$, $$$k$$$ ($$$1 \le n \le 10^{5}$$$, $$$1 \le k \le 10^{9}$$$) — number of vertices and hedgehog parameter.

Next $$$n-1$$$ lines contains two integers $$$u$$$ $$$v$$$ ($$$1 \le u, \,\, v \le n; \,\, u \ne v$$$) — indices of vertices connected by edge.

It is guaranteed that given graph is a tree.

Output format:
Print "Yes" (without quotes), if given graph is $$$k$$$-multihedgehog, and "No" (without quotes) otherwise.

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

Note:
2-multihedgehog from the first example looks like this:

Its center is vertex $$$13$$$. Hedgehogs created on last step are: [4 (center), 1, 2, 3], [6 (center), 7, 8, 9], [5 (center), 10, 11, 12, 13].

Tree from second example is not a hedgehog because degree of center should be at least $$$3$$$.

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

Example output:
Yes

Example input:
3 1
1 3
2 3

Example output:
No

Editorial:
Solution 1:
Firstly let's find all vertices with degree $$$1$$$. Now we can delete them and all, verticies which were incident to them must became verticies with degree $$$1$$$. And also for each new veretice with degree $$$1$$$ we must have already deleted not less then $$$3$$$ verticies. If initial graph was $$$k$$$-multihedgehog, after deleting vertices with degree $$$1$$$ it would became $$$k-1$$$-multihedgehog.
It could be realised using bfs starting from all initial vertices with degree $$$1$$$.
Complexity is $$$O(n)$$$.
Solution 2:
First of all let's find diametr of the graph. After that we can find middle vertex in diameter and check if it is a center of $$$k$$$-multihedgehog using simple dfs.
Complexity is $$$O(n)$$$.
Knights
Contest: Codeforces Round 518 (Div. 1) [Thanks, Mail.Ru!]
Difficulty rating: 2600
Tags: constructive algorithms

Ivan places knights on infinite chessboard. Initially there are $$$n$$$ knights. If there is free cell which is under attack of at least $$$4$$$ knights then he places new knight in this cell. Ivan repeats this until there are no such free cells. One can prove that this process is finite. One can also prove that position in the end does not depend on the order in which new knights are placed.

Ivan asked you to find initial placement of exactly $$$n$$$ knights such that in the end there will be at least $$$\lfloor \frac{n^{2}}{10} \rfloor$$$ knights.

Input format:
The only line of input contains one integer $$$n$$$ ($$$1 \le n \le 10^{3}$$$) — number of knights in the initial placement.

Output format:
Print $$$n$$$ lines. Each line should contain $$$2$$$ numbers $$$x_{i}$$$ and $$$y_{i}$$$ ($$$-10^{9} \le x_{i}, \,\, y_{i} \le 10^{9}$$$) — coordinates of $$$i$$$-th knight. For all $$$i \ne j$$$, $$$(x_{i}, \,\, y_{i}) \ne (x_{j}, \,\, y_{j})$$$ should hold. In other words, all knights should be in different cells.

It is guaranteed that the solution exists.

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

Note:
Let's look at second example:

Green zeroes are initial knights. Cell $$$(3, \,\, 3)$$$ is under attack of $$$4$$$ knights in cells $$$(1, \,\, 2)$$$, $$$(2, \,\, 1)$$$, $$$(4, \,\, 1)$$$ and $$$(5, \,\, 2)$$$, therefore Ivan will place a knight in this cell. Cell $$$(4, \,\, 5)$$$ is initially attacked by only $$$3$$$ knights in cells $$$(2, \,\, 6)$$$, $$$(5, \,\, 7)$$$ and $$$(6, \,\, 6)$$$. But new knight in cell $$$(3, \,\, 3)$$$ also attacks cell $$$(4, \,\, 5)$$$, now it is attacked by $$$4$$$ knights and Ivan will place another knight in this cell. There are no more free cells which are attacked by $$$4$$$ or more knights, so the process stops. There are $$$9$$$ knights in the end, which is not less than $$$\lfloor \frac{7^{2}}{10} \rfloor = 4$$$.

Example input:
4

Example output:
1 1
3 1
1 5
4 4

Example input:
7

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

Editorial:
If after some loops of the process we will have two neighboring lines with length $$$x$$$ total complexity of knights would be not less than $$$O( \frac{x^2}{4} )$$$.
In this construction:

$$$0$$$ — initial placement.
$$$1, \,\, 2$$$ — added knights.
Would be two neighboring lines with length $$$O(\frac{2 \cdot n}{3})$$$ so total complexity of knights would be $$$O( \frac{(\frac{2 \cdot n}{3})^2}{4} ) = O( \frac{n^2}{9} )$$$.
The possible way to facilitate the invention this (or over) solutions is to write process modeling.
Bonus: Solve this problem with complexity $$$ O( \frac{n^2}{6} )$$$.
Hongcow Learns the Cyclic Shift
Contest: Codeforces Round 385 (Div. 2)
Difficulty rating: 900
Tags: implementation, strings

Hongcow is learning to spell! One day, his teacher gives him a word that he needs to learn to spell. Being a dutiful student, he immediately learns how to spell the word.

Hongcow has decided to try to make new words from this one. He starts by taking the word he just learned how to spell, and moves the last character of the word to the beginning of the word. He calls this a cyclic shift. He can apply cyclic shift many times. For example, consecutively applying cyclic shift operation to the word "abracadabra" Hongcow will get words "aabracadabr", "raabracadab" and so on.

Hongcow is now wondering how many distinct words he can generate by doing the cyclic shift arbitrarily many times. The initial string is also counted.

Input format:
The first line of input will be a single string s (1 ≤ |s| ≤ 50), the word Hongcow initially learns how to spell. The string s consists only of lowercase English letters ('a'–'z').

Output format:
Output a single integer equal to the number of distinct strings that Hongcow can obtain by applying the cyclic shift arbitrarily many times to the given string.

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

Note:
For the first sample, the strings Hongcow can generate are "abcd", "dabc", "cdab", and "bcda".

For the second sample, no matter how many times Hongcow does the cyclic shift, Hongcow can only generate "bbb".

For the third sample, the two strings Hongcow can generate are "yzyz" and "zyzy".

Example input:
abcd

Example output:
4

Example input:
bbb

Example output:
1

Editorial:
Hongcow Solves A Puzzle
Contest: Codeforces Round 385 (Div. 2)
Difficulty rating: 1400
Tags: implementation

Hongcow likes solving puzzles.

One day, Hongcow finds two identical puzzle pieces, with the instructions "make a rectangle" next to them. The pieces can be described by an n by m grid of characters, where the character 'X' denotes a part of the puzzle and '.' denotes an empty part of the grid. It is guaranteed that the puzzle pieces are one 4-connected piece. See the input format and samples for the exact details on how a jigsaw piece will be specified.

The puzzle pieces are very heavy, so Hongcow cannot rotate or flip the puzzle pieces. However, he is allowed to move them in any directions. The puzzle pieces also cannot overlap.

You are given as input the description of one of the pieces. Determine if it is possible to make a rectangle from two identical copies of the given input. The rectangle should be solid, i.e. there should be no empty holes inside it or on its border. Keep in mind that Hongcow is not allowed to flip or rotate pieces and they cannot overlap, i.e. no two 'X' from different pieces can share the same position.

Input format:
The first line of input will contain two integers n and m (1 ≤ n, m ≤ 500), the dimensions of the puzzle piece.

The next n lines will describe the jigsaw piece. Each line will have length m and will consist of characters '.' and 'X' only. 'X' corresponds to a part of the puzzle piece, '.' is an empty space.

It is guaranteed there is at least one 'X' character in the input and that the 'X' characters form a 4-connected region.

Output format:
Output "YES" if it is possible for Hongcow to make a rectangle. Output "NO" otherwise.

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

Note:
For the first sample, one example of a rectangle we can form is as follows

For the second sample, it is impossible to put two of those pieces without rotating or flipping to form a rectangle.

In the third sample, we can shift the first tile by one to the right, and then compose the following rectangle:

Example input:
2 3
XXX
XXX

Example output:
YES

Example input:
2 2
.X
XX

Example output:
NO

Editorial:
Wet Shark and Odd and Even
Contest: Codeforces Round 341 (Div. 2)
Difficulty rating: 900
Tags: implementation

Today, Wet Shark is given n integers. Using any of these integers no more than once, Wet Shark wants to get maximum possible even (divisible by 2) sum. Please, calculate this value for Wet Shark.

Note, that if Wet Shark uses no integers from the n integers, the sum is an even integer 0.

Input format:
The first line of the input contains one integer, n (1 ≤ n ≤ 100 000). The next line contains n space separated integers given to Wet Shark. Each of these integers is in range from 1 to 109, inclusive.

Output format:
Print the maximum possible even sum that can be obtained if we use some of the given integers.

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

Note:
In the first sample, we can simply take all three integers for a total sum of 6.

In the second sample Wet Shark should take any four out of five integers 999 999 999.

Example input:
3
1 2 3

Example output:
6

Example input:
5
999999999 999999999 999999999 999999999 999999999

Example output:
3999999996

Editorial:
Wet Shark and Bishops
Contest: Codeforces Round 341 (Div. 2)
Difficulty rating: 1300
Tags: combinatorics, implementation

Today, Wet Shark is given n bishops on a 1000 by 1000 grid. Both rows and columns of the grid are numbered from 1 to 1000. Rows are numbered from top to bottom, while columns are numbered from left to right.

Wet Shark thinks that two bishops attack each other if they share the same diagonal. Note, that this is the only criteria, so two bishops may attack each other (according to Wet Shark) even if there is another bishop located between them. Now Wet Shark wants to count the number of pairs of bishops that attack each other.

Input format:
The first line of the input contains n (1 ≤ n ≤ 200 000) — the number of bishops.

Each of next n lines contains two space separated integers xi and yi (1 ≤ xi, yi ≤ 1000) — the number of row and the number of column where i-th bishop is positioned. It's guaranteed that no two bishops share the same position.

Output format:
Output one integer — the number of pairs of bishops which attack each other.

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

Note:
In the first sample following pairs of bishops attack each other: (1, 3), (1, 5), (2, 3), (2, 4), (3, 4) and (3, 5). Pairs (1, 2), (1, 4), (2, 5) and (4, 5) do not attack each other because they do not share the same diagonal.

Example input:
5
1 1
1 5
3 3
5 1
5 5

Example output:
6

Example input:
3
1 1
2 3
3 5

Example output:
0

Editorial:
Wet Shark and Flowers
Contest: Codeforces Round 341 (Div. 2)
Difficulty rating: 1700
Tags: combinatorics, math, number theory, probabilities

There are n sharks who grow flowers for Wet Shark. They are all sitting around the table, such that sharks i and i + 1 are neighbours for all i from 1 to n - 1. Sharks n and 1 are neighbours too.

Each shark will grow some number of flowers si. For i-th shark value si is random integer equiprobably chosen in range from li to ri. Wet Shark has it's favourite prime number p, and he really likes it! If for any pair of neighbouring sharks i and j the product si·sj is divisible by p, then Wet Shark becomes happy and gives 1000 dollars to each of these sharks.

At the end of the day sharks sum all the money Wet Shark granted to them. Find the expectation of this value.

Input format:
The first line of the input contains two space-separated integers n and p (3 ≤ n ≤ 100 000, 2 ≤ p ≤ 109) — the number of sharks and Wet Shark's favourite prime number. It is guaranteed that p is prime.

The i-th of the following n lines contains information about i-th shark — two space-separated integers li and ri (1 ≤ li ≤ ri ≤ 109), the range of flowers shark i can produce. Remember that si is chosen equiprobably among all integers from li to ri, inclusive.

Output format:
Print a single real number — the expected number of dollars that the sharks receive in total. You 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:
A prime number is a positive integer number that is divisible only by 1 and itself. 1 is not considered to be prime.

Consider the first sample. First shark grows some number of flowers from 1 to 2, second sharks grows from 420 to 421 flowers and third from 420420 to 420421. There are eight cases for the quantities of flowers (s0, s1, s2) each shark grows:

1. (1, 420, 420420): note that s0·s1 = 420, s1·s2 = 176576400, and s2·s0 = 420420. For each pair, 1000 dollars will be awarded to each shark. Therefore, each shark will be awarded 2000 dollars, for a total of 6000 dollars.
2. (1, 420, 420421): now, the product s2·s0 is not divisible by 2. Therefore, sharks s0 and s2 will receive 1000 dollars, while shark s1 will receive 2000. The total is 4000.
3. (1, 421, 420420): total is 4000
4. (1, 421, 420421): total is 0.
5. (2, 420, 420420): total is 6000.
6. (2, 420, 420421): total is 6000.
7. (2, 421, 420420): total is 6000.
8. (2, 421, 420421): total is 4000.

The expected value is $${ \frac { 6 0 0 0 + 4 0 0 0 + 4 0 0 0 + 0 + 6 0 0 0 + 6 0 0 0 + 6 0 0 0 + 4 0 0 0 } { 8 } } = 4 5 0 0$$.

In the second sample, no combination of quantities will garner the sharks any money.

Example input:
3 2
1 2
420 421
420420 420421

Example output:
4500.0

Example input:
3 5
1 4
2 3
11 14

Example output:
0.0

Editorial: