1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
The Child and Toy
Contest: Codeforces Round 250 (Div. 2)
Difficulty rating: 1400
Tags: graphs, greedy, sortings

On Children's Day, the child got a toy from Delayyy as a present. However, the child is so naughty that he can't wait to destroy the toy.

The toy consists of n parts and m ropes. Each rope links two parts, but every pair of parts is linked by at most one rope. To split the toy, the child must remove all its parts. The child can remove a single part at a time, and each remove consume an energy. Let's define an energy value of part i as vi. The child spend vf1 + vf2 + ... + vfk energy for removing part i where f1, f2, ..., fk are the parts that are directly connected to the i-th and haven't been removed.

Help the child to find out, what is the minimum total energy he should spend to remove all n parts.

Input format:
The first line contains two integers n and m (1 ≤ n ≤ 1000; 0 ≤ m ≤ 2000). The second line contains n integers: v1, v2, ..., vn (0 ≤ vi ≤ 105). Then followed m lines, each line contains two integers xi and yi, representing a rope from part xi to part yi (1 ≤ xi, yi ≤ n; xi ≠ yi).

Consider all the parts are numbered from 1 to n.

Output format:
Output the minimum total energy the child should spend to remove all n parts of the toy.

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

Note:
One of the optimal sequence of actions in the first sample is:

- First, remove part 3, cost of the action is 20.
- Then, remove part 2, cost of the action is 10.
- Next, remove part 4, cost of the action is 10.
- At last, remove part 1, cost of the action is 0.

So the total energy the child paid is 20 + 10 + 10 + 0 = 40, which is the minimum.

In the second sample, the child will spend 400 no matter in what order he will remove the parts.

Example input:
4 3
10 20 30 40
1 4
1 2
2 3

Example output:
40

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

Example output:
400

Editorial:
The Child and Zoo
Contest: Codeforces Round 250 (Div. 2)
Difficulty rating: 1900
Tags: dsu, sortings

Of course our child likes walking in a zoo. The zoo has n areas, that are numbered from 1 to n. The i-th area contains ai animals in it. Also there are m roads in the zoo, and each road connects two distinct areas. Naturally the zoo is connected, so you can reach any area of the zoo from any other area using the roads.

Our child is very smart. Imagine the child want to go from area p to area q. Firstly he considers all the simple routes from p to q. For each route the child writes down the number, that is equal to the minimum number of animals among the route areas. Let's denote the largest of the written numbers as f(p, q). Finally, the child chooses one of the routes for which he writes down the value f(p, q).

After the child has visited the zoo, he thinks about the question: what is the average value of f(p, q) for all pairs p, q (p ≠ q)? Can you answer his question?

Input format:
The first line contains two integers n and m (2 ≤ n ≤ 105; 0 ≤ m ≤ 105). The second line contains n integers: a1, a2, ..., an (0 ≤ ai ≤ 105). Then follow m lines, each line contains two integers xi and yi (1 ≤ xi, yi ≤ n; xi ≠ yi), denoting the road between areas xi and yi.

All roads are bidirectional, each pair of areas is connected by at most one road.

Output format:
Output a real number — the value of $$\frac{\sum_{p,q,p\neq q} f(p,q)}{n(n-1)}$$.

The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 4.

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

Note:
Consider the first sample. There are 12 possible situations:

- p = 1, q = 3, f(p, q) = 10.
- p = 2, q = 3, f(p, q) = 20.
- p = 4, q = 3, f(p, q) = 30.
- p = 1, q = 2, f(p, q) = 10.
- p = 2, q = 4, f(p, q) = 20.
- p = 4, q = 1, f(p, q) = 10.

Another 6 cases are symmetrical to the above. The average is $$(10+20+30+10+20+10)\times 2\over 12 \approx 16.666667$$.

Consider the second sample. There are 6 possible situations:

- p = 1, q = 2, f(p, q) = 10.
- p = 2, q = 3, f(p, q) = 20.
- p = 1, q = 3, f(p, q) = 10.

Another 3 cases are symmetrical to the above. The average is $$(10+20+10)\times2\over6\approx13.333333$$.

Example input:
4 3
10 20 30 40
1 3
2 3
4 3

Example output:
16.666667

Example input:
3 3
10 20 30
1 2
2 3
3 1

Example output:
13.333333

Editorial:
The Child and Polygon
Contest: Codeforces Round 250 (Div. 2)
Difficulty rating: 2500
Tags: dp, geometry

This time our child has a simple polygon. He has to find the number of ways to split the polygon into non-degenerate triangles, each way must satisfy the following requirements:

- each vertex of each triangle is one of the polygon vertex;
- each side of the polygon must be the side of exactly one triangle;
- the area of intersection of every two triangles equals to zero, and the sum of all areas of triangles equals to the area of the polygon;
- each triangle must be completely inside the polygon;
- each side of each triangle must contain exactly two vertices of the polygon.

The picture below depicts an example of a correct splitting.

Please, help the child. Calculate the described number of ways modulo 1000000007 (109  +  7) for him.

Input format:
The first line contains one integer n (3 ≤ n ≤ 200) — the number of vertices of the polygon. Then follow n lines, each line containing two integers. The i-th line contains xi, yi (|xi|, |yi| ≤ 107) — the i-th vertex of the polygon in clockwise or counterclockwise order.

It's guaranteed that the polygon is simple.

Output format:
Output the number of ways modulo 1000000007 (109  +  7).

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

Note:
In the first sample, there are two possible splittings:

In the second sample, there are only one possible splitting:

Example input:
4
0 0
0 1
1 1
1 0

Example output:
2

Example input:
4
0 0
1 0
0 1
-1 0

Example output:
1

Editorial:
Dead Pixel
Contest: Codeforces Round 623 (Div. 2, based on VK Cup 2019-2020 - Elimination Round, Engine)
Difficulty rating: 800
Tags: implementation

Screen resolution of Polycarp's monitor is $$$a \times b$$$ pixels. Unfortunately, there is one dead pixel at his screen. It has coordinates $$$(x, y)$$$ ($$$0 \le x < a, 0 \le y < b$$$). You can consider columns of pixels to be numbered from $$$0$$$ to $$$a-1$$$, and rows — from $$$0$$$ to $$$b-1$$$.

Polycarp wants to open a rectangular window of maximal size, which doesn't contain the dead pixel. The boundaries of the window should be parallel to the sides of the screen.

Print the maximal area (in pixels) of a window that doesn't contain the dead pixel inside itself.

Input format:
In the first line you are given an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test. In the next lines you are given descriptions of $$$t$$$ test cases.

Each test case contains a single line which consists of $$$4$$$ integers $$$a, b, x$$$ and $$$y$$$ ($$$1 \le a, b \le 10^4$$$; $$$0 \le x < a$$$; $$$0 \le y < b$$$) — the resolution of the screen and the coordinates of a dead pixel. It is guaranteed that $$$a+b>2$$$ (e.g. $$$a=b=1$$$ is impossible).

Output format:
Print $$$t$$$ integers — the answers for each test case. Each answer should contain an integer equal to the maximal possible area (in pixels) of a rectangular window, that doesn't contain the dead pixel.

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

Note:
In the first test case, the screen resolution is $$$8 \times 8$$$, and the upper left pixel is a dead pixel. Here you can see one of two possible layouts of the maximal window.

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

Example output:
56
6
442
1
45
80

Editorial:
You can see that you should place the window in such a way so that the dead pixel is next to one of the borders of the screen: otherwise we can definitely increase the size of the window.
There are four possible ways to place the window right next to the dead pixel — you can place it below, above, to the left or to the right of the dead pixel.
• if you place the window to the left to the pixel, the maximal size of the screen will be $$$x \cdot b$$$;
• if you place the window to the right to the pixel, the maximal size of the screen will be $$$(a - 1 - x) \cdot b$$$;
• if you place the window above the pixel, the maximal size of the screen will be $$$a \cdot y$$$;
• if you place the window above the pixel, the maximal size of the screen will be $$$a \cdot (b - 1 - y)$$$.
These four cases can be united to one formula like $$$\max(\max(x, a-1-x) \cdot b, a \cdot \max(y, b-1-y))$$$.
Game
Contest: Codeforces Round 775 (Div. 2, based on Moscow Open Olympiad in Informatics)
Difficulty rating: 800
Tags: implementation

You are playing a very popular computer game. The next level consists of $$$n$$$ consecutive locations, numbered from $$$1$$$ to $$$n$$$, each of them containing either land or water. It is known that the first and last locations contain land, and for completing the level you have to move from the first location to the last. Also, if you become inside a location with water, you will die, so you can only move between locations with land.

You can jump between adjacent locations for free, as well as no more than once jump from any location with land $$$i$$$ to any location with land $$$i + x$$$, spending $$$x$$$ coins ($$$x \geq 0$$$).

Your task is to spend the minimum possible number of coins to move from the first location to the last one.

Note that this is always possible since both the first and last locations are the land locations.

Input format:
There are several test cases in the input data. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. This is followed by the test cases description.

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

The second line of the test case contains a sequence of integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 1$$$), where $$$a_i = 1$$$ means that the $$$i$$$-th location is the location with land, and $$$a_i = 0$$$ means that the $$$i$$$-th location is the location with water. It is guaranteed that $$$a_1 = 1$$$ and $$$a_n = 1$$$.

Output format:
For each test case print a single integer — the answer to the problem.

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

Note:
In the first test case, it is enough to make one free jump from the first location to the second one, which is also the last one, so the answer is $$$0$$$.

In the second test case, the only way to move from the first location to the last one is to jump between them, which will cost $$$4$$$ coins.

In the third test case, you can jump from the first location to the third for $$$2$$$ coins, and then jump to the fourth location for free, so the answer is $$$2$$$. It can be shown that this is the optimal way.

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

Example output:
0
4
2

Editorial:
It is easy to see that if there are no water locations, the answer is $$$0$$$. Otherwise, we should jump from the last accessible from the start land location to the first land location from which the finish is accessible. In order to find these locations, one can use two consecutive while loops, one increasing $$$l$$$ from $$$1$$$ until $$$a_{l + 1} = 0$$$, and the other one decreasing $$$r$$$ from $$$n$$$ until $$$a_{r - 1} = 0$$$. After the loops finish, we know that we should jump from the $$$l$$$-th location to the $$$r$$$-th at the cost of $$$r - l$$$.
Game of Ball Passing
Contest: Codeforces Round 775 (Div. 2, based on Moscow Open Olympiad in Informatics)
Difficulty rating: 1300
Tags: greedy, implementation

Daniel is watching a football team playing a game during their training session. They want to improve their passing skills during that session.

The game involves $$$n$$$ players, making multiple passes towards each other. Unfortunately, since the balls were moving too fast, after the session Daniel is unable to know how many balls were involved during the game. The only thing he knows is the number of passes delivered by each player during all the session.

Find the minimum possible amount of balls that were involved in the game.

Input format:
There are several test cases in the input data. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains one integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — the number of players.

The second line of the test case contains a sequence of integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$), where $$$a_i$$$ is the number of passes delivered by the $$$i$$$-th player.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

Output format:
For each test case print a single integer — the answer to the problem.

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

Note:
In the first test case, with the only ball, the game can go like this:

$$$2 \rightarrow 1 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 2$$$.

In the second test case, there is no possible way to play the game with only one ball. One possible way to play with two balls:

$$$2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1$$$.

$$$2 \rightarrow 3 \rightarrow 2 \rightarrow 1$$$

In the third example, there were no passes, so $$$0$$$ balls are possible.

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

Example output:
1
2
0
1

Editorial:
If $$$max(a) \cdot 2 \leq sum(a)$$$, we can always prove that we can only use one ball.
For other cases, the number of balls is determined by $$$2 \cdot max(a) - sum(a)$$$.
Space Navigation
Contest: Codeforces Round 699 (Div. 2)
Difficulty rating: 800
Tags: greedy, strings

You were dreaming that you are traveling to a planet named Planetforces on your personal spaceship. Unfortunately, its piloting system was corrupted and now you need to fix it in order to reach Planetforces.

Space can be represented as the $$$XY$$$ plane. You are starting at point $$$(0, 0)$$$, and Planetforces is located in point $$$(p_x, p_y)$$$.

The piloting system of your spaceship follows its list of orders which can be represented as a string $$$s$$$. The system reads $$$s$$$ from left to right. Suppose you are at point $$$(x, y)$$$ and current order is $$$s_i$$$:

- if $$$s_i = \text{U}$$$, you move to $$$(x, y + 1)$$$;
- if $$$s_i = \text{D}$$$, you move to $$$(x, y - 1)$$$;
- if $$$s_i = \text{R}$$$, you move to $$$(x + 1, y)$$$;
- if $$$s_i = \text{L}$$$, you move to $$$(x - 1, y)$$$.

Since string $$$s$$$ could be corrupted, there is a possibility that you won't reach Planetforces in the end. Fortunately, you can delete some orders from $$$s$$$ but you can't change their positions.

Can you delete several orders (possibly, zero) from $$$s$$$ in such a way, that you'll reach Planetforces after the system processes all orders?

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

Each test case consists of two lines. The first line in each test case contains two integers $$$p_x$$$ and $$$p_y$$$ ($$$-10^5 \le p_x, p_y \le 10^5$$$; $$$(p_x, p_y) \neq (0, 0)$$$) — the coordinates of Planetforces $$$(p_x, p_y)$$$.

The second line contains the string $$$s$$$ ($$$1 \le |s| \le 10^5$$$: $$$|s|$$$ is the length of string $$$s$$$) — the list of orders.

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

Output format:
For each test case, print "YES" if you can delete several orders (possibly, zero) from $$$s$$$ in such a way, that you'll reach Planetforces. Otherwise, print "NO". You can print each letter in any case (upper or lower).

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

Note:
In the first case, you don't need to modify $$$s$$$, since the given $$$s$$$ will bring you to Planetforces.

In the second case, you can delete orders $$$s_2$$$, $$$s_3$$$, $$$s_4$$$, $$$s_6$$$, $$$s_7$$$ and $$$s_8$$$, so $$$s$$$ becomes equal to "UR".

In the third test case, you have to delete order $$$s_9$$$, otherwise, you won't finish in the position of Planetforces.

Example input:
6
10 5
RRRRRRRRRRUUUUU
1 1
UDDDRLLL
-3 -5
LDLDLDDDR
1 2
LLLLUU
3 -2
RDULRLLDR
-1 6
RUDURUUUUR

Example output:
YES
YES
YES
NO
YES
NO

Editorial:
Hint 1: You can think of this problem as 2 independent 1D questions (one is up and down , and the other is left and right) instead of 1 2D question.
Hint 2: For each 1D part what is the interval of positions that you can reach and see if the end point is in this interval.
Hint 3: The interval of up and down is [-The count of D , The count of U] and the interval of left and right is [-The count of L , The count of R].
Two Subsequences
Contest: Codeforces Round 751 (Div. 2)
Difficulty rating: 800
Tags: implementation

You are given a string $$$s$$$. You need to find two non-empty strings $$$a$$$ and $$$b$$$ such that the following conditions are satisfied:

1. Strings $$$a$$$ and $$$b$$$ are both subsequences of $$$s$$$.
2. For each index $$$i$$$, character $$$s_i$$$ of string $$$s$$$ must belong to exactly one of strings $$$a$$$ or $$$b$$$.
3. String $$$a$$$ is lexicographically minimum possible; string $$$b$$$ may be any possible string.

Given string $$$s$$$, print any valid $$$a$$$ and $$$b$$$.

Reminder:

A string $$$a$$$ ($$$b$$$) is a subsequence of a string $$$s$$$ if $$$a$$$ ($$$b$$$) can be obtained from $$$s$$$ by deletion of several (possibly, zero) elements. For example, "dores", "cf", and "for" are subsequences of "codeforces", while "decor" and "fork" are not.

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

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

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). Description of the test cases follows.

The first and only line of each test case contains one string $$$s$$$ ($$$2 \le |s| \le 100$$$ where $$$|s|$$$ means the length of $$$s$$$). String $$$s$$$ consists of lowercase Latin letters.

Output format:
For each test case, print the strings $$$a$$$ and $$$b$$$ that satisfy the given conditions. If there are multiple answers, print any.

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

Note:
In the first test case, there are only two choices: either $$$a =$$$ f and $$$b = $$$ c or $$$a = $$$ c and $$$b = $$$ f. And $$$a = $$$c is lexicographically smaller than $$$a = $$$ f.

In the second test case, a is the only character in the string.

In the third test case, it can be proven that b is the lexicographically smallest subsequence of $$$s$$$. The second string can be of two variants; one of them is given here.

Example input:
3
fc
aaaa
thebrightboiler

Example output:
c f
a aaa
b therightboiler

Editorial:
Note that taking $$$a$$$ as minimum character in $$$s$$$ is always optimal ($$$a$$$ starts with minimum possible character and is prefix of any other longer string). In such case, $$$b$$$ is just all characters from $$$s$$$ except character from $$$a$$$.
Elevator
Contest: School Regional Team Contest, Saratov, 2011
Difficulty rating: 1000
Tags: brute force, implementation, math

A sky scraper with 1000 floors has been built in the city of N. It has modern superfast elevators to help to travel from one floor to another. Each elevator has two doors, the front one and the back one. If one goes in through the front door, he goes out through the back one and vice versa. The elevator has two rails numbered with numbers 1 and 2. Rail 1 is located to the left of the entrance to the front door (or correspondingly, to the right of the entrance to the back door). Rail 2 is located opposite it, to the right of the entrance to the front door and to the left of the entrance to the back door. We know that each person in the city of N holds at a rail with the strongest hand.

One day a VIP person visited the city and of course, he took a look at the skyscraper and took a ride in the elevator. We know the door through which he entered and the rail he was holding at. Now we need to determine as soon as possible whether he is left-handed or right-handed.

Input format:
The first line indicates the door through which the very important person entered the elevator. It contains "front" if the person enters the elevator through the front door and "back" if he entered the elevator through the back door. The second line contains integer a (1 ≤ a ≤ 2) which denotes the number of the rail at which the person was holding.

Output format:
Print character "R" if the VIP is right-handed or "L" if he is left-handed.

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

Example input:
front
1

Example output:
L

Editorial:
Quiz League
Contest: School Regional Team Contest, Saratov, 2011
Difficulty rating: 1100
Tags: implementation

A team quiz game called "What? Where? When?" is very popular in Berland. The game is centered on two teams competing. They are the team of six Experts versus the team of the Audience. A person from the audience asks a question and the experts are allowed a minute on brainstorming and finding the right answer to the question. All it takes to answer a typical question is general knowledge and common logic. The question sent be the audience are in envelops lain out in a circle on a round table. Each envelop is marked by the name of the asker's town. Each question is positioned in a separate sector. In the centre of the table is a spinning arrow. Thus, the table rather resembles a roulette table with no ball but with a spinning arrow instead. The host sets off the spinning arrow to choose a question for the experts: when the arrow stops spinning, the question it is pointing at is chosen. If the arrow points at the question that has already been asked, the host chooses the next unanswered question in the clockwise direction. Your task is to determine which will be the number of the next asked question if the arrow points at sector number k.

Input format:
The first line contains two positive integers n and k (1 ≤ n ≤ 1000 and 1 ≤ k ≤ n) — the numbers of sectors on the table and the number of the sector where the arrow is pointing. The second line contains n numbers: ai = 0 if the question from sector i has already been asked and ai = 1 if the question from sector i hasn't been asked yet (1 ≤ i ≤ n). The sectors are given in the clockwise order, the first sector follows after the n-th one.

Output format:
Print the single number — the number of the sector containing the question the experts will be asked. It is guaranteed that the answer exists, that is that not all the questions have already been asked.

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

Example input:
5 5
0 1 0 1 0

Example output:
2

Example input:
2 1
1 1

Example output:
1

Editorial: