1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Intergalaxy Trips
Contest: Codeforces Round 335 (Div. 1)
Difficulty rating: 2700
Tags: probabilities, shortest paths

The scientists have recently discovered wormholes — objects in space that allow to travel very long distances between galaxies and star systems.

The scientists know that there are n galaxies within reach. You are in the galaxy number 1 and you need to get to the galaxy number n. To get from galaxy i to galaxy j, you need to fly onto a wormhole (i, j) and in exactly one galaxy day you will find yourself in galaxy j.

Unfortunately, the required wormhole is not always available. Every galaxy day they disappear and appear at random. However, the state of wormholes does not change within one galaxy day. A wormhole from galaxy i to galaxy j exists during each galaxy day taken separately with probability pij. You can always find out what wormholes exist at the given moment. At each moment you can either travel to another galaxy through one of wormholes that exist at this moment or you can simply wait for one galaxy day to see which wormholes will lead from your current position at the next day.

Your task is to find the expected value of time needed to travel from galaxy 1 to galaxy n, if you act in the optimal way. It is guaranteed that this expected value exists.

Input format:
The first line of the input contains a single integer n (1 ≤ n ≤ 1000) — the number of galaxies within reach.

Then follows a matrix of n rows and n columns. Each element pij represents the probability that there is a wormhole from galaxy i to galaxy j. All the probabilities are given in percents and are integers. It is guaranteed that all the elements on the main diagonal are equal to 100.

Output format:
Print a single real value — the expected value of the time needed to travel from galaxy 1 to galaxy n if one acts in an optimal way. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$.

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

Note:
In the second sample the wormhole from galaxy 1 to galaxy 2 appears every day with probability equal to 0.3. The expected value of days one needs to wait before this event occurs is $$\frac { 1 } { 0. 3 } = 3 \frac { 1 } { 3 }$$.

Example input:
3
100 50 50
0 100 80
0 0 100

Example output:
1.750000000000000

Example input:
2
100 30
40 100

Example output:
3.333333333333333

Editorial:
Dasha and Stairs
Contest: Codeforces Round 394 (Div. 2)
Difficulty rating: 1000
Tags: brute force, constructive algorithms, implementation, math

On her way to programming school tiger Dasha faced her first test — a huge staircase!

The steps were numbered from one to infinity. As we know, tigers are very fond of all striped things, it is possible that it has something to do with their color. So on some interval of her way she calculated two values — the number of steps with even and odd numbers.

You need to check whether there is an interval of steps from the l-th to the r-th (1 ≤ l ≤ r), for which values that Dasha has found are correct.

Input format:
In the only line you are given two integers a, b (0 ≤ a, b ≤ 100) — the number of even and odd steps, accordingly.

Output format:
In the only line print "YES", if the interval of steps described above exists, and "NO" otherwise.

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

Note:
In the first example one of suitable intervals is from 1 to 5. The interval contains two even steps — 2 and 4, and three odd: 1, 3 and 5.

Example input:
2 3

Example output:
YES

Example input:
3 1

Example output:
NO

Editorial:
It's obvious, that if |a - b| > 1 — the answer is «NO». «NO» answer was also in the case, when a and b are equal to 0, because according to the statement, such interval should exist. In other cases the answer is «YES».
Dasha and friends
Contest: Codeforces Round 394 (Div. 2)
Difficulty rating: 1300
Tags: brute force, implementation, math

Running with barriers on the circle track is very popular in the country where Dasha lives, so no wonder that on her way to classes she saw the following situation:

The track is the circle with length L, in distinct points of which there are n barriers. Athlete always run the track in counterclockwise direction if you look on him from above. All barriers are located at integer distance from each other along the track.

Her friends the parrot Kefa and the leopard Sasha participated in competitions and each of them ran one lap. Each of the friends started from some integral point on the track. Both friends wrote the distance from their start along the track to each of the n barriers. Thus, each of them wrote n integers in the ascending order, each of them was between 0 and L - 1, inclusively.

Consider an example. Let L = 8, blue points are barriers, and green points are Kefa's start (A) and Sasha's start (B). Then Kefa writes down the sequence [2, 4, 6], and Sasha writes down [1, 5, 7].

There are several tracks in the country, all of them have same length and same number of barriers, but the positions of the barriers can differ among different tracks. Now Dasha is interested if it is possible that Kefa and Sasha ran the same track or they participated on different tracks.

Write the program which will check that Kefa's and Sasha's tracks coincide (it means that one can be obtained from the other by changing the start position). Note that they always run the track in one direction — counterclockwise, if you look on a track from above.

Input format:
The first line contains two integers n and L (1 ≤ n ≤ 50, n ≤ L ≤ 100) — the number of barriers on a track and its length.

The second line contains n distinct integers in the ascending order — the distance from Kefa's start to each barrier in the order of its appearance. All integers are in the range from 0 to L - 1 inclusively.

The second line contains n distinct integers in the ascending order — the distance from Sasha's start to each barrier in the order of its overcoming. All integers are in the range from 0 to L - 1 inclusively.

Output format:
Print "YES" (without quotes), if Kefa and Sasha ran the coinciding tracks (it means that the position of all barriers coincides, if they start running from the same points on the track). Otherwise print "NO" (without quotes).

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

Note:
The first test is analyzed in the statement.

Example input:
3 8
2 4 6
1 5 7

Example output:
YES

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

Example output:
YES

Editorial:
Let's add distances between pairs of adjacent barriers of both tracks in arrays and check if it possible to get one of them from another using cycling shift of the elements.
Dasha and Password
Contest: Codeforces Round 394 (Div. 2)
Difficulty rating: 1500
Tags: brute force, dp, implementation

After overcoming the stairs Dasha came to classes. She needed to write a password to begin her classes. The password is a string of length n which satisfies the following requirements:

- There is at least one digit in the string,
- There is at least one lowercase (small) letter of the Latin alphabet in the string,
- There is at least one of three listed symbols in the string: '#', '*', '&'.

Considering that these are programming classes it is not easy to write the password.

For each character of the password we have a fixed string of length m, on each of these n strings there is a pointer on some character. The i-th character displayed on the screen is the pointed character in the i-th string. Initially, all pointers are on characters with indexes 1 in the corresponding strings (all positions are numbered starting from one).

During one operation Dasha can move a pointer in one string one character to the left or to the right. Strings are cyclic, it means that when we move the pointer which is on the character with index 1 to the left, it moves to the character with the index m, and when we move it to the right from the position m it moves to the position 1.

You need to determine the minimum number of operations necessary to make the string displayed on the screen a valid password.

Input format:
The first line contains two integers n, m (3 ≤ n ≤ 50, 1 ≤ m ≤ 50) — the length of the password and the length of strings which are assigned to password symbols.

Each of the next n lines contains the string which is assigned to the i-th symbol of the password string. Its length is m, it consists of digits, lowercase English letters, and characters '#', '*' or '&'.

You have such input data that you can always get a valid password.

Output format:
Print one integer — the minimum number of operations which is necessary to make the string, which is displayed on the screen, a valid password.

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

Note:
In the first test it is necessary to move the pointer of the third string to one left to get the optimal answer.

In the second test one of possible algorithms will be:

- to move the pointer of the second symbol once to the right.
- to move the pointer of the third symbol twice to the right.

Example input:
3 4
1**2
a3*0
c4**

Example output:
1

Example input:
5 5
#*&#*
*a1c&
&q2w*
#a3c#
*&#*&

Example output:
3

Editorial:
Let's iterate the string, where we want to get a digit to the password, then the string, where we'll get a letter to the password and the string, where we'll get one of the characters '&', '*', '#'. Obviously, in the other strings we can pick any character, so we only need to compute minimal number of moves we have to do to get corresponding characters in fixed strings. We can do it just by iterating that strings.
Dasha and Very Difficult Problem
Contest: Codeforces Round 394 (Div. 2)
Difficulty rating: 1700
Tags: binary search, brute force, constructive algorithms, greedy, sortings

Dasha logged into the system and began to solve problems. One of them is as follows:

Given two sequences a and b of length n each you need to write a sequence c of length n, the i-th element of which is calculated as follows: ci = bi - ai.

About sequences a and b we know that their elements are in the range from l to r. More formally, elements satisfy the following conditions: l ≤ ai ≤ r and l ≤ bi ≤ r. About sequence c we know that all its elements are distinct.

Dasha wrote a solution to that problem quickly, but checking her work on the standard test was not so easy. Due to an error in the test system only the sequence a and the compressed sequence of the sequence c were known from that test.

Let's give the definition to a compressed sequence. A compressed sequence of sequence c of length n is a sequence p of length n, so that pi equals to the number of integers which are less than or equal to ci in the sequence c. For example, for the sequence c = [250, 200, 300, 100, 50] the compressed sequence will be p = [4, 3, 5, 2, 1]. Pay attention that in c all integers are distinct. Consequently, the compressed sequence contains all integers from 1 to n inclusively.

Help Dasha to find any sequence b for which the calculated compressed sequence of sequence c is correct.

Input format:
The first line contains three integers n, l, r (1 ≤ n ≤ 105, 1 ≤ l ≤ r ≤ 109) — the length of the sequence and boundaries of the segment where the elements of sequences a and b are.

The next line contains n integers a1,  a2,  ...,  an (l ≤ ai ≤ r) — the elements of the sequence a.

The next line contains n distinct integers p1,  p2,  ...,  pn (1 ≤ pi ≤ n) — the compressed sequence of the sequence c.

Output format:
If there is no the suitable sequence b, then in the only line print "-1".

Otherwise, in the only line print n integers — the elements of any suitable sequence b.

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

Note:
Sequence b which was found in the second sample is suitable, because calculated sequence c = [2 - 3, 2 - 4, 2 - 8, 9 - 9] = [ - 1,  - 2,  - 6, 0] (note that ci = bi - ai) has compressed sequence equals to p = [3, 2, 1, 4].

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

Example output:
3 1 5 4 2

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

Example output:
2 2 2 9

Editorial:
Let's match each element of a interval of values, which corresponding element of c could take, i.e for i-th element interval [l - ai;r - ai]. Let posi be the index of element equal to i in permutation p. Now you can know, that solving the initial task is reduced to picking a number of each interval, so that this numbers form an increasing sequence in order from pos1 to posn. It is easy to know that we can pick the numbers greedily, picking a number that is greater than previous and belongs to current interval.
Dasha and Puzzle
Contest: Codeforces Round 394 (Div. 2)
Difficulty rating: 2000
Tags: constructive algorithms, dfs and similar, graphs, greedy, trees

Dasha decided to have a rest after solving the problem. She had been ready to start her favourite activity — origami, but remembered the puzzle that she could not solve.

The tree is a non-oriented connected graph without cycles. In particular, there always are n - 1 edges in a tree with n vertices.

The puzzle is to position the vertices at the points of the Cartesian plane with integral coordinates, so that the segments between the vertices connected by edges are parallel to the coordinate axes. Also, the intersection of segments is allowed only at their ends. Distinct vertices should be placed at different points.

Help Dasha to find any suitable way to position the tree vertices on the plane.

It is guaranteed that if it is possible to position the tree vertices on the plane without violating the condition which is given above, then you can do it by using points with integral coordinates which don't exceed 1018 in absolute value.

Input format:
The first line contains single integer n (1 ≤ n ≤ 30) — the number of vertices in the tree.

Each of next n - 1 lines contains two integers ui, vi (1 ≤ ui, vi ≤ n) that mean that the i-th edge of the tree connects vertices ui and vi.

It is guaranteed that the described graph is a tree.

Output format:
If the puzzle doesn't have a solution then in the only line print "NO".

Otherwise, the first line should contain "YES". The next n lines should contain the pair of integers xi, yi (|xi|, |yi| ≤ 1018) — the coordinates of the point which corresponds to the i-th vertex of the tree.

If there are several solutions, print any of them.

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

Note:
In the first sample one of the possible positions of tree is:

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

Example output:
YES
0 0
1 0
0 1
2 0
1 -1
-1 1
0 2

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

Example output:
NO

Editorial:
The answer doesn't exist, when there is a vertex with degree > 4. We'll use power of two as length of each edge in the tree. Let's dfs our tree and store in the recursion: the direction, where our parent is located (one of four possible), and the length of the edge we'll build from current vertex. Then iterate the new direction, some neighbour of the vertex and continue recursion. The edges will not intersect, except in the verteces, because 20 + 21 + ... + 2k < 2k + 1.
Comment: It's worth noting that it is possible to solve problem for greater n, using the fact that nothing depends on the coordinates, only ratios between X and Y coordinates seperatly, so we can compress them.
Elections
Contest: Codeforces Round 519 by Botan Investments
Difficulty rating: 800
Tags: implementation, math

Awruk is taking part in elections in his school. It is the final round. He has only one opponent — Elodreip. The are $$$n$$$ students in the school. Each student has exactly $$$k$$$ votes and is obligated to use all of them. So Awruk knows that if a person gives $$$a_i$$$ votes for Elodreip, than he will get exactly $$$k - a_i$$$ votes from this person. Of course $$$0 \le k - a_i$$$ holds.

Awruk knows that if he loses his life is over. He has been speaking a lot with his friends and now he knows $$$a_1, a_2, \dots, a_n$$$ — how many votes for Elodreip each student wants to give. Now he wants to change the number $$$k$$$ to win the elections. Of course he knows that bigger $$$k$$$ means bigger chance that somebody may notice that he has changed something and then he will be disqualified.

So, Awruk knows $$$a_1, a_2, \dots, a_n$$$ — how many votes each student will give to his opponent. Help him select the smallest winning number $$$k$$$. In order to win, Awruk needs to get strictly more votes than Elodreip.

Input format:
The first line contains integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of students in the school.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 100$$$) — the number of votes each student gives to Elodreip.

Output format:
Output the smallest integer $$$k$$$ ($$$k \ge \max a_i$$$) which gives Awruk the victory. In order to win, Awruk needs to get strictly more votes than Elodreip.

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

Note:
In the first example, Elodreip gets $$$1 + 1 + 1 + 5 + 1 = 9$$$ votes. The smallest possible $$$k$$$ is $$$5$$$ (it surely can't be less due to the fourth person), and it leads to $$$4 + 4 + 4 + 0 + 4 = 16$$$ votes for Awruk, which is enough to win.

In the second example, Elodreip gets $$$11$$$ votes. If $$$k = 4$$$, Awruk gets $$$9$$$ votes and loses to Elodreip.

Example input:
5
1 1 1 5 1

Example output:
5

Example input:
5
2 2 3 2 2

Example output:
5

Editorial:
Lost Array
Contest: Codeforces Round 519 by Botan Investments
Difficulty rating: 1200
Tags: implementation

Bajtek, known for his unusual gifts, recently got an integer array $$$x_0, x_1, \ldots, x_{k-1}$$$.

Unfortunately, after a huge array-party with his extraordinary friends, he realized that he'd lost it. After hours spent on searching for a new toy, Bajtek found on the arrays producer's website another array $$$a$$$ of length $$$n + 1$$$. As a formal description of $$$a$$$ says, $$$a_0 = 0$$$ and for all other $$$i$$$ ($$$1 \le i \le n$$$) $$$a_i = x_{(i-1)\bmod k} + a_{i-1}$$$, where $$$p \bmod q$$$ denotes the remainder of division $$$p$$$ by $$$q$$$.

For example, if the $$$x = [1, 2, 3]$$$ and $$$n = 5$$$, then:

- $$$a_0 = 0$$$,
- $$$a_1 = x_{0\bmod 3}+a_0=x_0+0=1$$$,
- $$$a_2 = x_{1\bmod 3}+a_1=x_1+1=3$$$,
- $$$a_3 = x_{2\bmod 3}+a_2=x_2+3=6$$$,
- $$$a_4 = x_{3\bmod 3}+a_3=x_0+6=7$$$,
- $$$a_5 = x_{4\bmod 3}+a_4=x_1+7=9$$$.

So, if the $$$x = [1, 2, 3]$$$ and $$$n = 5$$$, then $$$a = [0, 1, 3, 6, 7, 9]$$$.

Now the boy hopes that he will be able to restore $$$x$$$ from $$$a$$$! Knowing that $$$1 \le k \le n$$$, help him and find all possible values of $$$k$$$ — possible lengths of the lost array.

Input format:
The first line contains exactly one integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the length of the array $$$a$$$, excluding the element $$$a_0$$$.

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

Note that $$$a_0$$$ is always $$$0$$$ and is not given in the input.

Output format:
The first line of the output should contain one integer $$$l$$$ denoting the number of correct lengths of the lost array.

The second line of the output should contain $$$l$$$ integers — possible lengths of the lost array in increasing order.

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

Note:
In the first example, any $$$k$$$ is suitable, since $$$a$$$ is an arithmetic progression.

Possible arrays $$$x$$$:

- $$$[1]$$$
- $$$[1, 1]$$$
- $$$[1, 1, 1]$$$
- $$$[1, 1, 1, 1]$$$
- $$$[1, 1, 1, 1, 1]$$$

In the second example, Bajtek's array can have three or five elements.

Possible arrays $$$x$$$:

- $$$[1, 2, 2]$$$
- $$$[1, 2, 2, 1, 2]$$$

For example, $$$k = 4$$$ is bad, since it leads to $$$6 + x_0 = 8$$$ and $$$0 + x_0 = 1$$$, which is an obvious contradiction.

In the third example, only $$$k = n$$$ is good.

Array $$$[1, 4, -2]$$$ satisfies the requirements.

Note that $$$x_i$$$ may be negative.

Example input:
5
1 2 3 4 5

Example output:
5
1 2 3 4 5

Example input:
5
1 3 5 6 8

Example output:
2
3 5

Editorial:
Smallest Word
Contest: Codeforces Round 519 by Botan Investments
Difficulty rating: 1500
Tags: constructive algorithms, greedy, implementation

IA has so many colorful magnets on her fridge! Exactly one letter is written on each magnet, 'a' or 'b'. She loves to play with them, placing all magnets in a row. However, the girl is quickly bored and usually thinks how to make her entertainment more interesting.

Today, when IA looked at the fridge, she noticed that the word formed by magnets is really messy. "It would look much better when I'll swap some of them!" — thought the girl — "but how to do it?". After a while, she got an idea. IA will look at all prefixes with lengths from $$$1$$$ to the length of the word and for each prefix she will either reverse this prefix or leave it as it is. She will consider the prefixes in the fixed order: from the shortest to the largest. She wants to get the lexicographically smallest possible word after she considers all prefixes. Can you help her, telling which prefixes should be chosen for reversing?

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 and the only line contains a string $$$s$$$ ($$$1 \le |s| \le 1000$$$), describing the initial string formed by magnets. The string $$$s$$$ consists only of characters 'a' and 'b'.

Output format:
Output exactly $$$|s|$$$ integers. If IA should reverse the $$$i$$$-th prefix (that is, the substring from $$$1$$$ to $$$i$$$), the $$$i$$$-th integer should be equal to $$$1$$$, and it should be equal to $$$0$$$ otherwise.

If there are multiple possible sequences leading to the optimal answer, print any of them.

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

Note:
In the first example, IA can reverse the second and the third prefix and get a string "abbb". She cannot get better result, since it is also lexicographically smallest string obtainable by permuting characters of the initial string.

In the second example, she can reverse any subset of prefixes — all letters are 'a'.

Example input:
bbab

Example output:
0 1 1 0

Example input:
aaaaa

Example output:
1 0 0 0 1

Editorial: