1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Design Tutorial: Learn from a Game
Contest: Codeforces Round 270
Difficulty rating: 2800
Tags: constructive algorithms, implementation

One way to create task is to learn from game. You should pick a game and focus on part of the mechanic of that game, then it might be a good task.

Let's have a try. Puzzle and Dragon was a popular game in Japan, we focus on the puzzle part of that game, it is a tile-matching puzzle.

(Picture from Wikipedia page: http://en.wikipedia.org/wiki/Puzzle_&_Dragons)

There is an n × m board which consists of orbs. During the game you can do the following move. In the beginning of move you touch a cell of the board, then you can move your finger to one of the adjacent cells (a cell not on the boundary has 8 adjacent cells), then you can move your finger from the current cell to one of the adjacent cells one more time, and so on. Each time you move your finger from a cell to another cell, the orbs in these cells swap with each other. In other words whatever move you make, the orb in the cell you are touching never changes.

The goal is to achieve such kind of pattern that the orbs will be cancelled and your monster will attack the enemy, but we don't care about these details. Instead, we will give you the initial board as an input and the target board as an output. Your goal is to determine whether there is a way to reach the target in a single move.

Input format:
The first line contains two integers: n and m (1 ≤ n, m ≤ 30).

The next n lines each contains m integers — the description of the initial board. The j-th integer in the i-th line is si, j (1 ≤ si, j ≤ 900), where si, j denotes the type of the orb located in the i-th row and j-th column of the board.

The next n lines contain the target board in the same format. Note, that the initial board and the target board will be different.

Output format:
If there is no solution, then output: -1.

If there is a solution, then in the first line output an integer k (1 ≤ k ≤ 106) — the number of finger moves.

In the next line print two integers x0 and y0 (1 ≤ x0 ≤ n; 1 ≤ y0 ≤ m) — the position of the cell you touch at the beginning. In each of the next k lines print two integers xi and yi (1 ≤ xi ≤ n; 1 ≤ yi ≤ m) — the position you move to. Note that this position must be adjacent to the previous position, that is max(|xi - xi - 1|, |yi - yi - 1|) = 1.

If there are multiple solutions, you can print any of them. We can prove that under these constraints if there exists a solution then there is a solution with no more than 106 operations.

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

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

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

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

Example output:
-1

Editorial:
Design Tutorial: Change the Goal
Contest: Codeforces Round 270
Difficulty rating: 2700
Tags: constructive algorithms, math, matrices

There are some tasks which have the following structure: you are given a model, and you can do some operations, you should use these operations to achive the goal. One way to create a new task is to use the same model and same operations, but change the goal.

Let's have a try. I have created the following task for Topcoder SRM 557 Div1-Hard: you are given n integers x1, x2, ..., xn. You are allowed to perform the assignments (as many as you want) of the following form xi ^= xj (in the original task i and j must be different, but in this task we allow i to equal j). The goal is to maximize the sum of all xi.

Now we just change the goal. You are also given n integers y1, y2, ..., yn. You should make x1, x2, ..., xn exactly equal to y1, y2, ..., yn. In other words, for each i number xi should be equal to yi.

Input format:
The first line contains an integer n (1 ≤ n ≤ 10000). The second line contains n integers: x1 to xn (0 ≤ xi ≤ 109). The third line contains n integers: y1 to yn (0 ≤ yi ≤ 109).

Output format:
If there is no solution, output -1.

If there is a solution, then in the first line output an integer m (0 ≤ m ≤ 1000000) – the number of assignments you need to perform. Then print m lines, each line should contain two integers i and j (1 ≤ i, j ≤ n), which denote assignment xi ^= xj.

If there are multiple solutions you can print any of them. We can prove that under these constraints if there exists a solution then there always exists a solution with no more than 106 operations.

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

Note:
Assignment a ^= b denotes assignment a = a ^ b, where operation "^" is bitwise XOR of two integers.

Example input:
2
3 5
6 0

Example output:
2
1 2
2 2

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

Example output:
-1

Editorial:
Design Tutorial: Increase the Constraints
Contest: Codeforces Round 270
Difficulty rating: 2800
Tags: bitmasks, data structures, fft

There is a simple way to create hard tasks: take one simple problem as the query, and try to find an algorithm that can solve it faster than bruteforce. This kind of tasks usually appears in OI contest, and usually involves data structures.

Let's try to create a task, for example, we take the "Hamming distance problem": for two binary strings s and t with the same length, the Hamming distance between them is the number of positions at which the corresponding symbols are different. For example, the Hamming distance between "00111" and "10101" is 2 (the different symbols are marked with bold).

We use the Hamming distance problem as a query in the following way: you are given two strings a and b and several queries. Each query will be: what is the Hamming distance between two strings ap1ap1 + 1...ap1 + len - 1 and bp2bp2 + 1...bp2 + len - 1?

Note, that in this problem the strings are zero-based, that is s = s0s1... s|s| - 1.

Input format:
The first line contains a string a (1 ≤ |a| ≤ 200000). The second line contains a string b (1 ≤ |b| ≤ 200000). Each character of both strings is either "0" or "1".

The third line contains an integer q (1 ≤ q ≤ 400000) — the number of queries. Each of the following q lines contains three integers: p1, p2 and len (0 ≤ p1 ≤ |a| - len; 0 ≤ p2 ≤ |b| - len), these numbers denote the parameters of the current query.

Output format:
Output q integers — the answers for the queries.

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

Example input:
101010
11110000
3
0 0 3
2 3 4
5 7 1

Example output:
1
1
0

Example input:
10001010101011001010100101010011010
101010100101001010100100101010
5
0 0 12
3 9 7
6 4 15
12 15 10
13 3 20

Example output:
5
4
3
5
13

Editorial:
Orac and Models
Contest: Codeforces Round 641 (Div. 2)
Difficulty rating: 1400
Tags: dp, math, number theory

There are $$$n$$$ models in the shop numbered from $$$1$$$ to $$$n$$$, with sizes $$$s_1, s_2, \ldots, s_n$$$.

Orac will buy some of the models and will arrange them in the order of increasing numbers (i.e. indices, but not sizes).

Orac thinks that the obtained arrangement is beatiful, if for any two adjacent models with indices $$$i_j$$$ and $$$i_{j+1}$$$ (note that $$$i_j < i_{j+1}$$$, because Orac arranged them properly), $$$i_{j+1}$$$ is divisible by $$$i_j$$$ and $$$s_{i_j} < s_{i_{j+1}}$$$.

For example, for $$$6$$$ models with sizes $$$\{3, 6, 7, 7, 7, 7\}$$$, he can buy models with indices $$$1$$$, $$$2$$$, and $$$6$$$, and the obtained arrangement will be beautiful. Also, note that the arrangement with exactly one model is also considered beautiful.

Orac wants to know the maximum number of models that he can buy, and he may ask you these queries many times.

Input format:
The first line contains one integer $$$t\ (1 \le t\le 100)$$$: the number of queries.

Each query contains two lines. The first line contains one integer $$$n\ (1\le n\le 100\,000)$$$: the number of models in the shop, and the second line contains $$$n$$$ integers $$$s_1,\dots,s_n\ (1\le s_i\le 10^9)$$$: the sizes of models.

It is guaranteed that the total sum of $$$n$$$ is at most $$$100\,000$$$.

Output format:
Print $$$t$$$ lines, the $$$i$$$-th of them should contain the maximum number of models that Orac can buy for the $$$i$$$-th query.

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

Note:
In the first query, for example, Orac can buy models with indices $$$2$$$ and $$$4$$$, the arrangement will be beautiful because $$$4$$$ is divisible by $$$2$$$ and $$$6$$$ is more than $$$3$$$. By enumerating, we can easily find that there are no beautiful arrangements with more than two models.

In the second query, Orac can buy models with indices $$$1$$$, $$$3$$$, and $$$6$$$. By enumerating, we can easily find that there are no beautiful arrangements with more than three models.

In the third query, there are no beautiful arrangements with more than one model.

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

Example output:
2
3
1
1

Editorial:
Considering DP, we can design DP statuses as follow: $$$f_i$$$ stands for the length of the longest beautiful sequence end up with index $$$i$$$.
We can find the transformation easily: $$$$$$ f_i = \max\limits_{j\mid i, s_j<s_i} \{f_j + 1\} $$$$$$
Then, the length of answer sequence is the maximum value among $$$f_1,f_2,\cdots,f_n$$$.
About the complexity of DP: If you transform by iterating multiples, it will be $$$O(n\log n)$$$ (According to properties of Harmonic Series); if you iterate divisors, then it will be $$$O(n\sqrt n)$$$. Fortunately, both of them are acceptable in this problem.
Equalize Prices Again
Contest: Codeforces Round 590 (Div. 3)
Difficulty rating: 800
Tags: math

You are both a shop keeper and a shop assistant at a small nearby shop. You have $$$n$$$ goods, the $$$i$$$-th good costs $$$a_i$$$ coins.

You got tired of remembering the price of each product when customers ask for it, thus you decided to simplify your life. More precisely you decided to set the same price for all $$$n$$$ goods you have.

However, you don't want to lose any money so you want to choose the price in such a way that the sum of new prices is not less than the sum of the initial prices. It means that if you sell all $$$n$$$ goods for the new price, you will receive at least the same (or greater) amount of money as if you sell them for their initial prices.

On the other hand, you don't want to lose customers because of big prices so among all prices you can choose you need to choose the minimum one.

So you need to find the minimum possible equal price of all $$$n$$$ goods so if you sell them for this price, you will receive at least the same (or greater) amount of money as if you sell them for their initial prices.

You have to answer $$$q$$$ independent queries.

Input format:
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 100$$$) — the number of queries. Then $$$q$$$ queries follow.

The first line of the query contains one integer $$$n$$$ ($$$1 \le n \le 100)$$$ — the number of goods. The second line of the query contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^7$$$), where $$$a_i$$$ is the price of the $$$i$$$-th good.

Output format:
For each query, print the answer for it — the minimum possible equal price of all $$$n$$$ goods so if you sell them for this price, you will receive at least the same (or greater) amount of money as if you sell them for their initial prices.

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

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

Example output:
3
2
1

Editorial:
In this problem, we need to find the minimum possible $$$price$$$ such that $$$price \cdot n \ge sum$$$, where $$$sum$$$ is the sum of all $$$a_i$$$. $$$price$$$ equals to $$$\lceil \frac{sum}{n} \rceil$$$, where $$$\lceil \frac{x}{y} \rceil$$$ is $$$x$$$ divided by $$$y$$$ rounded up.
Distinct Characters Queries
Contest: Codeforces Round 590 (Div. 3)
Difficulty rating: 1600
Tags: data structures

You are given a string $$$s$$$ consisting of lowercase Latin letters and $$$q$$$ queries for this string.

Recall that the substring $$$s[l; r]$$$ of the string $$$s$$$ is the string $$$s_l s_{l + 1} \dots s_r$$$. For example, the substrings of "codeforces" are "code", "force", "f", "for", but not "coder" and "top".

There are two types of queries:

- $$$1~ pos~ c$$$ ($$$1 \le pos \le |s|$$$, $$$c$$$ is lowercase Latin letter): replace $$$s_{pos}$$$ with $$$c$$$ (set $$$s_{pos} := c$$$);
- $$$2~ l~ r$$$ ($$$1 \le l \le r \le |s|$$$): calculate the number of distinct characters in the substring $$$s[l; r]$$$.

Input format:
The first line of the input contains one string $$$s$$$ consisting of no more than $$$10^5$$$ lowercase Latin letters.

The second line of the input contains one integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of queries.

The next $$$q$$$ lines contain queries, one per line. Each query is given in the format described in the problem statement. It is guaranteed that there is at least one query of the second type.

Output format:
For each query of the second type print the answer for it — the number of distinct characters in the required substring in this query.

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

Example input:
abacaba
5
2 1 4
1 4 b
1 5 b
2 4 6
2 1 7

Example output:
3
1
2

Example input:
dfcbbcfeeedbaea
15
1 6 e
1 4 b
2 6 14
1 7 b
1 12 c
2 6 8
2 1 6
1 7 c
1 2 f
1 10 a
2 7 9
1 10 a
1 14 b
1 1 f
2 1 11

Example output:
5
2
5
2
6

Editorial:
Let's store for each letter all positions in which it appears in some data structure. We need such a data structure that can add, remove and find the next element greater than or equal to our element, fast enough. Suddenly, this data structure is std::set again (in C++).
When we meet the first type query, let's just modify two elements of corresponding sets (one remove, one add). When we meet the second type query, let's iterate over all letters. If the current letter is in the segment $$$[l; r]$$$ then the first element greater than or equal to $$$l$$$ in the corresponding set should exist and be less than or equal to $$$r$$$. If it is so, let's increase the answer by one. After iterating over all letters just print the answer.
Time complexity: $$$O(n \log{n} AL)$$$, when $$$AL$$$ is the size of the alphabet.
Drazil and His Happy Friends
Contest: Codeforces Round 292 (Div. 1)
Difficulty rating: 3100
Tags: math, number theory

Drazil has many friends. Some of them are happy and some of them are unhappy. Drazil wants to make all his friends become happy. So he invented the following plan.

There are n boys and m girls among his friends. Let's number them from 0 to n - 1 and 0 to m - 1 separately. In i-th day, Drazil invites $$(i \bmod n)$$-th boy and $$(i \bmod m)$$-th girl to have dinner together (as Drazil is programmer, i starts from 0). If one of those two people is happy, the other one will also become happy. Otherwise, those two people remain in their states. Once a person becomes happy (or if it is happy originally), he stays happy forever.

Drazil wants to know on which day all his friends become happy or to determine if they won't become all happy at all.

Input format:
The first line contains two integer n and m (1 ≤ n, m ≤ 109).

The second line contains integer b (0 ≤ b ≤ min(n, 105)), denoting the number of happy boys among friends of Drazil, and then follow b distinct integers x1, x2, ..., xb (0 ≤ xi < n), denoting the list of indices of happy boys.

The third line conatins integer g (0 ≤ g ≤ min(m, 105)), denoting the number of happy girls among friends of Drazil, and then follow g distinct integers y1, y2, ... , yg (0 ≤ yj < m), denoting the list of indices of happy girls.

It is guaranteed that there is at least one person that is unhappy among his friends.

Output format:
Print the number of the first day that all friends of Drazil become happy. If this day won't come at all, you print -1.

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

Note:
By $$i \bmod k$$ we define the remainder of integer division of i by k.

In first sample case:

- On the 0-th day, Drazil invites 0-th boy and 0-th girl. Because 0-th girl is happy at the beginning, 0-th boy become happy at this day.
- On the 1-st day, Drazil invites 1-st boy and 1-st girl. They are both unhappy, so nothing changes at this day.
- On the 2-nd day, Drazil invites 0-th boy and 2-nd girl. Because 0-th boy is already happy he makes 2-nd girl become happy at this day.
- On the 3-rd day, Drazil invites 1-st boy and 0-th girl. 0-th girl is happy, so she makes 1-st boy happy.
- On the 4-th day, Drazil invites 0-th boy and 1-st girl. 0-th boy is happy, so he makes the 1-st girl happy. So, all friends become happy at this moment.

Example input:
2 3
0
1 0

Example output:
4

Example input:
2 4
1 0
1 2

Example output:
-1

Editorial:
MP3
Contest: Codeforces Round 576 (Div. 1)
Difficulty rating: 1600
Tags: sortings, two pointers

One common way of digitalizing sound is to record sound intensity at particular time moments. For each time moment intensity is recorded as a non-negative integer. Thus we can represent a sound file as an array of $$$n$$$ non-negative integers.

If there are exactly $$$K$$$ distinct values in the array, then we need $$$k = \lceil \log_{2} K \rceil$$$ bits to store each value. It then takes $$$nk$$$ bits to store the whole file.

To reduce the memory consumption we need to apply some compression. One common way is to reduce the number of possible intensity values. We choose two integers $$$l \le r$$$, and after that all intensity values are changed in the following way: if the intensity value is within the range $$$[l;r]$$$, we don't change it. If it is less than $$$l$$$, we change it to $$$l$$$; if it is greater than $$$r$$$, we change it to $$$r$$$. You can see that we lose some low and some high intensities.

Your task is to apply this compression in such a way that the file fits onto a disk of size $$$I$$$ bytes, and the number of changed elements in the array is minimal possible.

We remind you that $$$1$$$ byte contains $$$8$$$ bits.

$$$k = \lceil log_{2} K \rceil$$$ is the smallest integer such that $$$K \le 2^{k}$$$. In particular, if $$$K = 1$$$, then $$$k = 0$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$I$$$ ($$$1 \le n \le 4 \cdot 10^{5}$$$, $$$1 \le I \le 10^{8}$$$) — the length of the array and the size of the disk in bytes, respectively.

The next line contains $$$n$$$ integers $$$a_{i}$$$ ($$$0 \le a_{i} \le 10^{9}$$$) — the array denoting the sound file.

Output format:
Print a single integer — the minimal possible number of changed elements.

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

Note:
In the first example we can choose $$$l=2, r=3$$$. The array becomes 2 2 2 3 3 3, the number of distinct elements is $$$K=2$$$, and the sound file fits onto the disk. Only two values are changed.

In the second example the disk is larger, so the initial file fits it and no changes are required.

In the third example we have to change both 1s or both 3s.

Example input:
6 1
2 1 2 3 4 3

Example output:
2

Example input:
6 2
2 1 2 3 4 3

Example output:
0

Editorial:
First let's calculate how many different values we can have. Maximal $$$k$$$ is $$$\frac{8I}{n}$$$, maximal $$$K$$$ is $$$2^{k}$$$. We have to be careful not to overflow, let's use $$$K=2^{\min(20, k)}$$$ ($$$2^{20}$$$ is bigger than any $$$n$$$).
Let's sort the array and compress equal values. Now we have to choose no more than $$$K$$$ consecutive values in such a way that they cover as much elements as possible. If $$$K$$$ is bigger than number of different values, then answer is 0. Otherwise we can precalculate prefix sums and try all the variants to choose $$$K$$$ consecutive values.
Complexity is $$$O(n \log n)$$$.
Welfare State
Contest: Codeforces Round 576 (Div. 1)
Difficulty rating: 1600
Tags: binary search, brute force, data structures, sortings

There is a country with $$$n$$$ citizens. The $$$i$$$-th of them initially has $$$a_{i}$$$ money. The government strictly controls the wealth of its citizens. Whenever a citizen makes a purchase or earns some money, they must send a receipt to the social services mentioning the amount of money they currently have.

Sometimes the government makes payouts to the poor: all citizens who have strictly less money than $$$x$$$ are paid accordingly so that after the payout they have exactly $$$x$$$ money. In this case the citizens don't send a receipt.

You know the initial wealth of every citizen and the log of all events: receipts and payouts. Restore the amount of money each citizen has after all events.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^{5}$$$) — the numer of citizens.

The next line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_{i} \le 10^{9}$$$) — the initial balances of citizens.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^{5}$$$) — the number of events.

Each of the next $$$q$$$ lines contains a single event. The events are given in chronological order.

Each event is described as either 1 p x ($$$1 \le p \le n$$$, $$$0 \le x \le 10^{9}$$$), or 2 x ($$$0 \le x \le 10^{9}$$$). In the first case we have a receipt that the balance of the $$$p$$$-th person becomes equal to $$$x$$$. In the second case we have a payoff with parameter $$$x$$$.

Output format:
Print $$$n$$$ integers — the balances of all citizens after all events.

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

Note:
In the first example the balances change as follows: 1 2 3 4 $$$\rightarrow$$$ 3 3 3 4 $$$\rightarrow$$$ 3 2 3 4 $$$\rightarrow$$$ 3 2 3 4

In the second example the balances change as follows: 3 50 2 1 10 $$$\rightarrow$$$ 3 0 2 1 10 $$$\rightarrow$$$ 8 8 8 8 10 $$$\rightarrow$$$ 8 8 20 8 10

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

Example output:
3 2 3 4

Example input:
5
3 50 2 1 10
3
1 2 0
2 8
1 3 20

Example output:
8 8 20 8 10

Editorial:
For every citizen only the last query of type $$$1$$$ matters. Moreover, all queries before don't matter at all. So the answer for each citizen is maximum of $$$x$$$ for last query of type $$$1$$$ for this citizen and maximum of all $$$x$$$ for queries of type $$$2$$$ after that. We can calculate maximum $$$x$$$ for all suffices of queries of type $$$2$$$, and remember the last query of type $$$1$$$ for each citizen. It can be implemented in $$$O(n+q)$$$ time.
Rectangle Painting 1
Contest: Codeforces Round 576 (Div. 1)
Difficulty rating: 2300
Tags: dp

There is a square grid of size $$$n \times n$$$. Some cells are colored in black, all others are colored in white. In one operation you can select some rectangle and color all its cells in white. It costs $$$\max(h, w)$$$ to color a rectangle of size $$$h \times w$$$. You are to make all cells white for minimum total cost.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 50$$$) — the size of the square grid.

Each of the next $$$n$$$ lines contains a string of length $$$n$$$, consisting of characters '.' and '#'. The $$$j$$$-th character of the $$$i$$$-th line is '#' if the cell with coordinates $$$(i, j)$$$ is black, otherwise it is white.

Output format:
Print a single integer — the minimum total cost to paint all cells in white.

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

Note:
The examples and some of optimal solutions are shown on the pictures below.

Example input:
3
###
#.#
###

Example output:
3

Example input:
3
...
...
...

Example output:
0

Editorial:
Let's solve the problem for rectangle $$$W \times H$$$ ($$$W \ge H$$$). Of course, we can cover all rectangle with itself for cost $$$W$$$. To get something smaller than $$$W$$$ we have to leave at least one column uncovered — otherwise we pay at least sum of $$$w$$$ over all rectangles which is at least $$$W$$$. This gives us an idea to use DP on rectangles to solve the problem: $$$dp[x_{1}][x_{2}][y_{1}][y_{2}]$$$ is minimal cost to cover the rectangle $$$[x_{1};x_{2})\times[y_{1};y_{2})$$$. It is initialized by $$$\max(x_{2}-x_{1}, y_{2}-y_{1})$$$, and we have to try not to cover every column/row. Of course, we have to check if it is all white from the beginning; to do that we will precalculate 2D prefix sums. Total complexity is $$$O(n^{5})$$$.