1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Painting the Fence
Contest: Educational Codeforces Round 61 (Rated for Div. 2)
Difficulty rating: 1700
Tags: brute force

You have a long fence which consists of $$$n$$$ sections. Unfortunately, it is not painted, so you decided to hire $$$q$$$ painters to paint it. $$$i$$$-th painter will paint all sections $$$x$$$ such that $$$l_i \le x \le r_i$$$.

Unfortunately, you are on a tight budget, so you may hire only $$$q - 2$$$ painters. Obviously, only painters you hire will do their work.

You want to maximize the number of painted sections if you choose $$$q - 2$$$ painters optimally. A section is considered painted if at least one painter paints it.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$3 \le n, q \le 5000$$$) — the number of sections and the number of painters availible for hire, respectively.

Then $$$q$$$ lines follow, each describing one of the painters: $$$i$$$-th line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).

Output format:
Print one integer — maximum number of painted sections if you hire $$$q - 2$$$ painters.

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

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

Example output:
7

Example input:
4 3
1 1
2 2
3 4

Example output:
2

Editorial:
Let $$$c_i$$$ be the number of painters that are painting the $$$i$$$-th section.
Let's fix the first painter (denote his index as $$$x$$$) we won't take and decrease the numbers of array $$$c$$$ in the range which he paints.
Then we may new array $$$d$$$, such that $$$d_i$$$ is equal to $$$1$$$ if and only if $$$c_i = 1$$$, and $$$0$$$ otherwise. This array corresponds to segments that are painted by only one painter
After that we build prefix sum array $$$p$$$ on array $$$d$$$: $$$p_i = \sum\limits_{j=1}^{i} d_j$$$. This should be done in $$$O(n)$$$.
Now, for each remaining painter we can count the number of sections that are painted only by him. For painter $$$i$$$ it will be equal to $$$p_{r_i} - p_{l_i - 1}$$$. Let's denote it as $$$res_i$$$.
Finally, find an painter with the minimum value of $$$res_i$$$, denote it as $$$MinRes$$$. The answer (if we choose painter $$$x$$$ as one of two that won't be hired) will be equal to $$$cnt - MinRes$$$, where $$$cnt$$$ is the number of elements greater than $$$0$$$ in the array $$$c$$$ after removing the painter $$$x$$$.
And, of course, we should do the same for all painters.
Knapsack
Contest: Educational Codeforces Round 61 (Rated for Div. 2)
Difficulty rating: 2300
Tags: dfs and similar, dp, greedy

You have a set of items, each having some integer weight not greater than $$$8$$$. You denote that a subset of items is good if total weight of items in the subset does not exceed $$$W$$$.

You want to calculate the maximum possible weight of a good subset of items. Note that you have to consider the empty set and the original set when calculating the answer.

Input format:
The first line contains one integer $$$W$$$ ($$$0 \le W \le 10^{18}$$$) — the maximum total weight of a good subset.

The second line denotes the set of items you have. It contains $$$8$$$ integers $$$cnt_1$$$, $$$cnt_2$$$, ..., $$$cnt_8$$$ ($$$0 \le cnt_i \le 10^{16}$$$), where $$$cnt_i$$$ is the number of items having weight $$$i$$$ in the set.

Output format:
Print one integer — the maximum possible weight of a good subset of items.

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

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

Example output:
10

Example input:
0
0 0 0 0 0 0 0 0

Example output:
0

Editorial:
Let's consider the optimal answer. Suppose we take $$$c_i$$$ items of weight $$$i$$$.
Let $$$L$$$ be the least common multiple of all weights (that is $$$840$$$). Then we may represent $$$c_i$$$ as $$$c_i = \frac{L}{i} p_i + q_i$$$, where $$$0 \le q < \frac{L}{i}$$$. Let's do the following trick: we will take $$$q_i$$$ items of weight $$$i$$$, and all the remaining items of this weight can be merged into some items of weight $$$L$$$.
Then we can write a brute force solution that picks less than $$$\frac{L}{i}$$$ items of each weight, transforms the remaining ones into items of weight $$$L$$$ as much as possible, and when we fix the whole subset, adds maximum possible number of items of weight $$$L$$$ to the answer. This works in something like $$$\prod \limits_{i = 1}^8 \frac{L}{i} = \frac{L^8}{8!}$$$ operations, which is too much.
How can we speed it up? Rewrite it using dynamic programming! When we have fixed the number of items we take from $$$x$$$ first sets, the only two things that matter now are the current total weight of taken items and the number of items of weight $$$L$$$ we can use; and it's obvious that the more items of weight $$$L$$$ we can use, the better. So let's write the following dynamic programming solution: $$$dp[x][y]$$$ — maximum number of items of weight $$$L$$$ we can have, if we processed first $$$x$$$ types of items, and current total weight is $$$y$$$. Note that the second dimension should have size $$$8L$$$.
Clear the String
Contest: Educational Codeforces Round 61 (Rated for Div. 2)
Difficulty rating: 2000
Tags: dp

You are given a string $$$s$$$ of length $$$n$$$ consisting of lowercase Latin letters. You may apply some operations to this string: in one operation you can delete some contiguous substring of this string, if all letters in the substring you delete are equal. For example, after deleting substring bbbb from string abbbbaccdd we get the string aaccdd.

Calculate the minimum number of operations to delete the whole string $$$s$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 500$$$) — the length of string $$$s$$$.

The second line contains the string $$$s$$$ ($$$|s| = n$$$) consisting of lowercase Latin letters.

Output format:
Output a single integer — the minimal number of operation to delete string $$$s$$$.

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

Example input:
5
abaca

Example output:
3

Example input:
8
abcddcba

Example output:
4

Editorial:
We will solve the problem by dynamic programming.
Let $$$dp_{l, r}$$$ be the answer for substring $$$s_{l, l + 1, \dots, r}$$$. Then we have two cases:
1. The first letter of the substring is deleted separately from the rest, then $$$dp_{l, r} = 1 + dp_{l + 1, r}$$$;
2. The first letter of the substring is deleted alongside with some other letter (both letters must be equal), then $$$dp_{l,r} = \min \limits_{l < i \le r, s_i = s_r} dp_{l + 1, i - 1} + dp_{i, r}$$$.
Pasha and Stick
Contest: Codeforces Round 337 (Div. 2)
Difficulty rating: 1000
Tags: combinatorics, math

Pasha has a wooden stick of some positive integer length n. He wants to perform exactly three cuts to get four parts of the stick. Each part must have some positive integer length and the sum of these lengths will obviously be n.

Pasha likes rectangles but hates squares, so he wonders, how many ways are there to split a stick into four parts so that it's possible to form a rectangle using these parts, but is impossible to form a square.

Your task is to help Pasha and count the number of such ways. Two ways to cut the stick are considered distinct if there exists some integer x, such that the number of parts of length x in the first way differ from the number of parts of length x in the second way.

Input format:
The first line of the input contains a positive integer n (1 ≤ n ≤ 2·109) — the length of Pasha's stick.

Output format:
The output should contain a single integer — the number of ways to split Pasha's stick into four parts of positive integer length so that it's possible to make a rectangle by connecting the ends of these parts, but is impossible to form a square.

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

Note:
There is only one way to divide the stick in the first sample {1, 1, 2, 2}.

Four ways to divide the stick in the second sample are {1, 1, 9, 9}, {2, 2, 8, 8}, {3, 3, 7, 7} and {4, 4, 6, 6}. Note that {5, 5, 5, 5} doesn't work.

Example input:
6

Example output:
1

Example input:
20

Example output:
4

Editorial:
Vika and Squares
Contest: Codeforces Round 337 (Div. 2)
Difficulty rating: 1300
Tags: constructive algorithms, implementation

Vika has n jars with paints of distinct colors. All the jars are numbered from 1 to n and the i-th jar contains ai liters of paint of color i.

Vika also has an infinitely long rectangular piece of paper of width 1, consisting of squares of size 1 × 1. Squares are numbered 1, 2, 3 and so on. Vika decided that she will start painting squares one by one from left to right, starting from the square number 1 and some arbitrary color. If the square was painted in color x, then the next square will be painted in color x + 1. In case of x = n, next square is painted in color 1. If there is no more paint of the color Vika wants to use now, then she stops.

Square is always painted in only one color, and it takes exactly 1 liter of paint. Your task is to calculate the maximum number of squares that might be painted, if Vika chooses right color to paint the first square.

Input format:
The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of jars with colors Vika has.

The second line of the input contains a sequence of integers a1, a2, ..., an (1 ≤ ai ≤ 109), where ai is equal to the number of liters of paint in the i-th jar, i.e. the number of liters of color i that Vika has.

Output format:
The only line of the output should contain a single integer — the maximum number of squares that Vika can paint if she follows the rules described above.

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

Note:
In the first sample the best strategy is to start painting using color 4. Then the squares will be painted in the following colors (from left to right): 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5.

In the second sample Vika can start to paint using any color.

In the third sample Vika should start painting using color number 5.

Example input:
5
2 4 2 3 3

Example output:
12

Example input:
3
5 5 5

Example output:
15

Editorial:
Harmony Analysis
Contest: Codeforces Round 337 (Div. 2)
Difficulty rating: 1800
Tags: constructive algorithms

The semester is already ending, so Danil made an effort and decided to visit a lesson on harmony analysis to know how does the professor look like, at least. Danil was very bored on this lesson until the teacher gave the group a simple task: find 4 vectors in 4-dimensional space, such that every coordinate of every vector is 1 or  - 1 and any two vectors are orthogonal. Just as a reminder, two vectors in n-dimensional space are considered to be orthogonal if and only if their scalar product is equal to zero, that is:

$$\sum_{i=1}^{n} a_i \cdot b_i = 0$$

Danil quickly managed to come up with the solution for this problem and the teacher noticed that the problem can be solved in a more general case for 2k vectors in 2k-dimensinoal space. When Danil came home, he quickly came up with the solution for this problem. Can you cope with it?

Input format:
The only line of the input contains a single integer k (0 ≤ k ≤ 9).

Output format:
Print 2k lines consisting of 2k characters each. The j-th character of the i-th line must be equal to ' * ' if the j-th coordinate of the i-th vector is equal to  - 1, and must be equal to ' + ' if it's equal to  + 1. It's guaranteed that the answer always exists.

If there are many correct answers, print any.

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

Note:
Consider all scalar products in example:

- Vectors 1 and 2: ( + 1)·( + 1) + ( + 1)·( - 1) + ( - 1)·( + 1) + ( - 1)·( - 1) = 0
- Vectors 1 and 3: ( + 1)·( + 1) + ( + 1)·( + 1) + ( - 1)·( + 1) + ( - 1)·( + 1) = 0
- Vectors 1 and 4: ( + 1)·( + 1) + ( + 1)·( - 1) + ( - 1)·( - 1) + ( - 1)·( + 1) = 0
- Vectors 2 and 3: ( + 1)·( + 1) + ( - 1)·( + 1) + ( + 1)·( + 1) + ( - 1)·( + 1) = 0
- Vectors 2 and 4: ( + 1)·( + 1) + ( - 1)·( - 1) + ( + 1)·( - 1) + ( - 1)·( + 1) = 0
- Vectors 3 and 4: ( + 1)·( + 1) + ( + 1)·( - 1) + ( + 1)·( - 1) + ( + 1)·( + 1) = 0

Example input:
2

Example output:
++**
+*+*
++++
+**+

Editorial:
Vika and Segments
Contest: Codeforces Round 337 (Div. 2)
Difficulty rating: 2300
Tags: constructive algorithms, data structures, geometry, two pointers

Vika has an infinite sheet of squared paper. Initially all squares are white. She introduced a two-dimensional coordinate system on this sheet and drew n black horizontal and vertical segments parallel to the coordinate axes. All segments have width equal to 1 square, that means every segment occupy some set of neighbouring squares situated in one row or one column.

Your task is to calculate the number of painted cells. If a cell was painted more than once, it should be calculated exactly once.

Input format:
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of segments drawn by Vika.

Each of the next n lines contains four integers x1, y1, x2 and y2 ( - 109 ≤ x1, y1, x2, y2 ≤ 109) — the coordinates of the endpoints of the segments drawn by Vika. It is guaranteed that all the segments are parallel to coordinate axes. Segments may touch, overlap and even completely coincide.

Output format:
Print the number of cells painted by Vika. If a cell was painted more than once, it should be calculated exactly once in the answer.

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

Note:
In the first sample Vika will paint squares (0, 1), (1, 1), (2, 1), (1, 2), (1, 3), (1, 4), (0, 3) and (2, 3).

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

Example output:
8

Example input:
4
-2 -1 2 -1
2 1 -2 1
-1 -2 -1 2
1 2 1 -2

Example output:
16

Editorial:
Alphabet Permutations
Contest: Codeforces Round 337 (Div. 2)
Difficulty rating: 2500
Tags: data structures, strings

You are given a string s of length n, consisting of first k lowercase English letters.

We define a c-repeat of some string q as a string, consisting of c copies of the string q. For example, string "acbacbacbacb" is a 4-repeat of the string "acb".

Let's say that string a contains string b as a subsequence, if string b can be obtained from a by erasing some symbols.

Let p be a string that represents some permutation of the first k lowercase English letters. We define function d(p) as the smallest integer such that a d(p)-repeat of the string p contains string s as a subsequence.

There are m operations of one of two types that can be applied to string s:

1. Replace all characters at positions from li to ri by a character ci.
2. For the given p, that is a permutation of first k lowercase English letters, find the value of function d(p).

All operations are performed sequentially, in the order they appear in the input. Your task is to determine the values of function d(p) for all operations of the second type.

Input format:
The first line contains three positive integers n, m and k (1 ≤ n ≤ 200 000, 1 ≤ m ≤ 20000, 1 ≤ k ≤ 10) — the length of the string s, the number of operations and the size of the alphabet respectively. The second line contains the string s itself.

Each of the following lines m contains a description of some operation:

1. Operation of the first type starts with 1 followed by a triple li, ri and ci, that denotes replacement of all characters at positions from li to ri by character ci (1 ≤ li ≤ ri ≤ n, ci is one of the first k lowercase English letters).
2. Operation of the second type starts with 2 followed by a permutation of the first k lowercase English letters.

Output format:
For each query of the second type the value of function d(p).

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

Note:
After the first operation the string s will be abbbbba.

In the second operation the answer is 6-repeat of abc: ABcaBcaBcaBcaBcAbc.

After the third operation the string s will be abbcbba.

In the fourth operation the answer is 5-repeat of cba: cbAcBacBaCBacBA.

Uppercase letters means the occurrences of symbols from the string s.

Example input:
7 4 3
abacaba
1 3 5 b
2 abc
1 4 4 c
2 cba

Example output:
6
5

Editorial:
Amusement Park
Contest: VK Cup 2017 - Wild Card Round 1
Difficulty rating: 2100
Tags: *special, ternary search

Pupils decided to go to amusement park. Some of them were with parents. In total, n people came to the park and they all want to get to the most extreme attraction and roll on it exactly once.

Tickets for group of x people are sold on the attraction, there should be at least one adult in each group (it is possible that the group consists of one adult). The ticket price for such group is c1 + c2·(x - 1)2 (in particular, if the group consists of one person, then the price is c1).

All pupils who came to the park and their parents decided to split into groups in such a way that each visitor join exactly one group, and the total price of visiting the most extreme attraction is as low as possible. You are to determine this minimum possible total price. There should be at least one adult in each group.

Input format:
The first line contains three integers n, c1 and c2 (1 ≤ n ≤ 200 000, 1 ≤ c1, c2 ≤ 107) — the number of visitors and parameters for determining the ticket prices for a group.

The second line contains the string of length n, which consists of zeros and ones. If the i-th symbol of the string is zero, then the i-th visitor is a pupil, otherwise the i-th person is an adult. It is guaranteed that there is at least one adult. It is possible that there are no pupils.

Output format:
Print the minimum price of visiting the most extreme attraction for all pupils and their parents. Each of them should roll on the attraction exactly once.

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

Note:
In the first test one group of three people should go to the attraction. Then they have to pay 4 + 1 * (3 - 1)2 = 8.

In the second test it is better to go to the attraction in two groups. The first group should consist of two adults (for example, the first and the second person), the second should consist of one pupil and one adult (the third and the fourth person). Then each group will have a size of two and for each the price of ticket is 7 + 2 * (2 - 1)2 = 9. Thus, the total price for two groups is 18.

Example input:
3 4 1
011

Example output:
8

Example input:
4 7 2
1101

Example output:
18

Editorial:
Для решения данной задачи сначала переберём на сколько групп поделятся пришедшие люди. Если cnt равно количеству взрослых, пришедших в парк, то количество групп может быть от 1 до cnt включительно.
Пусть текущее количество групп равно i. Тогда в каждой группе точно будет по одному взрослому, а остальных нужно равномерно распределить между группами, то есть каждого следующего человека нужно отдавать в наименьшую по размеру группу. Если таких групп несколько, то нам неважно куда его отдать. Таким образом, получится n mod i групп размера (n div i) + 1 и i - (n mod i) групп размера (n div i). Зная эту информацию, легко посчитать стоимость для текущего количества групп i и обновить этой стоимостью ответ.
Maximum Number
Contest: VK Cup 2017 - Wild Card Round 1
Difficulty rating: 1200
Tags: *special, constructive algorithms, greedy, implementation

Stepan has the newest electronic device with a display. Different digits can be shown on it. Each digit is shown on a seven-section indicator like it is shown on the picture below.

So, for example, to show the digit 3 on the display, 5 sections must be highlighted; and for the digit 6, 6 sections must be highlighted.

The battery of the newest device allows to highlight at most n sections on the display.

Stepan wants to know the maximum possible integer number which can be shown on the display of his newest device. Your task is to determine this number. Note that this number must not contain leading zeros. Assume that the size of the display is enough to show any integer.

Input format:
The first line contains the integer n (2 ≤ n ≤ 100 000) — the maximum number of sections which can be highlighted on the display.

Output format:
Print the maximum integer which can be shown on the display of Stepan's newest device.

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

Example input:
2

Example output:
1

Example input:
3

Example output:
7

Editorial:
Пользуясь жадными соображениями, нам выгодно в первую очередь максимизировать количество цифр в числе. Наименьшее количество секций нужно для изображения цифры 1. Поэтому для четного n выведем n / 2 единиц — это и будет ответим. Если же n нечетно, то нужно сначала вывести цифру 7, после чего останется n - 3 секции, которые можно подсветить, причем число n - 3 обязательно четно. Поэтому нужно вывести еще (n - 3) / 2 единицы.
Lie or Truth
Contest: VK Cup 2017 - Wild Card Round 1
Difficulty rating: 1500
Tags: *special, constructive algorithms, implementation, sortings

Vasya has a sequence of cubes and exactly one integer is written on each cube. Vasya exhibited all his cubes in a row. So the sequence of numbers written on the cubes in the order from the left to the right equals to a1, a2, ..., an.

While Vasya was walking, his little brother Stepan played with Vasya's cubes and changed their order, so now the sequence of numbers written on the cubes became equal to b1, b2, ..., bn.

Stepan said that he swapped only cubes which where on the positions between l and r, inclusive, and did not remove or add any other cubes (i. e. he said that he reordered cubes between positions l and r, inclusive, in some way).

Your task is to determine if it is possible that Stepan said the truth, or it is guaranteed that Stepan deceived his brother.

Input format:
The first line contains three integers n, l, r (1 ≤ n ≤ 105, 1 ≤ l ≤ r ≤ n) — the number of Vasya's cubes and the positions told by Stepan.

The second line contains the sequence a1, a2, ..., an (1 ≤ ai ≤ n) — the sequence of integers written on cubes in the Vasya's order.

The third line contains the sequence b1, b2, ..., bn (1 ≤ bi ≤ n) — the sequence of integers written on cubes after Stepan rearranged their order.

It is guaranteed that Stepan did not remove or add other cubes, he only rearranged Vasya's cubes.

Output format:
Print "LIE" (without quotes) if it is guaranteed that Stepan deceived his brother. In the other case, print "TRUTH" (without quotes).

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

Note:
In the first example there is a situation when Stepan said the truth. Initially the sequence of integers on the cubes was equal to [3, 4, 2, 3, 1]. Stepan could at first swap cubes on positions 2 and 3 (after that the sequence of integers on cubes became equal to [3, 2, 4, 3, 1]), and then swap cubes in positions 3 and 4 (after that the sequence of integers on cubes became equal to [3, 2, 3, 4, 1]).

In the second example it is not possible that Stepan said truth because he said that he swapped cubes only between positions 1 and 2, but we can see that it is guaranteed that he changed the position of the cube which was on the position 3 at first. So it is guaranteed that Stepan deceived his brother.

In the third example for any values l and r there is a situation when Stepan said the truth.

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

Example output:
TRUTH

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

Example output:
LIE

Editorial:
Так как гарантируется, что Степан не добавлял и не удалял кубики, нужно просто проверить, что в последовательностях a и b стоят одинаковые числа с позиции 1 до позиции l - 1, а также с позиции r + 1 до позиции n. Если для обоих отрезков числа в соответствующих позициях совпадают, то Степан может говорить правду. В противном случае он лжёт.