1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Parity Game
Contest: Codeforces Round 180 (Div. 1)
Difficulty rating: 1700
Tags: constructive algorithms

You are fishing with polar bears Alice and Bob. While waiting for the fish to bite, the polar bears get bored. They come up with a game. First Alice and Bob each writes a 01-string (strings that only contain character "0" and "1") a and b. Then you try to turn a into b using two types of operations:

- Write parity(a) to the end of a. For example, $$1010 \rightarrow 10100$$.
- Remove the first character of a. For example, $$1001 \rightarrow 001$$. You cannot perform this operation if a is empty.

You can use as many operations as you want. The problem is, is it possible to turn a into b?

The parity of a 01-string is 1 if there is an odd number of "1"s in the string, and 0 otherwise.

Input format:
The first line contains the string a and the second line contains the string b (1 ≤ |a|, |b| ≤ 1000). Both strings contain only the characters "0" and "1". Here |x| denotes the length of the string x.

Output format:
Print "YES" (without quotes) if it is possible to turn a into b, and "NO" (without quotes) otherwise.

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

Note:
In the first sample, the steps are as follows: 01011 → 1011 → 011 → 0110

Example input:
01011
0110

Example output:
YES

Example input:
0011
1110

Example output:
NO

Editorial:
Fish Weight
Contest: Codeforces Round 180 (Div. 1)
Difficulty rating: 1600
Tags: constructive algorithms, greedy

It is known that there are k fish species in the polar ocean, numbered from 1 to k. They are sorted by non-decreasing order of their weight, which is a positive number. Let the weight of the i-th type of fish be wi, then 0 < w1 ≤ w2 ≤ ... ≤ wk holds.

Polar bears Alice and Bob each have caught some fish, and they are guessing who has the larger sum of weight of the fish he/she's caught. Given the type of the fish they've caught, determine whether it is possible that the fish caught by Alice has a strictly larger total weight than Bob's. In other words, does there exist a sequence of weights wi (not necessary integers), such that the fish caught by Alice has a strictly larger total weight?

Input format:
The first line contains three integers n, m, k (1 ≤ n, m ≤ 105, 1 ≤ k ≤ 109) — the number of fish caught by Alice and Bob respectively, and the number of fish species.

The second line contains n integers each from 1 to k, the list of fish type caught by Alice. The third line contains m integers each from 1 to k, the list of fish type caught by Bob.

Note that one may have caught more than one fish for a same species.

Output format:
Output "YES" (without quotes) if it is possible, and "NO" (without quotes) otherwise.

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

Note:
In the first sample, if w1 = 1, w2 = 2, w3 = 2.5,  then Alice has a total of 2 + 2 + 2 = 6 weight units, while Bob only has 1 + 1 + 2.5 = 4.5.

In the second sample, the fish that Alice caught is a subset of Bob's. Therefore, the total weight of Bob’s fish is always not less than the total weight of Alice’s fish.

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

Example output:
YES

Example input:
4 7 9
5 2 7 3
3 5 2 7 3 8 7

Example output:
NO

Editorial:
Splitting the Uniqueness
Contest: Codeforces Round 180 (Div. 1)
Difficulty rating: 2400
Tags: constructive algorithms

Polar bears like unique arrays — that is, arrays without repeated elements.

You have got a unique array s with length n containing non-negative integers. Since you are good friends with Alice and Bob, you decide to split the array in two. Precisely, you need to construct two arrays a and b that are also of length n, with the following conditions for all i (1 ≤ i ≤ n):

- ai, bi are non-negative integers;
- si = ai + bi .

Ideally, a and b should also be unique arrays. However, life in the Arctic is hard and this is not always possible. Fortunately, Alice and Bob are still happy if their arrays are almost unique. We define an array of length n to be almost unique, if and only if it can be turned into a unique array by removing no more than $$\left\lceil \frac{n}{3} \right\rceil$$ entries.

For example, the array [1, 2, 1, 3, 2] is almost unique because after removing the first two entries, it becomes [1, 3, 2]. The array [1, 2, 1, 3, 1, 2] is not almost unique because we need to remove at least 3 entries to turn it into a unique array.

So, your task is to split the given unique array s into two almost unique arrays a and b.

Input format:
The first line of the input contains integer n (1 ≤ n ≤ 105).

The second line contains n distinct integers s1, s2, ... sn (0 ≤ si ≤ 109).

Output format:
If it is possible to make Alice and Bob happy (if you can split the given array), print "YES" (without quotes) in the first line. In the second line, print the array a. In the third line, print the array b. There may be more than one solution. Any of them will be accepted.

If it is impossible to split s into almost unique arrays a and b, print "NO" (without quotes) in the first line.

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

Note:
In the sample, we can remove the first two entries from a and the second entry from b to make them both unique.

Example input:
6
12 5 8 3 11 9

Example output:
YES
6 2 6 0 2 4
6 3 2 3 9 5

Editorial:
Color the Carpet
Contest: Codeforces Round 180 (Div. 1)
Difficulty rating: 2500
Tags: constructive algorithms

Even polar bears feel cold when lying on the ice. Therefore, a polar bear Alice is going to make a carpet. The carpet can be viewed as a grid with height h and width w. Then the grid is divided into h × w squares. Alice is going to assign one of k different colors to each square. The colors are numbered from 1 to k. She may choose not to use all of the colors.

However, there are some restrictions. For every two adjacent squares (squares that shares an edge) x and y, there is a color constraint in one of the forms:

- color(x) = color(y), or
- color(x) ≠ color(y).

Example of the color constraints:

Ideally, Alice wants to satisfy all color constraints. But again, life in the Arctic is hard. It is not always possible to satisfy all color constraints. Fortunately, she will still be happy if at least $$\frac{3}{4}$$ of the color constraints are satisfied.

If she has 4 colors she can color the carpet in the following way:

And she is happy because $${ \frac { 1 3 } { 1 7 } }$$ of the color constraints are satisfied, and $$\frac{13}{17} \geq \frac{3}{4}$$. Your task is to help her color the carpet.

Input format:
The first line contains three integers h, w, k (2 ≤ h, w ≤ 1000, 1 ≤ k ≤ w·h).

The next 2h - 1 lines describe the color constraints from top to bottom, left to right. They contain w - 1, w, w - 1, w, ..., w - 1 characters respectively. Each color constraint is represented by a character "E" or "N", where "E" means " = " and "N" means " ≠ ".

The color constraints listed in the order they are depicted on the picture.

Output format:
If there is a coloring that satisfies at least $$\frac{3}{4}$$ of the color constraints, print "YES" (without quotes) in the first line. In each of the next h lines, print w integers describing the coloring.

Otherwise, print "NO" (without quotes).

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

Example input:
3 4 4
ENE
NNEE
NEE
ENEN
ENN

Example output:
YES
1 1 2 2
3 4 1 1
3 3 2 4

Editorial:
Mystic Carvings
Contest: Codeforces Round 180 (Div. 1)
Difficulty rating: 3000
Tags: data structures

The polar bears have discovered a gigantic circular piece of floating ice with some mystic carvings on it. There are n lines carved on the ice. Each line connects two points on the boundary of the ice (we call these points endpoints). The endpoints are numbered 1, 2, ..., 2n counter-clockwise along the circumference. No two lines share an endpoint.

Now a group of 6 polar bears (Alice, Bob, Carol, Dave, Eve, Frank) are going to build caves on the endpoints. Each polar bear would build a cave and live in it. No two polar bears can build a cave on the same endpoints. Alice and Bob is a pair of superstitious lovers. They believe the lines are carved by aliens (or humans, which are pretty much the same thing to polar bears), and have certain spiritual power. Therefore they want to build their caves on two endpoints which are connected by a line. The same for Carol and Dave, Eve and Frank.

The distance between two caves X and Y is defined as one plus minimum number of other caves one need to pass through in order to travel from X to Y along the boundary of the ice (endpoints without caves are not counted).

To ensure fairness, the distances between the three pairs of lovers have to be the same (that is, the distance between Alice and Bob, the distance between Carol and Dave, and the distance between Eve and Frank are the same).

The figures below show two different configurations, where the dots on the circle are the endpoints. The configuration on the left is not valid. Although each pair of lovers (A and B, C and D, E and F) is connected a line, the distance requirement is not satisfied. The distance between A and B is 2 (one can go from A to B in the clockwise direction passing through F). The distance between E and F is also 2. However, the distance between C and D is 1 (one can go from C to D in the counter-clockwise direction without passing through any other caves). The configuration on the right is valid. All three pairs have the same distance 1.

Count the number of ways to build the caves under the requirements. Two configurations are considered the same if the same set of 6 endpoints are used.

Input format:
The first line contains integer n(3 ≤ n ≤ 105) — the number of lines.

Each of the following n lines contains two integers ai, bi (1 ≤ ai, bi ≤ 2n), which means that there is a line carved on the ice connecting the ai–th and bi–th endpoint.

It's guaranteed that each endpoints touches exactly one line.

Output format:
Print the number of ways to build the caves.

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:
The second sample corresponds to the figure in the problem statement.

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

Example output:
2

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

Example output:
6

Editorial:
Make A Equal to B
Contest: Codeforces Round 825 (Div. 2)
Difficulty rating: 800
Tags: brute force, greedy, sortings

You are given two arrays $$$a$$$ and $$$b$$$ of $$$n$$$ elements, each element is either $$$0$$$ or $$$1$$$.

You can make operations of $$$2$$$ kinds.

- Pick an index $$$i$$$ and change $$$a_i$$$ to $$$1-a_i$$$.
- Rearrange the array $$$a$$$ however you want.

Find the minimum number of operations required to make $$$a$$$ equal to $$$b$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the length of the arrays $$$a$$$ and $$$b$$$.

The second line of each test case contains $$$n$$$ space-separated integers $$$a_1,a_2,\ldots,a_n$$$ ($$$a_i$$$ is $$$0$$$ or $$$1$$$), representing the array $$$a$$$.

The third line of each test case contains $$$n$$$ space-separated integers $$$b_1,b_2,\ldots,b_n$$$ ($$$b_i$$$ is $$$0$$$ or $$$1$$$), representing the array $$$b$$$.

Output format:
For each test case, print the minimum number of operations required to make $$$a$$$ equal to $$$b$$$.

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

Note:
In the first case, we need only one operation: change $$$a_1$$$ to $$$1-a_i$$$. Now $$$a = [0, 0]$$$ which is equal to $$$b$$$.

In the second case, the optimal way is to rearrange $$$a$$$ to get the array $$$[0, 1, 11$$$. Now $$$a = [0, 0, 1]$$$ which is equal to $$$b$$$.

In the second case, one of optimal ways would be to first change $$$a_3$$$ to $$$1 - a_3$$$, then rearrange $$$a$$$.

In the third case, no operation is needed.

In the fourth case, the optimal way is to rearrange $$$a$$$ to get the array $$$[0, 1, 1, 0]$$$.

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

Example output:
1
2
0
1
1

Editorial:
It is easy to observe that the second operation needs to be performed at most once. Now, we just need to check $$$2$$$ cases, one in which the re-arrangement operation is used, and one in which it is not.
If the re-arrangement operation is to be used, then we just need to make the counts of $$$0$$$s and $$$1$$$s in $$$a$$$ equal to that of $$$b$$$. Without loss of generality assume $$$a$$$ contains $$$x$$$ more $$$0$$$s than $$$b$$$, then the cost in this case will just be $$$x + 1$$$ (extra one for re-arrangement cost).
If the re-arrangement operation is not to be used, then we just need to make each element of $$$a$$$ equal to the corresponding element of $$$b$$$.
Finally, our answer is the smaller cost of these $$$2$$$ cases.
Playing with GCD
Contest: Codeforces Round 825 (Div. 2)
Difficulty rating: 1200
Tags: math, number theory

You are given an integer array $$$a$$$ of length $$$n$$$.

Does there exist an array $$$b$$$ consisting of $$$n+1$$$ positive integers such that $$$a_i=\gcd (b_i,b_{i+1})$$$ for all $$$i$$$ ($$$1 \leq i \leq n$$$)?

Note that $$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^5$$$). Description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ space-separated integers $$$a_1,a_2,\ldots,a_n$$$ representing the array $$$a$$$ ($$$1 \leq a_i \leq 10^4$$$).

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

Output format:
For each test case, output "YES" if such $$$b$$$ exists, otherwise output "NO". You can print each letter in any case (upper or lower).

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

Note:
In the first test case, we can take $$$b=[343,343]$$$.

In the second test case, one possibility for $$$b$$$ is $$$b=[12,8,6]$$$.

In the third test case, it can be proved that there does not exist any array $$$b$$$ that fulfills all the conditions.

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

Example output:
YES
YES
NO
YES

Editorial:
Take $$$a_0 = a_{n+1} = 1$$$.
Now take $$$b_i=lcm(a_{i-1},a_i)$$$ for $$$1 \leq i \leq n+1$$$. If $$$b$$$ gives us $$$a$$$ after performing the $$$\gcd$$$ operations, then the answer is YES, otherwise the answer is NO. (When answer is NO, we would get a case like $$$\gcd(b_i, b_{i + 1}) = k \cdot a_i$$$(where $$$k > 1$$$ for some $$$i$$$).
Suppose $$$c$$$ is some valid array which gives us $$$a$$$. So, $$$c_i$$$ should be divisible by $$$b_i$$$. This means $$$\gcd(c_i, c_{i+1}) \geq \gcd(b_i, b_{i + 1})$$$.
So, if $$$\gcd(b_i, b_{i + 1}) > a_i$$$ for any $$$i$$$, we should also have $$$\gcd(c_i, c_{i+1}) > a_i$$$. This implies that $$$c$$$ is not valid if $$$b$$$ is not valid.
Good Subarrays (Easy Version)
Contest: Codeforces Round 825 (Div. 2)
Difficulty rating: 1300
Tags: binary search, data structures, schedules, two pointers

This is the easy version of this problem. In this version, we do not have queries. Note that we have multiple test cases in this version. You can make hacks only if both versions of the problem are solved.

An array $$$b$$$ of length $$$m$$$ is good if for all $$$i$$$ the $$$i$$$-th element is greater than or equal to $$$i$$$. In other words, $$$b$$$ is good if and only if $$$b_i \geq i$$$ for all $$$i$$$ ($$$1 \leq i \leq m$$$).

You are given an array $$$a$$$ consisting of $$$n$$$ positive integers. Find the number of pairs of indices $$$(l, r)$$$, where $$$1 \le l \le r \le n$$$, such that the array $$$[a_l, a_{l+1}, \ldots, a_r]$$$ is good.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$). Description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$), the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ space-separated integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$), representing the array $$$a$$$.

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 the number of suitable pairs of indices.

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

Note:
In the first test case, all subarrays of $$$a$$$ are good, so all pairs are suitable.

In the second test case, the pairs $$$(1, 1)$$$, $$$(2, 2)$$$, and $$$(3, 3)$$$ are suitable. For example, when $$$(l, r) = (1, 2)$$$, the array $$$b=[1,1]$$$ is not good because $$$b_2 < 2$$$.

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

Example output:
6
3
7

Editorial:
Suppose $$$l[i]$$$ represents the leftmost point such that subarray $$$a[l[i],i]$$$ is good.
Notice that the array $$$l$$$ is non-decreasing.
So suppose $$$dp[i]$$$ denotes the length of longest subarray which ends at index $$$i$$$.
Take $$$dp[0]=0$$$.
Now $$$dp[i]=min(dp[i-1]+1,a[i])$$$.
Suppose $$$a[i] \geq dp[i-1]+1$$$. Now we claim that $$$dp[i]=dp[i-1]+1$$$. We know $$$a[i-dp[i-1],i-1]$$$ is good. Now if we look at array $$$b=a[i-dp[i-1],i]$$$, $$$b_i \geq i $$$ for $$$ 1 \leq i \leq dp[i-1]$$$. For $$$b$$$ to be good, last element of $$$b$$$(which is $$$a[i]$$$) should be greater than or equal $$$dp[i-1]+1$$$(which is consistent with our supposition). So $$$b$$$ is good.
We can similarly cover the case when $$$a[i] < dp[i-1]+1$$$.
So our answer is $$$ \sum_{i=1}^{n} dp[i]$$$.
Swap and Take
Contest: Codeforces Round 825 (Div. 2)
Difficulty rating: 2600
Tags: dp, greedy

You're given an array consisting of $$$n$$$ integers. You have to perform $$$n$$$ turns.

Initially your score is $$$0$$$.

On the $$$i$$$-th turn, you are allowed to leave the array as it is or swap any one pair of $$$2$$$ adjacent elements in the array and change exactly one of them to $$$0$$$(and leave the value of other element unchanged) after swapping. In either case(whether you swap or not), after this you add $$$a_i$$$ to your score.

What's the maximum possible score you can get?

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 500$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

Output format:
Print a single integer — the maximum possible score.

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

Note:
In the first example, to get the maximum score we do as follows. Do nothing on the first turn, add $$$3$$$ to the score. Swap the first and the second elements and turn $$$1$$$ to $$$0$$$ on the second turn, and add $$$3$$$ to the score. The final score is $$$6$$$.

Example input:
2
3 1

Example output:
6

Example input:
5
7 3 9 6 12

Example output:
52

Editorial:
Tutorial will be available later.
Minimal String Xoration
Contest: Технокубок 2022 - Финал
Difficulty rating: 2800
Tags: bitmasks, data structures, strings

You are given an integer $$$n$$$ and a string $$$s$$$ consisting of $$$2^n$$$ lowercase letters of the English alphabet. The characters of the string $$$s$$$ are $$$s_0s_1s_2\cdots s_{2^n-1}$$$.

A string $$$t$$$ of length $$$2^n$$$ (whose characters are denoted by $$$t_0t_1t_2\cdots t_{2^n-1}$$$) is a xoration of $$$s$$$ if there exists an integer $$$j$$$ ($$$0\le j \leq 2^n-1$$$) such that, for each $$$0 \leq i \leq 2^n-1$$$, $$$t_i = s_{i \oplus j}$$$ (where $$$\oplus$$$ denotes the operation bitwise XOR).

Find the lexicographically minimal xoration of $$$s$$$.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 18$$$).

The second line contains a string $$$s$$$ consisting of $$$2^n$$$ lowercase letters of the English alphabet.

Output format:
Print a single line containing the lexicographically minimal xoration of $$$s$$$.

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

Note:
In the first test, the lexicographically minimal xoration $$$t$$$ of $$$s =$$$"acba" is "abca". It's a xoration because, for $$$j = 3$$$,

- $$$t_0 = s_{0 \oplus j} = s_3 =$$$ "a";
- $$$t_1 = s_{1 \oplus j} = s_2 =$$$ "b";
- $$$t_2 = s_{2 \oplus j} = s_1 =$$$ "c";
- $$$t_3 = s_{3 \oplus j} = s_0 =$$$ "a".

In the second test, the minimal string xoration corresponds to choosing $$$j = 4$$$ in the definition of xoration.

In the third test, the minimal string xoration corresponds to choosing $$$j = 11$$$ in the definition of xoration.

In the fourth test, the minimal string xoration corresponds to choosing $$$j = 10$$$ in the definition of xoration.

In the fifth test, the minimal string xoration corresponds to choosing either $$$j = 0$$$ or $$$j = 1$$$ in the definition of xoration.

Example input:
2
acba

Example output:
abca

Example input:
3
bcbaaabb

Example output:
aabbbcba

Editorial:
Let f(s,x) be the string t such that ti=si⊕x
.
The solution is inspired by the standard method to construct a suffix array. Let ak be an array of integers x such that 0≤x<2n, sorted according to the lexicographic ordering of the first 2k characters of f(s,x). We can construct ak using ak−1, and a0
is easy to construct as a base case.
In order to construct ak from ak−1, we will first construct an auxiliary array of integers v using ak−1, where vi<vj iff f(s,i)0..2k−1<f(s,j)0..2k−1. Then, we will sort the array ak according to the comparison of tuples (vi,vi⊕k)<(vj,vj⊕k)
.
Once we have an , then we just print f(s,an,0). In total, the solution takes O(2nn2) time, which can be optimized to O(2nn) using the fact that tuples of integers in the range [0,m] can be sorted using radix sort in O(m) time. This optimization was not required to get AC.