1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Maximum Cost Deletion
Contest: Educational Codeforces Round 111 (Rated for Div. 2)
Difficulty rating: 1000
Tags: greedy, math

You are given a string $$$s$$$ of length $$$n$$$ consisting only of the characters 0 and 1.

You perform the following operation until the string becomes empty: choose some consecutive substring of equal characters, erase it from the string and glue the remaining two parts together (any of them can be empty) in the same order. For example, if you erase the substring 111 from the string 111110, you will get the string 110. When you delete a substring of length $$$l$$$, you get $$$a \cdot l + b$$$ points.

Your task is to calculate the maximum number of points that you can score in total, if you have to make the given string empty.

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

The first line of each testcase contains three integers $$$n$$$, $$$a$$$ and $$$b$$$ ($$$1 \le n \le 100; -100 \le a, b \le 100$$$) — the length of the string $$$s$$$ and the parameters $$$a$$$ and $$$b$$$.

The second line contains the string $$$s$$$. The string $$$s$$$ consists only of the characters 0 and 1.

Output format:
For each testcase, print a single integer — the maximum number of points that you can score.

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

Note:
In the first example, it is enough to delete the entire string, then we will get $$$2 \cdot 3 + 0 = 6$$$ points.

In the second example, if we delete characters one by one, then for each deleted character we will get $$$(-2) \cdot 1 + 5 = 3$$$ points, i. e. $$$15$$$ points in total.

In the third example, we can delete the substring 00 from the string 100111, we get $$$1 \cdot 2 + (-4) = -2$$$ points, and the string will be equal to 1111, removing it entirely we get $$$1 \cdot 4 + (-4) = 0$$$ points. In total, we got $$$-2$$$ points for $$$2$$$ operations.

Example input:
3
3 2 0
000
5 -2 5
11001
6 1 -4
100111

Example output:
6
15
-2

Editorial:
Let $$$l_1, l_2, \dots, l_k$$$ be the length of the substring deleted at the $$$i$$$-th step. Then the number of points will be equal to $$$\sum\limits_{i=1}^{k} (a \cdot l_i + b)$$$ or $$$a\sum\limits_{i=1}^{k}l_i + bk$$$. The sum of all $$$l_i$$$ is equal to $$$n$$$ (because in the end we deleted the entire string), so the final formula has the form $$$an + bk$$$. Obviously, for $$$b \ge 0$$$, you should delete the characters one by one so that $$$k=n$$$. Now $$$b < 0$$$ and you have to delete the string in the minimum number of operations. Let the string $$$s$$$ consist of $$$m$$$ blocks of zeros and ones, then $$$\lfloor\frac{m}{2}\rfloor + 1$$$ is the minimum number of operations for which the entire string can be deleted. As long as the number of blocks is more than $$$2$$$, we will delete the second block, the number of blocks will decrease by $$$2$$$ after each such operation (the block that we delete will disappear, and the first and third blocks will merge into one).
Dima and Friends
Contest: Codeforces Round 167 (Div. 2)
Difficulty rating: 1000
Tags: implementation, math

Dima and his friends have been playing hide and seek at Dima's place all night. As a result, Dima's place got messy. In the morning they decided that they need to clean the place.

To decide who exactly would clean the apartment, the friends want to play a counting-out game. First, all the guys stand in a circle, and then each of them shows some number of fingers on one hand (one to five), and then the boys count in a circle, starting from Dima, the number of people, respective to the total number of fingers shown. The person on who the countdown stops will clean the apartment.

For example, if Dima and one of his friends played hide and seek, and 7 fingers were shown during the counting-out, then Dima would clean the place. If there were 2 or say, 8 fingers shown, then his friend would clean the place.

Dima knows how many fingers each of his friends will show during the counting-out. Now he is interested in the number of ways to show some number of fingers on one hand (one to five), so that he did not have to clean the place. Help Dima.

Input format:
The first line contains integer n (1 ≤ n ≤ 100) — the number of Dima's friends. Dima himself isn't considered to be his own friend. The second line contains n positive integers, not exceeding 5, representing, how many fingers the Dima's friends will show.

The numbers in the lines are separated by a single space.

Output format:
In a single line print the answer to the problem.

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

Note:
In the first sample Dima can show 1, 3 or 5 fingers. If Dima shows 3 fingers, then the counting-out will go like that: Dima, his friend, Dima, his friend.

In the second sample Dima can show 2 or 4 fingers.

Example input:
1
1

Example output:
3

Example input:
1
2

Example output:
2

Editorial:
Dima and Sequence
Contest: Codeforces Round 167 (Div. 2)
Difficulty rating: 1400
Tags: implementation, math

Dima got into number sequences. Now he's got sequence a1, a2, ..., an, consisting of n positive integers. Also, Dima has got a function f(x), which can be defined with the following recurrence:

- f(0) = 0;
- f(2·x) = f(x);
- f(2·x + 1) = f(x) + 1.

Dima wonders, how many pairs of indexes (i, j) (1 ≤ i < j ≤ n) are there, such that f(ai) = f(aj). Help him, count the number of such pairs.

Input format:
The first line contains integer n (1 ≤ n ≤ 105). The second line contains n positive integers a1, a2, ..., an (1 ≤ ai ≤ 109).

The numbers in the lines are separated by single spaces.

Output format:
In a single line print the answer to the problem.

Please, don't use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

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

Note:
In the first sample any pair (i, j) will do, so the answer is 3.

In the second sample only pair (1, 2) will do.

Example input:
3
1 2 4

Example output:
3

Example input:
3
5 3 1

Example output:
1

Editorial:
Dima and Staircase
Contest: Codeforces Round 167 (Div. 2)
Difficulty rating: 1500
Tags: data structures, implementation

Dima's got a staircase that consists of n stairs. The first stair is at height a1, the second one is at a2, the last one is at an (1 ≤ a1 ≤ a2 ≤ ... ≤ an).

Dima decided to play with the staircase, so he is throwing rectangular boxes at the staircase from above. The i-th box has width wi and height hi. Dima throws each box vertically down on the first wi stairs of the staircase, that is, the box covers stairs with numbers 1, 2, ..., wi. Each thrown box flies vertically down until at least one of the two following events happen:

- the bottom of the box touches the top of a stair;
- the bottom of the box touches the top of a box, thrown earlier.

We only consider touching of the horizontal sides of stairs and boxes, at that touching with the corners isn't taken into consideration. Specifically, that implies that a box with width wi cannot touch the stair number wi + 1.

You are given the description of the staircase and the sequence in which Dima threw the boxes at it. For each box, determine how high the bottom of the box after landing will be. Consider a box to fall after the previous one lands.

Input format:
The first line contains integer n (1 ≤ n ≤ 105) — the number of stairs in the staircase. The second line contains a non-decreasing sequence, consisting of n integers, a1, a2, ..., an (1 ≤ ai ≤ 109; ai ≤ ai + 1).

The next line contains integer m (1 ≤ m ≤ 105) — the number of boxes. Each of the following m lines contains a pair of integers wi, hi (1 ≤ wi ≤ n; 1 ≤ hi ≤ 109) — the size of the i-th thrown box.

The numbers in the lines are separated by spaces.

Output format:
Print m integers — for each box the height, where the bottom of the box will be after landing. Print the answers for the boxes in the order, in which the boxes are given in the input.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

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

Note:
The first sample are shown on the picture.

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

Example output:
1
3
4
6

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

Example output:
1
3

Editorial:
Dima and Two Sequences
Contest: Codeforces Round 167 (Div. 2)
Difficulty rating: 1600
Tags: combinatorics, math, sortings

Little Dima has two sequences of points with integer coordinates: sequence (a1, 1), (a2, 2), ..., (an, n) and sequence (b1, 1), (b2, 2), ..., (bn, n).

Now Dima wants to count the number of distinct sequences of points of length 2·n that can be assembled from these sequences, such that the x-coordinates of points in the assembled sequence will not decrease. Help him with that. Note that each element of the initial sequences should be used exactly once in the assembled sequence.

Dima considers two assembled sequences (p1, q1), (p2, q2), ..., (p2·n, q2·n) and (x1, y1), (x2, y2), ..., (x2·n, y2·n) distinct, if there is such i (1 ≤ i ≤ 2·n), that (pi, qi) ≠ (xi, yi).

As the answer can be rather large, print the remainder from dividing the answer by number m.

Input format:
The first line contains integer n (1 ≤ n ≤ 105). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109). The third line contains n integers b1, b2, ..., bn (1 ≤ bi ≤ 109). The numbers in the lines are separated by spaces.

The last line contains integer m (2 ≤ m ≤ 109 + 7).

Output format:
In the single line print the remainder after dividing the answer to the problem by number m.

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

Note:
In the first sample you can get only one sequence: (1, 1), (2, 1).

In the second sample you can get such sequences : (1, 1), (2, 2), (2, 1), (3, 2); (1, 1), (2, 1), (2, 2), (3, 2). Thus, the answer is 2.

Example input:
1
1
2
7

Example output:
1

Example input:
2
1 2
2 3
11

Example output:
2

Editorial:
Dima and Horses
Contest: Codeforces Round 167 (Div. 2)
Difficulty rating: 2200
Tags: combinatorics, constructive algorithms, graphs

Dima came to the horse land. There are n horses living in the land. Each horse in the horse land has several enemies (enmity is a symmetric relationship). The horse land isn't very hostile, so the number of enemies of each horse is at most 3.

Right now the horse land is going through an election campaign. So the horses trusted Dima to split them into two parts. At that the horses want the following condition to hold: a horse shouldn't have more than one enemy in its party.

Help Dima split the horses into parties. Note that one of the parties can turn out to be empty.

Input format:
The first line contains two integers n, m $$( 1 \leq n \leq 3 \cdot 10^{5} ; 0 \leq m \leq \min ( 3 \cdot 10^{5}, \frac { n ( n - 1 ) } { 2 } ) )$$ — the number of horses in the horse land and the number of enemy pairs.

Next m lines define the enemy pairs. The i-th line contains integers ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi), which mean that horse ai is the enemy of horse bi.

Consider the horses indexed in some way from 1 to n. It is guaranteed that each horse has at most three enemies. No pair of enemies occurs more than once in the input.

Output format:
Print a line, consisting of n characters: the i-th character of the line must equal "0", if the horse number i needs to go to the first party, otherwise this character should equal "1".

If there isn't a way to divide the horses as required, print -1.

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

Example input:
3 3
1 2
3 2
3 1

Example output:
100

Example input:
2 1
2 1

Example output:
00

Editorial:
Tidying Up
Contest: ABBYY Cup 3.0
Difficulty rating: 2200
Tags: flows

Smart Beaver is careful about his appearance and pays special attention to shoes so he has a huge number of pairs of shoes from the most famous brands of the forest. He's trying to handle his shoes carefully so that each pair stood side by side. But by the end of the week because of his very active lifestyle in his dressing room becomes a mess.

Smart Beaver from ABBYY is not only the brightest beaver in the area, but he also is the most domestically oriented. For example, on Mondays the Smart Beaver cleans everything in his home.

It's Monday morning. Smart Beaver does not want to spend the whole day cleaning, besides, there is much in to do and it’s the gym day, so he wants to clean up as soon as possible. Now the floors are washed, the dust is wiped off — it’s time to clean up in the dressing room. But as soon as the Smart Beaver entered the dressing room, all plans for the day were suddenly destroyed: chaos reigned there and it seemed impossible to handle, even in a week. Give our hero some hope: tell him what is the minimum number of shoes need to change the position to make the dressing room neat.

The dressing room is rectangular and is divided into n × m equal squares, each square contains exactly one shoe. Each pair of shoes has a unique number that is integer from 1 to $${ \frac { n \cdot m } { 2 } }$$, more formally, a square with coordinates (i, j) contains an integer number of the pair which is lying on it. The Smart Beaver believes that the dressing room is neat only when each pair of sneakers lies together. We assume that the pair of sneakers in squares (i1, j1) and (i2, j2) lies together if |i1 - i2| + |j1 - j2| = 1.

Input format:
The first line contains two space-separated integers n and m. They correspond to the dressing room size. Next n lines contain m space-separated integers each. Those numbers describe the dressing room. Each number corresponds to a snicker.

It is guaranteed that:

- n·m is even.
- All numbers, corresponding to the numbers of pairs of shoes in the dressing room, will lie between 1 and $${ \frac { n \cdot m } { 2 } }$$.
- Each number from 1 to $${ \frac { n \cdot m } { 2 } }$$ will occur exactly twice.

The input limits for scoring 30 points are (subproblem C1):

- 2 ≤ n, m ≤ 8.

The input limits for scoring 100 points are (subproblems C1+C2):

- 2 ≤ n, m ≤ 80.

Output format:
Print exactly one integer — the minimum number of the sneakers that need to change their location.

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

Note:
The second sample.

Example input:
2 3
1 1 2
2 3 3

Example output:
2

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

Example output:
4

Editorial:
PE Lesson
Contest: ABBYY Cup 3.0
Difficulty rating: 2300
Tags: brute force, dp

Smart Beaver decided to be not only smart, but also a healthy beaver! And so he began to attend physical education classes at school X. In this school, physical education has a very creative teacher. One of his favorite warm-up exercises is throwing balls. Students line up. Each one gets a single ball in the beginning. The balls are numbered from 1 to n (by the demand of the inventory commission).

Figure 1. The initial position for n = 5.

After receiving the balls the students perform the warm-up exercise. The exercise takes place in a few throws. For each throw the teacher chooses any two arbitrary different students who will participate in it. The selected students throw their balls to each other. Thus, after each throw the students remain in their positions, and the two balls are swapped.

Figure 2. The example of a throw.

In this case there was a throw between the students, who were holding the 2-nd and the 4-th balls. Since the warm-up has many exercises, each of them can only continue for little time. Therefore, for each student we know the maximum number of throws he can participate in. For this lessons maximum number of throws will be 1 or 2.

Note that after all phases of the considered exercise any ball can end up with any student. Smart Beaver decided to formalize it and introduced the concept of the "ball order". The ball order is a sequence of n numbers that correspond to the order of balls in the line. The first number will match the number of the ball of the first from the left student in the line, the second number will match the ball of the second student, and so on. For example, in figure 2 the order of the balls was (1, 2, 3, 4, 5), and after the throw it was (1, 4, 3, 2, 5). Smart beaver knows the number of students and for each student he knows the maximum number of throws in which he can participate. And now he is wondering: what is the number of distinct ways of ball orders by the end of the exercise.

Input format:
The first line contains a single number n — the number of students in the line and the number of balls. The next line contains exactly n space-separated integers. Each number corresponds to a student in the line (the i-th number corresponds to the i-th from the left student in the line) and shows the number of throws he can participate in.

The input limits for scoring 30 points are (subproblem D1):

- 1 ≤ n ≤ 10.

The input limits for scoring 70 points are (subproblems D1+D2):

- 1 ≤ n ≤ 500.

The input limits for scoring 100 points are (subproblems D1+D2+D3):

- 1 ≤ n ≤ 1000000.

Output format:
The output should contain a single integer — the number of variants of ball orders after the warm up exercise is complete. As the number can be rather large, print it modulo 1000000007 (109 + 7).

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

Example input:
5
1 2 2 1 2

Example output:
120

Example input:
8
1 2 2 1 2 1 1 2

Example output:
16800

Editorial:
Summer Homework
Contest: ABBYY Cup 3.0
Difficulty rating: 1500
Tags: brute force, data structures

By the age of three Smart Beaver mastered all arithmetic operations and got this summer homework from the amazed teacher:

You are given a sequence of integers a1, a2, ..., an. Your task is to perform on it m consecutive operations of the following type:

1. For given numbers xi and vi assign value vi to element axi.
2. For given numbers li and ri you've got to calculate sum $$\sum_{x=0}^{r_i-l_i} (f_x \cdot a_{l_i+x})$$, where f0 = f1 = 1 and at i ≥ 2: fi = fi - 1 + fi - 2.
3. For a group of three numbers li ri di you should increase value ax by di for all x (li ≤ x ≤ ri).

Smart Beaver planned a tour around great Canadian lakes, so he asked you to help him solve the given problem.

Input format:
The first line contains two integers n and m (1 ≤ n, m ≤ 2·105) — the number of integers in the sequence and the number of operations, correspondingly. The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 105). Then follow m lines, each describes an operation. Each line starts with an integer ti (1 ≤ ti ≤ 3) — the operation type:

- if ti = 1, then next follow two integers xi vi (1 ≤ xi ≤ n, 0 ≤ vi ≤ 105);
- if ti = 2, then next follow two integers li ri (1 ≤ li ≤ ri ≤ n);
- if ti = 3, then next follow three integers li ri di (1 ≤ li ≤ ri ≤ n, 0 ≤ di ≤ 105).

The input limits for scoring 30 points are (subproblem E1):

- It is guaranteed that n does not exceed 100, m does not exceed 10000 and there will be no queries of the 3-rd type.

The input limits for scoring 70 points are (subproblems E1+E2):

- It is guaranteed that there will be queries of the 1-st and 2-nd type only.

The input limits for scoring 100 points are (subproblems E1+E2+E3):

- No extra limitations.

Output format:
For each query print the calculated sum modulo 1000000000 (109).

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

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

Example output:
12
32
8
50

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

Example output:
12
45

Editorial:
Suns and Rays
Contest: ABBYY Cup 3.0
Difficulty rating: 2200
Tags: dfs and similar, implementation

Smart Beaver became interested in drawing. He draws suns. However, at some point, Smart Beaver realized that simply drawing suns is boring. So he decided to design a program that will process his drawings. You are given a picture drawn by the beaver. It will have two colors: one for the background and one for the suns in the image. Your task will be to count the number of suns in the image and for each of them to count the number of rays.

Sun is arbitrarily rotated ellipse with rays. Ray is a segment which connects point on boundary of the ellipse with some point outside ellipse.

An image where all suns are circles.

An image where all suns are ellipses, their axes are parallel to the coordinate axes.

An image where all suns are rotated ellipses.

It is guaranteed that:

- No two suns have common points.
- The rays’ width is 3 pixels.
- The lengths of the ellipsis suns’ axes will lie between 40 and 200 pixels.
- No two rays intersect.
- The lengths of all rays will lie between 10 and 30 pixels.

Input format:
The first line contains two integers h and w — the height and width of the image (1 ≤ h, w ≤ 1600). Next h lines will contain w space-separated integers each. They describe Smart Beaver’s picture. Each number equals either a 0 (the image background), or a 1 (the sun color).

The input limits for scoring 30 points are (subproblem F1):

- All suns on the image are circles.

The input limits for scoring 70 points are (subproblems F1+F2):

- All suns on the image are ellipses with axes parallel to the coordinate axes.

The input limits for scoring 100 points are (subproblems F1+F2+F3):

- All suns on the image are ellipses, they can be arbitrarily rotated.

Output format:
The first line must contain a single number k — the number of suns on the beaver’s image. The second line must contain exactly k space-separated integers, corresponding to the number of rays on each sun. The numbers of the second line must be sorted in the increasing order.

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

Note:
For each complexity level you are suggested a sample in the initial data. You can download the samples at http://www.abbyy.ru/sun.zip.

Editorial:
Good Substrings
Contest: ABBYY Cup 3.0
Difficulty rating: 1700
Tags: hashing, strings

Smart Beaver recently got interested in a new word game. The point is as follows: count the number of distinct good substrings of some string s. To determine if a string is good or not the game uses rules. Overall there are n rules. Each rule is described by a group of three (p, l, r), where p is a string and l and r (l ≤ r) are integers. We’ll say that string t complies with rule (p, l, r), if the number of occurrences of string t in string p lies between l and r, inclusive. For example, string "ab", complies with rules ("ab", 1, 2) and ("aab", 0, 1), but does not comply with rules ("cd", 1, 2) and ("abab", 0, 1).

A substring s[l... r] (1 ≤ l ≤ r ≤ |s|) of string s = s1s2... s|s| (|s| is a length of s) is string slsl + 1... sr.

Consider a number of occurrences  of string t in string p as a number of pairs of integers l, r (1 ≤ l ≤ r ≤ |p|) such that p[l... r] = t.

We’ll say that string t is good if it complies with all n rules. Smart Beaver asks you to help him to write a program that can calculate the number of distinct good substrings of string s. Two substrings s[x... y] and s[z... w] are cosidered to be distinct iff s[x... y] ≠ s[z... w].

Input format:
The first line contains string s. The second line contains integer n. Next n lines contain the rules, one per line. Each of these lines contains a string and two integers pi, li, ri, separated by single spaces (0 ≤ li ≤ ri ≤ |pi|). It is guaranteed that all the given strings are non-empty and only contain lowercase English letters.

The input limits for scoring 30 points are (subproblem G1):

- 0 ≤ n ≤ 10.
- The length of string s and the maximum length of string p is  ≤ 200.

The input limits for scoring 70 points are (subproblems G1+G2):

- 0 ≤ n ≤ 10.
- The length of string s and the maximum length of string p is  ≤ 2000.

The input limits for scoring 100 points are (subproblems G1+G2+G3):

- 0 ≤ n ≤ 10.
- The length of string s and the maximum length of string p is  ≤ 50000.

Output format:
Print a single integer — the number of good substrings of string s.

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

Note:
There are three good substrings in the first sample test: «aab», «ab» and «b».

In the second test only substrings «e» and «t» are good.

Example input:
aaab
2
aa 0 0
aab 1 1

Example output:
3

Example input:
ltntlnen
3
n 0 0
ttlneenl 1 4
lelllt 1 1

Example output:
2

Editorial: