1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Yuhao and a Parenthesis
Contest: Hello 2019
Difficulty rating: 1400
Tags: greedy, implementation

One day, Yuhao came across a problem about checking if some bracket sequences are correct bracket sequences.

A bracket sequence is any non-empty sequence of opening and closing parentheses. A bracket sequence is called a correct bracket sequence if it's possible to obtain a correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, the sequences "(())()", "()" and "(()(()))" are correct, while the bracket sequences ")(", "(()" and "(()))(" are not correct.

Yuhao found this problem too simple for him so he decided to make the problem harder. You are given many (not necessarily correct) bracket sequences. The task is to connect some of them into ordered pairs so that each bracket sequence occurs in at most one pair and the concatenation of the bracket sequences in each pair is a correct bracket sequence. The goal is to create as many pairs as possible.

This problem unfortunately turned out to be too difficult for Yuhao. Can you help him and solve it?

Input format:
The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of bracket sequences.

Each of the following $$$n$$$ lines contains one bracket sequence — a non-empty string which consists only of characters "(" and ")".

The sum of lengths of all bracket sequences in the input is at most $$$5 \cdot 10^5$$$.

Note that a bracket sequence may appear in the input multiple times. In this case, you can use each copy of the sequence separately. Also note that the order in which strings appear in the input doesn't matter.

Output format:
Print a single integer — the maximum number of pairs which can be made, adhering to the conditions in the statement.

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

Note:
In the first example, it's optimal to construct two pairs: "((     )())" and "(     )".

Example input:
7
)())
)
((
((
(
)
)

Example output:
2

Example input:
4
(
((
(((
(())

Example output:
0

Editorial:
It turns out that each bracket sequence can be described by a pair $$$(a, b)$$$, where $$$a$$$ and $$$b$$$ are the minimal non-negative integers such that after adding $$$a$$$ opening parentheses "(" to the left of the string and $$$b$$$ closing parentheses ")" to the right of the string it becomes a correct bracket sequence. These numbers can be easily found with a single loop.
If $$$a \neq 0$$$ and $$$b \neq 0$$$, we cannot pair this string with any other string, because it needs brackets on its both sides.
If $$$a=b=0$$$, then this string is a correct bracket sequence and can be paired with any other correct bracket sequence. If there are $$$k$$$ such strings, then $$$\left\lfloor \frac{k}{2} \right\rfloor$$$ pairs can be formed.
If we want to concatenate two other bracket sequences (say, $$$i$$$-th and $$$j$$$-th) in order to produce a correct bracket sequence, the excess of the opening parentheses in the $$$i$$$-th sequence must equal the excess of the closing parentheses in the $$$j$$$-th sequence; that is, $$$b_i = a_j$$$. This allows us to pair the sequences greedily.
Makoto and a Blackboard
Contest: Hello 2019
Difficulty rating: 2200
Tags: dp, math, number theory, probabilities

Makoto has a big blackboard with a positive integer $$$n$$$ written on it. He will perform the following action exactly $$$k$$$ times:

Suppose the number currently written on the blackboard is $$$v$$$. He will randomly pick one of the divisors of $$$v$$$ (possibly $$$1$$$ and $$$v$$$) and replace $$$v$$$ with this divisor. As Makoto uses his famous random number generator (RNG) and as he always uses $$$58$$$ as his generator seed, each divisor is guaranteed to be chosen with equal probability.

He now wonders what is the expected value of the number written on the blackboard after $$$k$$$ steps.

It can be shown that this value can be represented as $$$\frac{P}{Q}$$$ where $$$P$$$ and $$$Q$$$ are coprime integers and $$$Q \not\equiv 0 \pmod{10^9+7}$$$. Print the value of $$$P \cdot Q^{-1}$$$ modulo $$$10^9+7$$$.

Input format:
The only line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^{15}$$$, $$$1 \leq k \leq 10^4$$$).

Output format:
Print a single integer — the expected value of the number on the blackboard after $$$k$$$ steps as $$$P \cdot Q^{-1} \pmod{10^9+7}$$$ for $$$P$$$, $$$Q$$$ defined above.

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

Note:
In the first example, after one step, the number written on the blackboard is $$$1$$$, $$$2$$$, $$$3$$$ or $$$6$$$ — each occurring with equal probability. Hence, the answer is $$$\frac{1+2+3+6}{4}=3$$$.

In the second example, the answer is equal to $$$1 \cdot \frac{9}{16}+2 \cdot \frac{3}{16}+3 \cdot \frac{3}{16}+6 \cdot \frac{1}{16}=\frac{15}{8}$$$.

Example input:
6 1

Example output:
3

Example input:
6 2

Example output:
875000008

Editorial:
How to solve the problem if $$$n$$$ is a prime power $$$p^{\alpha}$$$? We can simply use dynamic programming. Let $$$DP_{i, j}$$$ denote the probability that after $$$i$$$ steps the current number on the blackboard is $$$p^j$$$. At the beginning, $$$DP_{0, \alpha} = 1$$$. The transitions in DP are rather straightforward. The expected value of the number on the blackboard is then $$$$$$ \sum_{j=0}^{\alpha} DP_{k, j} p^j. $$$$$$
What if $$$n$$$ is not a prime power? We can observe that the result is multiplicative on $$$n$$$. Therefore, we factorize $$$n = p_1^{\alpha_1} p_2^{\alpha_k} \dots p_\ell^{\alpha_\ell}$$$, apply the solution above for each prime power $$$p_1^{\alpha_1}$$$ through $$$p_\ell^{\alpha_\ell}$$$, and eventually multiply the results.
Another problem is that we need to write a single integer modulo $$$10^9+7$$$ even though the answer is a rational number. To cope with this, we notice that $$$10^9+7$$$ is prime. Therefore, thanks to the Fermat Little Theorem, dividing by some number $$$x$$$ is equivalent to multiplying by $$$x^{10^9+5}$$$, modulo $$$10^9+7$$$. We use the quick exponentiation to compute the results.
The overall complexity is $$$O(\sqrt{n}+k \cdot \log n)$$$.
Hashing Trees
Contest: Codeforces Round 453 (Div. 1)
Difficulty rating: 1500
Tags: constructive algorithms, trees

Sasha is taking part in a programming competition. In one of the problems she should check if some rooted trees are isomorphic or not. She has never seen this problem before, but, being an experienced participant, she guessed that she should match trees to some sequences and then compare these sequences instead of trees. Sasha wants to match each tree with a sequence a0, a1, ..., ah, where h is the height of the tree, and ai equals to the number of vertices that are at distance of i edges from root.

Unfortunately, this time Sasha's intuition was wrong, and there could be several trees matching the same sequence. To show it, you need to write a program that, given the sequence ai, builds two non-isomorphic rooted trees that match that sequence, or determines that there is only one such tree.

Two rooted trees are isomorphic, if you can reenumerate the vertices of the first one in such a way, that the index of the root becomes equal the index of the root of the second tree, and these two trees become equal.

The height of a rooted tree is the maximum number of edges on a path from the root to any other vertex.

Input format:
The first line contains a single integer h (2 ≤ h ≤ 105) — the height of the tree.

The second line contains h + 1 integers — the sequence a0, a1, ..., ah (1 ≤ ai ≤ 2·105). The sum of all ai does not exceed 2·105. It is guaranteed that there is at least one tree matching this sequence.

Output format:
If there is only one tree matching this sequence, print "perfect".

Otherwise print "ambiguous" in the first line. In the second and in the third line print descriptions of two trees in the following format: in one line print $$\sum_{i=0}^{h} a_i$$ integers, the k-th of them should be the parent of vertex k or be equal to zero, if the k-th vertex is the root.

These treese should be non-isomorphic and should match the given sequence.

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

Note:
The only tree in the first example and the two printed trees from the second example are shown on the picture:

Example input:
2
1 1 1

Example output:
perfect

Example input:
2
1 2 2

Example output:
ambiguous
0 1 1 3 3
0 1 1 3 2

Editorial:
There are many ways to solve the problem. First of all you should build any single tree. To do this, you first build the longest path from the root and then attach remained vertices on proper heights. Thus each vertex is either on the longest path or has parent on this path. To build the second tree you should use different vertices from previous levels during construction to make it different from first tree. This is always possible if there are two consecutive ai > 1. Otherwise the tree is determined uniquely by ai sequence.
Weighting a Tree
Contest: Codeforces Round 453 (Div. 1)
Difficulty rating: 2700
Tags: constructive algorithms, dfs and similar, graphs

You are given a connected undirected graph with n vertices and m edges. The vertices are enumerated from 1 to n.

You are given n integers c1, c2, ..., cn, each of them is between  - n and n, inclusive. It is also guaranteed that the parity of cv equals the parity of degree of vertex v. The degree of a vertex is the number of edges connected to it.

You are to write a weight between  - 2·n2 and 2·n2 (inclusive) on each edge in such a way, that for each vertex v the sum of weights on edges connected to this vertex is equal to cv, or determine that this is impossible.

Input format:
The first line contains two integers n and m (2 ≤ n ≤ 105, n - 1 ≤ m ≤ 105) — the number of vertices and the number of edges.

The next line contains n integers c1, c2, ..., cn ( - n ≤ ci ≤ n), where ci is the required sum of weights of edges connected to vertex i. It is guaranteed that the parity of ci equals the parity of degree of vertex i.

The next m lines describe edges of the graph. The i-th of these lines contains two integers ai and bi (1 ≤ ai, bi ≤ n; ai ≠ bi), meaning that the i-th edge connects vertices ai and bi.

It is guaranteed that the given graph is connected and does not contain loops and multiple edges.

Output format:
If there is no solution, print "NO".

Otherwise print "YES" and then m lines, the i-th of them is the weight of the i-th edge wi ( - 2·n2 ≤ wi ≤ 2·n2).

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

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

Example output:
YES
1
1
1

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

Example output:
YES
-1
1
1

Editorial:
Let's solve two cases.
First case is when graph is the bipartite graph
Then the sum of weights of the left part should be equal to the sum of weights of the right part (because each edge will bring an equal contribution to the sums of both part).
We will leave any spanning tree of this graph, then for it the solution is unique (take the edges entering the leafs, their weights are uniquely determined, subtract weights from weights of the second ends of this edges, delete the leafs, recursively) this solution can be found with dfs, then in the end, the root will has weight 0 (because sum of weights of the left part equal to the sum of weights of the right part) Thus, the answer exists when the sum of the weights of the left part is equal to the sum of the weights of the right part.
Second case when graph has the odd cycle.
We find an odd cycle, root the tree for any of its vertices, solve the tree. Then, we add to the weights of the edges of the cycle adjacent to the root minus its weight divided by 2 (it is even, because it is the sum of the weights of all vertices (with different signs) equal to the sum of the degrees of vertices by modulo 2). , and for all others we alternate the signs with which we add this value, then for all vertices except the root the sum does not change, but for the root we get the required value.
Example code: https://pastebin.com/b2bGp4Bh
Save the problem!
Contest: MemSQL Start[c]UP 3.0 - Round 2 (onsite finalists)
Difficulty rating: 1400
Tags: constructive algorithms

Attention: we lost all the test cases for this problem, so instead of solving the problem, we need you to generate test cases. We're going to give you the answer, and you need to print a test case that produces the given answer. The original problem is in the following paragraph.

People don't use cash as often as they used to. Having a credit card solves some of the hassles of cash, such as having to receive change when you can't form the exact amount of money needed to purchase an item. Typically cashiers will give you as few coins as possible in change, but they don't have to. For example, if your change is 30 cents, a cashier could give you a 5 cent piece and a 25 cent piece, or they could give you three 10 cent pieces, or ten 1 cent pieces, two 5 cent pieces, and one 10 cent piece. Altogether there are 18 different ways to make 30 cents using only 1 cent pieces, 5 cent pieces, 10 cent pieces, and 25 cent pieces. Two ways are considered different if they contain a different number of at least one type of coin. Given the denominations of the coins and an amount of change to be made, how many different ways are there to make change?

As we mentioned before, we lost all the test cases for this problem, so we're actually going to give you the number of ways, and want you to produce a test case for which the number of ways is the given number. There could be many ways to achieve this (we guarantee there's always at least one), so you can print any, as long as it meets the constraints described below.

Input format:
Input will consist of a single integer A (1 ≤ A ≤ 105), the desired number of ways.

Output format:
In the first line print integers N and M (1 ≤ N ≤ 106, 1 ≤ M ≤ 10), the amount of change to be made, and the number of denominations, respectively.

Then print M integers D1, D2, ..., DM (1 ≤ Di ≤ 106), the denominations of the coins. All denominations must be distinct: for any i ≠ j we must have Di ≠ Dj.

If there are multiple tests, print any of them. You can print denominations in atbitrary order.

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

Example input:
18

Example output:
30 4
1 5 10 25

Example input:
3

Example output:
20 2
5 2

Editorial:
The simplest solution is to make the denominations always {1, 2}, and set N = 2·A - 1. This provides exactly A ways to make change, because you can choose any number of 2 cent pieces from 0 to A - 1, then the rest must be 1 cent pieces.
Ordering Pizza
Contest: MemSQL Start[c]UP 3.0 - Round 2 (onsite finalists)
Difficulty rating: 1900
Tags: binary search, sortings, ternary search

It's another Start[c]up finals, and that means there is pizza to order for the onsite contestants. There are only 2 types of pizza (obviously not, but let's just pretend for the sake of the problem), and all pizzas contain exactly S slices.

It is known that the i-th contestant will eat si slices of pizza, and gain ai happiness for each slice of type 1 pizza they eat, and bi happiness for each slice of type 2 pizza they eat. We can order any number of type 1 and type 2 pizzas, but we want to buy the minimum possible number of pizzas for all of the contestants to be able to eat their required number of slices. Given that restriction, what is the maximum possible total happiness that can be achieved?

Input format:
The first line of input will contain integers N and S (1 ≤ N ≤ 105, 1 ≤ S ≤ 105), the number of contestants and the number of slices per pizza, respectively. N lines follow.

The i-th such line contains integers si, ai, and bi (1 ≤ si ≤ 105, 1 ≤ ai ≤ 105, 1 ≤ bi ≤ 105), the number of slices the i-th contestant will eat, the happiness they will gain from each type 1 slice they eat, and the happiness they will gain from each type 2 slice they eat, respectively.

Output format:
Print the maximum total happiness that can be achieved.

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

Note:
In the first example, you only need to buy one pizza. If you buy a type 1 pizza, the total happiness will be 3·5 + 4·6 + 5·9 = 84, and if you buy a type 2 pizza, the total happiness will be 3·7 + 4·7 + 5·5 = 74.

Example input:
3 12
3 5 7
4 6 7
5 9 5

Example output:
84

Example input:
6 10
7 4 7
5 8 8
12 5 8
6 11 6
3 3 7
5 9 6

Example output:
314

Editorial:
To simplify things, let's first add a dummy contestant who will eat all the "leftover" pizza but gain no happiness. Then let's sort the contestants by bi - ai. Now we can describe the optimal way to feed the contestants once the pizzas are already bought: we should line up the contestants in order, and line up the pizzas in order with the type 1 pizzas at the front and type 2 pizzas at the back. Then the first contestant should take the first s1 slices, then the second contestant should take the next s2 slices, and so on.
Observe that there can be at most 1 pizza whose slices are taken by some contestants prefer type 1 and others prefer type 2. The remainder of pizzas will have only one type of preference (or possibly no preference), so those pizzas can be made of whichever type is preferred. For the final pizza we can check both possibilities and order the one that provides more happiness.
Buy Low Sell High
Contest: MemSQL Start[c]UP 3.0 - Round 2 (onsite finalists)
Difficulty rating: 2400
Tags: constructive algorithms, data structures, greedy

You can perfectly predict the price of a certain stock for the next N days. You would like to profit on this knowledge, but only want to transact one share of stock per day. That is, each day you will either buy one share, sell one share, or do nothing. Initially you own zero shares, and you cannot sell shares when you don't own any. At the end of the N days you would like to again own zero shares, but want to have as much money as possible.

Input format:
Input begins with an integer N (2 ≤ N ≤ 3·105), the number of days.

Following this is a line with exactly N integers p1, p2, ..., pN (1 ≤ pi ≤ 106). The price of one share of stock on the i-th day is given by pi.

Output format:
Print the maximum amount of money you can end up with at the end of N days.

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

Note:
In the first example, buy a share at 5, buy another at 4, sell one at 9 and another at 12. Then buy at 2 and sell at 10. The total profit is  - 5 - 4 + 9 + 12 - 2 + 10 = 20.

Example input:
9
10 5 4 7 9 12 6 2 10

Example output:
20

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

Example output:
41

Editorial:
Let's introduce the idea of options to the problem. Instead of having to buy stock when it is at a given price, each day you gain the option to buy a share at that days price, which you can exercise at any time in the future. This way we only need to exercise an option in order to sell it, and we never need to "hold" any stock.
Each day, 2 things happen. First, we get one more option. Second, if there is some option whose price is lower than today's price, we can be sure that we're going to exercise that option. What we don't know is when it's best to sell that option. However, we don't need to know when the best time is to sell - we can just sell it now, but give ourselves the option to buy it back at the price we just sold it for.
Options can be stored in a heap since we only ever care about the cheapest one. Running time $${\mathcal O}(N\log N)$$.