1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Easy Scheduling
Contest: ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 1200
Tags: implementation, math

Eonathan Eostar decided to learn the magic of multiprocessor systems. He has a full binary tree of tasks with height $$$h$$$. In the beginning, there is only one ready task in the tree — the task in the root. At each moment of time, $$$p$$$ processes choose at most $$$p$$$ ready tasks and perform them. After that, tasks whose parents were performed become ready for the next moment of time. Once the task becomes ready, it stays ready until it is performed.

You shall calculate the smallest number of time moments the system needs to perform all the tasks.

Input format:
The first line of the input contains the number of tests $$$t$$$ ($$$1 \leq t \leq 5\cdot 10^5$$$). Each of the next $$$t$$$ lines contains the description of a test. A test is described by two integers $$$h$$$ ($$$1 \leq h \leq 50$$$) and $$$p$$$ ($$$1 \leq p \leq 10^4$$$) — the height of the full binary tree and the number of processes. It is guaranteed that all the tests are different.

Output format:
For each test output one integer on a separate line — the smallest number of time moments the system needs to perform all the tasks.

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

Note:
Let us consider the second test from the sample input. There is a full binary tree of height $$$3$$$ and there are two processes. At the first moment of time, there is only one ready task, $$$1$$$, and $$$p_1$$$ performs it. At the second moment of time, there are two ready tasks, $$$2$$$ and $$$3$$$, and the processes perform them. At the third moment of time, there are four ready tasks, $$$4$$$, $$$5$$$, $$$6$$$, and $$$7$$$, and $$$p_1$$$ performs $$$6$$$ and $$$p_2$$$ performs $$$5$$$. At the fourth moment of time, there are two ready tasks, $$$4$$$ and $$$7$$$, and the processes perform them. Thus, the system spends $$$4$$$ moments of time to perform all the tasks.

Example input:
3
3 1
3 2
10 6

Example output:
7
4
173

Editorial:
Framing Pictures
Contest: ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2900
Tags: geometry

Life has been discovered on Venus! What is more, the life forms appear to be convex polygons. An international consortium is designing a probe to send to Venus to take pictures, but they need to estimate the bandwidth needed to send back pictures.

When the probe takes a picture of a life form and wishes to send it back to Earth, the bandwidth required is proportional to the area of the bounding box (in other words, the smallest axis-aligned rectangle that contains the life-form). The shape and size of the life forms are known, but the orientation relative to the camera is random. You must thus determine the expected (average) area of the bounding box across all orientations.

Input format:
The input describes the shape of a life form as a convex polygon in two dimensions.

The first line of input contains an integer $$$n$$$ ($$$3 \le n \le 200\,000$$$) — the number of vertices. The remaining $$$n$$$ lines each contain two integers $$$x$$$ and $$$y$$$ ($$$-10^9 \le x, y \le 10^9$$$) — the coordinates of a vertex. The vertices are given in counterclockwise order, and no three vertices lie on a straight line.

Output format:
Output a single line containing the expected area of the bounding box of the polygon. Your answer should have an absolute or relative error of at most $$$10^{-6}$$$.

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

Note:
The pictures show example life forms and various camera orientations.

Example input:
4
0 0
10 0
10 10
0 10

Example output:
163.661977237

Example input:
5
0 0
10 0
15 8
5 20
-5 7

Example output:
365.666028588

Editorial:
Game of Chance
Contest: ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 3500
Tags: math, probabilities

The King wants to marry off his daughter, and he wants her husband to have the greatest innate luckiness possible. To find such a person he decided to hold a heads-or-tails tournament.

If person $$$A$$$ with luckiness $$$x$$$ and person $$$B$$$ with luckiness $$$y$$$ play heads-or-tails against each other, person $$$A$$$ wins with probability $$$x/(x+y)$$$.

The tournament has several rounds. Each round some participants are split into pairs. Each pair plays against each other, and the loser leaves the tournament.

The participants are numbered from $$$1$$$ to $$$n$$$. During the first round, a number $$$k$$$ ($$$1 \le k \le n$$$) is selected such that $$$n-k/2$$$ is a power of $$$2$$$ (such $$$k$$$ always exists and is unique). Only participants numbered from $$$1$$$ to $$$k$$$ take part in the first round. It ensures that in all other rounds the number of participants is the power of $$$2$$$.

During other rounds, all the participants who still have not left the tournament take part. If during some round, participants numbered $$$p_1 < \ldots < p_{2m}$$$ take part, then they are split into pairs in the following manner: participant $$$p_{2i-1}$$$ plays against participant $$$p_{2i}$$$ for each $$$i$$$ from $$$1$$$ to $$$m$$$.

The rounds are held until only one participant is left. He is declared the winner of the tournament and he will marry the King's daughter. The princess can't wait to find out who is her future husband. She asked every participant to tell her his luckiness. Assuming they did not lie, she wants to know the probability of each participant winning the tournament. As you are the best friend of the princess, she asks you to help her.

Input format:
The first line of the input contains the number of participants, $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$). The second line of the input contains $$$n$$$ integer numbers, $$$a_1, \ldots, a_{n}$$$ ($$$1 \le a_i \le 10^9$$$). The luckiness of the $$$i$$$-th participant equals to $$$a_i$$$.

Output format:
Print $$$n$$$ numbers $$$p_i$$$. The $$$i$$$-th number should be the probability of the $$$i$$$-th participant winning the tournament. The absolute error of your answer must not exceed $$$10^{-9}$$$.

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

Note:
Here is an example of a tournament bracket, showing the winning probability in each pair.

Example input:
5
1 4 1 1 4

Example output:
0.026 0.3584 0.0676 0.0616 0.4864

Editorial:
Higher Order Functions
Contest: ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 1700
Tags: implementation, strings

Helen studies functional programming and she is fascinated with a concept of higher order functions — functions that are taking other functions as parameters. She decides to generalize the concept of the function order and to test it on some examples.

For her study, she defines a simple grammar of types. In her grammar, a type non-terminal $$$T$$$ is defined as one of the following grammar productions, together with $$$\textrm{order}(T)$$$, defining an order of the corresponding type:

- "()" is a unit type, $$$\textrm{order}(\textrm{"}\texttt{()}\textrm{"}) = 0$$$.
- "(" $$$T$$$ ")" is a parenthesized type, $$$\textrm{order}(\textrm{"}\texttt{(}\textrm{"}\,T\,\textrm{"}\texttt{)}\textrm{"}) = \textrm{order}(T)$$$.
- $$$T_1$$$ "->" $$$T_2$$$ is a functional type, $$$\textrm{order}(T_1\,\textrm{"}\texttt{->}\textrm{"}\,T_2) = max(\textrm{order}(T_1) + 1, \textrm{order}(T_2))$$$. The function constructor $$$T_1$$$ "->" $$$T_2$$$ is right-to-left associative, so the type "()->()->()" is the same as the type "()->(()->())" of a function returning a function, and it has an order of $$$1$$$. While "(()->())->()" is a function that has an order-1 type "(()->())" as a parameter, and it has an order of $$$2$$$.

Helen asks for your help in writing a program that computes an order of the given type.

Input format:
The single line of the input contains a string consisting of characters '(', ')', '-', and '>' that describes a type that is valid according to the grammar from the problem statement. The length of the line is at most $$$10^4$$$ characters.

Output format:
Print a single integer — the order of the given type.

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

Example input:
()

Example output:
0

Example input:
()->()

Example output:
1

Editorial:
Interactive Rays
Contest: ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 3300
Tags: geometry, interactive

This is an interactive problem.

Your goal is to find a circle on a plane by shooting rays and getting the distance to the circle as a result.

Interactor has three hidden integer parameters that are determined in advance for each test, but which you don't know — $$$x_c$$$, $$$y_c$$$, and $$$r_c$$$. $$$(x_c, y_c)$$$ are coordinates of the circle's center and $$$r_c$$$ is its radius. The absolute values of $$$x_c$$$, $$$y_c$$$, and $$$r_c$$$ do not exceed $$$10^5$$$, and $$$1 \leq r_c \leq \sqrt{x_c^2 + y_c^2} - 1$$$.

You can shoot rays that extend from the origin $$$(0,0)$$$ and go via a point $$$(x_q,y_q)$$$ with the integer coordinates you specify. For each ray, you get a distance from the ray to the circle or $$$0$$$ if the ray intersects the circle.

Interaction format:
The interaction starts with your program printing a query to the standard output and finishes when your program finds and prints the answer to the problem.

Each query has a form of "? $$$x_q$$$ $$$y_q$$$", where $$$x_q$$$ and $$$y_q$$$ are integers ($$$|x_q|, |y_q| \le 10^6$$$; $$$x_q \ne 0$$$ or $$$y_q \ne 0$$$).

The interactor outputs a line with a single floating-point number — the distance between a query ray and a circle that is precise to $$$10^{-10}$$$ by an absolute value.

Your program can make the next query, read the output, and so on. You are allowed to do at most $$$60$$$ queries. At the end of the interaction, print the answer line "! $$$x_c$$$ $$$y_c$$$ $$$r_c$$$", flush the output and exit.

Note, that the output of the interactor is actually rounded to the 10-th digit after a decimal point, so if you are stress-testing your solution locally, make sure that you also perform the corresponding rounding.

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

Note:
Illustration of the queries from the example interaction.

Example input:
? 0 -10

? 10 -10

? 10 0

? 10 10

? 10 20

? 10 30

! 20 10 10

Example output:
12.360679775

11.2132034356

0.0

0.0

3.416407865

5.8113883008

Editorial:
Just Kingdom
Contest: ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 3100
Tags: brute force, data structures, dfs and similar

The Just Kingdom is ruled by a king and his $$$n$$$ lords, numbered $$$1$$$ to $$$n$$$. Each of the lords is a vassal of some overlord, who might be the king himself, or a different lord closer to the king. The king, and all his lords, are just and kind.

Each lord has certain needs, which can be expressed as a certain amount of money they need. However, if a lord, or the king, receives any money, they will first split it equally between all their vassals who still have unmet needs. Only if all the needs of all their vassals are met, they will take the money to fulfill their own needs. If there is any money left over, they will return the excess to their overlord (who follows the standard procedure for distributing money).

At the beginning of the year, the king receives a certain sum of tax money and proceeds to split it according to the rules above. If the amount of tax money is greater than the total needs of all the lords, the procedure guarantees everybody's needs will be fulfilled, and the excess money will be left with the king. However, if there is not enough money, some lords will not have their needs met.

For each lord, determine the minimum amount of tax money the king has to receive so that this lord's needs are met.

Input format:
The first line of the input contains the number of lords $$$n$$$ ($$$0 \le n \le 3 \cdot 10^5$$$). Each of the next $$$n$$$ lines describes one of the lords. The $$$i$$$-th line contains two integers: $$$o_i$$$ ($$$0 \le o_i < i$$$) — the index of the overlord of the $$$i$$$-th lord (with zero meaning the king is the overlord), and $$$m_i$$$ ($$$1 \le m_i \le 10^6$$$) — the amount of money the $$$i$$$-th lord needs.

Output format:
Print $$$n$$$ integer numbers $$$t_i$$$. The $$$i$$$-th number should be the minimum integer amount of tax money the king has to receive for which the needs of the $$$i$$$-th lord will be met.

Constraints:
Time limit: 5.0 s
Memory limit: 1024.0 MB

Note:
In the sample input, if the king receives $$$5$$$ units of tax money, he will split it equally between his vassals — the lords $$$1$$$, $$$3$$$, and $$$5$$$, with each receiving $$$\frac{5}{3}$$$ of money.

Lord $$$1$$$ will split the money equally between his vassals — $$$2$$$ and $$$4$$$, with each receiving $$$\frac{5}{6}$$$. Lord $$$5$$$ will keep the money (having no vassals). Lord $$$3$$$ will keep $$$1$$$ unit of money, and give the remaining $$$\frac{2}{3}$$$ to the king. The king will then split the $$$\frac{2}{3}$$$ between the vassals with unmet needs — $$$1$$$ and $$$5$$$, passing $$$\frac{1}{3}$$$ to each. Lord $$$5$$$ will keep the extra cash (now having a total of $$$2$$$, still not enough to meet his needs). Lord $$$1$$$ will split it equally between his vassals, and the extra $$$\frac{1}{6}$$$ will be enough to meet the needs of lord $$$4$$$.

Example input:
5
0 2
1 2
0 1
1 1
0 5

Example output:
11
7
3
5
11

Editorial:
Kingdom of Islands
Contest: ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2800
Tags: brute force, graphs, implementation

The Kingdom of Islands consists of $$$p$$$ islands. As the king, you rule over the whole kingdom, while each island is ruled over by one or several jarls under your rule. In total, there are $$$n$$$ jarls under your jurisdiction.

Each island of the kingdom has its own strong traditions, so jarls that rule over the same island support each other and never have conflicts. The downsides of such strength are cultural conflicts between people inhabiting different islands. Thus, two jarls that rule over different islands are in conflict.

However, recent years brought a few changes to traditional relations between the jarls. To your knowledge, there are exactly $$$k$$$ pairs of jarls such that relationships between two jarls in the pair are different from the traditional. That is, if two jarls of the pair you know rule over the same island, these jarls are in conflict. If they rule over different islands, then they overcome cultural disagreement and there is no conflict between them anymore.

As a true responsible king, you are worried about whether the kingdom is close to a major conflict. In order to estimate the current situation, you would like to find the largest possible group of jarls such that every two jarls in the group are in conflict.

Input format:
The first line of the input consists of two integers $$$p$$$ and $$$n$$$ ($$$1 \le p \le n \le 10^5$$$; $$$1 \le p \le 10^4$$$).

The second line consists of $$$n$$$ integers $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le s_i \le p$$$). The integer $$$s_i$$$ denotes that the $$$i$$$-th jarl rules over the island number $$$s_i$$$. It is guaranteed that each island is ruled by at least one jarl.

The third line consists of a single integer $$$k$$$ ($$$0 \le k \le 20$$$).

Then $$$k$$$ lines follow. The $$$j$$$-th of these lines consists of two distinct integers $$$a_j$$$ and $$$b_j$$$ ($$$1 \le a_j < b_j \le n$$$), denoting that the relation between the $$$a_j$$$-th jarl and the $$$b_j$$$-th jarl differs from traditional. It is guaranteed that no pair of jarls appears twice in this list.

Output format:
In the first line print a single integer $$$q$$$ between $$$1$$$ and $$$n$$$ — the largest possible number of jarls in a pairwise conflicting group. In the second line print $$$q$$$ distinct integers between $$$1$$$ and $$$n$$$ — the numbers of jarls in the group. The numbers of jarls can be printed in any order.

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

Note:
The conflict graph for the last sample testcase is given below. Each circle represents an island.

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

Example output:
3
1 4 2

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

Example output:
3
2 4 3

Editorial:
Labyrinth
Contest: ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2400
Tags: binary search, dsu, greedy

In a dream, Lucy found herself in a labyrinth. This labyrinth consists of $$$n$$$ rooms, connected by $$$m$$$ passages ($$$i$$$-th passage is $$$w_i$$$ cm wide). Each passage can be traversed in both directions. It is guaranteed that it is possible to get from any room to any other room. But this is not an ordinary labyrinth — each room in this labyrinth contains a magic candy. When Lucy eats this magic candy, she is getting wider. Specifically, if she eats candy from room $$$i$$$ she becomes wider by $$$c_i$$$ cm. Note that she is not obliged to eat candy the first time she visits a particular room, but she can eat each candy only once.

Unfortunately, passages in this labyrinth are pretty narrow, so after eating some candy, Lucy can get too wide and will not be able to traverse them — her width should not be greater than the width of the corresponding passage.

Lucy starts her journey in a room number $$$1$$$. She wants to eat all the candies. After that, she will just wake up, so she does not have to be able to return to the room $$$1$$$. She realizes that with her current width, she may not be able to do so, so she plans a workout before embarking on her journey. Lucy wants to know if it is possible to start with some positive width and still eat all the candies. If yes, then what is the maximal starting width with which it is possible.

Input format:
The first line contains two integers, $$$n$$$ and $$$m$$$ ($$$2 \le n \le 10^5; n - 1 \le m \le 10^5$$$) — the number of rooms and the number of passages.

The second line contains $$$n$$$ integers — $$$c_i$$$ ($$$1 \le c_i \le 10^9$$$).

Next $$$m$$$ lines contain three integers each — $$$a_i$$$, $$$b_i$$$ and $$$w_i$$$ ($$$1 \le a_i, b_i \le n; a_i \ne b_i; 1 \le w_i \le 10^9$$$) describing passage that connects rooms $$$a_i$$$ and $$$b_i$$$ and is $$$w_i$$$ cm wide. It is guaranteed that the resulting labyrinth is connected and there is at most one passage between any pair of rooms.

Output format:
If it is possible to eat all the candies, output the maximal possible starting width, otherwise output $$$-1$$$.

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

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

Example output:
3

Example input:
2 1
1 1
1 2 1

Example output:
-1

Editorial:
Forked!
Contest: Codeforces Round 914 (Div. 2)
Difficulty rating: 900
Tags: brute force, implementation

Lunchbox is done with playing chess! His queen and king just got forked again!

In chess, a fork is when a knight attacks two pieces of higher value, commonly the king and the queen. Lunchbox knows that knights can be tricky, and in the version of chess that he is playing, knights are even trickier: instead of moving $$$1$$$ tile in one direction and $$$2$$$ tiles in the other, knights in Lunchbox's modified game move $$$a$$$ tiles in one direction and $$$b$$$ tiles in the other.

Lunchbox is playing chess on an infinite chessboard which contains all cells $$$(x,y)$$$ where $$$x$$$ and $$$y$$$ are (possibly negative) integers. Lunchbox's king and queen are placed on cells $$$(x_K,y_K)$$$ and $$$(x_Q,y_Q)$$$ respectively. Find the number of positions such that if a knight was placed on that cell, it would attack both the king and queen.

Input format:
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 10^8$$$) — describing the possible moves of the knight.

The second line of each test case contains two integers $$$x_K$$$ and $$$y_K$$$ ($$$0 \le x_K, y_K \le 10^8$$$) — the position of Lunchbox's king.

The third line in a test case contains $$$x_Q$$$ and $$$y_Q$$$ ($$$0 \le x_Q, y_Q \le 10^8$$$) — the position of Lunchbox's queen.

It is guaranteed that Lunchbox's queen and king will occupy different cells. That is, $$$(x_K,y_K) \neq (x_Q,y_Q)$$$.

Output format:
For each test case, output the number of positions on an infinite chessboard such that a knight can attack both the king and the queen.

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

Note:
In the first test case, the knight can move 2 squares in one direction and 1 square in the other (it is essentially the same as the knight in standard chess). A knight placed on $$$(2, 1)$$$ or $$$(1, 2)$$$ would attack both the king and queen.

Example of a knight placement that forks the queen and king in the first test case. The squares that the knight attacks are highlighted in red.

In the second test case, a knight placed on $$$(2, 2)$$$ would attack both the king and queen.

Example of a knight placement that does not fork the queen and king in the second test case. The knight attacks the king but not the queen.

In the third test case, a knight placed on $$$(4, 4)$$$ or $$$(4, -4)$$$ would attack both the king and queen.

In the fourth test case, there are no positions where the knight can attack both the king and the queen.

(Credits to EnDeRBeaT for the nice images)

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

Example output:
2
1
2
0

Editorial:
Collecting Game
Contest: Codeforces Round 914 (Div. 2)
Difficulty rating: 1100
Tags: binary search, dp, greedy, sortings, two pointers

You are given an array $$$a$$$ of $$$n$$$ positive integers and a score. If your score is greater than or equal to $$$a_i$$$, then you can increase your score by $$$a_i$$$ and remove $$$a_i$$$ from the array.

For each index $$$i$$$, output the maximum number of additional array elements that you can remove if you remove $$$a_i$$$ and then set your score to $$$a_i$$$. Note that the removal of $$$a_i$$$ should not be counted in the answer.

Input format:
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 5000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array.

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

Output format:
For each test case, output $$$n$$$ integers, the $$$i$$$-th of which denotes the maximum number of additional array elements that you can remove if you remove $$$a_i$$$ from the array and then set your score to $$$a_i$$$.

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

Note:
In the first test case, the answers are as follows:

If we start with $$$i=4$$$, our initial score is $$$a_4=4$$$ and $$$a=[20,5,1,2]$$$. We can remove $$$3$$$ additional elements in the following order:

1. Since $$$4 \ge 1$$$, we can remove $$$1$$$ and our score becomes $$$5$$$. After this, $$$a=[20,5,2]$$$.
2. Since $$$5 \ge 5$$$, we can remove $$$5$$$ and our score becomes $$$10$$$. After this, $$$a=[20,2]$$$.
3. Since $$$10 \ge 2$$$, we can remove $$$2$$$ and our score becomes $$$12$$$. After this, $$$a=[20]$$$.

If we start with $$$i=1$$$ we can remove all remaining elements in the array, so the answer is $$$4$$$.

If we start with $$$i=2$$$, we can remove $$$3$$$ additional elements in the following order: $$$1$$$, $$$4$$$, $$$2$$$.

If we start with $$$i=3$$$, we can remove no additional elements.

If we start with $$$i=5$$$, we can remove $$$1$$$ additional element: $$$1$$$.

Example input:
4
5
20 5 1 4 2
3
1434 7 1442
1
1
5
999999999 999999999 999999999 1000000000 1000000000

Example output:
4 3 0 3 1 
1 0 2 
0 
4 4 4 4 4

Editorial: