1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Even Picture
Contest: Codeforces Global Round 8
Difficulty rating: 1500
Tags: constructive algorithms

Leo Jr. draws pictures in his notebook with checkered sheets (that is, each sheet has a regular square grid printed on it). We can assume that the sheets are infinitely large in any direction.

To draw a picture, Leo Jr. colors some of the cells on a sheet gray. He considers the resulting picture beautiful if the following conditions are satisfied:

- The picture is connected, that is, it is possible to get from any gray cell to any other by following a chain of gray cells, with each pair of adjacent cells in the path being neighbours (that is, sharing a side).
- Each gray cell has an even number of gray neighbours.
- There are exactly $$$n$$$ gray cells with all gray neighbours. The number of other gray cells can be arbitrary (but reasonable, so that they can all be listed).

Leo Jr. is now struggling to draw a beautiful picture with a particular choice of $$$n$$$. Help him, and provide any example of a beautiful picture.

To output cell coordinates in your answer, assume that the sheet is provided with a Cartesian coordinate system such that one of the cells is chosen to be the origin $$$(0, 0)$$$, axes $$$0x$$$ and $$$0y$$$ are orthogonal and parallel to grid lines, and a unit step along any axis in any direction takes you to a neighbouring cell.

Input format:
The only line contains a single integer $$$n$$$ ($$$1 \leq n \leq 500$$$) — the number of gray cells with all gray neighbours in a beautiful picture.

Output format:
In the first line, print a single integer $$$k$$$ — the number of gray cells in your picture. For technical reasons, $$$k$$$ should not exceed $$$5 \cdot 10^5$$$.

Each of the following $$$k$$$ lines should contain two integers — coordinates of a gray cell in your picture. All listed cells should be distinct, and the picture should satisdfy all the properties listed above. All coordinates should not exceed $$$10^9$$$ by absolute value.

One can show that there exists an answer satisfying all requirements with a small enough $$$k$$$.

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

Note:
The answer for the sample is pictured below:

Example input:
4

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

Editorial:
The sample picture was a red herring, it's hard to generalize to work for arbitrary $$$n$$$. After drawing for a while you may come up with something like this:
or like this:
or something even more complicated. Of course, having a simpler construction (like the first one) saves time on implementation compared to other ones. Don't settle for a solution if it feels too clunky, take a moment and see if you can make it simpler.
Breadboard Capacity (easy version)
Contest: Codeforces Global Round 8
Difficulty rating: 3300
Tags: dp, flows, greedy

This is an easier version of the problem H without modification queries.

Lester and Delbert work at an electronics company. They are currently working on a microchip component serving to connect two independent parts of a large supercomputer.

The component is built on top of a breadboard — a grid-like base for a microchip. The breadboard has $$$n$$$ rows and $$$m$$$ columns, and each row-column intersection contains a node. Also, on each side of the breadboard there are ports that can be attached to adjacent nodes. Left and right side have $$$n$$$ ports each, and top and bottom side have $$$m$$$ ports each. Each of the ports is connected on the outside to one of the parts bridged by the breadboard, and is colored red or blue respectively.

Ports can be connected by wires going inside the breadboard. However, there are a few rules to follow:

- Each wire should connect a red port with a blue port, and each port should be connected to at most one wire.
- Each part of the wire should be horizontal or vertical, and turns are only possible at one of the nodes.
- To avoid interference, wires can not have common parts of non-zero length (but may have common nodes). Also, a wire can not cover the same segment of non-zero length twice.

The capacity of the breadboard is the largest number of red-blue wire connections that can be made subject to the rules above. For example, the breadboard above has capacity $$$7$$$, and one way to make seven connections is pictured below.

Up to this point statements of both versions are identical. Differences follow below.

Given the current breadboard configuration, help Lester and Delbert find its capacity efficiently.

Input format:
The first line contains three integers $$$n, m, q$$$ ($$$1 \leq n, m \leq 10^5$$$, $$$\pmb{q = 0}$$$). $$$n$$$ and $$$m$$$ are the number of rows and columns of the breadboard respectively. In this version $$$q$$$ is always zero, and is only present for consistency with the harder version.

The next four lines describe initial coloring of the ports. Each character in these lines is either R or B, depending on the coloring of the respective port. The first two of these lines contain $$$n$$$ characters each, and describe ports on the left and right sides respectively from top to bottom. The last two lines contain $$$m$$$ characters each, and describe ports on the top and bottom sides respectively from left to right.

Output format:
Print a single integer — the given breadboard capacity.

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

Example input:
4 5 0
BBRR
RBBR
BBBBB
RRRRR

Example output:
7

Editorial:
Quirky Quantifiers
Contest: April Fools Contest 2018
Difficulty rating: 800
Tags: math

Input format:
The input contains a single integer a (10 ≤ a ≤ 999).

Output format:
Output 0 or 1.

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

Example input:
13

Example output:
1

Example input:
927

Example output:
1

Editorial:
JAPE riddle generator is a program which can produce question-answer puns. This problem has been inspired by one of the witticisms produced by it:
What do you call a quirky quantifier? An odd number.
All you had to do was to check whether the given "quantifier" was "quirky".
A Map of the Cat
Contest: April Fools Contest 2018
Difficulty rating: 1900
Tags: *special, brute force, interactive

If you have ever interacted with a cat, you have probably noticed that they are quite particular about how to pet them. Here is an approximate map of a normal cat.

However, some cats won't tolerate this nonsense from the humans. Here is a map of a grumpy cat.

You have met a cat. Can you figure out whether it's normal or grumpy?

Interaction format:
This is an interactive problem. Initially you're not given any information about the cat. Instead, the cat is divided into ten areas, indexed from 0 to 9.

In one query you can choose which area you'll pet and print the corresponding index to standard out. You will get the cat's response, as depicted on the corresponding map, via standard in. For simplicity all responses are written in lowercase.

Once you're certain what type of cat you're dealing with, output "normal" or "grumpy" to standard out.

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

Note:
Please make sure to use the stream flushing operation after each query in order not to leave part of your output in some buffer.

Editorial:
This problem was inspired by the awesome book "Surely You're Joking, Mr. Feynman!" In one of his stories Feynman asks a librarian to fetch him a map of a cat, having a zoological chart in mind. Of course, such a serious interpretation was unsuitable for my purposes :-)
This was a perfectly straightforward problem: just pet the cat! If the reaction you get is "no", try a different spot, otherwise you can figure out what kind of a cat this is right away. Just make sure you're not carried away: both kinds of cats get bored after 7th attempt to pet them and send you away without letting you guess their kind.
Ravioli Sort
Contest: April Fools Contest 2018
Difficulty rating: 1600
Tags: implementation

Everybody knows of spaghetti sort. You decided to implement an analog sorting algorithm yourself, but as you survey your pantry you realize you're out of spaghetti! The only type of pasta you have is ravioli, but you are not going to let this stop you...

You come up with the following algorithm. For each number in the array ai, build a stack of ai ravioli. The image shows the stack for ai = 4.

Arrange the stacks in one row in the order in which the corresponding numbers appear in the input array. Find the tallest one (if there are several stacks of maximal height, use the leftmost one). Remove it and add its height to the end of the output array. Shift the stacks in the row so that there is no gap between them. Repeat the procedure until all stacks have been removed.

At first you are very happy with your algorithm, but as you try it on more inputs you realize that it doesn't always produce the right sorted array. Turns out when two stacks of ravioli are next to each other (at any step of the process) and differ in height by two or more, the top ravioli of the taller stack slides down on top of the lower stack.

Given an input array, figure out whether the described algorithm will sort it correctly.

Input format:
The first line of input contains a single number n (1 ≤ n ≤ 10) — the size of the array.

The second line of input contains n space-separated integers ai (1 ≤ ai ≤ 100) — the elements of the array.

Output format:
Output "YES" if the array can be sorted using the described procedure and "NO" if it can not.

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

Note:
In the second example the array will change even before the tallest stack is chosen for the first time: ravioli from stack of height 3 will slide on the stack of height 1, and the algorithm will output an array {2, 2, 2}.

Example input:
3
1 2 3

Example output:
YES

Example input:
3
3 1 2

Example output:
NO

Editorial:
Let's call the row of stacks "stable" if each adjacent pair of stacks in it differs in height by at most one (so no ravioli are going to slide to a different stack). It is easy to show that if a row is stable, then after removal of the tallest stack the resulting row is also stable. Indeed, after removing stack ai the only new pair of adjacent stacks is ai - 1 and ai + 1. The row was stable, so |ai - ai - 1| ≤ 1 and |ai - ai + 1| ≤ 1. But ai was the tallest stack, so ai - 1 ≤ ai - 1, ai + 1 ≤ ai. Thus the difference in height between ai - 1 and ai + 1 is at most 1, and the resulting row is also stable.
This means that the output will be correct if and only if the original array was stable (obviously, if the original array was not stable, at least one of the stacks would change even before the first tallest stack is chosen, and once some stacks change it's impossible to fix all of them).
I'm Feeling Lucky!
Contest: April Fools Contest 2018
Difficulty rating: 1800
Tags: probabilities

You have one chip and one chance to play roulette. Are you feeling lucky?

Output format:
Print your bet. Your chip must be placed entirely within some square (not on an edge or a corner shared by adjacent squares).

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

Editorial:
Cheese Board
Contest: April Fools Contest 2018
Difficulty rating: 2000

Not to be confused with chessboard.

Input format:
The first line of input contains a single integer N (1 ≤ N ≤ 100) — the number of cheeses you have.

The next N lines describe the cheeses you have. Each line contains two space-separated strings: the name of the cheese and its type. The name is a string of lowercase English letters between 1 and 10 characters long. The type is either "soft" or "hard. All cheese names are distinct.

Output format:
Output a single number.

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

Example input:
9
brie soft
camembert soft
feta soft
goat soft
muenster soft
asiago hard
cheddar hard
gouda hard
swiss hard

Example output:
3

Example input:
6
parmesan hard
emmental hard
edam hard
colby hard
gruyere hard
asiago hard

Example output:
4

Editorial:
This problem was inspired by the first line of Wikipedia article Chessboard: "Not to be confused with cheese board". Indeed, cheese board, chess board, what's the difference really? :-)
The image in the statement showed a bunch of cheeses (from the first example) arranged in a chessboard pattern, with soft cheeses representing one "color" of the squares and hard cheeses representing the other. The task was to find out the smallest size of a square "chessboard" on which the given cheeses could be arranged in such a way that soft and hard cheeses would alternate, and cheeses of the same type would never occupy adjacent squares.
Once you've figured out the task, the solution is very straightforward. First, count the numbers of soft and hard cheeses. Iterate through the sizes of the chessboard, starting with 1, and for each size count the number of black and white cells on it. If the number of black cells is greater than or equal to the number of hard cheeses and the number of white cells is greater than or equal to the number of soft cheeses or vice versa, return this size of the board.
2 + 2 != 4
Contest: April Fools Contest 2018
Difficulty rating: 2400

One very experienced problem writer decided to prepare a problem for April Fools Day contest. The task was very simple - given an arithmetic expression, return the result of evaluating this expression. However, looks like there is a bug in the reference solution...

Input format:
The only line of input data contains the arithmetic expression. The expression will contain between 2 and 10 operands, separated with arithmetic signs plus and/or minus. Each operand will be an integer between 0 and 255, inclusive.

Output format:
Reproduce the output of the reference solution, including the bug.

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

Example input:
8-7+6-5+4-3+2-1-0

Example output:
4

Example input:
2+2

Example output:
-46

Editorial:
This problem is based on a real bug in the checker for problem http://codeforces.com/contest/784/problem/G. Fortunately, we caught it before the contest, which is why I can laugh about it today :-)
The checker successfully iterated through the characters of the expression and accumulated them into a "current number" variable to add it to the result or to subtract it from the result. But due to a missing check in current number accumulation plus and minus characters were also counted as digits of the number. In "2+2" example, the first number was correctly interpreted as 2, but for the second one the first digit was ('+'-'0') = -5, and so the second number was interpreted as (-5)*10 + 2 = -48. Minus sign would be interpreted as an extra leading ('-'-'0') = -3 "digit".
The solution follows:
long long result = 0, cur = 0; expr += "+"; int sign = +1; for (char c : expr) { if (c == '+' || c == '-') { result += sign * cur; cur = 0; } if (c == '-') sign = -1; if (c == '+') sign = +1; // bug: + and - signs are accumulated into the number cur = cur * 10 + (c - '0'); }
Maximum Substring
Contest: CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 800
Tags: brute force, greedy, implementation

A binary string is a string consisting only of the characters 0 and 1. You are given a binary string $$$s$$$.

For some non-empty substring$$$^\dagger$$$ $$$t$$$ of string $$$s$$$ containing $$$x$$$ characters 0 and $$$y$$$ characters 1, define its cost as:

- $$$x \cdot y$$$, if $$$x > 0$$$ and $$$y > 0$$$;
- $$$x^2$$$, if $$$x > 0$$$ and $$$y = 0$$$;
- $$$y^2$$$, if $$$x = 0$$$ and $$$y > 0$$$.

Given a binary string $$$s$$$ of length $$$n$$$, find the maximum cost across all its non-empty substrings.

$$$^\dagger$$$ A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. The description of test cases follows.

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

The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$.

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, print a single integer — the maximum cost across all substrings.

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

Note:
In the first test case, we can take a substring $$$111$$$. It contains $$$3$$$ characters 1 and $$$0$$$ characters 0. So $$$a = 3$$$, $$$b = 0$$$ and its cost is $$$3^2 = 9$$$.

In the second test case, we can take the whole string. It contains $$$4$$$ characters 1 and $$$3$$$ characters 0. So $$$a = 4$$$, $$$b = 3$$$ and its cost is $$$4 \cdot 3 = 12$$$.

In the third test case, we can can take a substring $$$1111$$$ and its cost is $$$4^2 = 16$$$.

In the fourth test case, we can take the whole string and cost is $$$4 \cdot 3 = 12$$$.

In the fifth test case, we can take a substring $$$000$$$ and its cost is $$$3 \cdot 3 = 9$$$.

In the sixth test case, we can only take the substring $$$0$$$ and its cost is $$$1 \cdot 1 = 1$$$.

Example input:
6
5
11100
7
1100110
6
011110
7
1001010
4
1000
1
0

Example output:
9
12
16
12
9
1

Editorial:
Considering that if we want to find the max value of $$$x \dot y$$$, then the whole string is the best to calculate, for it 0s and 1s are the max.
Then considering $$$x \dot x$$$ and $$$y \dot y$$$ : what we need to do is to calculate the max continuous number of $$$0$$$ or $$$1$$$, compare its square to the first condition, then take the bigger one as the answer.
Count GCD
Contest: CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 1800
Tags: combinatorics, math, number theory

You are given two integers $$$n$$$ and $$$m$$$ and an array $$$a$$$ of $$$n$$$ integers. For each $$$1 \le i \le n$$$ it holds that $$$1 \le a_i \le m$$$.

Your task is to count the number of different arrays $$$b$$$ of length $$$n$$$ such that:

- $$$1 \le b_i \le m$$$ for each $$$1 \le i \le n$$$, and
- $$$\gcd(b_1,b_2,b_3,...,b_i) = a_i$$$ for each $$$1 \le i \le n$$$.

Here $$$\gcd(a_1,a_2,\dots,a_i)$$$ denotes the greatest common divisor (GCD) of integers $$$a_1,a_2,\ldots,a_i$$$.

Since this number can be too large, print it modulo $$$998\,244\,353$$$.

Input format:
Each test consist of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 10^9$$$) — the length of the array $$$a$$$ and the maximum possible value of the element.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — the elements of the array $$$a$$$.

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

Output format:
For each test case, print a single integer — the number of different arrays satisfying the conditions above. Since this number can be large, print it modulo $$$998\,244\,353$$$.

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

Note:
In the first test case, the possible arrays $$$b$$$ are:

- $$$[4,2,1]$$$;
- $$$[4,2,3]$$$;
- $$$[4,2,5]$$$.

In the second test case, the only array satisfying the demands is $$$[1,1]$$$.

In the third test case, it can be proven no such array exists.

Example input:
5
3 5
4 2 1
2 1
1 1
5 50
2 3 5 2 3
4 1000000000
60 30 1 1
2 1000000000
1000000000 2

Example output:
3
1
0
595458194
200000000

Editorial:
We can notice that if for some $$$2 \le i \le n$$$, $$$a_{i-1}$$$ is not divisible by $$$a_{i}$$$, then the answer is $$$0$$$. Else, note that all the prime factors of $$$a_1$$$ are also prime factors in all the other values. Thus after factorizing $$$a_1$$$ we can quickly factorize every other value.
Now let's find the number of ways we can select $$$b_i$$$ for every $$$i$$$. The answer will be the product of these values since each position is independent. It's easy to see that there is only one way to select $$$b_1$$$, that is $$$a_1$$$. Now for $$$i > 1$$$ we need to find the number of values $$$x$$$ such that $$$gcd(a_{i-1},x)=a_i$$$. Let $$$x=a_i \cdot k$$$, we can rephrase as $$$gcd( \frac{a_{i-1}}{a_i} \cdot a_i, a_i \cdot k) = a_i$$$, which is also equivalent to $$$gcd( \frac{a_{i-1}}{a_i}, k) = 1$$$. We have $$$k \le \frac{m}{a_i}$$$, thus the task reduces to a simple principle of inclusion-exclusion problem.
Time complexity $$$O(2^9 \cdot 9 \cdot log + \sqrt{M})$$$ per testcase.
Reverse and Concatenate
Contest: Codeforces Round 770 (Div. 2)
Difficulty rating: 800
Tags: greedy, strings

You are given a string $$$s$$$ of length $$$n$$$ and a number $$$k$$$. Let's denote by $$$rev(s)$$$ the reversed string $$$s$$$ (i.e. $$$rev(s) = s_n s_{n-1} ... s_1$$$). You can apply one of the two kinds of operations to the string:

- replace the string $$$s$$$ with $$$s + rev(s)$$$
- replace the string $$$s$$$ with $$$rev(s) + s$$$

How many different strings can you get as a result of performing exactly $$$k$$$ operations (possibly of different kinds) on the original string $$$s$$$?

In this statement we denoted the concatenation of strings $$$s$$$ and $$$t$$$ as $$$s + t$$$. In other words, $$$s + t = s_1 s_2 ... s_n t_1 t_2 ... t_m$$$, where $$$n$$$ and $$$m$$$ are the lengths of strings $$$s$$$ and $$$t$$$ respectively.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — number of test cases. Next $$$2 \cdot t$$$ lines contain $$$t$$$ test cases:

The first line of a test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100$$$, $$$0 \le k \le 1000$$$) — the length of the string and the number of operations respectively.

The second string of a test case contains one string $$$s$$$ of length $$$n$$$ consisting of lowercase Latin letters.

Output format:
For each test case, print the answer (that is, the number of different strings that you can get after exactly $$$k$$$ operations) on a separate line.

It can be shown that the answer does not exceed $$$10^9$$$ under the given constraints.

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

Note:
In the first test case of the example:

After the first operation the string $$$s$$$ can become either aabbaa or baaaab. After the second operation there are 2 possibilities for $$$s$$$: aabbaaaabbaa and baaaabbaaaab.

Example input:
4
3 2
aab
3 3
aab
7 1
abacaba
2 0
ab

Example output:
2
2
1
1

Editorial:
If $$$k = 0$$$, the answer is $$$1$$$. Otherwise, consider two cases:
• The string is a palindrome (that is, $$$s = rev(s)$$$). Then $$$rev(s) + s = s + rev(s) = s + s$$$, so both operations will replace $$$s$$$ by the string $$$s+s$$$, which is also a palindrome. Then for any $$$k$$$ the answer is $$$1$$$.
• Otherwise $$$s \ne rev(s)$$$. Then after the first operation we get either $$$s + rev(s)$$$ (which is a palindrome) or $$$rev(s) + s$$$ (also a palindrome). Also note that if we apply the operation to two different palindromes of length $$$x$$$ any number of times, they cannot become equal, since they do not have the same prefix of length $$$x$$$. So, after the first operation from a non-palindrome 2 different strings will be obtained, and after all following operations 2 unequal strings will be obtained. So the answer is — $$$2$$$.