1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Evil
Contest: Codeforces Round 192 (Div. 1)
Difficulty rating: 3100
Tags: math

There are n cities on a two dimensional Cartesian plane. The distance between two cities is equal to the Manhattan distance between them (see the Notes for definition). A Hamiltonian cycle of the cities is defined as a permutation of all n cities. The length of this Hamiltonian cycle is defined as the sum of the distances between adjacent cities in the permutation plus the distance between the first and final city in the permutation. Please compute the longest possible length of a Hamiltonian cycle of the given cities.

Input format:
The first line contains an integer n (3 ≤ n ≤ 105). Then n lines follow, each consisting of two integers xi and yi (0 ≤ xi, yi ≤ 109), denoting the coordinates of a city. All given points will be distinct.

Output format:
A single line denoting the longest possible length of a Hamiltonian cycle of the given cities. You should not output the cycle, only its length.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

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

Note:
In the example, one of the possible Hamiltonian cycles with length 6 is (1, 1) (1, 2) (2, 1) (2, 2). There does not exist any other Hamiltonian cycle with a length greater than 6.

The Manhattan distance between two cities (xi, yi) and (xj, yj) is |xi - xj| + |yi - yj|.

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

Example output:
6

Editorial:
Cirno's Perfect Bitmasks Classroom
Contest: Codeforces Round 796 (Div. 2)
Difficulty rating: 800
Tags: bitmasks, brute force

Cirno's perfect bitmasks classroom has just started!

Cirno gave her students a positive integer $$$x$$$. As an assignment, her students need to find the minimum positive integer $$$y$$$, which satisfies the following two conditions:

$$$$$$x\ \texttt{and}\ y > 0$$$$$$ $$$$$$x\ \texttt{xor}\ y > 0$$$$$$

Where $$$\texttt{and}$$$ is the bitwise AND operation, and $$$\texttt{xor}$$$ is the bitwise XOR operation.

Among the students was Mystia, who was truly baffled by all these new operators. Please help her!

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

For each test case, the only line of input contains one integer $$$x$$$ ($$$1 \leq x \leq 2^{30}$$$).

Output format:
For each test case, print a single integer — the minimum number of $$$y$$$.

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

Note:
Test case 1:

$$$1\; \texttt{and}\; 3=1>0$$$, $$$1\; \texttt{xor}\; 3=2>0$$$.

Test case 2:

$$$2\; \texttt{and}\; 3=2>0$$$, $$$2\; \texttt{xor}\; 3=1>0$$$.

Example input:
7
1
2
5
9
16
114514
1000000

Example output:
3
3
1
1
17
2
64

Editorial:
Let $$$p_i$$$ be the $$$i$$$-th bit of $$$x$$$, $$$q_i$$$ be the $$$i$$$-th bit of $$$y$$$ (both indexed from $$$0$$$).
$$$x\ \texttt{and}\ y > 0\Leftrightarrow \exists i,\ p_i= q_i = 1$$$.
$$$x\ \texttt{xor}\ y > 0\Leftrightarrow \exists i,\ p_i\ne q_i$$$.
To satisfy the first condition, find the minimum integer $$$k$$$ satisfying $$$p_k=1$$$, and assign $$$1$$$ to $$$q_k$$$.
If $$$x\ne 2^k$$$, the second condition is satisfied now. Otherwise, find the minimum integer $$$j$$$ satisfying $$$p_j=0$$$, and assign $$$1$$$ to $$$q_j$$$.
1-3-5
Contest: Kotlin Heroes: Episode 10
Difficulty rating: 1100
Tags: *special, dp

In Berland, coins of worth $$$1$$$, $$$3$$$ and $$$5$$$ burles are commonly used (burles are local currency).

Eva has to pay exactly $$$n$$$ burles in a shop. She has an infinite amount of coins of all three types. However, she doesn't like to pay using coins worth $$$1$$$ burle — she thinks they are the most convenient to use.

Help Eva to calculate the minimum number of coins worth $$$1$$$ burle she has to use, if she has to pay exactly $$$n$$$ burles. Note that she can spend any number of coins worth $$$3$$$ and/or $$$5$$$ burles.

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

Each test case consists of one line, containing one integer $$$n$$$ ($$$1 \le n \le 100$$$).

Output format:
For each test case, print one integer — the minimum number of $$$1$$$-burle coins Eva has to use.

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

Note:
In the first test case, Eva should use $$$1$$$ coin worth $$$1$$$ burle, and $$$2$$$ coins worth $$$3$$$ burles.

In the second test case, Eva should use $$$1$$$ coin worth $$$3$$$ burles and $$$1$$$ coin worth $$$5$$$ burles.

In the third test case, Eva should use $$$14$$$ coins worth $$$3$$$ burles.

In the fourth test case, Eva should use $$$2$$$ coins worth $$$1$$$ burle.

In the fifth test case, Eva should use $$$2$$$ coins worth $$$3$$$ burles and $$$1$$$ coin worth $$$5$$$ burles.

Example input:
5
7
8
42
2
11

Example output:
1
0
0
2
0

Editorial:
There are two main ways to solve this problem: brute force and casework.
To solve this problem with brute force, you can use three nested loops to iterate on the number of coins of each type from $$$0$$$ to $$$n$$$, check if they give exactly $$$n$$$ burles in total, and update the answer. This can be optimized in many different ways, like iterating only on the number of coins worth $$$3$$$ and $$$5$$$ burles and calculating the number of coins worth $$$1$$$ burle in $$$O(1)$$$. However, the approach with three nested loops works in $$$O(n^3)$$$ and is fast enough.
The solution with casework basically works because of an observation that if $$$n$$$ is big enough ($$$8$$$ or greater), it can always be expressed as the sum of $$$3$$$'s and/or $$$5$$$'s. So, we can get the answers for $$$n \le 7$$$ by hand and if $$$n > 7$$$, jsut output $$$0$$$. This observation is kinda intuitive, but if you want a proof, you can use Chicken McNugget Theorem (in my opinion, one of the coolest names for a math topic!)
Clock in the Pool
Contest: Kotlin Heroes: Episode 10
Difficulty rating: 1400
Tags: *special, math

You are swimming in the pool, and you need to control the time of swimming.

The pool has a clock that cycles between three different modes: showing water temperature, showing air temperature, and showing time. At the start of the $$$0$$$-th second it starts showing water temperature, at the start of the $$$k$$$-th second it switches to air temperature. At the start of the $$$2k$$$-th second, it switches to showing time.

At the start of the $$$3k$$$-th second the clock starts showing water temperature again, at the start of the $$$4k$$$-th second — air temperature, and so on.

You looked at the clock during the $$$m$$$-th second to check the time, but it may be that the clock is not showing time right now. How much time do you have to wait to see the time on the clock?

Answer $$$t$$$ independent test cases.

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

The first and only line of each test case contains two integers $$$k$$$ and $$$m$$$ ($$$1 \le k \le 10^8; 1 \le m \le 10^9$$$) — the length of the period of the clock and the moment of time you check the clock.

Output format:
For each test case, print a single integer — the time you have to wait from the moment $$$m$$$ until the moment the clock starts showing the time.

You can assume that you are able to read the time instantly the moment it displays on the clock.

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

Note:
In the first test case, the clock will start showing time during the $$$2$$$-nd second, so you have to wait $$$2 - 1 = 1$$$ second.

In the second test case, the clock shows time from the $$$10$$$-th until the $$$15$$$-th second, so during the $$$14$$$-th second it shows time, and you don't have to wait.

In the third test case, during the $$$15$$$-th second, the clock is already showing water temperature. So you have to wait till the $$$25$$$-th second, when the clock starts showing time again. You'll wait $$$25 - 15 = 10$$$ seconds.

In the fourth test case, the clock will start showing time at the start of the $$$110$$$-th second, so you'll wait $$$110 - 110 = 0$$$ seconds.

Example input:
5
1 1
5 14
5 15
10 110
99999999 1000000000

Example output:
1
0
10
0
99999989

Editorial:
Let's write down intervals when the clock shows time using formulas. Segments are $$$[3k \cdot x + 2k, 3k \cdot (x + 1))$$$ for all integer $$$x \ge 0$$$.
We need to find the first interval that finished later than $$$m$$$. It may start either earlier or later than $$$m$$$, but it must finish later than $$$m$$$.
In formulas, it means that we should find the minimum $$$x$$$ such that $$$m < 3k \cdot (x + 1)$$$ or $$$x > \frac{m}{3k} - 1$$$. It means that we should take $$$x = \mathrm{floor}(\frac{m}{3k})$$$.
Since now we know $$$x$$$, we can calculate when the $$$x$$$-th interval starts: it's moment $$$3kx + 2k$$$. If $$$3kx + 2k > m$$$, we should wait exactly $$$3kx + 2k - m$$$ seconds. If $$$3kx + 2k \le m$$$, then time is showing right now, and we don't need to wait.
Firewood
Contest: Kotlin Heroes: Episode 10
Difficulty rating: 1500
Tags: *special

It's pretty cold in Berland (yes, even in May). So Monocarp has to light his fireplace.

Monocarp has a big log of wood, which weighs $$$2^n$$$ grams. Monocarp has watched the weather forecast and decided that he has to burn $$$k$$$ grams of wood in the fireplace today, and the remaining $$$2^n-k$$$ grams of wood will be used tomorrow.

In one minute, Monocarp can use his saw to split one of his logs in half. Initially he has only one log, but of course, after splitting a log, he gets two new logs. If the weight of the log is $$$x$$$, then each of the resulting logs has weight equal to $$$\frac{x}{2}$$$. Monocarp can't split logs of weight $$$1$$$ gram.

Monocarp has to cut his log in such a way that some of the resulting logs weigh exactly $$$k$$$ grams in total (and since the total weight of wood doesn't change, the remaining logs will have a total weight equal to exactly $$$2^n-k$$$). Help him to calculate the minimum number of minutes he has to spend cutting the logs.

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

Each test case consists of one line containing two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 60$$$; $$$1 \le k \le 2^n-1$$$).

Output format:
For each test case, print one integer — the minimum number of minutes Monocarp has to spend splitting the wood.

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

Note:
In the first test case, Monocarp has to cut his log exactly once. Then he will have two logs weighing $$$2$$$ grams each.

In the second test case, Monocarp has to cut his log of $$$4$$$ grams once, then cut one of the resulting logs. He will have one log of weight $$$2$$$ and two logs of weight $$$1$$$, so he can use two logs to get exactly $$$3$$$ grams.

Example input:
4
2 2
2 1
10 3
50 36679020707840

Example output:
1
2
10
16

Editorial:
Suppose $$$k$$$ is not divisible by $$$2^m$$$ ($$$m$$$ is an arbitrary positive integer). Then we should have at least one log with weight not divisible by $$$2^m$$$, since if all logs are divisible by $$$2^m$$$, we cannot get the sum of log weights which is not divisible by $$$2^m$$$.
So, let $$$d$$$ be the maximum integer such that $$$k$$$ is divisible by $$$2^d$$$. After we split the logs, there should be at least one log having weight $$$2^d$$$ or less. So, we need to do at least $$$n - d$$$ actions.
And we can show that $$$n - d$$$ actions are always sufficient. Split the smallest log every time, so you get logs of size $$$2^{n-1}, 2^{n-2}, 2^{n-3}, \dots, 2^{d+1}, 2^d, 2^d$$$. We can always choose a subset of logs with total weight equal to $$$k$$$, if $$$k$$$ is divisible by $$$2^d$$$ and less than $$$n$$$. For example, we can make this subset if for every bit set to $$$1$$$ in $$$k$$$, we take the corresponding log.
The Beaver's Problem - 3
Contest: Abbyy Cup 2.0 - Final
Difficulty rating: 1800

The Smart Beaver from ABBYY came up with another splendid problem for the ABBYY Cup participants! This time the Beaver invites the contest participants to check out a problem on sorting documents by their subjects. Let's describe the problem:

You've got some training set of documents. For each document you know its subject. The subject in this problem is an integer from 1 to 3. Each of these numbers has a physical meaning. For instance, all documents with subject 3 are about trade.

You can download the training set of documents at the following link: http://download4.abbyy.com/a2/X2RZ2ZWXBG5VYWAL61H76ZQM/train.zip. The archive contains three directories with names "1", "2", "3". Directory named "1" contains documents on the 1-st subject, directory "2" contains documents on the 2-nd subject, and directory "3" contains documents on the 3-rd subject. Each document corresponds to exactly one file from some directory.

All documents have the following format: the first line contains the document identifier, the second line contains the name of the document, all subsequent lines contain the text of the document. The document identifier is used to make installing the problem more convenient and has no useful information for the participants.

You need to write a program that should indicate the subject for a given document. It is guaranteed that all documents given as input to your program correspond to one of the three subjects of the training set.

Input format:
The first line contains integer id (0 ≤ id ≤ 106) — the document identifier. The second line contains the name of the document. The third and the subsequent lines contain the text of the document. It is guaranteed that the size of any given document will not exceed 10 kilobytes.

The tests for this problem are divided into 10 groups. Documents of groups 1 and 2 are taken from the training set, but their identifiers will not match the identifiers specified in the training set. Groups from the 3-rd to the 10-th are roughly sorted by the author in ascending order of difficulty (these groups contain documents which aren't present in the training set).

Output format:
Print an integer from 1 to 3, inclusive — the number of the subject the given document corresponds to.

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

Editorial:
Buy the String
Contest: Codeforces Round 684 (Div. 2)
Difficulty rating: 800
Tags: implementation, math

You are given four integers $$$n$$$, $$$c_0$$$, $$$c_1$$$ and $$$h$$$ and a binary string $$$s$$$ of length $$$n$$$.

A binary string is a string consisting of characters $$$0$$$ and $$$1$$$.

You can change any character of the string $$$s$$$ (the string should be still binary after the change). You should pay $$$h$$$ coins for each change.

After some changes (possibly zero) you want to buy the string. To buy the string you should buy all its characters. To buy the character $$$0$$$ you should pay $$$c_0$$$ coins, to buy the character $$$1$$$ you should pay $$$c_1$$$ coins.

Find the minimum number of coins needed to buy the string.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10$$$) — the number of test cases. Next $$$2t$$$ lines contain descriptions of test cases.

The first line of the description of each test case contains four integers $$$n$$$, $$$c_{0}$$$, $$$c_{1}$$$, $$$h$$$ ($$$1 \leq n, c_{0}, c_{1}, h \leq 1000$$$).

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

Output format:
For each test case print a single integer — the minimum number of coins needed to buy the string.

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

Note:
In the first test case, you can buy all characters and pay $$$3$$$ coins, because both characters $$$0$$$ and $$$1$$$ costs $$$1$$$ coin.

In the second test case, you can firstly change $$$2$$$-nd and $$$4$$$-th symbols of the string from $$$1$$$ to $$$0$$$ and pay $$$2$$$ coins for that. Your string will be $$$00000$$$. After that, you can buy the string and pay $$$5 \cdot 10 = 50$$$ coins for that. The total number of coins paid will be $$$2 + 50 = 52$$$.

Example input:
6
3 1 1 1
100
5 10 100 1
01010
5 10 1 1
11111
5 1 10 1
11111
12 2 1 10
101110110101
2 100 1 10
00

Example output:
3
52
5
10
16
22

Editorial:
We will consider each character seperately. Look at the $$$i$$$-th character; if it is originally a $$$1$$$, we can either change it to a $$$0$$$ and pay $$$h + c_0$$$ coins for this specific character, or we can not change it and pay $$$c_1$$$ coins for it. Since we want to pay as little as possible, we take the minimum of these two. So if the $$$i$$$th character is a $$$1$$$, we will have to pay $$$min(c_1, h + c_0)$$$ coins for it. A similar logic can be used for the zeroes; if the $$$i$$$th character is a $$$0$$$ we will have to pay $$$min(c_0, h + c_1)$$$ coins. So we iterate over $$$s$$$, and for each character we add the required minimum to the sum, depending on whether it's a $$$0$$$ or $$$1$$$.
Time complexity: $$$O(n)$$$
Two Semiknights Meet
Contest: Codeforces Round 212 (Div. 2)
Difficulty rating: 1500
Tags: greedy, math

A boy Petya loves chess very much. He even came up with a chess piece of his own, a semiknight. The semiknight can move in any of these four directions: 2 squares forward and 2 squares to the right, 2 squares forward and 2 squares to the left, 2 squares backward and 2 to the right and 2 squares backward and 2 to the left. Naturally, the semiknight cannot move beyond the limits of the chessboard.

Petya put two semiknights on a standard chessboard. Petya simultaneously moves with both semiknights. The squares are rather large, so after some move the semiknights can meet, that is, they can end up in the same square. After the meeting the semiknights can move on, so it is possible that they meet again. Petya wonders if there is such sequence of moves when the semiknights meet. Petya considers some squares bad. That is, they do not suit for the meeting. The semiknights can move through these squares but their meetings in these squares don't count.

Petya prepared multiple chess boards. Help Petya find out whether the semiknights can meet on some good square for each board.

Please see the test case analysis.

Input format:
The first line contains number t (1 ≤ t ≤ 50) — the number of boards. Each board is described by a matrix of characters, consisting of 8 rows and 8 columns. The matrix consists of characters ".", "#", "K", representing an empty good square, a bad square and the semiknight's position, correspondingly. It is guaranteed that matrix contains exactly 2 semiknights. The semiknight's squares are considered good for the meeting. The tests are separated by empty line.

Output format:
For each test, print on a single line the answer to the problem: "YES", if the semiknights can meet and "NO" otherwise.

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

Note:
Consider the first board from the sample. We will assume the rows and columns of the matrix to be numbered 1 through 8 from top to bottom and from left to right, correspondingly. The knights can meet, for example, in square (2, 7). The semiknight from square (4, 1) goes to square (2, 3) and the semiknight goes from square (8, 1) to square (6, 3). Then both semiknights go to (4, 5) but this square is bad, so they move together to square (2, 7).

On the second board the semiknights will never meet.

Example input:
2
........
........
......#.
K..##..#
.......#
...##..#
......#.
K.......
........
........
..#.....
..#..#..
..####..
...##...
........
....K#K#

Example output:
YES
NO

Editorial:
Petya and Staircases
Contest: Codeforces Round 212 (Div. 2)
Difficulty rating: 1100
Tags: implementation, sortings

Little boy Petya loves stairs very much. But he is bored from simple going up and down them — he loves jumping over several stairs at a time. As he stands on some stair, he can either jump to the next one or jump over one or two stairs at a time. But some stairs are too dirty and Petya doesn't want to step on them.

Now Petya is on the first stair of the staircase, consisting of n stairs. He also knows the numbers of the dirty stairs of this staircase. Help Petya find out if he can jump through the entire staircase and reach the last stair number n without touching a dirty stair once.

One has to note that anyway Petya should step on the first and last stairs, so if the first or the last stair is dirty, then Petya cannot choose a path with clean steps only.

Input format:
The first line contains two integers n and m (1 ≤ n ≤ 109, 0 ≤ m ≤ 3000) — the number of stairs in the staircase and the number of dirty stairs, correspondingly. The second line contains m different space-separated integers d1, d2, ..., dm (1 ≤ di ≤ n) — the numbers of the dirty stairs (in an arbitrary order).

Output format:
Print "YES" if Petya can reach stair number n, stepping only on the clean stairs. Otherwise print "NO".

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

Example input:
10 5
2 4 8 3 6

Example output:
NO

Example input:
10 5
2 4 5 7 9

Example output:
YES

Editorial:
Insertion Sort
Contest: Codeforces Round 212 (Div. 2)
Difficulty rating: 1900
Tags: data structures, dp, implementation, math

Petya is a beginner programmer. He has already mastered the basics of the C++ language and moved on to learning algorithms. The first algorithm he encountered was insertion sort. Petya has already written the code that implements this algorithm and sorts the given integer zero-indexed array a of size n in the non-decreasing order.

Petya uses this algorithm only for sorting of arrays that are permutations of numbers from 0 to n - 1. He has already chosen the permutation he wants to sort but he first decided to swap some two of its elements. Petya wants to choose these elements in such a way that the number of times the sorting executes function swap, was minimum. Help Petya find out the number of ways in which he can make the swap and fulfill this requirement.

It is guaranteed that it's always possible to swap two elements of the input permutation in such a way that the number of swap function calls decreases.

Input format:
The first line contains a single integer n (2 ≤ n ≤ 5000) — the length of the permutation. The second line contains n different integers from 0 to n - 1, inclusive — the actual permutation.

Output format:
Print two integers: the minimum number of times the swap function is executed and the number of such pairs (i, j) that swapping the elements of the input permutation with indexes i and j leads to the minimum number of the executions.

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

Note:
In the first sample the appropriate pairs are (0, 3) and (0, 4).

In the second sample the appropriate pairs are (0, 4), (1, 4), (2, 4) and (3, 4).

Example input:
5
4 0 3 1 2

Example output:
3 2

Example input:
5
1 2 3 4 0

Example output:
3 4

Editorial: