1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Print Check
Contest: Codeforces Round 344 (Div. 2)
Difficulty rating: 1200
Tags: constructive algorithms, implementation

Kris works in a large company "Blake Technologies". As a best engineer of the company he was assigned a task to develop a printer that will be able to print horizontal and vertical strips. First prototype is already built and Kris wants to tests it. He wants you to implement the program that checks the result of the printing.

Printer works with a rectangular sheet of paper of size n × m. Consider the list as a table consisting of n rows and m columns. Rows are numbered from top to bottom with integers from 1 to n, while columns are numbered from left to right with integers from 1 to m. Initially, all cells are painted in color 0.

Your program has to support two operations:

1. Paint all cells in row ri in color ai;
2. Paint all cells in column ci in color ai.

If during some operation i there is a cell that have already been painted, the color of this cell also changes to ai.

Your program has to print the resulting table after k operation.

Input format:
The first line of the input contains three integers n, m and k (1  ≤  n,  m  ≤ 5000, n·m ≤ 100 000, 1 ≤ k ≤ 100 000) — the dimensions of the sheet and the number of operations, respectively.

Each of the next k lines contains the description of exactly one query:

- 1 ri ai (1 ≤ ri ≤ n, 1 ≤ ai ≤ 109), means that row ri is painted in color ai;
- 2 ci ai (1 ≤ ci ≤ m, 1 ≤ ai ≤ 109), means that column ci is painted in color ai.

Output format:
Print n lines containing m integers each — the resulting table after all operations are applied.

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

Note:
The figure below shows all three operations for the first sample step by step. The cells that were painted on the corresponding step are marked gray.

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

Example output:
3 1 3
2 2 2
0 1 0

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

Example output:
1 1 1
1 0 1
1 1 1
1 0 1
1 1 1

Editorial:
Report
Contest: Codeforces Round 344 (Div. 2)
Difficulty rating: 1700
Tags: data structures, sortings

Each month Blake gets the report containing main economic indicators of the company "Blake Technologies". There are n commodities produced by the company. For each of them there is exactly one integer in the final report, that denotes corresponding revenue. Before the report gets to Blake, it passes through the hands of m managers. Each of them may reorder the elements in some order. Namely, the i-th manager either sorts first ri numbers in non-descending or non-ascending order and then passes the report to the manager i + 1, or directly to Blake (if this manager has number i = m).

Employees of the "Blake Technologies" are preparing the report right now. You know the initial sequence ai of length n and the description of each manager, that is value ri and his favourite order. You are asked to speed up the process and determine how the final report will look like.

Input format:
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 200 000) — the number of commodities in the report and the number of managers, respectively.

The second line contains n integers ai (|ai| ≤ 109) — the initial report before it gets to the first manager.

Then follow m lines with the descriptions of the operations managers are going to perform. The i-th of these lines contains two integers ti and ri ($$t_{i} \in \{1,2\}$$, 1 ≤ ri ≤ n), meaning that the i-th manager sorts the first ri numbers either in the non-descending (if ti = 1) or non-ascending (if ti = 2) order.

Output format:
Print n integers — the final report, which will be passed to Blake by manager number m.

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

Note:
In the first sample, the initial report looked like: 1 2 3. After the first manager the first two numbers were transposed: 2 1 3. The report got to Blake in this form.

In the second sample the original report was like this: 1 2 4 3. After the first manager the report changed to: 4 2 1 3. After the second manager the report changed to: 2 4 1 3. This report was handed over to Blake.

Example input:
3 1
1 2 3
2 2

Example output:
2 1 3

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

Example output:
2 4 1 3

Editorial:
Messenger
Contest: Codeforces Round 344 (Div. 2)
Difficulty rating: 2100
Tags: data structures, hashing, implementation, string suffix structures, strings

Each employee of the "Blake Techologies" company uses a special messaging app "Blake Messenger". All the stuff likes this app and uses it constantly. However, some important futures are missing. For example, many users want to be able to search through the message history. It was already announced that the new feature will appear in the nearest update, when developers faced some troubles that only you may help them to solve.

All the messages are represented as a strings consisting of only lowercase English letters. In order to reduce the network load strings are represented in the special compressed form. Compression algorithm works as follows: string is represented as a concatenation of n blocks, each block containing only equal characters. One block may be described as a pair (li, ci), where li is the length of the i-th block and ci is the corresponding letter. Thus, the string s may be written as the sequence of pairs $${ \bigg < } ( l _ { 1 }, c _ { 1 } ), ( l _ { 2 }, c _ { 2 } ), \ldots, ( l _ { n }, c _ { n } ) { \bigg > }$$.

Your task is to write the program, that given two compressed string t and s finds all occurrences of s in t. Developers know that there may be many such occurrences, so they only ask you to find the number of them. Note that p is the starting position of some occurrence of s in t if and only if tptp + 1...tp + |s| - 1 = s, where ti is the i-th character of string t.

Note that the way to represent the string in compressed form may not be unique. For example string "aaaa" may be given as $$(4,a)$$, $${ \langle ( 3, a ), ( 1, a ) \rangle }$$, $${ \bigl \langle } ( 2, a ), ( 2, a ) { \bigr \rangle }$$...

Input format:
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 200 000) — the number of blocks in the strings t and s, respectively.

The second line contains the descriptions of n parts of string t in the format "li-ci" (1 ≤ li ≤ 1 000 000) — the length of the i-th part and the corresponding lowercase English letter.

The second line contains the descriptions of m parts of string s in the format "li-ci" (1 ≤ li ≤ 1 000 000) — the length of the i-th part and the corresponding lowercase English letter.

Output format:
Print a single integer — the number of occurrences of s in t.

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

Note:
In the first sample, t = "aaabbccccaaacc", and string s = "aabbc". The only occurrence of string s in string t starts at position p = 2.

In the second sample, t = "aaabbbbbbaaaaaaacccceeeeeeeeaa", and s = "aaa". The occurrences of s in t start at positions p = 1, p = 10, p = 11, p = 12, p = 13 and p = 14.

Example input:
5 3
3-a 2-b 4-c 3-a 2-c
2-a 2-b 1-c

Example output:
1

Example input:
6 1
3-a 6-b 7-a 4-c 8-e 2-a
3-a

Example output:
6

Editorial:
Product Sum
Contest: Codeforces Round 344 (Div. 2)
Difficulty rating: 2600
Tags: data structures, dp, geometry

Blake is the boss of Kris, however, this doesn't spoil their friendship. They often gather at the bar to talk about intriguing problems about maximising some values. This time the problem is really special.

You are given an array a of length n. The characteristic of this array is the value $$c = \sum_{i=1}^{n} a_i \cdot i$$ — the sum of the products of the values ai by i. One may perform the following operation exactly once: pick some element of the array and move to any position. In particular, it's allowed to move the element to the beginning or to the end of the array. Also, it's allowed to put it back to the initial position. The goal is to get the array with the maximum possible value of characteristic.

Input format:
The first line of the input contains a single integer n (2 ≤ n ≤ 200 000) — the size of the array a.

The second line contains n integers ai (1 ≤ i ≤ n, |ai| ≤ 1 000 000) — the elements of the array a.

Output format:
Print a single integer — the maximum possible value of characteristic of a that can be obtained by performing no more than one move.

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

Note:
In the first sample, one may pick the first element and place it before the third (before 5). Thus, the answer will be 3·1 + 2·2 + 4·3 + 5·4 = 39.

In the second sample, one may pick the fifth element of the array and place it before the third. The answer will be 1·1 + 1·2 + 1·3 + 2·4 + 7·5 = 49.

Example input:
4
4 3 2 5

Example output:
39

Example input:
5
1 1 2 7 1

Example output:
49

Editorial:
Cute number
Contest: Codeforces Round 796 (Div. 1)
Difficulty rating: 2900
Tags: binary search, brute force, data structures, dsu, implementation, math

Ran Yakumo is a cute girl who loves creating cute Maths problems.

Let $$$f(x)$$$ be the minimal square number strictly greater than $$$x$$$, and $$$g(x)$$$ be the maximal square number less than or equal to $$$x$$$. For example, $$$f(1)=f(2)=g(4)=g(8)=4$$$.

A positive integer $$$x$$$ is cute if $$$x-g(x)<f(x)-x$$$. For example, $$$1,5,11$$$ are cute integers, while $$$3,8,15$$$ are not.

Ran gives you an array $$$a$$$ of length $$$n$$$. She wants you to find the smallest non-negative integer $$$k$$$ such that $$$a_i + k$$$ is a cute number for any element of $$$a$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — the length of $$$a$$$.

The second line contains $$$n$$$ intergers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq 2\cdot 10^6$$$) — the array $$$a$$$.

Output format:
Print a single interger $$$k$$$ — the answer.

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

Note:
Test case 1:

$$$3$$$ is not cute integer, so $$$k\ne 0$$$.

$$$2,4,9,11$$$ are cute integers, so $$$k=1$$$.

Example input:
4
1 3 8 10

Example output:
1

Example input:
5
2 3 8 9 11

Example output:
8

Editorial:
For any integer $$$x$$$, iff we can find $$$w$$$ satisfying $$$x\in[w^2,w^2+w]$$$, we have $$$x-w^2 < (w+1)^2-x$$$, which means $$$x$$$ is beautiful. Define $$$f(x)=w$$$.
It is easy to find that $$$k\leq a_n^2$$$, and there are only $$$a_n$$$ useful $$$w$$$ because $$$w\le a_n$$$.
Enumerate $$$f(a_1+k)$$$ ($$$f(a_1+k)\le a_n$$$), and calculate the range of $$$a_i+k$$$ in order. It can be shown that the range is an interval for all $$$1\le i\le n$$$. So we can solve this problem in $$$O(n a_n)$$$.
We call $$$i$$$ a jump if $$$f(a_{i}+k)\ne f(a_{i-1}+k)$$$. Assuming $$$f(a_1+k)=w$$$, there is no more than $$$\frac{a_n}{w}$$$ jumps. We only need to enumerate jumps to calculate the ranges. We can use linked list or set in c++ to maintain it.
The time complexity is $$$O(\sum\limits_{w=1}^{a_n} \frac {a_n}{w}=a_n\log a_n)$$$.
Musical Puzzle
Contest: Codeforces Round 874 (Div. 3)
Difficulty rating: 800
Tags: implementation, strings

Vlad decided to compose a melody on his guitar. Let's represent the melody as a sequence of notes corresponding to the characters 'a', 'b', 'c', 'd', 'e', 'f', and 'g'.

However, Vlad is not very experienced in playing the guitar and can only record exactly two notes at a time. Vlad wants to obtain the melody $$$s$$$, and to do this, he can merge the recorded melodies together. In this case, the last sound of the first melody must match the first sound of the second melody.

For example, if Vlad recorded the melodies "ab" and "ba", he can merge them together and obtain the melody "aba", and then merge the result with "ab" to get "abab".

Help Vlad determine the minimum number of melodies consisting of two notes that he needs to record in order to obtain the melody $$$s$$$.

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

Following that are the descriptions of the test cases.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 50$$$) — the length of the melody $$$s$$$.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$, consisting of characters 'a', 'b', 'c', 'd', 'e', 'f', 'g'.

Output format:
Output $$$t$$$ integers, each representing the answer for the corresponding test case. As the answer output minimum number of melodies consisting of two notes that Vlad needs to record.

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

Note:
In the first sample, you need to record the melodies "ab" and "ba", as described in the problem statement.

In the second sample, you need to record the melodies "ab", "ba", "ac", and "ca".

In the third sample, the only necessary melody is "aa".

Example input:
5
4
abab
7
abacaba
6
aaaaaa
7
abcdefg
5
babdd

Example output:
2
4
1
6
4

Editorial:
Let's construct the melody sequentially. In the first step, we can record the notes $$$s_1$$$ and $$$s_2$$$. In the next step, we need to record $$$s_2$$$ and $$$s_3$$$, because there must be a common symbol when gluing and so on.
That is, we need to have recorded melodies $$$s_i$$$+$$$s_{i+1}$$$ for all $$$1 \le i < n$$$. We only need to count how many different ones among them, because we don't need to record one melody twice.
Vlad Building Beautiful Array
Contest: Codeforces Round 874 (Div. 3)
Difficulty rating: 800
Tags: greedy, math

Vlad was given an array $$$a$$$ of $$$n$$$ positive integers. Now he wants to build a beautiful array $$$b$$$ of length $$$n$$$ from it.

Vlad considers an array beautiful if all the numbers in it are positive and have the same parity. That is, all numbers in the beautiful array are greater than zero and are either all even or all odd.

To build the array $$$b$$$, Vlad can assign each $$$b_i$$$ either the value $$$a_i$$$ or $$$a_i - a_j$$$, where any $$$j$$$ from $$$1$$$ to $$$n$$$ can be chosen.

To avoid trying to do the impossible, Vlad asks you to determine whether it is possible to build a beautiful array $$$b$$$ of length $$$n$$$ using his array $$$a$$$.

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

Then follow the descriptions of the test cases.

The first line of each case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each case contains $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.

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

Output format:
Output $$$t$$$ strings, each of which is the answer to the corresponding test case. As the answer, output "YES" if Vlad can build a beautiful array $$$b$$$, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

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

Example input:
7
5
2 6 8 4 3
5
1 4 7 6 9
4
2 6 4 10
7
5 29 13 9 10000001 11 3
5
2 1 2 4 2
5
2 4 5 4 3
4
2 5 5 4

Example output:
NO
YES
YES
YES
YES
NO
NO

Editorial:
If all the numbers in the array already have the same parity, then for each $$$i$$$ it is sufficient to assign $$$b_i=a_i$$$.
Otherwise, it is impossible to make all the numbers even by leaving them positive, because the parity changes only when subtracting an odd number, and we cannot make the minimum odd number an even number.
It remains only to make all numbers odd, that is, subtract odd numbers from even numbers. This can be done if the minimum number in the array is odd, because we can subtract it from every even number.
Round Dance
Contest: Codeforces Round 874 (Div. 3)
Difficulty rating: 1600
Tags: dfs and similar, dsu, graphs, shortest paths

$$$n$$$ people came to the festival and decided to dance a few round dances. There are at least $$$2$$$ people in the round dance and each person has exactly two neighbors. If there are $$$2$$$ people in the round dance then they have the same neighbor on each side.

You decided to find out exactly how many dances there were. But each participant of the holiday remembered exactly one neighbor. Your task is to determine what the minimum and maximum number of round dances could be.

For example, if there were $$$6$$$ people at the holiday, and the numbers of the neighbors they remembered are equal $$$[2, 1, 4, 3, 6, 5]$$$, then the minimum number of round dances is$$$1$$$:

- $$$1 - 2 - 3 - 4 - 5 - 6 - 1$$$

- $$$1 - 2 - 1$$$
- $$$3 - 4 - 3$$$
- $$$5 - 6 - 5$$$

Input format:
The first line contains a positive number $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The following is a description of the test cases.

The first line of the description of each test case contains a positive number $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of people at the holiday.

The second line of the description of each test case contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le n, a_i \neq i$$$) — the number of the neighbor that the $$$i$$$th person remembered.

It is guaranteed that the test cases are correct and corresponds to at least one division of people into round dances.

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 two integers — the minimum and maximum number of round dances that could be.

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

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

Example output:
1 3
2 2
1 3
1 1
1 2
1 1
1 1
2 2
1 2
1 1

Editorial:
Let's build an undirected graph, draw the edges $$$i \to a_i$$$. Let's split this graph into connectivity components, denote their number by $$$k$$$. There could not be more than $$$k$$$ round dances.
Since the degree of each vertex is no more than two, the connectivity components are simple cycles and bamboos. If we connect the vertices of degree one in each bamboo, we get a partition into $$$k$$$ round dances.
Now let's try to get the minimum number of round dances. Nothing can be done with cycles, and all bamboos can be combined into one. If you get $$$b$$$ bamboos and $$$c$$$ cycles, then the answer is $$$\langle c + \min(b, 1), c + b \rangle$$$.
Time complexity is $$$O(n)$$$.
Stickogon
Contest: Codeforces Round 940 (Div. 2) and CodeCraft-23
Difficulty rating: 800
Tags: constructive algorithms, greedy

You are given $$$n$$$ sticks of lengths $$$a_1, a_2, \ldots, a_n$$$. Find the maximum number of regular (equal-sided) polygons you can construct simultaneously, such that:

- Each side of a polygon is formed by exactly one stick.
- No stick is used in more than $$$1$$$ polygon.

Note: Sticks cannot be broken.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the number of sticks available.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 100$$$) — the stick lengths.

Output format:
For each test case, output a single integer on a new line — the maximum number of regular (equal-sided) polygons you can make simultaneously from the sticks available.

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

Note:
In the first test case, we only have one stick, hence we can't form any polygon.

In the second test case, the two sticks aren't enough to form a polygon either.

In the third test case, we can use the $$$4$$$ sticks of length $$$3$$$ to create a square.

In the fourth test case, we can make a pentagon with side length $$$2$$$, and a square of side length $$$4$$$.

Example input:
4
1
1
2
1 1
6
2 2 3 3 3 3
9
4 2 2 2 2 4 2 4 4

Example output:
0
0
1
2

Editorial:
The first observation that needs to be made in this problem is that we have to greedily try to build triangles from the sticks available.
The number of triangles that can be created simultaneously by $$$S$$$ sticks of the same length is $$$\left\lfloor \frac{S}{3} \right\rfloor$$$. Hence, the answer is just the sum of the count of all triangles for all stick lengths, $$$\sum\limits_{i = 1}^{100} \left\lfloor \frac{S_i}{3} \right\rfloor$$$, where $$$S_i$$$ denotes the number of sticks of length $$$i$$$.
The time complexity of the problem is therefore $$$O(n) + O(100) = O(n)$$$.
A BIT of a Construction
Contest: Codeforces Round 940 (Div. 2) and CodeCraft-23
Difficulty rating: 1100
Tags: bitmasks, constructive algorithms, greedy, implementation

Given integers $$$n$$$ and $$$k$$$, construct a sequence of $$$n$$$ non-negative (i.e. $$$\geq 0$$$) integers $$$a_1, a_2, \ldots, a_n$$$ such that

1. $$$\sum\limits_{i = 1}^n a_i = k$$$
2. The number of $$$1$$$s in the binary representation of $$$a_1 | a_2 | \ldots | a_n$$$ is maximized, where $$$|$$$ denotes the bitwise OR operation.

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

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq k \leq 10^9$$$) — the number of non-negative integers to be printed and the sum respectively.

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, output a sequence $$$a_1, a_2, \ldots, a_n$$$ on a new line that satisfies the conditions given above.

If there are multiple solutions, print any of them.

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

Note:
In the first test case, we have to print exactly one integer, hence we can only output $$$5$$$ as the answer.

In the second test case, we output $$$1, 2$$$ which sum up to $$$3$$$, and $$$1 | 2 = (11)_2$$$ has two $$$1$$$s in its binary representation, which is the maximum we can achieve in these constraints.

In the fourth test case, we output $$$3, 1, 1, 32, 2, 12$$$ which sum up to $$$51$$$, and $$$3 | 1 | 1 | 32 | 2 | 12 = (101\,111)_2$$$ has five $$$1$$$s in its binary representation, which is the maximum we can achieve in these constraints.

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

Example output:
5
1 2
5 0
3 1 1 32 2 12

Editorial:
The case $$$n = 1$$$ needs to be handled separately, as we can only output $$$k$$$ itself.
For $$$n > 1$$$, we make the following observations. Let $$$x$$$ be the position of the most significant bit in $$$k$$$, that is $$$2^{x} \leq k < 2^{x+1}$$$. From this, we learn that the bitwise OR of the sequence cannot have more than $$$x+1$$$ set bits because that would make the sum greater than $$$2^{x+1}$$$.
Now, having $$$x+1$$$ bits set in the bitwise OR of the sequence is only possible if $$$k = 2^{x+1} - 1$$$ (or $$$k = 111\ldots1_2$$$). Any $$$k$$$ less than this cannot have $$$x+1$$$ bits set in the bitwise OR of the sequence, as otherwise the sum would exceed $$$k$$$.
However, we can always set $$$x$$$ bits, as we can always have one number in the sequence as $$$2^x - 1$$$ (which has exactly $$$x$$$ bits set). Using these observations, we get our solution as $$$2^x - 1, k - (2^x - 1), 0, 0, 0,\ldots, 0$$$. This ensures that we have at least $$$x$$$ bits set in the bitwise OR, and additionally also handles the case where $$$x+1$$$ bits can be set, while maintaining the sum.