1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Brain's Photos
Contest: Codeforces Round 368 (Div. 2)
Difficulty rating: 800
Tags: implementation

Small, but very brave, mouse Brain was not accepted to summer school of young villains. He was upset and decided to postpone his plans of taking over the world, but to become a photographer instead.

As you may know, the coolest photos are on the film (because you can specify the hashtag #film for such).

Brain took a lot of colourful pictures on colored and black-and-white film. Then he developed and translated it into a digital form. But now, color and black-and-white photos are in one folder, and to sort them, one needs to spend more than one hour!

As soon as Brain is a photographer not programmer now, he asks you to help him determine for a single photo whether it is colored or black-and-white.

Photo can be represented as a matrix sized n × m, and each element of the matrix stores a symbol indicating corresponding pixel color. There are only 6 colors:

- 'C' (cyan)
- 'M' (magenta)
- 'Y' (yellow)
- 'W' (white)
- 'G' (grey)
- 'B' (black)

The photo is considered black-and-white if it has only white, black and grey pixels in it. If there are any of cyan, magenta or yellow pixels in the photo then it is considered colored.

Input format:
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 100) — the number of photo pixel matrix rows and columns respectively.

Then n lines describing matrix rows follow. Each of them contains m space-separated characters describing colors of pixels in a row. Each character in the line is one of the 'C', 'M', 'Y', 'W', 'G' or 'B'.

Output format:
Print the "#Black&White" (without quotes), if the photo is black-and-white and "#Color" (without quotes), if it is colored, in the only line.

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

Example input:
2 2
C M
Y Y

Example output:
#Color

Example input:
3 2
W W
W W
B B

Example output:
#Black&White

Editorial:
Bakery
Contest: Codeforces Round 368 (Div. 2)
Difficulty rating: 1300
Tags: graphs

Masha wants to open her own bakery and bake muffins in one of the n cities numbered from 1 to n. There are m bidirectional roads, each of whose connects some pair of cities.

To bake muffins in her bakery, Masha needs to establish flour supply from some storage. There are only k storages, located in different cities numbered a1, a2, ..., ak.

Unforunately the law of the country Masha lives in prohibits opening bakery in any of the cities which has storage located in it. She can open it only in one of another n - k cities, and, of course, flour delivery should be paid — for every kilometer of path between storage and bakery Masha should pay 1 ruble.

Formally, Masha will pay x roubles, if she will open the bakery in some city b (ai ≠ b for every 1 ≤ i ≤ k) and choose a storage in some city s (s = aj for some 1 ≤ j ≤ k) and b and s are connected by some path of roads of summary length x (if there are more than one path, Masha is able to choose which of them should be used).

Masha is very thrifty and rational. She is interested in a city, where she can open her bakery (and choose one of k storages and one of the paths between city with bakery and city with storage) and pay minimum possible amount of rubles for flour delivery. Please help Masha find this amount.

Input format:
The first line of the input contains three integers n, m and k (1 ≤ n, m ≤ 105, 0 ≤ k ≤ n) — the number of cities in country Masha lives in, the number of roads between them and the number of flour storages respectively.

Then m lines follow. Each of them contains three integers u, v and l (1 ≤ u, v ≤ n, 1 ≤ l ≤ 109, u ≠ v) meaning that there is a road between cities u and v of length of l kilometers .

If k > 0, then the last line of the input contains k distinct integers a1, a2, ..., ak (1 ≤ ai ≤ n) — the number of cities having flour storage located in. If k = 0 then this line is not presented in the input.

Output format:
Print the minimum possible amount of rubles Masha should pay for flour delivery in the only line.

If the bakery can not be opened (while satisfying conditions) in any of the n cities, print  - 1 in the only line.

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

Note:
Image illustrates the first sample case. Cities with storage located in and the road representing the answer are darkened.

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

Example output:
3

Example input:
3 1 1
1 2 3
3

Example output:
-1

Editorial:
Pythagorean Triples
Contest: Codeforces Round 368 (Div. 2)
Difficulty rating: 1500
Tags: math, number theory

Katya studies in a fifth grade. Recently her class studied right triangles and the Pythagorean theorem. It appeared, that there are triples of positive integers such that you can construct a right triangle with segments of lengths corresponding to triple. Such triples are called Pythagorean triples.

For example, triples (3, 4, 5), (5, 12, 13) and (6, 8, 10) are Pythagorean triples.

Here Katya wondered if she can specify the length of some side of right triangle and find any Pythagorean triple corresponding to such length? Note that the side which length is specified can be a cathetus as well as hypotenuse.

Katya had no problems with completing this task. Will you do the same?

Input format:
The only line of the input contains single integer n (1 ≤ n ≤ 109) — the length of some side of a right triangle.

Output format:
Print two integers m and k (1 ≤ m, k ≤ 1018), such that n, m and k form a Pythagorean triple, in the only line.

In case if there is no any Pythagorean triple containing integer n, print  - 1 in the only line. If there are many answers, print any of them.

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

Note:
Illustration for the first sample.

Example input:
3

Example output:
4 5

Example input:
6

Example output:
8 10

Editorial:
Persistent Bookcase
Contest: Codeforces Round 368 (Div. 2)
Difficulty rating: 2200
Tags: bitmasks, data structures, dfs and similar, implementation

Recently in school Alina has learned what are the persistent data structures: they are data structures that always preserves the previous version of itself and access to it when it is modified.

After reaching home Alina decided to invent her own persistent data structure. Inventing didn't take long: there is a bookcase right behind her bed. Alina thinks that the bookcase is a good choice for a persistent data structure. Initially the bookcase is empty, thus there is no book at any position at any shelf.

The bookcase consists of n shelves, and each shelf has exactly m positions for books at it. Alina enumerates shelves by integers from 1 to n and positions at shelves — from 1 to m. Initially the bookcase is empty, thus there is no book at any position at any shelf in it.

Alina wrote down q operations, which will be consecutively applied to the bookcase. Each of the operations has one of four types:

- 1 i j — Place a book at position j at shelf i if there is no book at it.
- 2 i j — Remove the book from position j at shelf i if there is a book at it.
- 3 i — Invert book placing at shelf i. This means that from every position at shelf i which has a book at it, the book should be removed, and at every position at shelf i which has not book at it, a book should be placed.
- 4 k — Return the books in the bookcase in a state they were after applying k-th operation. In particular, k = 0 means that the bookcase should be in initial state, thus every book in the bookcase should be removed from its position.

After applying each of operation Alina is interested in the number of books in the bookcase. Alina got 'A' in the school and had no problem finding this values. Will you do so?

Input format:
The first line of the input contains three integers n, m and q (1 ≤ n, m ≤ 103, 1 ≤ q ≤ 105) — the bookcase dimensions and the number of operations respectively.

The next q lines describes operations in chronological order — i-th of them describes i-th operation in one of the four formats described in the statement.

It is guaranteed that shelf indices and position indices are correct, and in each of fourth-type operation the number k corresponds to some operation before it or equals to 0.

Output format:
For each operation, print the number of books in the bookcase after applying it in a separate line. The answers should be printed in chronological order.

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

Note:
This image illustrates the second sample case.

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

Example output:
1
4
0

Example input:
4 2 6
3 2
2 2 2
3 3
3 2
2 2 2
3 2

Example output:
2
1
3
3
2
4

Editorial:
Weakened Common Divisor
Contest: Codeforces Round 505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)
Difficulty rating: 1600
Tags: brute force, greedy, number theory

During the research on properties of the greatest common divisor (GCD) of a set of numbers, Ildar, a famous mathematician, introduced a brand new concept of the weakened common divisor (WCD) of a list of pairs of integers.

For a given list of pairs of integers $$$(a_1, b_1)$$$, $$$(a_2, b_2)$$$, ..., $$$(a_n, b_n)$$$ their WCD is arbitrary integer greater than $$$1$$$, such that it divides at least one element in each pair. WCD may not exist for some lists.

For example, if the list looks like $$$[(12, 15), (25, 18), (10, 24)]$$$, then their WCD can be equal to $$$2$$$, $$$3$$$, $$$5$$$ or $$$6$$$ (each of these numbers is strictly greater than $$$1$$$ and divides at least one number in each pair).

You're currently pursuing your PhD degree under Ildar's mentorship, and that's why this problem was delegated to you. Your task is to calculate WCD efficiently.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 150\,000$$$) — the number of pairs.

Each of the next $$$n$$$ lines contains two integer values $$$a_i$$$, $$$b_i$$$ ($$$2 \le a_i, b_i \le 2 \cdot 10^9$$$).

Output format:
Print a single integer — the WCD of the set of pairs.

If there are multiple possible answers, output any; if there is no answer, print $$$-1$$$.

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

Note:
In the first example the answer is $$$6$$$ since it divides $$$18$$$ from the first pair, $$$24$$$ from the second and $$$12$$$ from the third ones. Note that other valid answers will also be accepted.

In the second example there are no integers greater than $$$1$$$ satisfying the conditions.

In the third example one of the possible answers is $$$5$$$. Note that, for example, $$$15$$$ is also allowed, but it's not necessary to maximize the output.

Example input:
3
17 18
15 24
12 15

Example output:
6

Example input:
2
10 16
7 17

Example output:
-1

Editorial:
The obvious solution of finding all divisors of all numbers in $$$\mathcal{O}(n \cdot \sqrt{a_{max}})$$$ definitely won't pass, so we have to come up with a slight optimization.
One may notice that is's sufficient to take a prime WCD (because if some value is an answer, it can be factorized without losing the answer property). To decrease the number of primes to check, let's get rid of the redundant ones.
Take an arbitrary pair of elements ($$$a_i$$$, $$$b_i$$$) and take the union of their prime factorizations. It's easy to see at this point that the cardinality of this union doesn't exceed $$$2 \cdot \log{a_{max}}$$$. The rest is to check whether there exists such prime that divides at least one element in each pair in $$$\mathcal{O}(n \cdot \log{a_{max}})$$$ time.
Plasticine zebra
Contest: Codeforces Round 505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)
Difficulty rating: 1600
Tags: constructive algorithms, implementation

Is there anything better than going to the zoo after a tiresome week at work? No wonder Grisha feels the same while spending the entire weekend accompanied by pretty striped zebras.

Inspired by this adventure and an accidentally found plasticine pack (represented as a sequence of black and white stripes), Grisha now wants to select several consequent (contiguous) pieces of alternating colors to create a zebra. Let's call the number of selected pieces the length of the zebra.

Before assembling the zebra Grisha can make the following operation $$$0$$$ or more times. He splits the sequence in some place into two parts, then reverses each of them and sticks them together again. For example, if Grisha has pieces in the order "bwbbw" (here 'b' denotes a black strip, and 'w' denotes a white strip), then he can split the sequence as bw|bbw (here the vertical bar represents the cut), reverse both parts and obtain "wbwbb".

Determine the maximum possible length of the zebra that Grisha can produce.

Input format:
The only line contains a string $$$s$$$ ($$$1 \le |s| \le 10^5$$$, where $$$|s|$$$ denotes the length of the string $$$s$$$) comprised of lowercase English letters 'b' and 'w' only, where 'w' denotes a white piece and 'b' denotes a black piece.

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

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

Note:
In the first example one of the possible sequence of operations is bwwwbww|bw $$$\to$$$ w|wbwwwbwb $$$\to$$$ wbwbwwwbw, that gives the answer equal to $$$5$$$.

In the second example no operation can increase the answer.

Example input:
bwwwbwwbw

Example output:
5

Example input:
bwwbwwb

Example output:
3

Editorial:
Imagine just for a second, that in reality our string is cyclic with a cut at point $$$0$$$ and clockwise traversal direction.
Now let's apply the cut & reverse operation at point $$$i$$$. The key fact here is that nothing happens to the cyclic string — it's just the traversal direction and the cut point (now $$$i$$$ instead of $$$0$$$) that change.
Here's an example. Let the string be $$$bwwbwbbw$$$ and we cut it after the $$$2$$$-nd letter ($$$1$$$-indexed). It's easy to see that it transforms to $$$wbwbbwbw$$$, which equals the initial one after shifting it to the left by $$$2$$$ and inverting the traversal direction.
This observation helps us see that all strings obtained within these operations are in fact just cuts of one cyclic strings with precision up to traversal direction. In other words, it's enough to find the longest zebra inside the cyclic string — this value will be the answer to the problem.
Recovering BST
Contest: Codeforces Round 505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)
Difficulty rating: 2100
Tags: brute force, dp, math, number theory, trees

Dima the hamster enjoys nibbling different things: cages, sticks, bad problemsetters and even trees!

Recently he found a binary search tree and instinctively nibbled all of its edges, hence messing up the vertices. Dima knows that if Andrew, who has been thoroughly assembling the tree for a long time, comes home and sees his creation demolished, he'll get extremely upset.

To not let that happen, Dima has to recover the binary search tree. Luckily, he noticed that any two vertices connected by a direct edge had their greatest common divisor value exceed $$$1$$$.

Help Dima construct such a binary search tree or determine that it's impossible. The definition and properties of a binary search tree can be found here.

Input format:
The first line contains the number of vertices $$$n$$$ ($$$2 \le n \le 700$$$).

The second line features $$$n$$$ distinct integers $$$a_i$$$ ($$$2 \le a_i \le 10^9$$$) — the values of vertices in ascending order.

Output format:
If it is possible to reassemble the binary search tree, such that the greatest common divisor of any two vertices connected by the edge is greater than $$$1$$$, print "Yes" (quotes for clarity).

Otherwise, print "No" (quotes for clarity).

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

Note:
The picture below illustrates one of the possible trees for the first example.

The picture below illustrates one of the possible trees for the third example.

Example input:
6
3 6 9 18 36 108

Example output:
Yes

Example input:
2
7 17

Example output:
No

Editorial:
Let $$$\mathcal{dp}(l, r, root)$$$ be a dp determining whether it's possible to assemble a tree rooted at $$$root$$$ from the subsegment $$$[l..r]$$$.
It's easy to see that calculating it requires extracting such $$$root_{left}$$$ from $$$[l..root - 1]$$$ and $$$root_{right}$$$ from $$$[root + 1..right]$$$ that:
• $$$\mathcal{gcd}(a_{root}, a_{root_{left}}) > 1$$$;
• $$$\mathcal{gcd}(a_{root}, a_{root_{right}}) > 1$$$;
• $$$\mathcal{dp}(l, root - 1, root_{left}) = 1$$$;
• $$$\mathcal{dp}(root + 1, r, root_{right}) = 1$$$.
This can be done in $$$\mathcal{O}(r - l)$$$ provided we are given all $$$\mathcal{dp}(x, y, z)$$$ values for all subsegments of $$$[l..r]$$$. Considering a total of $$$\mathcal{O}(n^3)$$$ dp states, the final complexity is $$$\mathcal{O}(n^4)$$$. That's too much.
Let's turn our dp into $$$\mathcal{dp_{new}}(l, r, side)$$$ where $$$side$$$ can be either $$$0$$$ or $$$1$$$ — is it possible to make a tree from $$$[l..r]$$$ rooted at $$$l - 1$$$ or $$$r + 1$$$ respectively. It immediately turns out that $$$\mathcal{dp}(l, r, root)$$$ is inherited form $$$\mathcal{dp_{new}}(l, root - 1, 1)$$$ and $$$\mathcal{dp_{new}}(root + 1, r, 0)$$$. Now we have $$$\mathcal{O}(n^2)$$$ states, but at the same time all transitions are performed in linear time; thus final complexity is $$$\mathcal{O}(n^3)$$$ which is sufficient to pass.
LCM Problem
Contest: Educational Codeforces Round 92 (Rated for Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, greedy, math, number theory

Let $$$LCM(x, y)$$$ be the minimum positive integer that is divisible by both $$$x$$$ and $$$y$$$. For example, $$$LCM(13, 37) = 481$$$, $$$LCM(9, 6) = 18$$$.

You are given two integers $$$l$$$ and $$$r$$$. Find two integers $$$x$$$ and $$$y$$$ such that $$$l \le x < y \le r$$$ and $$$l \le LCM(x, y) \le r$$$.

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

Each test case is represented by one line containing two integers $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le 10^9$$$).

Output format:
For each test case, print two integers:

- if it is impossible to find integers $$$x$$$ and $$$y$$$ meeting the constraints in the statement, print two integers equal to $$$-1$$$;
- otherwise, print the values of $$$x$$$ and $$$y$$$ (if there are multiple valid answers, you may print any of them).

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

Example input:
4
1 1337
13 69
2 4
88 89

Example output:
6 7
14 21
2 4
-1 -1

Editorial:
Suppose we have chosen $$$x$$$ and $$$y$$$ as the answer, and $$$x$$$ is not a divisor of $$$y$$$. Since $$$LCM(x, y)$$$ belongs to $$$[l, r]$$$, we could have chosen $$$x$$$ and $$$LCM(x, y)$$$ instead. So if the answer exists, there also exists an answer where $$$x$$$ is a divisor of $$$y$$$.
If $$$2l > r$$$, then there is no pair $$$(x, y)$$$ such that $$$l \le x < y \le r$$$ and $$$x|y$$$. Otherwise, $$$x = l$$$ and $$$y = 2l$$$ is the answer.
Good String
Contest: Educational Codeforces Round 92 (Rated for Div. 2)
Difficulty rating: 1500
Tags: brute force, dp, greedy, two pointers

Let's call left cyclic shift of some string $$$t_1 t_2 t_3 \dots t_{n - 1} t_n$$$ as string $$$t_2 t_3 \dots t_{n - 1} t_n t_1$$$.

Analogically, let's call right cyclic shift of string $$$t$$$ as string $$$t_n t_1 t_2 t_3 \dots t_{n - 1}$$$.

Let's say string $$$t$$$ is good if its left cyclic shift is equal to its right cyclic shift.

You are given string $$$s$$$ which consists of digits 0–9.

What is the minimum number of characters you need to erase from $$$s$$$ to make it good?

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

Next $$$t$$$ lines contains test cases — one per line. The first and only line of each test case contains string $$$s$$$ ($$$2 \le |s| \le 2 \cdot 10^5$$$). Each character $$$s_i$$$ is digit 0–9.

It's guaranteed that the total length of strings doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print the minimum number of characters you need to erase from $$$s$$$ to make it good.

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

Note:
In the first test case, you can erase any $$$3$$$ characters, for example, the $$$1$$$-st, the $$$3$$$-rd, and the $$$4$$$-th. You'll get string 51 and it is good.

In the second test case, we can erase all characters except 0: the remaining string is 0000 and it's good.

In the third test case, the given string $$$s$$$ is already good.

Example input:
3
95831
100120013
252525252525

Example output:
3
5
0

Editorial:
Let's analyze when the string is good. Suppose it is $$$t_1t_2 \dots t_k$$$.
The cyclic shifts of this string are $$$t_kt_1t_2 \dots t_{k-1}$$$ and $$$t_2t_3 \dots t_k t_1$$$. We get the following constraints for a good string: $$$t_k = t_2$$$, $$$t_1 = t_3$$$, $$$t_2 = t_4$$$, ..., $$$t_{k - 2} = t_k$$$, $$$t_{k - 1} = t_1$$$. If the string has odd length, then all characters should be equal to each other; otherwise, all characters on odd positions should be equal, and all characters on even positions should be equal.
Now, since there are only $$$10$$$ different types of characters, we can brute force all possible combinations of the first and the second character of the string we want to obtain (there are only $$$100$$$ of them) and, for each combination, greedily construct the longest possible subsequence of $$$s$$$ beginning with those characters in $$$O(n)$$$.
Calendar Ambiguity
Contest: Educational Codeforces Round 92 (Rated for Div. 2)
Difficulty rating: 2200
Tags: math, number theory

Berland year consists of $$$m$$$ months with $$$d$$$ days each. Months are numbered from $$$1$$$ to $$$m$$$. Berland week consists of $$$w$$$ days. The first day of the year is also the first day of the week. Note that the last week of the year might be shorter than $$$w$$$ days.

A pair $$$(x, y)$$$ such that $$$x < y$$$ is ambiguous if day $$$x$$$ of month $$$y$$$ is the same day of the week as day $$$y$$$ of month $$$x$$$.

Count the number of ambiguous pairs.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of testcases.

Each of the next $$$t$$$ lines contains three integers $$$m$$$, $$$d$$$ and $$$w$$$ ($$$1 \le m, d, w \le 10^9$$$) — the number of months in a year, the number of days in a month and the number of days in a week.

Output format:
Print $$$t$$$ integers — for each testcase output the number of pairs $$$(x, y)$$$ such that $$$x < y$$$ and day $$$x$$$ of month $$$y$$$ is the same day of the week as day $$$y$$$ of month $$$x$$$.

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

Note:
Here are the pairs for the first test case:

Example input:
5
6 7 4
10 7 12
12 30 7
1 1 1
3247834 10298779 625324

Example output:
6
9
5
0
116461800

Editorial:
Let the month, the days in them and the days of the week be numbered $$$0$$$-based.
Translate the $$$x$$$-th day of the $$$y$$$-th month to the index of that day in a year; that would be $$$yd + x$$$. Thus, the corresponding day of the week is $$$(yd + x)~mod~w$$$.
So we can rewrite the condition for a pair as $$$xd + y \equiv yd + x~(mod~w)$$$. That's also $$$(xd + y) - (yd + x) \equiv 0~(mod~w)$$$. Continue with $$$(x - y)(d - 1) \equiv 0~(mod~w)$$$. So $$$(x - y)(d - 1)$$$ should be divisible by $$$w$$$. $$$d - 1$$$ is fixed and some prime divisors of $$$w$$$ might have appeared in it already. If we remove them from $$$w$$$ then $$$(x - y)$$$ should just be divisible by the resulting number. So we can divide $$$w$$$ by $$$gcd(w, d - 1)$$$ and obtain that $$$w'$$$.
Now we should just count the number of pairs $$$(x, y)$$$ such that $$$x - y$$$ is divisible by $$$w'$$$. We know that the difference $$$x - y$$$ should be from $$$1$$$ to $$$min(d, m)$$$. So we can fix the difference and add the number of pairs for that difference. That would be $$$mn - k$$$ for a difference $$$k$$$. Finally, the answer is $$$\sum \limits_{i=1}^{min(d, m) / w'} mn - i \cdot w'$$$. Use the formula for the sum of arithmetic progression to solve that in $$$O(1)$$$.
Overall complexity: $$$O(\log(w + d))$$$ per testcase.