1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
The Road to Berland is Paved With Good Intentions
Contest: Codeforces Round 141 (Div. 2)
Difficulty rating: 1900
Tags: 2-sat, dfs and similar, dsu, graphs

Berland has n cities, some of them are connected by bidirectional roads. For each road we know whether it is asphalted or not.

The King of Berland Valera II wants to asphalt all roads of Berland, for that he gathered a group of workers. Every day Valera chooses exactly one city and orders the crew to asphalt all roads that come from the city. The valiant crew fulfilled the King's order in a day, then workers went home.

Unfortunately, not everything is as great as Valera II would like. The main part of the group were gastarbeiters — illegal immigrants who are enthusiastic but not exactly good at understanding orders in Berlandian. Therefore, having received orders to asphalt the roads coming from some of the city, the group asphalted all non-asphalted roads coming from the city, and vice versa, took the asphalt from the roads that had it.

Upon learning of this progress, Valera II was very upset, but since it was too late to change anything, he asked you to make a program that determines whether you can in some way asphalt Berlandian roads in at most n days. Help the king.

Input format:
The first line contains two space-separated integers n, m $$( 1 \leq n \leq 100 ; \; 1 \leq m \leq \frac { n \cdot ( n - 1 ) } { 2 } )$$ — the number of cities and roads in Berland, correspondingly. Next m lines contain the descriptions of roads in Berland: the i-th line contains three space-separated integers ai, bi, ci (1 ≤ ai, bi ≤ n; ai ≠ bi; 0 ≤ ci ≤ 1). The first two integers (ai, bi) are indexes of the cities that are connected by the i-th road, the third integer (ci) equals 1, if the road was initially asphalted, and 0 otherwise.

Consider the cities in Berland indexed from 1 to n, and the roads indexed from 1 to m. It is guaranteed that between two Berlandian cities there is not more than one road.

Output format:
In the first line print a single integer x (0 ≤ x ≤ n) — the number of days needed to asphalt all roads. In the second line print x space-separated integers — the indexes of the cities to send the workers to. Print the cities in the order, in which Valera send the workers to asphalt roads. If there are multiple solutions, print any of them.

If there's no way to asphalt all roads, print "Impossible" (without the quotes).

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

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

Example output:
4
3 2 1 3

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

Example output:
Impossible

Editorial:
Verify Password
Contest: Educational Codeforces Round 166 (Rated for Div. 2)
Difficulty rating: 800
Tags: implementation, sortings, strings

Monocarp is working on his new site, and the current challenge is to make the users pick strong passwords.

Monocarp decided that strong passwords should satisfy the following conditions:

- password should consist only of lowercase Latin letters and digits;
- there should be no digit that comes after a letter (so, after each letter, there is either another letter or the string ends);
- all digits should be sorted in the non-decreasing order;
- all letters should be sorted in the non-decreasing order.

Note that it's allowed for the password to have only letters or only digits.

Monocarp managed to implement the first condition, but he struggles with the remaining ones. Can you help him to verify the passwords?

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

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 20$$$) — the length of the password.

The second line contains a string, consisting of exactly $$$n$$$ characters. Each character is either a lowercase Latin letter or a digit.

Output format:
For each testcase, print "YES" if the given password is strong and "NO" otherwise.

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

Note:
In the second testcase, the letters are not sorted in the non-decreasing order.

In the fourth testcase, there is a digit that comes after a letter — digit '1' after a letter 'c'.

Example input:
5
4
12ac
5
123wa
9
allllmost
5
ac123
6
011679

Example output:
YES
NO
YES
NO
YES

Editorial:
There's no real idea in the problem, the main difficulty is the implementation.
Many programming languages have functions to check if a character is a digit or if it's a letter. They can be used to check that no digit follows a letter.
How does the order check work? Well, most languages allow you to compare characters with inequality signs (so, we have to check that $$$s_i \le s_{i + 1}$$$ for all corresponding $$$i$$$ — separately for digits and letters). How does that work? Inside the language, every character is assigned a code. That's called an ASCII table. It contains digits, letters and lots of other characters. And the less or equal check uses that table.
If you look at the table carefully, you'll notice that the digits come before the lowercase Latin letters. Digits have codes from 48 to 57 and the lowercase letters have codes from 97 to 122. Thus, you can ignore the check that the digits come before the letters and just make sure that all characters of the string (regardless of their types) and sorted in a non-decreasing order.
For example, you can sort the string and compare the result with the original string. If they are the same, then the answer is "YES". Alternatively, you can use function is_sorted if your language has it.
Overall complexity: $$$O(n)$$$ or $$$O(n \log n)$$$ per testcase.
Was it Rated?
Contest: April Fools Day Contest 2023
Tags: *special, *special, *special, brute force, implementation

Input format:
The only line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 25$$$).

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

Example input:
1

Example output:
YES

Example input:
15

Example output:
NO

Editorial:
The input to the problem represents a Codeforces contest ID. Out of the first $$$25$$$ Codeforces contests, the only unrated ones had IDs $$$15$$$, $$$20$$$, and $$$21$$$.
So we output NO if $$$n \in \{15, 20, 21\}$$$, and YES otherwise.
Digits
Contest: April Fools Day Contest 2023
Tags: *special

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

Each test case contains $$$n$$$ lines. The $$$i$$$-th line contains an integer $$$a_i$$$ ($$$1 \le a_i \le 9$$$).

The sum of $$$n$$$ over all test cases doesn't exceed $$$155$$$.

Output format:
For each test case, print one integer — the answer.

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

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

Example output:
8
7
30

Editorial:
The answer is the product of $$$a_i$$$ in a test case. In other words, it is
$$$$$$\prod_{i=1}^n a_i.$$$$$$
But what is $$$n$$$? In the samples, the value of $$$n$$$ in each test case is either $$$[3, 2, 3]$$$ or $$$[3, 1, 4]$$$. The latter looks familiar – it is the digits of $$$\pi$$$! There are subtle hints about this in the problem, for example the problem name or the fact that Pi is the symbol for product. We may verify that $$$\pi$$$ is the answer by checking that its $$$32$$$ digits sum to $$$155$$$.
The full solution is: In the $$$k$$$-th test case, read $$$n$$$ numbers (where $$$n$$$ is the $$$k$$$-th digit of $$$\pi$$$), then print the product of those $$$n$$$ numbers.
Trivial Conjecture
Contest: April Fools Day Contest 2023
Tags: *special, constructive algorithms, math, number theory

$$$$$$f(n) = \left\{ \begin{array}{ll} \frac{n}{2} & n \equiv 0 \pmod{2}\\ 3n+1 & n \equiv 1 \pmod{2}\\ \end{array} \right.$$$$$$

Find an integer $$$n$$$ so that none of the first $$$k$$$ terms of the sequence $$$n, f(n), f(f(n)), f(f(f(n))), \dots$$$ are equal to $$$1$$$.

Input format:
The only line contains an integer $$$k$$$ ($$$1 \leq k \leq \min(\textbf{[REDACTED]}, 10^{18})$$$).

Output format:
Output a single integer $$$n$$$ such that none of the first $$$k$$$ terms of the sequence $$$n, f(n), f(f(n)), f(f(f(n))), \dots$$$ are equal to $$$1$$$.

Integer $$$n$$$ should have at most $$$10^3$$$ digits.

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

Note:
In the first test, the sequence created with $$$n = 5$$$ looks like $$$5, 16, 8, 4, 2, 1, 4, \dots$$$, and none of the first $$$k=1$$$ terms are equal to $$$1$$$.

In the second test, the sequence created with $$$n = 6$$$ looks like $$$6, 3, 10, 5, 16, 8, 4, \dots$$$, and none of the first $$$k=5$$$ terms are equal to $$$1$$$.

Example input:
1

Example output:
5

Example input:
5

Example output:
6

Editorial:
A comic about the problem
The given function in the statement defines Collatz Conjecture. It is one of the most famous unsolved problems in mathematics. This is why the problem is actually harder to solve if you have a math background.
Basically, the problem asks you to find a number such that it doesn't take less than $$$k$$$ steps to reach $$$1$$$ using the defined function. There are many numbers that take a high amount of steps, but they don't seem to get accepted.
Many people tried to find the value of $$$[REDACTED]$$$ and find a number that takes longer than it. However, doing so is very hard and wastes a lot of time. For people who tried to do so and interested in its value, it is $$$142023$$$ (01/04/2023).
The important thing here is to read the statement very carefully. Collatz Conjecture is defined on positive integers. However, the statement only says "Output a single integer $$$n$$$", which means it's possible to print a negative integer or $$$0$$$. Doing so solves the problem successfully because any integer $$$n \leq 0$$$ never becomes $$$1$$$. We don't know if this is the only solution. It's possible that there is a positive integer that takes longer than $$$142023$$$ steps. If you find a number that takes very long or actually takes longer than $$$142023$$$ steps, please write in the comments.
Not a Geometry Problem
Contest: April Fools Day Contest 2023
Tags: *special, *special, constructive algorithms, geometry, math

Input format:
The only line of input contains three integers $$$x$$$, $$$y$$$, $$$z$$$ ($$$-1000 \le x, y, z \le 1000$$$).

Output format:
Output one real number — the answer.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^6$$$. Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a-b|}{\max(1,|b|)} \le 10^6$$$.

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

Example input:
1 1 1

Example output:
1.7320508075688772

Example input:
1 -2 -2

Example output:
21.727922061357855

Editorial:
The error should be at most $$$10^{+6}$$$, instead of the usual $$$10^{-6}$$$.
This means that you can just output $$$0$$$, since then $$$\frac{|a-b|}{\max(1,|b|)} = \frac{|-b|}{\max(1,|b|)} = \frac{|b|}{\max(1,|b|)} \le 10^6$$$.
Factorization
Contest: April Fools Day Contest 2023
Tags: *special, number theory

What is the largest prime factor of $$$n$$$?

Input format:
The only line contains an integer $$$n$$$ ($$$n = 4167792762229302596005813$$$ or $$$n =$$$ $$$5023266485352224530541666346579718188045725802556947855902702063768930526665237598287495728$$$ $$$2186920039740245544313021979167491414627648054421626450903732301970386214502290904360792618$$$ $$$5591029614599889902115472391135622402044979347133959392884686037208893694733655782993294168$$$ $$$1679738555852317096830120847236770822731988661111203691013036774095229665675217827154840019$$$ $$$9277276899311984129170278649605877582438144407974816241674549565633361834348720814779487433$$$ $$$7933873576016717726298883519261055062303842274145012056670644839715140659887936321934474824$$$ $$$687778512706909988484451300384818197143498259061041$$$).

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

Editorial:
If we factor the first number (using Wolfram|Alpha or some program you code), you can see that it is the product of two primes: $$$991999999999 \times 4201403994187$$$. This first prime is an example of a glitch prime: a prime whose digits are all the same, except one.
The conclusion is that the larger number should also be the product of two primes, one of which is a glitch prime. So you can test all glitch primes using a local program, which shouldn't take more than a few minutes (or you can even submit it directly to Codeforces and it should work).
We won't spoil the factorization here, you should try to figure it out ;)
Colour Vision
Contest: April Fools Day Contest 2023
Tags: *special, implementation

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

Example input:
1
1
R
R

Example output:
YES

Editorial:
The rectangles are in the shape of the Codeforces logo. The only other information that the picture gives us is the fact that they are green, so if we want to get information from this shade of green, we can use hex codes! Extracting the hex code gives us #01722B.
What about Codeforces is related to 01722B? It looks suspiciously similar to a problem code, and indeed, if you go to https://codeforces.com/contest/1722/problem/B, you get the problem Colourblindness, which is clearly related to the title of this problem!
Looking at the sample, then, solution is simple: just solve the problem Colourblindness, and send the code to this problem.
Expected Twist
Contest: April Fools Day Contest 2023
Tags: *special, interactive

This is an interactive problem.

There is an array $$$a_1, a_2, \dots, a_n$$$ of $$$n$$$ integers hidden from you. Your task is to find the smallest element of the array.

To do this, you can ask several queries. In each query, you can pick two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$). In return, you will be given the value of $$$\max(a_l, a_{l+1}, \dots, a_r)$$$. In other words, you will be told the maximum value of the subarray from $$$a_l$$$ to $$$a_r$$$.

Find the minimum of the array. You can ask at most $$$\mathbf{624}$$$ queries.

It is guaranteed that the values $$$a_1, a_2, \dots, a_n$$$ are chosen uniformly at random between $$$0$$$ and $$$2^{32}-1$$$ (inclusive).

Interaction format:
Begin the interaction by reading an integer $$$n$$$ ($$$1 \le n \le 10^4$$$) on a separate line.

To ask a query, print a line in the form $$$\texttt{?}\;\;l\;\;r$$$ ($$$1 \le l \le r \le n$$$). Then you should read a single line containing the answer to your query.

After you have determined the answer, print a line in the form $$$\texttt{!}\;\;x$$$ where $$$x$$$ is the minimum value.

After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see the documentation for other languages.

Answer $$$\texttt{-1}$$$ means that you made an invalid query. Exit immediately after receiving $$$\texttt{-1}$$$ and you will see Wrong answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

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

Example input:
3

1295320727

984617979

1295320727

167316954

Example output:
? 1 3

? 1 1

? 2 2

? 3 3

! 167316954

Editorial:
Doing the web searches in the hint above shows results about the Mersenne Twister (or more specifically, MT19937), which is a random number generator. With additional hint from the problem name, it is reasonable to assume that the array $$$a$$$ is generated by an MT19937 like this:
Searching more on the web shows the following fact: given the first 624 output values of an MT19937, its entire internal state can be recovered, and therefore we can know all its future outputs.
In fact, many top results from DuckDuckGo and Google, when given the keyword "624 random", show how to break the MT19937 generator, and many implementations are available online. We can use this to solve the problem. The full solution is:
1. For $$$i=1,2,\dots,624$$$, query $$$\texttt{?}\ i\ i$$$ to get the value of $$$a_i$$$.
2. Recover the state of the MT19937 used to generate $$$a$$$ using the first 624 values.
3. Generate the remaining values of $$$a$$$ with the recovered generator.
4. Output the minimum value of $$$a$$$ which we now know.
Mountain Climber
Contest: April Fools Day Contest 2023
Tags: *special

Input format:
The first line of input contains $$$t$$$ ($$$1 \leq t \leq 25$$$) — the number of test cases.

The only line of each test case contains a single string $$$s$$$ ($$$1 \leq |s| \leq 100$$$) consisting only of lowercase English letters.

Output format:
For each test case, print YES or NO.

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

Example input:
23
big
flashing
clump
i
underpass
passunder
tranquilizing
pole
andrej
dumpling
bocchiryonijikakitasingingsongs
alperen
toxicpie
ari
bucketpotato
flamestorm
scarlets
maisakurajima
misakamikoto
ninfia
sylveon
pikachu
mewheniseearulhiiarul

Example output:
YES
NO
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO

Editorial:
This problem provides very little information, giving us only the samples, and minor confirmation in the form of the title.
By looking carefully at the accepted samples, particularly the shorter ones such as big and clump, we may notice that they have a similar "shape". As it turns out, this problem is related to the concept of ascenders and descenders in typography. The title of the problem provides a nice bit of confirmation for this idea. Ultimately, a string is accepted if and only if its sequence of ascenders of descenders is a regular bracket sequence, and we can implement this easily.
There is a little ambiguity regarding whether the dots on i and j count as ascenders, but the given samples are enough to disambiguate and conclude that j is considered to have a descender, whereas i is considered to have neither an ascender nor a descender.
Unmysterious Language
Contest: April Fools Day Contest 2023
Tags: *special, constructive algorithms, strings

There is an unmysterious language. You should make a submission in this language, and the judge will read your submission to determine whether it is accepted.

You can only submit in the Mysterious Language we have provided. You can view the judge's response by clicking the submission ID on the "My Submissions" page.

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

Editorial:
The unmysterious language is English. You just need to ask the checker nicely, i.e. have "please". However, our AI gets tired from reading long messages, so if your output is too long, it won't accept it either!
Pretty Permutations
Contest: Codeforces Round 728 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, greedy, implementation

There are $$$n$$$ cats in a line, labeled from $$$1$$$ to $$$n$$$, with the $$$i$$$-th cat at position $$$i$$$. They are bored of gyrating in the same spot all day, so they want to reorder themselves such that no cat is in the same place as before. They are also lazy, so they want to minimize the total distance they move. Help them decide what cat should be at each location after the reordering.

For example, if there are $$$3$$$ cats, this is a valid reordering: $$$[3, 1, 2]$$$. No cat is in its original position. The total distance the cats move is $$$1 + 1 + 2 = 4$$$ as cat $$$1$$$ moves one place to the right, cat $$$2$$$ moves one place to the right, and cat $$$3$$$ moves two places to the left.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first and only line of each test case contains one integer $$$n$$$ ($$$2 \leq n \leq 100$$$) — the number of cats.

It can be proven that under the constraints of the problem, an answer always exist.

Output format:
Output $$$t$$$ answers, one for each test case. Each answer consists of $$$n$$$ integers — a permutation with the minimum total distance. If there are multiple answers, print any.

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

Note:
For the first test case, there is only one possible permutation that satisfies the conditions: $$$[2, 1]$$$.

The second test case was described in the statement. Another possible answer is $$$[2, 3, 1]$$$.

Example input:
2
2
3

Example output:
2 1 
3 1 2

Editorial:
There are two cases:
• if $$$n$$$ is even, print: $$$[2, 1, 4, 3, 6, 5 \ldots n, n-1]$$$ Formally, you swap every other pair of adjacent elements. This is optimal because the total distance is $$$n$$$, which has to be minimal since the distance of one cat must be $$$ \geq 1$$$.
• if $$$n$$$ is odd, first print $$$[3, 1, 2]$$$ then solve the even case for the remaining elements. This is optimal because the distance is $$$n+1$$$, which has to be minimal since a distance of $$$n$$$ is not achievable.
Pleasant Pairs
Contest: Codeforces Round 728 (Div. 2)
Difficulty rating: 1200
Tags: brute force, implementation, math, number theory

You are given an array $$$a_1, a_2, \dots, a_n$$$ consisting of $$$n$$$ distinct integers. Count the number of pairs of indices $$$(i, j)$$$ such that $$$i < j$$$ and $$$a_i \cdot a_j = i + j$$$.

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

The first line of each test case contains one integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — the length of 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 2 \cdot n$$$) — the array $$$a$$$. It is guaranteed that all elements are distinct.

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, output the number of pairs of indices $$$(i, j)$$$ such that $$$i < j$$$ and $$$a_i \cdot a_j = i + j$$$.

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

Note:
For the first test case, the only pair that satisfies the constraints is $$$(1, 2)$$$, as $$$a_1 \cdot a_2 = 1 + 2 = 3$$$

For the second test case, the only pair that satisfies the constraints is $$$(2, 3)$$$.

For the third test case, the pairs that satisfy the constraints are $$$(1, 2)$$$, $$$(1, 5)$$$, and $$$(2, 3)$$$.

Example input:
3
2
3 1
3
6 1 5
5
3 1 5 9 2

Example output:
1
1
3

Editorial:
Loop over all values of $$$a_i$$$ and $$$a_j$$$. Because $$$i + j \leq 2 \cdot n$$$, we only care about pairs $$$(a_i, a_j)$$$ if $$$a_i \cdot a_j \leq 2 \cdot n$$$. The number of such pairs is $$$O(n log n)$$$, so you can brute force all pairs.
The reason the total number of pairs is $$$O(n log n)$$$ is because if the first element of the pair is $$$x$$$, there are only $$$\frac{2 \cdot n}{x}$$$ possible values of $$$y$$$. $$$\frac{2 \cdot n}{1} + \frac{2 \cdot n}{2} + \frac{2 \cdot n}{3} + \ldots \frac{2 \cdot n}{n} = 2 \cdot n (\frac{1}{1} + \frac{1}{2} + \frac{1}{3} \ldots \frac{1}{n}) = O(n log n)$$$ by the harmonic series. Thus the solution runs in $$$O(n log n)$$$ time total.