1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Pursuit For Artifacts
Contest: Educational Codeforces Round 10
Difficulty rating: 2300
Tags: dfs and similar, dsu, graphs, trees

Johnny is playing a well-known computer game. The game are in some country, where the player can freely travel, pass quests and gain an experience.

In that country there are n islands and m bridges between them, so you can travel from any island to any other. In the middle of some bridges are lying ancient powerful artifacts. Johnny is not interested in artifacts, but he can get some money by selling some artifact.

At the start Johnny is in the island a and the artifact-dealer is in the island b (possibly they are on the same island). Johnny wants to find some artifact, come to the dealer and sell it. The only difficulty is that bridges are too old and destroying right after passing over them. Johnnie's character can't swim, fly and teleport, so the problem became too difficult.

Note that Johnny can't pass the half of the bridge, collect the artifact and return to the same island.

Determine if Johnny can find some artifact and sell it.

Input format:
The first line contains two integers n and m (1 ≤ n ≤ 3·105, 0 ≤ m ≤ 3·105) — the number of islands and bridges in the game.

Each of the next m lines contains the description of the bridge — three integers xi, yi, zi (1 ≤ xi, yi ≤ n, xi ≠ yi, 0 ≤ zi ≤ 1), where xi and yi are the islands connected by the i-th bridge, zi equals to one if that bridge contains an artifact and to zero otherwise. There are no more than one bridge between any pair of islands. It is guaranteed that it's possible to travel between any pair of islands.

The last line contains two integers a and b (1 ≤ a, b ≤ n) — the islands where are Johnny and the artifact-dealer respectively.

Output format:
If Johnny can find some artifact and sell it print the only word "YES" (without quotes). Otherwise print the word "NO" (without quotes).

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

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

Example output:
YES

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

Example output:
NO

Editorial:
Ants on a Circle
Contest: Educational Codeforces Round 10
Difficulty rating: 2800
Tags: constructive algorithms, math

n ants are on a circle of length m. An ant travels one unit of distance per one unit of time. Initially, the ant number i is located at the position si and is facing in the direction di (which is either L or R). Positions are numbered in counterclockwise order starting from some point. Positions of the all ants are distinct.

All the ants move simultaneously, and whenever two ants touch, they will both switch their directions. Note that it is possible for an ant to move in some direction for a half of a unit of time and in opposite direction for another half of a unit of time.

Print the positions of the ants after t time units.

Input format:
The first line contains three integers n, m and t (2 ≤ n ≤ 3·105, 2 ≤ m ≤ 109, 0 ≤ t ≤ 1018) — the number of ants, the length of the circle and the number of time units.

Each of the next n lines contains integer si and symbol di (1 ≤ si ≤ m and di is either L or R) — the position and the direction of the i-th ant at the start. The directions L and R corresponds to the clockwise and counterclockwise directions, respectively.

It is guaranteed that all positions si are distinct.

Output format:
Print n integers xj — the position of the j-th ant after t units of time. The ants are numbered from 1 to n in order of their appearing in input.

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

Example input:
2 4 8
1 R
3 L

Example output:
1 3

Example input:
4 8 6
6 R
5 L
1 R
8 L

Example output:
7 4 2 7

Editorial:
Three Integers Again
Contest: Kotlin Heroes: Episode 1
Tags: *special, math

We have three positive integers $$$a$$$, $$$b$$$ and $$$c$$$. You don't know their values, but you know some information about them. Consider all three pairwise sums, i.e. the numbers $$$a+b$$$, $$$a+c$$$ and $$$b+c$$$. You know exactly two (any) of three pairwise sums.

Your task is to find such three positive integers $$$a$$$, $$$b$$$ and $$$c$$$ which match the given information. It means that if you consider $$$a+b$$$, $$$a+c$$$ and $$$b+c$$$, two out of all three of them are given in the input. Among all such triples, you must choose one with the minimum possible sum $$$a+b+c$$$, and among all triples with the minimum sum, you can print any.

You have to process $$$q$$$ independent queries.

Input format:
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 1000$$$) — the number of queries.

The next $$$q$$$ lines contain queries. Each query is given as two integers $$$x$$$ and $$$y$$$ ($$$2 \le x, y \le 2 \cdot 10^9$$$), where $$$x$$$ and $$$y$$$ are any two out of the three numbers $$$a+b$$$, $$$a+c$$$ and $$$b+c$$$.

Output format:
For each query print the answer to it: three positive integers $$$a$$$, $$$b$$$ and $$$c$$$ consistent with the given information. Among all such triples, you have to choose one with the minimum possible sum $$$a+b+c$$$. Among all triples with the minimum sum, you can print any.

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

Example input:
3
123 13
2 2
2000000000 2000000000

Example output:
111 1 12
1 1 1
1999999999 1 1

Editorial:
We always can consider that the numbers in the input are $$$x = a + b$$$ and $$$y = b + c$$$. If $$$x > y$$$ let's swap them. Note, that $$$a + b + c = a + b + (y - b) = a + y$$$. That's why it's optimal to minimize value of $$$a$$$. So the value of $$$a$$$ can always be $$$1$$$. Then we can restore $$$b = x - a$$$, and $$$c = y - b$$$.
Bad Days
Contest: Kotlin Heroes: Episode 1
Tags: *special, implementation

Every day Kotlin heroes analyze the statistics of their website. For $$$n$$$ days, they wrote out $$$n$$$ numbers $$$a_1, a_2, \dots, a_n$$$, where $$$a_i$$$ is the number of visits on the $$$i$$$-th day.

They believe that a day is bad if there are at least $$$2$$$ days before it with a strictly greater number of visits. For example, if $$$n=8$$$ and $$$a=[3, 1, 4, 1, 5, 9, 2, 6]$$$, then the day $$$4$$$ is bad (because $$$a_4=1$$$, but there are $$$a_1=3$$$ and $$$a_3=4$$$). Also, the day with the number $$$7$$$ is bad too.

Write a program that finds the number of bad days.

Input format:
The first line contains an integer $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$), where $$$n$$$ is the number of days. The second line contains $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the number of website visits on the $$$i$$$-th day.

Output format:
Print the number of bad days, i.e. such days that there are at least two days before it with a strictly greater number of visits.

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

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

Example output:
2

Example input:
5
1 1 1 1 1

Example output:
0

Editorial:
Iterate over all elements in $$$a$$$ from $$$a_1$$$ to $$$a_n$$$ one by one. You can easily maintain two maximum values. If the current element is strictly less than the second maximum, increment the result. Here is the main part of the code:
Minus and Minus Give Plus
Contest: Kotlin Heroes: Episode 1
Tags: *special, implementation, strings

Everyone knows that two consecutive (adjacent) "minus" signs can be replaced with a single "plus" sign.

You are given the string $$$s$$$, consisting of "plus" and "minus" signs only. Zero or more operations can be performed with it. In each operation you can choose any two adjacent "minus" signs, and replace them with a single "plus" sign. Thus, in one operation, the length of the string is reduced by exactly $$$1$$$.

You are given two strings $$$s$$$ and $$$t$$$. Determine if you can use $$$0$$$ or more operations to get the string $$$t$$$ from the string $$$s$$$.

Input format:
The first line of the input contains an integer $$$k$$$ ($$$1 \le k \le 10^5$$$), denoting the number of test cases in the input. The following lines contain descriptions of the test sets, each set consists of two lines. First comes the line containing $$$s$$$ (the length of the line $$$s$$$ does not exceed $$$2\cdot10^5$$$), then comes the line containing $$$t$$$ (the length of the line $$$t$$$ does not exceed $$$2\cdot10^5$$$). The lines $$$s$$$ and $$$t$$$ are non-empty, and they contain only "plus" and "minus" signs.

The sum of the lengths of lines $$$s$$$ over all test cases in the input does not exceed $$$2\cdot10^5$$$. Similarly, the sum of the lengths of lines $$$t$$$ over all test cases in the input does not exceed $$$2\cdot10^5$$$.

Output format:
Print $$$k$$$ lines: the $$$i$$$-th line must contain YES if the answer to the $$$i$$$-th test case is positive, otherwise NO. Print YES and NO using uppercase letters only.

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

Example input:
5
-+--+
-+++
--------
-+--+-
-
+
--
---
+++
+++

Example output:
YES
YES
NO
NO
YES

Editorial:
Let's process $$$s$$$ and $$$t$$$ character by character from left to right in parallel. Let's use two indices $$$i$$$ and $$$j$$$: the index $$$i$$$ is for $$$s$$$ and the index $$$j$$$ is for $$$t$$$. Initially, $$$i=j=0$$$. If $$$s[i] == t[j]$$$ then you can simply increase both indices $$$i$$$ and $$$j$$$ ($$$i$$$++, $$$j$$$++). In the opposite case, the only allowed situation is $$$s[i] = s[i+1] = $$$ '-' and $$$t[j] = $$$ '+'. In this case, increase $$$i$$$ by $$$2$$$ and $$$j$$$ by one. Stop the process if at least one index ($$$i$$$ or $$$j$$$) reaches the end of the corresponding string. Return positive answer YES if and only if both $$$i$$$ and $$$j$$$ reach the ends of strings $$$s$$$ and $$$t$$$ ($$$i=len(s), j=len(t)$$$) at the same time.
Graph Decomposition
Contest: Kotlin Heroes: Episode 1
Tags: *special, graphs

You are given an undirected graph consisting of $$$n$$$ vertices and $$$m$$$ edges.

Recall that a cycle is a path that starts and ends in the same vertex. A cycle in a graph is called simple if it contains each vertex (except the starting and ending one) no more than once (the starting and the ending one is contained always twice). Note that loops are considered to be simple cycles.

In one move you can choose any simple cycle in this graph and erase the edges corresponding to this cycle (corresponding vertices remain in the graph). It is allowed to erase the loop or two copies of the same edge (take a look at examples).

Your problem is to apply some sequence of moves to obtain the graph without edges. It is not necessary to minimize the number of cycles. If it is impossible, print "NO".

Input format:
The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the number of vertices and the number of edges in the graph.

The next $$$m$$$ lines contain edges of the graph. The $$$i$$$-th line contains the $$$i$$$-th edge $$$x_i, y_i$$$ ($$$1 \le x_i, y_i \le n$$$), where $$$x_i$$$ and $$$y_i$$$ are vertices connected by the $$$i$$$-th edge. The graph can contain loops or multiple edges.

Output format:
If it is impossible to decompose the given graph into simple cycles, print "NO" in the first line.

Otherwise print "YES" in the first line. In the second line print $$$k$$$ — the number of simple cycles in the graph decomposition.

In the next $$$k$$$ lines print cycles themselves. The $$$j$$$-th line should contain the $$$j$$$-th cycle. First, print $$$c_j$$$ — the number of vertices in the $$$j$$$-th cycle. Then print the cycle as a sequence of vertices. All neighbouring (adjacent) vertices in the printed path should be connected by an edge that isn't contained in other cycles.

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

Note:
The picture corresponding to the first example:

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

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

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

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

Editorial:
If there exists vertex with the odd degree then the answer is "NO", otherwise the answer is "YES". Let's find a way to constuct it.
Almost all we need is to run euler cycle finding for each component of the given graph. It can be done with the following code:
In the part when we pushes a new vertex into the path we should try to restore a new cycle. How do we check and do it? Let's maintain an array $$$used$$$: $$$used_v$$$ is true when the vertex $$$v$$$ is in $$$path$$$. When we try to add the vertex $$$v$$$ that already in $$$path$$$ ($$$used_v$$$ is true), let's extract the new simple cycle instead of adding this vertex. Let's pop out all vertices $$$u$$$ we pushed until the last vertex equals to $$$v$$$ (and don't forget to set $$$used_u$$$ to false). Otherwise let's add this vertex into the list and set $$$used_v$$$ to true.
Likes Display
Contest: Kotlin Heroes: Episode 3
Tags: *special, implementation

Polycarp is working on the implementation of displaying likes on the Codehorses social network. The number of likes should be displayed in a format that will be easy to read by users. It was decided that for large numbers of likes the format should be like 123K (one hundred twenty-three thousand) or like 56M (fifty-six million).

The following displaying strategy has been approved:

- the number will be displayed either as an integer number from 0 to 999, or as a positive integer number of thousands (from 1K to 999K), or as a positive integer number of millions (from 1M on),
- the specified exact number of likes $$$n$$$ when displaying should be rounded to the nearest view from the case above (if rounding is ambiguous, it must be rounded up): for example, $$$1785$$$ should be rounded to 2K instead of 1K, $$$4500000$$$ should be rounded to 5M.

Help Polycarp implement this part of the functionality: for a given non-negative integer number of likes $$$n$$$, print its view in the Codehorses interface.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases in the input. The following are descriptions of the $$$t$$$ input test cases, one per line.

The description of each test case consists of a single line that contains a non-negative integer $$$n$$$ ($$$0 \le n \le 2\cdot10^9$$$) — the number of likes.

Output format:
Print $$$t$$$ answers to the given test cases in the order from the input. Each printed value must have one of the following types:

- either an integer from 0 to 999 which corresponds just to the number of likes,
- or a number of thousands from 1K to 999K,
- or a number of millions from 1M to 2000M.

The answer is equal to a view which is the closest (by difference) to the given number $$$n$$$. If this rounding is ambiguous, then round answer up (to a greater value).

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

Note:
Let's describe some test cases:

- $$$1782$$$ can be displayed either as 1K or as 2K but 2K is the nearest view;
- $$$1500$$$ have same difference with 1K and 2K so it should be rounded up;
- $$$999999$$$ should be displayed as 1M since it's closer to it than to 999K.

Example input:
9
999
123
0
1782
31415926
1500
999999
35499710
2000000000

Example output:
999
123
0
2K
31M
2K
1M
35M
2000M

Editorial:
There are three different variants to display $$$n$$$: exact number, thousands or millions. Let's find out what range $$$n$$$ should be in for each variant:
• if $$$n \in [0, 999]$$$ then we should print its exact value;
• if $$$n \in [1000, 999499]$$$ then we should print it as a number of thousands rounded to the nearest value;
• otherwise we should print it as a number of millions also rounded to the nearest value.
The last question is how to round to the nearest number of thousands (millions). There are two ways to do it:
• we can avoid using numbers with floating points, i.e. use formula $$$\left\lfloor \frac{n + 500}{1000} \right\rfloor$$$ (or $$$\left\lfloor \frac{n + 5 \cdot 10^5}{10^6} \right\rfloor$$$)
• or we can use $$$roundToInt()$$$ function on Double value.
Cartoons
Contest: Kotlin Heroes: Episode 3
Tags: *special, implementation, sortings

Tanya likes cartoons. She knows that $$$n$$$ new cartoons will be released in his favorite cinema: the $$$i$$$-th of them will be airing from the day $$$a_i$$$ to the day $$$b_i$$$ ($$$1 \le a_i \le b_i \le 10^9$$$).

The cinema has a special offer: there is a huge discount every day when only one cartoon is airing.

Tanya doesn't care which cartoon she will watch but she'd like to save some money. That's why she asks you to find any day $$$x$$$ when only one cartoon will be airing. Formally: find $$$x$$$ such that there is exactly one $$$i$$$ ($$$1 \le i \le n$$$) with $$$a_i \le x \le b_i$$$. If there are several possible answers, print any of them. If there is no such day, print -1.

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

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

In the next $$$n$$$ lines, the cartoons themselves are described, one per line, by a pair of integers $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i \le b_i \le 10^9$$$) — the first and last airing days for the $$$i$$$-th cartoon.

It is guaranteed that the sum of the values $$$n$$$ for all test cases in the input does not exceed $$$2000$$$.

Output format:
Print $$$t$$$ answers to given test cases in the order in which they appear in the input: the $$$i$$$-th answer is such $$$x$$$, that only one cartoon will be airing on day $$$x$$$ or -1 if there are no such days.

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

Note:
In the third test case: at day $$$1$$$ and $$$2$$$, first and third cartoons will be airing, and days $$$3$$$ and $$$4$$$, second and third cartoons will be airing. So, there is no day when only one cartoon will be airing.

In the fourth test case, $$$11$$$ is also a possible answer.

Example input:
5
1
1 1
3
2 1000000000
2 500000000
500000002 1000000000
3
1 2
3 4
1 4
2
4 11
4 9
3
1 5
10 10
1 5

Example output:
1
500000001
-1
10
10

Editorial:
Let's prove the next proposition: if the answer is not equal to $$$-1$$$ then exists such answer $$$x$$$ that either $$$|x - l_i| \le 1$$$ or $$$|x - r_i| \le 1$$$ for some $$$1 \le i \le n$$$. Let we have the answer $$$x$$$ and $$$x \ne l_i$$$ and $$$x \ne r_i$$$. Then let's move $$$x$$$ to the left one by one until we fulfill the condition above — it will surely happens since there is at least one $$$l_i < x$$$.
We can use the proposition above in such way: there are only $$$O(n)$$$ candidates for an answer to check: $$$l_i - 1$$$, $$$l_i$$$, $$$l_i + 1$$$, $$$r_i - 1$$$, $$$r_i$$$ and $$$r_i + 1$$$ for all $$$i$$$. And for each candidate, we just calculate the number of segments it is in.
The total complexity is $$$O(\sum\limits_{\text{test cases}}{n^2})$$$.
M-numbers
Contest: Kotlin Heroes: Episode 3
Tags: *special, dp, math

For a given positive integer $$$m$$$, a positive number is called a $$$m$$$-number if the product of its digits is $$$m$$$. For example, the beginning of a series of $$$24$$$-numbers are as follows: $$$38$$$, $$$46$$$, $$$64$$$, $$$83$$$, $$$138$$$, $$$146$$$, $$$164$$$, $$$183$$$, $$$226$$$ ...

You are given a positive integer $$$m$$$ and $$$k$$$. Print $$$k$$$-th among $$$m$$$-numbers if all $$$m$$$-numbers are sorted in ascending order.

Input format:
A single line of input contains two integers $$$m$$$ and $$$k$$$ ($$$2 \le m \le 10^9$$$, $$$1 \le k \le 10^9$$$).

Output format:
Print the desired number — $$$k$$$-th among all $$$m$$$-numbers if $$$m$$$-numbers are sorted in ascending order. If the answer does not exist, print -1.

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

Example input:
24 9

Example output:
226

Example input:
24 1

Example output:
38

Editorial:
Note, that since each divisor of $$$m$$$ should be a digit less than $$$10$$$ then all prime divisors of $$$m$$$ should be less than $$$10$$$, i.e. we can represent $$$m$$$ as $$$m = 2^{f_1} \cdot 3^{f_2} \cdot 5^{f_3} \cdot 7^{f_4}$$$. Otherwise, the answer is $$$-1$$$.
Now, let's just write dynamic programming $$$dp$$$ with state $$$(f_1, f_2, f_3, f_4, len)$$$ which is equal to the number of $$$m$$$-numbers of length $$$len$$$ and $$$m = 2^{f_1} \cdot 3^{f_2} \cdot 5^{f_3} \cdot 7^{f_4}$$$. The transisions are quite straightforward: let's choose what the last digit $$$d$$$ is or let's check all posible last digit $$$d \in [1, 9]$$$ recalculate array $$$f$$$ and ask value of state $$$(f_1', f_2', f_3', f_4', len - 1)$$$.
The trick is that we'd visit not so many different states, so it's enough just to memorize all of them by hashing and map structure.
The last question is how to find $$$k$$$-th smallest in lexicographical order. It's quite a standard algorithm. At first, let find the length of the answer. It should be equal to the minimum $$$len$$$ such that the total number of $$$m$$$-numbers of length no more than $$$len$$$ is at least $$$k$$$. Then let's build the answer from the prefix deciding for each position, what digit should be here. It can be done using the $$$dp$$$ to calculate a number of $$$m'$$$-numbers which has a fixed prefix.
Guilty — to the kitchen!
Contest: Codeforces Beta Round 41
Difficulty rating: 1400
Tags: greedy, implementation

It's a very unfortunate day for Volodya today. He got bad mark in algebra and was therefore forced to do some work in the kitchen, namely to cook borscht (traditional Russian soup). This should also improve his algebra skills.

According to the borscht recipe it consists of n ingredients that have to be mixed in proportion $$(a_{1}:a_{2}:\ldots:a_{n})$$ litres (thus, there should be a1 ·x, ..., an ·x litres of corresponding ingredients mixed for some non-negative x). In the kitchen Volodya found out that he has b1, ..., bn litres of these ingredients at his disposal correspondingly. In order to correct his algebra mistakes he ought to cook as much soup as possible in a V litres volume pan (which means the amount of soup cooked can be between 0 and V litres). What is the volume of borscht Volodya will cook ultimately?

Input format:
The first line of the input contains two space-separated integers n and V (1 ≤ n ≤ 20, 1 ≤ V ≤ 10000). The next line contains n space-separated integers ai (1 ≤ ai ≤ 100). Finally, the last line contains n space-separated integers bi (0 ≤ bi ≤ 100).

Output format:
Your program should output just one real number — the volume of soup that Volodya will cook. Your answer must have a relative or absolute error less than 10 - 4.

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

Example input:
1 100
1
40

Example output:
40.0

Example input:
2 100
1 1
25 30

Example output:
50.0

Editorial: