1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Best Subsegment
Contest: Educational Codeforces Round 60 (Rated for Div. 2)
Difficulty rating: 1100
Tags: implementation, math

You are given array $$$a_1, a_2, \dots, a_n$$$. Find the subsegment $$$a_l, a_{l+1}, \dots, a_r$$$ ($$$1 \le l \le r \le n$$$) with maximum arithmetic mean $$$\frac{1}{r - l + 1}\sum\limits_{i=l}^{r}{a_i}$$$ (in floating-point numbers, i.e. without any rounding).

If there are many such subsegments find the longest one.

Input format:
The first line contains single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the array $$$a$$$.

Output format:
Print the single integer — the length of the longest subsegment with maximum possible arithmetic mean.

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

Note:
The subsegment $$$[3, 4]$$$ is the longest among all subsegments with maximum arithmetic mean.

Example input:
5
6 1 6 6 0

Example output:
2

Editorial:
There is a property of arithmetic mean: $$$\frac{1}{k}\sum\limits_{i=1}^{k}{c_i} \le \max\limits_{1 \le i \le k}{c_i}$$$ and the equality holds when $$$c_1 = c_2 = \dots = c_k$$$.
Obviously, we can always gain maximum arithmetic mean equal to $$$\max\limits_{1 \le i \le n}{a_i}$$$ by taking single maximum element from $$$a$$$. Considering the property above, we need to take only maximum elements in our subsegment, that's why we need to find the longest subsegment consisting only of maximum elements.
Emotes
Contest: Educational Codeforces Round 60 (Rated for Div. 2)
Difficulty rating: 1000
Tags: greedy, math, sortings

There are $$$n$$$ emotes in very popular digital collectible card game (the game is pretty famous so we won't say its name). The $$$i$$$-th emote increases the opponent's happiness by $$$a_i$$$ units (we all know that emotes in this game are used to make opponents happy).

You have time to use some emotes only $$$m$$$ times. You are allowed to use any emotion once, more than once, or not use it at all. The only restriction is that you cannot use the same emote more than $$$k$$$ times in a row (otherwise the opponent will think that you're trolling him).

Note that two emotes $$$i$$$ and $$$j$$$ ($$$i \ne j$$$) such that $$$a_i = a_j$$$ are considered different.

You have to make your opponent as happy as possible. Find the maximum possible opponent's happiness.

Input format:
The first line of the input contains three integers $$$n, m$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le m \le 2 \cdot 10^9$$$) — the number of emotes, the number of times you can use emotes and the maximum number of times you may use the same emote in a row.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is value of the happiness of the $$$i$$$-th emote.

Output format:
Print one integer — the maximum opponent's happiness if you use emotes in a way satisfying the problem statement.

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

Note:
In the first example you may use emotes in the following sequence: $$$4, 4, 5, 4, 4, 5, 4, 4, 5$$$.

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

Example output:
54

Example input:
3 1000000000 1
1000000000 987654321 1000000000

Example output:
1000000000000000000

Editorial:
It is obvious that we always can use only two emotes with maximum $$$a_i$$$. Let their values be $$$x$$$ and $$$y$$$ ($$$x \ge y$$$).
We have to solve the problem by some formula. The best way to use emotes — use the emote with the value $$$x$$$ $$$k$$$ times, then use the emotion with the value $$$y$$$, then again use the emote with value $$$x$$$ $$$k$$$ times, and so on.
So the "cycle" has length $$$k+1$$$, and we can use the emote with the value $$$x$$$ the remaining number of times. So the answer is $$$\lfloor\frac{m}{k+1}\rfloor \cdot (x \cdot k + y) + (m \% (k + 1)) \cdot x$$$, where $$$x$$$ is the first maximum of $$$a$$$, $$$y$$$ is the second maximum of $$$a$$$, $$$\lfloor\frac{p}{q}\rfloor$$$ is $$$p$$$ divided by $$$q$$$ rounded down, and $$$p \% q$$$ is $$$p$$$ modulo $$$q$$$.
Magic Gems
Contest: Educational Codeforces Round 60 (Rated for Div. 2)
Difficulty rating: 2100
Tags: dp, math, matrices

Reziba has many magic gems. Each magic gem can be split into $$$M$$$ normal gems. The amount of space each magic (and normal) gem takes is $$$1$$$ unit. A normal gem cannot be split.

Reziba wants to choose a set of magic gems and split some of them, so the total space occupied by the resulting set of gems is $$$N$$$ units. If a magic gem is chosen and split, it takes $$$M$$$ units of space (since it is split into $$$M$$$ gems); if a magic gem is not split, it takes $$$1$$$ unit.

How many different configurations of the resulting set of gems can Reziba have, such that the total amount of space taken is $$$N$$$ units? Print the answer modulo $$$1000000007$$$ ($$$10^9+7$$$). Two configurations are considered different if the number of magic gems Reziba takes to form them differs, or the indices of gems Reziba has to split differ.

Input format:
The input contains a single line consisting of $$$2$$$ integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 10^{18}$$$, $$$2 \le M \le 100$$$).

Output format:
Print one integer, the total number of configurations of the resulting set of gems, given that the total amount of space taken is $$$N$$$ units. Print the answer modulo $$$1000000007$$$ ($$$10^9+7$$$).

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

Note:
In the first example each magic gem can split into $$$2$$$ normal gems, and we know that the total amount of gems are $$$4$$$.

Let $$$1$$$ denote a magic gem, and $$$0$$$ denote a normal gem.

The total configurations you can have is:

- $$$1 1 1 1$$$ (None of the gems split);
- $$$0 0 1 1$$$ (First magic gem splits into $$$2$$$ normal gems);
- $$$1 0 0 1$$$ (Second magic gem splits into $$$2$$$ normal gems);
- $$$1 1 0 0$$$ (Third magic gem splits into $$$2$$$ normal gems);
- $$$0 0 0 0$$$ (First and second magic gems split into total $$$4$$$ normal gems).

Hence, answer is $$$5$$$.

Example input:
4 2

Example output:
5

Example input:
3 2

Example output:
3

Editorial:
Let's reformulate the solution to the form of dynamic programming.
$$$dp_n$$$ — the number of ways to split the gems so that the total amount of space taken is $$$n$$$.
Then there are obvious transitions of either splitting the last gem or not. $$$dp_n = dp_{n - m} + dp_{n - 1}$$$.
And that can be easily rewritten in such a way that matrix exponentiation becomes the solution.
Overall complexity: $$$O(m^3 \cdot \log n)$$$.
Recursive Queries
Contest: Educational Codeforces Round 60 (Rated for Div. 2)
Difficulty rating: 2500
Tags: data structures

You are given a permutation $$$p_1, p_2, \dots, p_n$$$. You should answer $$$q$$$ queries. Each query is a pair $$$(l_i, r_i)$$$, and you should calculate $$$f(l_i, r_i)$$$.

Let's denote $$$m_{l, r}$$$ as the position of the maximum in subsegment $$$p_l, p_{l+1}, \dots, p_r$$$.

Then $$$f(l, r) = (r - l + 1) + f(l, m_{l,r} - 1) + f(m_{l,r} + 1, r)$$$ if $$$l \le r$$$ or $$$0$$$ otherwise.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le q \le 10^6$$$) — the size of the permutation $$$p$$$ and the number of queries.

The second line contains $$$n$$$ pairwise distinct integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$, $$$p_i \neq p_j$$$ for $$$i \neq j$$$) — permutation $$$p$$$.

The third line contains $$$q$$$ integers $$$l_1, l_2, \dots, l_q$$$ — the first parts of the queries.

The fourth line contains $$$q$$$ integers $$$r_1, r_2, \dots, r_q$$$ — the second parts of the queries.

It's guaranteed that $$$1 \le l_i \le r_i \le n$$$ for all queries.

Output format:
Print $$$q$$$ integers — the values $$$f(l_i, r_i)$$$ for the corresponding queries.

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

Note:
Description of the queries:

1. $$$f(2, 2) = (2 - 2 + 1) + f(2, 1) + f(3, 2) = 1 + 0 + 0 = 1$$$;
2. $$$f(1, 3) = (3 - 1 + 1) + f(1, 2) + f(4, 3) = 3 + (2 - 1 + 1) + f(1, 0) + f(2, 2) = 3 + 2 + (2 - 2 + 1) = 6$$$;
3. $$$f(1, 4) = (4 - 1 + 1) + f(1, 2) + f(4, 4) = 4 + 3 + 1 = 8$$$;
4. $$$f(2, 4) = (4 - 2 + 1) + f(2, 2) + f(4, 4) = 3 + 1 + 1 = 5$$$;
5. $$$f(1, 1) = (1 - 1 + 1) + 0 + 0 = 1$$$.

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

Example output:
1 6 8 5 1

Editorial:
Let's denote $$$fl(l, r) = (m_{l,r} - l) + fl(l, m_{l,r} - 1) + fl(m_{l,r} + 1, r)$$$ and, analogically, $$$fr(l, r) = (r - m_{l,r}) + fr(l, m_{l,r} - 1) + fr(m_{l,r} + 1, r)$$$. Then, we can note that $$$f(l, r) = (r - l + 1) + fl(l, r) + fr(l, r)$$$. So we can switch to calculating $$$fl$$$ (and $$$fr$$$).
Let's $$$lf[i]$$$ be the closest from the left to $$$i$$$ element such that $$$a[lf[i]] > a[i]$$$.
To calculate $$$fl(l, r)$$$ we will look from the other side: we will look at it as the sum of lengths of segments induced by each element from $$$[l, r]$$$. Each element $$$a_i$$$ ($$$l \le i \le r)$$$ will add to $$$fl(l, r)$$$ value equal to $$$\min(i - lf[i] - 1, i - l)$$$, or a piecewise linear function if we look at $$$l$$$ as a variable. And $$$fl(l, r)$$$ is a value of a sum of linear functions induced by $$$a[i]$$$ in a point $$$x = l$$$.
To process it efficiently we can one by one add induced linear functions to the corresponding subsegments using BIT or Segment Tree and if we've added functions induced by $$$a[k]$$$ we can calculate answer for all queries which looks like $$$(l_i, k)$$$.
To calculate $$$fr(l, r)$$$ we can just reverse array and all queries.
Result time complexity is $$$O((n + q) \log{n})$$$. Note, that it's still works quite slow, so you should use fast data structures like BIT of iterative segment tree.
Orchestra
Contest: 8VC Venture Cup 2016 - Final Round (Div. 2 Edition)
Difficulty rating: 1100
Tags: brute force, implementation

Paul is at the orchestra. The string section is arranged in an r × c rectangular grid and is filled with violinists with the exception of n violists. Paul really likes violas, so he would like to take a picture including at least k of them. Paul can take a picture of any axis-parallel rectangle in the orchestra. Count the number of possible pictures that Paul can take.

Two pictures are considered to be different if the coordinates of corresponding rectangles are different.

Input format:
The first line of input contains four space-separated integers r, c, n, k (1 ≤ r, c, n ≤ 10, 1 ≤ k ≤ n) — the number of rows and columns of the string section, the total number of violas, and the minimum number of violas Paul would like in his photograph, respectively.

The next n lines each contain two integers xi and yi (1 ≤ xi ≤ r, 1 ≤ yi ≤ c): the position of the i-th viola. It is guaranteed that no location appears more than once in the input.

Output format:
Print a single integer — the number of photographs Paul can take which include at least k violas.

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

Note:
We will use '*' to denote violinists and '#' to denote violists.

In the first sample, the orchestra looks as follows

In the second sample, the orchestra looks as follows

In the third sample, the orchestra looks the same as in the second sample.

Example input:
2 2 1 1
1 2

Example output:
4

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

Example output:
1

Editorial:
Patrick and Shopping
Contest: Codeforces Round 332 (Div. 2)
Difficulty rating: 800
Tags: implementation

Today Patrick waits for a visit from his friend Spongebob. To prepare for the visit, Patrick needs to buy some goodies in two stores located near his house. There is a d1 meter long road between his house and the first shop and a d2 meter long road between his house and the second shop. Also, there is a road of length d3 directly connecting these two shops to each other. Help Patrick calculate the minimum distance that he needs to walk in order to go to both shops and return to his house.

Patrick always starts at his house. He should visit both shops moving only along the three existing roads and return back to his house. He doesn't mind visiting the same shop or passing the same road multiple times. The only goal is to minimize the total distance traveled.

Input format:
The first line of the input contains three integers d1, d2, d3 (1 ≤ d1, d2, d3 ≤ 108) — the lengths of the paths.

- d1 is the length of the path connecting Patrick's house and the first shop;
- d2 is the length of the path connecting Patrick's house and the second shop;
- d3 is the length of the path connecting both shops.

Output format:
Print the minimum distance that Patrick will have to walk in order to visit both shops and return to his house.

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

Note:
The first sample is shown on the picture in the problem statement. One of the optimal routes is: house $$\rightarrow$$ first shop $$\rightarrow$$ second shop $$\rightarrow$$ house.

In the second sample one of the optimal routes is: house $$\rightarrow$$ first shop $$\rightarrow$$ house $$\rightarrow$$ second shop $$\rightarrow$$ house.

Example input:
10 20 30

Example output:
60

Example input:
1 1 5

Example output:
4

Editorial:
Spongebob and Joke
Contest: Codeforces Round 332 (Div. 2)
Difficulty rating: 1500
Tags: implementation

While Patrick was gone shopping, Spongebob decided to play a little trick on his friend. The naughty Sponge browsed through Patrick's personal stuff and found a sequence a1, a2, ..., am of length m, consisting of integers from 1 to n, not necessarily distinct. Then he picked some sequence f1, f2, ..., fn of length n and for each number ai got number bi = fai. To finish the prank he erased the initial sequence ai.

It's hard to express how sad Patrick was when he returned home from shopping! We will just say that Spongebob immediately got really sorry about what he has done and he is now trying to restore the original sequence. Help him do this or determine that this is impossible.

Input format:
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 100 000) — the lengths of sequences fi and bi respectively.

The second line contains n integers, determining sequence f1, f2, ..., fn (1 ≤ fi ≤ n).

The last line contains m integers, determining sequence b1, b2, ..., bm (1 ≤ bi ≤ n).

Output format:
Print "Possible" if there is exactly one sequence ai, such that bi = fai for all i from 1 to m. Then print m integers a1, a2, ..., am.

If there are multiple suitable sequences ai, print "Ambiguity".

If Spongebob has made a mistake in his calculations and no suitable sequence ai exists, print "Impossible".

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

Note:
In the first sample 3 is replaced by 1 and vice versa, while 2 never changes. The answer exists and is unique.

In the second sample all numbers are replaced by 1, so it is impossible to unambiguously restore the original sequence.

In the third sample fi ≠ 3 for all i, so no sequence ai transforms into such bi and we can say for sure that Spongebob has made a mistake.

Example input:
3 3
3 2 1
1 2 3

Example output:
Possible
3 2 1

Example input:
3 3
1 1 1
1 1 1

Example output:
Ambiguity

Editorial:
Day at the Beach
Contest: Codeforces Round 332 (Div. 2)
Difficulty rating: 1600
Tags: sortings

One day Squidward, Spongebob and Patrick decided to go to the beach. Unfortunately, the weather was bad, so the friends were unable to ride waves. However, they decided to spent their time building sand castles.

At the end of the day there were n castles built by friends. Castles are numbered from 1 to n, and the height of the i-th castle is equal to hi. When friends were about to leave, Squidward noticed, that castles are not ordered by their height, and this looks ugly. Now friends are going to reorder the castles in a way to obtain that condition hi ≤ hi + 1 holds for all i from 1 to n - 1.

Squidward suggested the following process of sorting castles:

- Castles are split into blocks — groups of consecutive castles. Therefore the block from i to j will include castles i, i + 1, ..., j. A block may consist of a single castle.
- The partitioning is chosen in such a way that every castle is a part of exactly one block.
- Each block is sorted independently from other blocks, that is the sequence hi, hi + 1, ..., hj becomes sorted.
- The partitioning should satisfy the condition that after each block is sorted, the sequence hi becomes sorted too. This may always be achieved by saying that the whole sequence is a single block.

Even Patrick understands that increasing the number of blocks in partitioning will ease the sorting process. Now friends ask you to count the maximum possible number of blocks in a partitioning that satisfies all the above requirements.

Input format:
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of castles Spongebob, Patrick and Squidward made from sand during the day.

The next line contains n integers hi (1 ≤ hi ≤ 109). The i-th of these integers corresponds to the height of the i-th castle.

Output format:
Print the maximum possible number of blocks in a valid partitioning.

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

Note:
In the first sample the partitioning looks like that: [1][2][3].

In the second sample the partitioning is: [2, 1][3, 2]

Example input:
3
1 2 3

Example output:
3

Example input:
4
2 1 3 2

Example output:
2

Editorial:
Spongebob and Squares
Contest: Codeforces Round 332 (Div. 2)
Difficulty rating: 1900
Tags: brute force, math

Spongebob is already tired trying to reason his weird actions and calculations, so he simply asked you to find all pairs of n and m, such that there are exactly x distinct squares in the table consisting of n rows and m columns. For example, in a 3 × 5 table there are 15 squares with side one, 8 squares with side two and 3 squares with side three. The total number of distinct squares in a 3 × 5 table is 15 + 8 + 3 = 26.

Input format:
The first line of the input contains a single integer x (1 ≤ x ≤ 1018) — the number of squares inside the tables Spongebob is interested in.

Output format:
First print a single integer k — the number of tables with exactly x distinct squares inside.

Then print k pairs of integers describing the tables. Print the pairs in the order of increasing n, and in case of equality — in the order of increasing m.

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

Note:
In a 1 × 2 table there are 2 1 × 1 squares. So, 2 distinct squares in total.

In a 2 × 3 table there are 6 1 × 1 squares and 2 2 × 2 squares. That is equal to 8 squares in total.

Example input:
26

Example output:
6
1 26
2 9
3 5
5 3
9 2
26 1

Example input:
2

Example output:
2
1 2
2 1

Editorial:
Sandy and Nuts
Contest: Codeforces Round 332 (Div. 2)
Difficulty rating: 2600
Tags: bitmasks, dp, trees

Rooted tree is a connected graph without any simple cycles with one vertex selected as a root. In this problem the vertex number 1 will always serve as a root.

Lowest common ancestor of two vertices u and v is the farthest from the root vertex that lies on both the path from u to the root and on path from v to the root. We will denote it as LCA(u, v).

Sandy had a rooted tree consisting of n vertices that she used to store her nuts. Unfortunately, the underwater storm broke her tree and she doesn't remember all it's edges. She only managed to restore m edges of the initial tree and q triples ai, bi and ci, for which she supposes LCA(ai, bi) = ci.

Help Sandy count the number of trees of size n with vertex 1 as a root, that match all the information she remembered. If she made a mess and there are no such trees then print 0. Two rooted trees are considered to be distinct if there exists an edge that occur in one of them and doesn't occur in the other one.

Input format:
The first line of the input contains three integers n, m and q (1 ≤ n ≤ 13, 0 ≤ m < n, 0 ≤ q ≤ 100) — the number of vertices, the number of edges and LCA triples remembered by Sandy respectively.

Each of the next m lines contains two integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — the numbers of vertices connected by the i-th edge. It's guaranteed that this set of edges is a subset of edges of some tree.

The last q lines contain the triplets of numbers ai, bi, ci (1 ≤ ai, bi, ci ≤ n). Each of these triples define LCA(ai, bi) = ci. It's not guaranteed that there exists a tree that satisfy all the given LCA conditions.

Output format:
Print a single integer — the number of trees of size n that satisfy all the conditions.

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

Note:
In the second sample correct answer looks like this:

In the third sample there are two possible trees:

In the fourth sample the answer is 0 because the information about LCA is inconsistent.

Example input:
4 0 0

Example output:
16

Example input:
4 0 1
3 4 2

Example output:
1

Editorial:
Boboniu Chats with Du
Contest: Codeforces Round 664 (Div. 1)
Difficulty rating: 1800
Tags: dp, greedy, sortings, two pointers

Have you ever used the chat application QQ? Well, in a chat group of QQ, administrators can muzzle a user for days.

In Boboniu's chat group, there's a person called Du Yi who likes to make fun of Boboniu every day.

Du will chat in the group for $$$n$$$ days. On the $$$i$$$-th day:

- If Du can speak, he'll make fun of Boboniu with fun factor $$$a_i$$$. But after that, he may be muzzled depending on Boboniu's mood.
- Otherwise, Du won't do anything.

Boboniu's mood is a constant $$$m$$$. On the $$$i$$$-th day:

- If Du can speak and $$$a_i>m$$$, then Boboniu will be angry and muzzle him for $$$d$$$ days, which means that Du won't be able to speak on the $$$i+1, i+2, \cdots, \min(i+d,n)$$$-th days.
- Otherwise, Boboniu won't do anything.

The total fun factor is the sum of the fun factors on the days when Du can speak.

Du asked you to find the maximum total fun factor among all possible permutations of $$$a$$$.

Input format:
The first line contains three integers $$$n$$$, $$$d$$$ and $$$m$$$ ($$$1\le d\le n\le 10^5,0\le m\le 10^9$$$).

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots,a_n$$$ ($$$0\le a_i\le 10^9$$$).

Output format:
Print one integer: the maximum total fun factor among all permutations of $$$a$$$.

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

Note:
In the first example, you can set $$$a'=[15, 5, 8, 10, 23]$$$. Then Du's chatting record will be:

1. Make fun of Boboniu with fun factor $$$15$$$.
2. Be muzzled.
3. Be muzzled.
4. Make fun of Boboniu with fun factor $$$10$$$.
5. Make fun of Boboniu with fun factor $$$23$$$.

Thus the total fun factor is $$$48$$$.

Example input:
5 2 11
8 10 15 23 5

Example output:
48

Example input:
20 2 16
20 5 8 2 18 16 2 16 16 1 5 16 2 13 6 16 4 17 21 7

Example output:
195

Editorial:
If $$$a_i>m$$$, we consider it as a big item with value $$$a_i$$$, else a small item with value $$$a_i$$$. We are asked to choose some items and maximize the total value. If an item is not chosen, it means we put it on a muzzled day.
Enumerate the number of chosen big item, which is denoted by $$$x$$$. Thus they take $$$(x-1)(d+1)+1$$$ days. The remaining days are used to place small item on it. Choose items greedily. i. e. We sort items by value from largest to smallest, choose previous $$$x$$$ big items and previous $$$n-(x-1)(d+1)-1$$$ small items and update the answer.
The total time complexity is $$$O(n\log n)$$$.