1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Fun
Contest: Codeforces Round 962 (Div. 3)
Difficulty rating: 1500
Tags: binary search, brute force, combinatorics, math, number theory

Given two integers $$$n$$$ and $$$x$$$, find the number of triplets ($$$a,b,c$$$) of positive integers such that $$$ab + ac + bc \le n$$$ and $$$a + b + c \le x$$$.

Note that order matters (e.g. ($$$1, 1, 2$$$) and ($$$1, 2, 1$$$) are treated as different) and $$$a$$$, $$$b$$$, $$$c$$$ must be strictly greater than $$$0$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$)  — the number of test cases.

Each test case contains two integers $$$n$$$ and $$$x$$$ ($$$1 \leq n,x \leq 10^6$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$ and that the sum of $$$x$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
Output a single integer — the number of triplets ($$$a,b,c$$$) of positive integers such that $$$ab + ac + bc \le n$$$ and $$$a + b + c \le x$$$.

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

Note:
In the first test case, the triplets are ($$$1, 1, 1$$$), ($$$1, 1, 2$$$), ($$$1, 2, 1$$$), and ($$$2, 1, 1$$$).

In the second test case, the triplets are ($$$1, 1, 1$$$), ($$$1, 1, 2$$$), ($$$1, 1, 3$$$), ($$$1, 2, 1$$$), ($$$1, 2, 2$$$), ($$$1, 3, 1$$$), ($$$2, 1, 1$$$), ($$$2, 1, 2$$$), ($$$2, 2, 1$$$), and ($$$3, 1, 1$$$).

Example input:
4
7 4
10 5
7 1000
900000 400000

Example output:
4
10
7
1768016938

Editorial:
Decode
Contest: Codeforces Round 962 (Div. 3)
Difficulty rating: 1600
Tags: combinatorics, data structures, implementation, math

In a desperate attempt to obtain your waifu favorite character, you have hacked into the source code of the game. After days of struggling, you finally find the binary string that encodes the gacha system of the game. In order to decode it, you must first solve the following problem.

You are given a binary string $$$s$$$ of length $$$n$$$. For each pair of integers $$$(l, r)$$$ $$$(1 \leq l \leq r \leq n)$$$, count the number of pairs $$$(x, y)$$$ $$$(l \leq x \leq y \leq r)$$$ such that the amount of $$$\mathtt{0}$$$ equals the amount of $$$\mathtt{1}$$$ in the substring $$$s_xs_{x+1}...s_y$$$.

Output the sum of counts over all possible $$$(l, r)$$$ modulo $$$10^9+7$$$.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

Each test case contains a binary string $$$s$$$ ($$$1 \leq |s| \leq 2 \cdot 10^5$$$). It is guaranteed $$$s$$$ only contains characters $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$.

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

Output format:
For each test case, output an integer, the answer modulo $$$10^9+7$$$.

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

Example input:
4
0000
01010101
1100111001
11000000111

Example output:
0
130
147
70

Editorial:
Bomb
Contest: Codeforces Round 962 (Div. 3)
Difficulty rating: 1900
Tags: binary search, greedy, math

Sparkle gives you two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$. Initially, your score is $$$0$$$. In one operation, you can choose an integer $$$i$$$ and add $$$a_i$$$ to your score. Then, you must set $$$a_i$$$ = $$$\max(0, a_i - b_i)$$$.

You only have time to perform $$$k$$$ operations before Sparkle sets off a nuclear bomb! What is the maximum score you can acquire after $$$k$$$ operations?

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

The first line of each test case contains $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^9$$$) — the length of the arrays and the number of operations you can perform.

The following line contains $$$n$$$ integers $$$a_1, a_2, ... a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

The following line contains $$$n$$$ integers $$$b_1, b_2, ... b_n$$$ ($$$1 \leq b_i \leq 10^9$$$).

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

Output format:
For each test case, output an integer, the maximum score you can acquire after $$$k$$$ operations.

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

Example input:
5
3 4
5 6 7
2 3 4
5 9
32 52 68 64 14
18 14 53 24 8
5 1000
1 2 3 4 5
5 4 3 2 1
1 1000000
1000000
1
10 6
3 3 5 10 6 8 6 8 7 7
6 1 7 4 1 1 8 9 3 1

Example output:
21
349
27
500000500000
47

Editorial:
Penacony
Contest: Codeforces Round 962 (Div. 3)
Difficulty rating: 2200
Tags: brute force, data structures, graphs, greedy, hashing

On Penacony, The Land of the Dreams, there exists $$$n$$$ houses and $$$n$$$ roads. There exists a road between house $$$i$$$ and $$$i+1$$$ for all $$$1 \leq i \leq n-1$$$ and a road between house $$$n$$$ and house $$$1$$$. All roads are bidirectional. However, due to the crisis on Penacony, the overseeing family has gone into debt and may not be able to maintain all roads.

There are $$$m$$$ pairs of friendships between the residents of Penacony. If the resident living in house $$$a$$$ is friends with the resident living in house $$$b$$$, there must be a path between houses $$$a$$$ and $$$b$$$ through maintained roads.

What is the minimum number of roads that must be maintained?

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) – the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$3 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5$$$) – the number of houses and the number of friendships.

The next $$$m$$$ lines contain two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a < b \leq n$$$) – the resident in house $$$a$$$ is friends with the resident in house $$$b$$$. It is guaranteed all ($$$a, b$$$) are distinct.

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

Output format:
For each test case, output an integer, the minimum number of roads that must be maintained.

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

Note:
For the first test case, the following roads must be maintained:

- $$$8 \leftarrow \rightarrow 1$$$
- $$$7 \leftarrow \rightarrow 8$$$
- $$$1 \leftarrow \rightarrow 2$$$
- $$$4 \leftarrow \rightarrow 5$$$

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

Example output:
4
7
2
7
2
3
3

Editorial:
Theatre Square
Contest: Codeforces Beta Round 1
Difficulty rating: 1000
Tags: math

Theatre Square in the capital city of Berland has a rectangular shape with the size n × m meters. On the occasion of the city's anniversary, a decision was taken to pave the Square with square granite flagstones. Each flagstone is of the size a × a.

What is the least number of flagstones needed to pave the Square? It's allowed to cover the surface larger than the Theatre Square, but the Square has to be covered. It's not allowed to break the flagstones. The sides of flagstones should be parallel to the sides of the Square.

Input format:
The input contains three positive integer numbers in the first line: n,  m and a (1 ≤  n, m, a ≤ 109).

Output format:
Write the needed number of flagstones.

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

Example input:
6 6 4

Example output:
4

Editorial:
Spreadsheets
Contest: Codeforces Beta Round 1
Difficulty rating: 1600
Tags: implementation, math

In the popular spreadsheets systems (for example, in Excel) the following numeration of columns is used. The first column has number A, the second — number B, etc. till column 26 that is marked by Z. Then there are two-letter numbers: column 27 has number AA, 28 — AB, column 52 is marked by AZ. After ZZ there follow three-letter numbers, etc.

The rows are marked by integer numbers starting with 1. The cell name is the concatenation of the column and the row numbers. For example, BC23 is the name for the cell that is in column 55, row 23.

Sometimes another numeration system is used: RXCY, where X and Y are integer numbers, showing the column and the row numbers respectfully. For instance, R23C55 is the cell from the previous example.

Your task is to write a program that reads the given sequence of cell coordinates and produce each item written according to the rules of another numeration system.

Input format:
The first line of the input contains integer number n (1 ≤ n ≤ 105), the number of coordinates in the test. Then there follow n lines, each of them contains coordinates. All the coordinates are correct, there are no cells with the column and/or the row numbers larger than 106 .

Output format:
Write n lines, each line should contain a cell coordinates in the other numeration system.

Constraints:
Time limit: 10.0 s
Memory limit: 64.0 MB

Example input:
2
R23C55
BC23

Example output:
BC23
R23C55

Editorial:
Ancient Berland Circus
Contest: Codeforces Beta Round 1
Difficulty rating: 2100
Tags: geometry, math

Nowadays all circuses in Berland have a round arena with diameter 13 meters, but in the past things were different.

In Ancient Berland arenas in circuses were shaped as a regular (equiangular) polygon, the size and the number of angles could vary from one circus to another. In each corner of the arena there was a special pillar, and the rope strung between the pillars marked the arena edges.

Recently the scientists from Berland have discovered the remains of the ancient circus arena. They found only three pillars, the others were destroyed by the time.

You are given the coordinates of these three pillars. Find out what is the smallest area that the arena could have.

Input format:
The input file consists of three lines, each of them contains a pair of numbers –– coordinates of the pillar. Any coordinate doesn't exceed 1000 by absolute value, and is given with at most six digits after decimal point.

Output format:
Output the smallest possible area of the ancient arena. This number should be accurate to at least 6 digits after the decimal point. It's guaranteed that the number of angles in the optimal polygon is not larger than 100.

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

Example input:
0.000000 0.000000
1.000000 1.000000
0.000000 1.000000

Example output:
1.00000000

Editorial:
Bank Robbery
Contest: Tinkoff Challenge - Final Round (Codeforces Round 414, rated, Div. 1 + Div. 2)
Difficulty rating: 800
Tags: brute force, implementation

A robber has attempted to rob a bank but failed to complete his task. However, he had managed to open all the safes.

Oleg the bank client loves money (who doesn't), and decides to take advantage of this failed robbery and steal some money from the safes. There are many safes arranged in a line, where the i-th safe from the left is called safe i. There are n banknotes left in all the safes in total. The i-th banknote is in safe xi. Oleg is now at safe a. There are two security guards, one of which guards the safe b such that b < a, i.e. the first guard is to the left of Oleg. The other guard guards the safe c so that c > a, i.e. he is to the right of Oleg.

The two guards are very lazy, so they do not move. In every second, Oleg can either take all the banknotes from the current safe or move to any of the neighboring safes. However, he cannot visit any safe that is guarded by security guards at any time, becaues he might be charged for stealing. Determine the maximum amount of banknotes Oleg can gather.

Input format:
The first line of input contains three space-separated integers, a, b and c (1 ≤ b < a < c ≤ 109), denoting the positions of Oleg, the first security guard and the second security guard, respectively.

The next line of input contains a single integer n (1 ≤ n ≤ 105), denoting the number of banknotes.

The next line of input contains n space-separated integers x1, x2, ..., xn (1 ≤ xi ≤ 109), denoting that the i-th banknote is located in the xi-th safe. Note that xi are not guaranteed to be distinct.

Output format:
Output a single integer: the maximum number of banknotes Oleg can take.

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

Note:
In the first example Oleg can take the banknotes in positions 4, 5, 6 (note that there are 2 banknotes at position 5). Oleg can't take the banknotes in safes 7 and 8 because he can't run into the second security guard. Similarly, Oleg cannot take the banknotes at positions 3 and 2 because he can't run into the first security guard. Thus, he can take a maximum of 4 banknotes.

For the second sample, Oleg can't take any banknotes without bumping into any of the security guards.

Example input:
5 3 7
8
4 7 5 5 3 6 2 8

Example output:
4

Example input:
6 5 7
5
1 5 7 92 3

Example output:
0

Editorial:
Cutting Carrot
Contest: Tinkoff Challenge - Final Round (Codeforces Round 414, rated, Div. 1 + Div. 2)
Difficulty rating: 1200
Tags: geometry, math

Igor the analyst has adopted n little bunnies. As we all know, bunnies love carrots. Thus, Igor has bought a carrot to be shared between his bunnies. Igor wants to treat all the bunnies equally, and thus he wants to cut the carrot into n pieces of equal area.

Formally, the carrot can be viewed as an isosceles triangle with base length equal to 1 and height equal to h. Igor wants to make n - 1 cuts parallel to the base to cut the carrot into n pieces. He wants to make sure that all n pieces have the same area. Can you help Igor determine where to cut the carrot so that each piece have equal area?

Illustration to the first example.

Input format:
The first and only line of input contains two space-separated integers, n and h (2 ≤ n ≤ 1000, 1 ≤ h ≤ 105).

Output format:
The output should contain n - 1 real numbers x1, x2, ..., xn - 1. The number xi denotes that the i-th cut must be made xi units away from the apex of the carrot. In addition, 0 < x1 < x2 < ... < xn - 1 < h must hold.

Your output will be considered correct if absolute or relative error of every number in your output doesn't exceed 10 - 6.

Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$.

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

Note:
Definition of isosceles triangle: https://en.wikipedia.org/wiki/Isosceles_triangle.

Example input:
3 2

Example output:
1.154700538379 1.632993161855

Example input:
2 100000

Example output:
70710.678118654752

Editorial:
Labelling Cities
Contest: Tinkoff Challenge - Final Round (Codeforces Round 414, rated, Div. 1 + Div. 2)
Difficulty rating: 2400
Tags: dfs and similar, graphs, hashing

Oleg the bank client lives in Bankopolia. There are n cities in Bankopolia and some pair of cities are connected directly by bi-directional roads. The cities are numbered from 1 to n. There are a total of m roads in Bankopolia, the i-th road connects cities ui and vi. It is guaranteed that from each city it is possible to travel to any other city using some of the roads.

Oleg wants to give a label to each city. Suppose the label of city i is equal to xi. Then, it must hold that for all pairs of cities (u, v) the condition |xu - xv| ≤ 1 holds if and only if there is a road connecting u and v.

Oleg wonders if such a labeling is possible. Find an example of such labeling if the task is possible and state that it is impossible otherwise.

Input format:
The first line of input contains two space-separated integers n and m (2 ≤ n ≤ 3·105, 1 ≤ m ≤ 3·105) — the number of cities and the number of roads.

Next, m lines follow. The i-th line contains two space-separated integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — the cities connected by the i-th road. It is guaranteed that there is at most one road between each pair of cities and it is possible to travel from any city to any other city using some roads.

Output format:
If the required labeling is not possible, output a single line containing the string "NO" (without quotes).

Otherwise, output the string "YES" (without quotes) on the first line. On the next line, output n space-separated integers, x1, x2, ..., xn. The condition 1 ≤ xi ≤ 109 must hold for all i, and for all pairs of cities (u, v) the condition |xu - xv| ≤ 1 must hold if and only if there is a road connecting u and v.

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

Note:
For the first sample, x1 = 2, x2 = 3, x3 = x4 = 1 is a valid labeling. Indeed, (3, 4), (1, 2), (1, 3), (1, 4) are the only pairs of cities with difference of labels not greater than 1, and these are precisely the roads of Bankopolia.

For the second sample, all pairs of cities have difference of labels not greater than 1 and all pairs of cities have a road connecting them.

For the last sample, it is impossible to construct a labeling satisfying the given constraints.

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

Example output:
YES
2 3 1 1

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

Example output:
YES
1 1 1 1 1

Editorial:
Replace All
Contest: Tinkoff Challenge - Final Round (Codeforces Round 414, rated, Div. 1 + Div. 2)
Difficulty rating: 3400
Tags: combinatorics, dp, math

Igor the analyst is at work. He learned about a feature in his text editor called "Replace All". Igor is too bored at work and thus he came up with the following problem:

Given two strings x and y which consist of the English letters 'A' and 'B' only, a pair of strings (s, t) is called good if:

- s and t consist of the characters '0' and '1' only.
- 1 ≤ |s|, |t| ≤ n, where |z| denotes the length of string z, and n is a fixed positive integer.
- If we replace all occurrences of 'A' in x and y with the string s, and replace all occurrences of 'B' in x and y with the string t, then the two obtained from x and y strings are equal.

For example, if x = AAB, y = BB and n = 4, then (01, 0101) is one of good pairs of strings, because both obtained after replacing strings are "01010101".

The flexibility of a pair of strings x and y is the number of pairs of good strings (s, t). The pairs are ordered, for example the pairs (0, 1) and (1, 0) are different.

You're given two strings c and d. They consist of characters 'A', 'B' and '?' only. Find the sum of flexibilities of all possible pairs of strings (c', d') such that c' and d' can be obtained from c and d respectively by replacing the question marks with either 'A' or 'B', modulo 109 + 7.

Input format:
The first line contains the string c (1 ≤ |c| ≤ 3·105).

The second line contains the string d (1 ≤ |d| ≤ 3·105).

The last line contains a single integer n (1 ≤ n ≤ 3·105).

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

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

Note:
For the first sample, there are four possible pairs of (c', d').

If (c', d') = (AA, A), then the flexibility is 0.

If (c', d') = (AB, A), then the flexibility is 0.

If (c', d') = (AA, B), then the flexibility is 2, as the pairs of binary strings (1, 11), (0, 00) are the only good pairs.

If (c', d') = (AB, B), then the flexibility is 0.

Thus, the total flexibility is 2.

For the second sample, there are 21 + 22 + ... + 210 = 2046 possible binary strings of length not greater 10, and the set of pairs of good strings is precisely the set of pairs (s, s), where s is a binary string of length not greater than 10.

Example input:
A?
?
3

Example output:
2

Example input:
A
B
10

Example output:
2046

Editorial:
The Child and Sequence
Contest: Codeforces Round 250 (Div. 1)
Difficulty rating: 2300
Tags: data structures, math

At the children's day, the child came to Picks's house, and messed his house up. Picks was angry at him. A lot of important things were lost, in particular the favorite sequence of Picks.

Fortunately, Picks remembers how to repair the sequence. Initially he should create an integer array a[1], a[2], ..., a[n]. Then he should perform a sequence of m operations. An operation can be one of the following:

1. Print operation l, r. Picks should write down the value of $$\sum_{i=l}^{r}a[i]$$.
2. Modulo operation l, r, x. Picks should perform assignment a[i] = a[i] mod x for each i (l ≤ i ≤ r).
3. Set operation k, x. Picks should set the value of a[k] to x (in other words perform an assignment a[k] = x).

Can you help Picks to perform the whole sequence of operations?

Input format:
The first line of input contains two integer: n, m (1 ≤ n, m ≤ 105). The second line contains n integers, separated by space: a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) — initial value of array elements.

Each of the next m lines begins with a number type $$(type \in \{1,2,3\})$$.

- If type = 1, there will be two integers more in the line: l, r (1 ≤ l ≤ r ≤ n), which correspond the operation 1.
- If type = 2, there will be three integers more in the line: l, r, x (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 109), which correspond the operation 2.
- If type = 3, there will be two integers more in the line: k, x (1 ≤ k ≤ n; 1 ≤ x ≤ 109), which correspond the operation 3.

Output format:
For each operation 1, please print a line containing the answer. Notice that the answer may exceed the 32-bit integer.

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

Note:
Consider the first testcase:

- At first, a = {1, 2, 3, 4, 5}.
- After operation 1, a = {1, 2, 3, 0, 1}.
- After operation 2, a = {1, 2, 5, 0, 1}.
- At operation 3, 2 + 5 + 0 + 1 = 8.
- After operation 4, a = {1, 2, 2, 0, 1}.
- At operation 5, 1 + 2 + 2 = 5.

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

Example output:
8
5

Example input:
10 10
6 9 6 7 6 1 10 10 9 5
1 3 9
2 7 10 9
2 5 10 8
1 4 7
3 3 7
2 7 9 9
1 2 4
1 6 6
1 5 9
3 1 10

Example output:
49
15
23
1
9

Editorial:
The Child and Binary Tree
Contest: Codeforces Round 250 (Div. 1)
Difficulty rating: 3100
Tags: combinatorics, divide and conquer, fft, number theory

Our child likes computer science very much, especially he likes binary trees.

Consider the sequence of n distinct positive integers: c1, c2, ..., cn. The child calls a vertex-weighted rooted binary tree good if and only if for every vertex v, the weight of v is in the set {c1, c2, ..., cn}. Also our child thinks that the weight of a vertex-weighted tree is the sum of all vertices' weights.

Given an integer m, can you for all s (1 ≤ s ≤ m) calculate the number of good vertex-weighted rooted binary trees with weight s? Please, check the samples for better understanding what trees are considered different.

We only want to know the answer modulo 998244353 (7 × 17 × 223 + 1, a prime number).

Input format:
The first line contains two integers n, m (1 ≤ n ≤ 105; 1 ≤ m ≤ 105). The second line contains n space-separated pairwise distinct integers c1, c2, ..., cn. (1 ≤ ci ≤ 105).

Output format:
Print m lines, each line containing a single integer. The i-th line must contain the number of good vertex-weighted rooted binary trees whose weight exactly equal to i. Print the answers modulo 998244353 (7 × 17 × 223 + 1, a prime number).

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

Note:
In the first example, there are 9 good vertex-weighted rooted binary trees whose weight exactly equal to 3:

Example input:
2 3
1 2

Example output:
1
3
9

Example input:
3 10
9 4 3

Example output:
0
0
1
1
0
2
4
2
6
15

Editorial: