1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Cases
Contest: Codeforces Round 961 (Div. 2)
Difficulty rating: 2300
Tags: bitmasks, brute force, dp, strings

You're a linguist studying a mysterious ancient language. You know that

1. Its words consist only of the first $$$c$$$ letters of the Latin alphabet.
2. Each word has a case which can be unambiguously determined by its last letter (different letters correspond to different cases). For example, words "ABACABA" and "ABA" (if they exist) have the same case in this language because they both have the same ending 'A', whereas "ALICE" and "BOB" have different cases. If the language does not have a case corresponding to some letter, it means that the word cannot end with this letter.
3. The length of each word is $$$k$$$ or less.

You have a single text written in this language. Unfortunately, as the language is really ancient, spaces between words are missing and all letters are uppercase. You wonder what is the minimum number of cases the language can have. Can you find this out?

Input format:
Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) — the number of test cases. It is followed by descriptions of the test cases.

The first line of each test case contains three integers $$$n$$$, $$$c$$$, $$$k$$$ ($$$1 \le k \le n \le 2^{18}$$$, $$$1 \le c \le 18$$$) — the length of the text, the number of letters in the language, and the maximum length of the word.

The second line contains a string of $$$n$$$ characters — the text itself. Each character is one of the first $$$c$$$ uppercase letters of the Latin alphabet.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2^{18}$$$ and the sum of $$$2^c$$$ over all test cases does not exceed $$$2^{18}$$$.

Output format:
For each test case, output a single line consisting of a single integer — the minimum number of cases in the language.

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

Note:
In the first test case, there must be five cases in the language (for each of the letters 'A', 'B', 'C', 'D', and 'E' there must be a case that has a corresponding ending).

In the fourth test case, one case with ending 'B' is sufficient.

Example input:
7
5 5 1
ABCDE
3 1 2
AAA
3 2 2
AAB
10 2 2
ABABABABAB
4 4 4
DCBA
1 17 1
Q
9 3 2
ABCABCABC

Example output:
5
1
2
1
1
1
2

Editorial:
Let Me Teach You a Lesson (Easy Version)
Contest: Codeforces Round 961 (Div. 2)
Difficulty rating: 2700
Tags: 2-sat, data structures, dp, matrices, two pointers

This is the easy version of a problem. The only difference between an easy and a hard version is the constraints on $$$t$$$ and $$$n$$$. You can make hacks only if both versions of the problem are solved.

Arthur is giving a lesson to his famous $$$2 n$$$ knights. Like any other students, they're sitting at the desks in pairs, but out of habit in a circle. The knight $$$2 i - 1$$$ is sitting at the desk with the knight $$$2 i$$$.

Each knight has intelligence, which can be measured by an integer. Let's denote the intelligence of the $$$i$$$-th knight as $$$a_i$$$. Arthur wants the maximal difference in total intelligence over all pairs of desks to be as small as possible. More formally, he wants to minimize $$$\max\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i}) - \min\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i})$$$.

However, the Code of Chivalry only allows swapping the opposite knights in the circle, i.e., Arthur can simultaneously perform $$$a_i := a_{i + n}$$$, $$$a_{i + n} := a_i$$$ for any $$$1 \le i \le n$$$. Arthur can make any number of such swaps. What is the best result he can achieve?

Input format:
Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. It is followed by descriptions of the test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$) — the number of desks.

The second line consists of $$$2n$$$ integers $$$a_1, a_2, \ldots, a_{2 n}$$$ ($$$1 \le a_i \le 10^9$$$) — the intelligence values of the knights.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

Output format:
For each test case, output a single line containing one integer — the minimal difference Arthur can achieve.

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

Note:
In the first test case, Arthur can swap the second and the fourth knights. Then the total intelligence at both desks will be $$$10$$$.

In the third test case, Arthur can make $$$0$$$ operations, which will result in the total intelligence of $$$11$$$ at each of the desks.

In the fourth test case, Arthur can swap knights with indices $$$2$$$ and $$$5$$$ and achieve the difference of $$$2$$$. It can be proven that he cannot improve his result any further.

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

Example output:
0
0
0
2
4

Editorial:
Let Me Teach You a Lesson (Hard Version)
Contest: Codeforces Round 961 (Div. 2)
Difficulty rating: 2900
Tags: data structures, dp, matrices, two pointers

This is the hard version of a problem. The only difference between an easy and a hard version is the constraints on $$$t$$$ and $$$n$$$. You can make hacks only if both versions of the problem are solved.

Arthur is giving a lesson to his famous $$$2 n$$$ knights. Like any other students, they're sitting at the desks in pairs, but out of habit in a circle. The knight $$$2 i - 1$$$ is sitting at the desk with the knight $$$2 i$$$.

Each knight has intelligence, which can be measured by an integer. Let's denote the intelligence of the $$$i$$$-th knight as $$$a_i$$$. Arthur wants the maximal difference in total intelligence over all pairs of desks to be as small as possible. More formally, he wants to minimize $$$\max\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i}) - \min\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i})$$$.

However, the Code of Chivalry only allows swapping the opposite knights in the circle, i.e., Arthur can simultaneously perform $$$a_i := a_{i + n}$$$, $$$a_{i + n} := a_i$$$ for any $$$1 \le i \le n$$$. Arthur can make any number of such swaps. What is the best result he can achieve?

Input format:
Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) — the number of test cases. It is followed by descriptions of the test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100\,000$$$) — the number of desks.

The second line consists of $$$2n$$$ integers $$$a_1, a_2, \ldots, a_{2 n}$$$ ($$$1 \le a_i \le 10^9$$$) — the intelligence values of the knights.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$100\,000$$$.

Output format:
For each test case, output a single line containing one integer — the minimal difference Arthur can achieve.

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

Note:
In the first test case, Arthur can swap the second and the fourth knights. Then the total intelligence at both desks will be $$$10$$$.

In the third test case, Arthur can make $$$0$$$ operations, which will result in the total intelligence of $$$11$$$ at each of the desks.

In the fourth test case, Arthur can swap knights with indices $$$2$$$ and $$$5$$$ and achieve the difference of $$$2$$$. It can be proven that he cannot improve his result any further.

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

Example output:
0
0
0
2
4

Editorial:
Rectangle Puzzle
Contest: Codeforces Round 172 (Div. 1)
Difficulty rating: 2000
Tags: geometry

You are given two rectangles on a plane. The centers of both rectangles are located in the origin of coordinates (meaning the center of the rectangle's symmetry). The first rectangle's sides are parallel to the coordinate axes: the length of the side that is parallel to the Ox axis, equals w, the length of the side that is parallel to the Oy axis, equals h. The second rectangle can be obtained by rotating the first rectangle relative to the origin of coordinates by angle α.

Your task is to find the area of the region which belongs to both given rectangles. This region is shaded in the picture.

Input format:
The first line contains three integers w, h, α (1 ≤ w, h ≤ 106; 0 ≤ α ≤ 180). Angle α is given in degrees.

Output format:
In a single line print a real number — the area of the region which belongs to both given rectangles.

The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 6.

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

Note:
The second sample has been drawn on the picture above.

Example input:
1 1 45

Example output:
0.828427125

Example input:
6 4 30

Example output:
19.668384925

Editorial:
Maximum Xor Secondary
Contest: Codeforces Round 172 (Div. 1)
Difficulty rating: 1800
Tags: data structures, implementation, two pointers

Bike loves looking for the second maximum element in the sequence. The second maximum element in the sequence of distinct numbers x1, x2, ..., xk (k > 1) is such maximum element xj, that the following inequality holds: $$x_j \neq \max_{i=1}^{k} x_i$$.

The lucky number of the sequence of distinct positive integers x1, x2, ..., xk (k > 1) is the number that is equal to the bitwise excluding OR of the maximum element of the sequence and the second maximum element of the sequence.

You've got a sequence of distinct positive integers s1, s2, ..., sn (n > 1). Let's denote sequence sl, sl + 1, ..., sr as s[l..r] (1 ≤ l < r ≤ n). Your task is to find the maximum number among all lucky numbers of sequences s[l..r].

Note that as all numbers in sequence s are distinct, all the given definitions make sence.

Input format:
The first line contains integer n (1 < n ≤ 105). The second line contains n distinct integers s1, s2, ..., sn (1 ≤ si ≤ 109).

Output format:
Print a single integer — the maximum lucky number among all lucky numbers of sequences s[l..r].

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

Note:
For the first sample you can choose s[4..5] = {4, 3} and its lucky number is (4 xor 3) = 7. You can also choose s[1..2].

For the second sample you must choose s[2..5] = {8, 3, 5, 7}.

Example input:
5
5 2 1 4 3

Example output:
7

Example input:
5
9 8 3 5 7

Example output:
15

Editorial:
Game on Tree
Contest: Codeforces Round 172 (Div. 1)
Difficulty rating: 2200
Tags: implementation, math, probabilities, trees

Momiji has got a rooted tree, consisting of n nodes. The tree nodes are numbered by integers from 1 to n. The root has number 1. Momiji decided to play a game on this tree.

The game consists of several steps. On each step, Momiji chooses one of the remaining tree nodes (let's denote it by v) and removes all the subtree nodes with the root in node v from the tree. Node v gets deleted as well. The game finishes when the tree has no nodes left. In other words, the game finishes after the step that chooses the node number 1.

Each time Momiji chooses a new node uniformly among all the remaining nodes. Your task is to find the expectation of the number of steps in the described game.

Input format:
The first line contains integer n (1 ≤ n ≤ 105) — the number of nodes in the tree. The next n - 1 lines contain the tree edges. The i-th line contains integers ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — the numbers of the nodes that are connected by the i-th edge.

It is guaranteed that the given graph is a tree.

Output format:
Print a single real number — the expectation of the number of steps in the described game.

The answer will be considered correct if the absolute or relative error doesn't exceed 10 - 6.

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

Note:
In the first sample, there are two cases. One is directly remove the root and another is remove the root after one step. Thus the expected steps are:

1 × (1 / 2) + 2 × (1 / 2) = 1.5

In the second sample, things get more complex. There are two cases that reduce to the first sample, and one case cleaned at once. Thus the expected steps are:

1 × (1 / 3) + (1 + 1.5) × (2 / 3) = (1 / 3) + (5 / 3) = 2

Example input:
2
1 2

Example output:
1.50000000000000000000

Example input:
3
1 2
1 3

Example output:
2.00000000000000000000

Editorial:
k-Maximum Subsequence Sum
Contest: Codeforces Round 172 (Div. 1)
Difficulty rating: 2800
Tags: data structures, flows, graphs, implementation

Consider integer sequence a1, a2, ..., an. You should run queries of two types:

- The query format is "0 i val". In reply to this query you should make the following assignment: ai = val.
- The query format is "1 l r k". In reply to this query you should print the maximum sum of at most k non-intersecting subsegments of sequence al, al + 1, ..., ar. Formally, you should choose at most k pairs of integers (x1, y1), (x2, y2), ..., (xt, yt) (l ≤ x1 ≤ y1 < x2 ≤ y2 < ... < xt ≤ yt ≤ r; t ≤ k) such that the sum ax1 + ax1 + 1 + ... + ay1 + ax2 + ax2 + 1 + ... + ay2 + ... + axt + axt + 1 + ... + ayt is as large as possible. Note that you should choose at most k subsegments. Particularly, you can choose 0 subsegments. In this case the described sum considered equal to zero.

Input format:
The first line contains integer n (1 ≤ n ≤ 105), showing how many numbers the sequence has. The next line contains n integers a1, a2, ..., an (|ai| ≤ 500).

The third line contains integer m (1 ≤ m ≤ 105) — the number of queries. The next m lines contain the queries in the format, given in the statement.

All changing queries fit into limits: 1 ≤ i ≤ n, |val| ≤ 500.

All queries to count the maximum sum of at most k non-intersecting subsegments fit into limits: 1 ≤ l ≤ r ≤ n, 1 ≤ k ≤ 20. It is guaranteed that the number of the queries to count the maximum sum of at most k non-intersecting subsegments doesn't exceed 10000.

Output format:
For each query to count the maximum sum of at most k non-intersecting subsegments print the reply — the maximum sum. Print the answers to the queries in the order, in which the queries follow in the input.

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

Note:
In the first query of the first example you can select a single pair (1, 9). So the described sum will be 17.

Look at the second query of the first example. How to choose two subsegments? (1, 3) and (7, 9)? Definitely not, the sum we could get from (1, 3) and (7, 9) is 20, against the optimal configuration (1, 7) and (9, 9) with 25.

The answer to the third query is 0, we prefer select nothing if all of the numbers in the given interval are negative.

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

Example output:
17
25
0

Example input:
15
-4 8 -3 -10 10 4 -7 -7 0 -6 3 8 -10 7 2
15
1 3 9 2
1 6 12 1
0 6 5
0 10 -7
1 4 9 1
1 7 9 1
0 10 -3
1 4 10 2
1 3 13 2
1 4 11 2
0 15 -9
0 13 -9
0 11 -10
1 5 14 2
1 6 12 1

Example output:
14
11
15
0
15
26
18
23
8

Editorial:
Sequence Transformation
Contest: Codeforces Round 172 (Div. 1)
Difficulty rating: 3000
Tags: brute force, data structures, dp, implementation, math

You've got a non-decreasing sequence x1, x2, ..., xn (1 ≤ x1 ≤ x2 ≤ ... ≤ xn ≤ q). You've also got two integers a and b (a ≤ b; a·(n - 1) < q).

Your task is to transform sequence x1, x2, ..., xn into some sequence y1, y2, ..., yn (1 ≤ yi ≤ q; a ≤ yi + 1 - yi ≤ b). The transformation price is the following sum: $$\sum_{i=1}^{n}(y_i - x_i)^2$$. Your task is to choose such sequence y that minimizes the described transformation price.

Input format:
The first line contains four integers n, q, a, b (2 ≤ n ≤ 6000; 1 ≤ q, a, b ≤ 109; a·(n - 1) < q; a ≤ b).

The second line contains a non-decreasing integer sequence x1, x2, ..., xn (1 ≤ x1 ≤ x2 ≤ ... ≤ xn ≤ q).

Output format:
In the first line print n real numbers — the sought sequence y1, y2, ..., yn (1 ≤ yi ≤ q; a ≤ yi + 1 - yi ≤ b). In the second line print the minimum transformation price, that is, $$\sum_{i=1}^{n}(y_i - x_i)^2$$.

If there are multiple optimal answers you can print any of them.

The answer will be considered correct if the absolute or relative error doesn't exceed 10 - 6.

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

Example input:
3 6 2 2
1 4 6

Example output:
1.666667 3.666667 5.666667
0.666667

Example input:
10 100000 8714 9344
3378 14705 17588 22672 32405 34309 37446 51327 81228 94982

Example output:
1.000000 8715.000000 17429.000000 26143.000000 34857.000000 43571.000000 52285.000000 61629.000000 70973.000000 80317.000000
797708674.000000

Editorial:
Crystal Ball Sequence
Contest: Surprise Language Round 7
Difficulty rating: 1400
Tags: *special, implementation

Crystal ball sequence on hexagonal lattice is defined as follows: n-th element is the number of lattice points inside a hexagon with (n + 1) points on each side. The formula is Hn = 3·n·(n + 1) + 1. You are given n; calculate n-th element of the sequence.

Input format:
The only line of input contains an integer n (0 ≤ n ≤ 9).

Output format:
Output the n-th element of crystal ball sequence.

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

Example input:
1

Example output:
7

Example input:
3

Example output:
37

Editorial:
Hexakosioihexekontahexaphobia
Contest: Surprise Language Round 7
Difficulty rating: 1800
Tags: *special

This (unpronounceable) word means simply fear of number 666.

You are given a string of digits. Check whether it is scary for a person suffering from this phobia, i.e., whether it contains number 666 as a substring.

Input format:
The input will consist of a single string p. The string contains between 1 and 100 digits ('0'-'9'), inclusive. The string doesn't contain any other characters except digits.

Output format:
Output "YES" if given string contains number 666, and "NO" otherwise (quotes for clarity only).

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

Note:
Note that 666 must be a contiguous substring of p, not a subsequence (see sample 3).

Example input:
123098

Example output:
NO

Example input:
16660

Example output:
YES

Editorial:
Eval
Contest: Surprise Language Round 7
Difficulty rating: 1900
Tags: *special

You are given a simple arithmetic expression of the form a?b, where a and b are integer constants, and ? can be one of the following operations: '+' (addition), '-' (subtraction), '*' (multiplication), '/' (integer division) or '%' (modulo operation).

Output the result of evaluation of this expression.

Input format:
The input is a single line containing an expression a?b. Here a and b are integers between 1 and 999, inclusive; ? is an operation character: '+', '-' (ASCII code 45), '*', '/' or '%'.

Output format:
Output a single integer — the result of evaluation of this expression.

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

Example input:
123+456

Example output:
579

Example input:
192/5

Example output:
38

Editorial:
Caesar Cipher
Contest: Surprise Language Round 7
Difficulty rating: 1900
Tags: *special

Caesar cipher is one of the simplest encryption techniques. To transform the original message into encrypted one using key k, one has to replace each letter with a letter which is k positions later in the alphabet (if this takes the position beyond Z, the rest of it is counted from the start of the alphabet). In a more formal way, if letters of the alphabet are enumerated starting with 0, the result of encryption for character x will be $$(x+k) \mod 26$$ (26 is the number of letters in the Latin alphabet).

You are given the original message and the encryption key k. Output the result of encryption.

Input format:
The first line of input contains an integer k (0 ≤ k ≤ 25) — the encryption key.

The second line contains the original message — a sequence of uppercase Latin letters ('A'-'Z'). The length of the message is from 1 to 10, inclusive.

Output format:
Output the result of encryption.

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

Example input:
5
CODEFORCES

Example output:
HTIJKTWHJX

Example input:
13
FALSERULEZ

Example output:
SNYFREHYRM

Editorial:
Chessboard
Contest: Surprise Language Round 7
Difficulty rating: 1900
Tags: *special

Chessboard is a board of n × n squares arranged in two alternating colors (black and white). Top left square is white. You are given board size n. Output an image of a chessboard, with black and white squares marked with '#' and '.' characters, respectively.

Input format:
The only line of input contains an integer n (1 ≤ n ≤ 9).

Output format:
Output an image of n × n chessboard.

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

Example input:
4

Example output:
.#.#
#.#.
.#.#
#.#.

Editorial:
Pairwise Sums
Contest: Surprise Language Round 7
Difficulty rating: 2300
Tags: *special

You are given an array of n integers. For each element output the sum of itself and the previous element. For the first element, output the sum of the first and the last elements of the array.

Input format:
The input consists of a single line of space-separated integers. The first number is n (2 ≤ n ≤ 50) — the size of the array. The following n numbers are the elements of the array (1 ≤ ai ≤ 1000).

Output format:
Output the sums a1 + an, a2 + a1, ..., an + an - 1, separated with spaces.

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

Example input:
4 1 2 3 4

Example output:
5 3 5 7

Example input:
5 5 46 372 81 9

Example output:
14 51 418 453 90

Editorial:
Hamming Distance
Contest: Surprise Language Round 7
Difficulty rating: 2300
Tags: *special

Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. You are given two strings; calculate the distance between them.

Input format:
The input consists of two lines. Each line contains a string of characters 'A'-'Z' between 1 and 100 characters, inclusive. The strings have equal length.

Output format:
Output Hamming distance between the strings.

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

Example input:
CODECHEF
TOPCODER

Example output:
6

Example input:
HAMMING
DISTANC

Example output:
6

Editorial:
Array Sorting
Contest: Surprise Language Round 7
Difficulty rating: 2300
Tags: *special

Sorting arrays is traditionally associated with high-level languages. How hard can it be in FALSE? Sort the given array in non-descending order.

Input format:
The input consists of a single line of space-separated integers. The first number is n (1 ≤ n ≤ 10) — the size of the array. The following n numbers are the elements of the array (1 ≤ ai ≤ 100).

Output format:
Output space-separated elements of the sorted array.

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

Example input:
3 3 1 2

Example output:
1 2 3

Example input:
7 12 2 3 44 5 60 2

Example output:
2 2 3 5 12 44 60

Editorial: