1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Draw!
Contest: Codeforces Round 541 (Div. 2)
Difficulty rating: 1400
Tags: greedy, implementation

You still have partial information about the score during the historic football match. You are given a set of pairs $$$(a_i, b_i)$$$, indicating that at some point during the match the score was "$$$a_i$$$: $$$b_i$$$". It is known that if the current score is «$$$x$$$:$$$y$$$», then after the goal it will change to "$$$x+1$$$:$$$y$$$" or "$$$x$$$:$$$y+1$$$". What is the largest number of times a draw could appear on the scoreboard?

The pairs "$$$a_i$$$:$$$b_i$$$" are given in chronological order (time increases), but you are given score only for some moments of time. The last pair corresponds to the end of the match.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10000$$$) — the number of known moments in the match.

Each of the next $$$n$$$ lines contains integers $$$a_i$$$ and $$$b_i$$$ ($$$0 \le a_i, b_i \le 10^9$$$), denoting the score of the match at that moment (that is, the number of goals by the first team and the number of goals by the second team).

All moments are given in chronological order, that is, sequences $$$x_i$$$ and $$$y_j$$$ are non-decreasing. The last score denotes the final result of the match.

Output format:
Print the maximum number of moments of time, during which the score was a draw. The starting moment of the match (with a score 0:0) is also counted.

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

Note:
In the example one of the possible score sequences leading to the maximum number of draws is as follows: 0:0, 1:0, 2:0, 2:1, 3:1, 3:2, 3:3, 3:4.

Example input:
3
2 0
3 1
3 4

Example output:
2

Example input:
3
0 0
0 0
0 0

Example output:
1

Editorial:
Since some scores are already fixed, we only have "liberty" in between of them.
One can easily see, that basically we need to solve the problem between each neighboring pair and then sum all the answers (it may turn out, that for a fixed score, it will be accounted twice, in the "left" pair and in the "right", but it's easy to subtract it back).
How to solve the problem between score $$$(a, b)$$$ and $$$(c, d)$$$? We want to put in the middle as much pairs $$$(x, x)$$$ as possible. So we have $$$a \le x \le c$$$ and $$$b \le x \le d$$$, hence $$$\max(a, b) \le x \le \min(c, d)$$$, it's easy to count the number of such $$$x$$$'s and you can also see, that there is a goal sequence which achieves all such $$$(x, x)$$$'s together.
Lucky Days
Contest: Mail.Ru Cup 2018 Round 2
Difficulty rating: 1900
Tags: math, number theory

Bob and Alice are often participating in various programming competitions. Like many competitive programmers, Alice and Bob have good and bad days. They noticed, that their lucky and unlucky days are repeating with some period. For example, for Alice days $$$[l_a; r_a]$$$ are lucky, then there are some unlucky days: $$$[r_a + 1; l_a + t_a - 1]$$$, and then there are lucky days again: $$$[l_a + t_a; r_a + t_a]$$$ and so on. In other words, the day is lucky for Alice if it lies in the segment $$$[l_a + k t_a; r_a + k t_a]$$$ for some non-negative integer $$$k$$$.

The Bob's lucky day have similar structure, however the parameters of his sequence are different: $$$l_b$$$, $$$r_b$$$, $$$t_b$$$. So a day is a lucky for Bob if it lies in a segment $$$[l_b + k t_b; r_b + k t_b]$$$, for some non-negative integer $$$k$$$.

Alice and Bob want to participate in team competitions together and so they want to find out what is the largest possible number of consecutive days, which are lucky for both Alice and Bob.

Input format:
The first line contains three integers $$$l_a$$$, $$$r_a$$$, $$$t_a$$$ ($$$0 \le l_a \le r_a \le t_a - 1, 2 \le t_a \le 10^9$$$) and describes Alice's lucky days.

The second line contains three integers $$$l_b$$$, $$$r_b$$$, $$$t_b$$$ ($$$0 \le l_b \le r_b \le t_b - 1, 2 \le t_b \le 10^9$$$) and describes Bob's lucky days.

It is guaranteed that both Alice and Bob have some unlucky days.

Output format:
Print one integer: the maximum number of days in the row that are lucky for both Alice and Bob.

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

Note:
The graphs below correspond to the two sample tests and show the lucky and unlucky days of Alice and Bob as well as the possible solutions for these tests.

Example input:
0 2 5
1 3 5

Example output:
2

Example input:
0 1 3
2 3 6

Example output:
1

Editorial:
All possible shifts of Alice's and Bobs' pattern periods are the multiples of $$$\mathrm{gcd}(t_a, t_b)$$$. You want to use such a shift that the start of their lucky days is as close as possible. Also if they can't coincide precisely, you need to try shifting in such way that Alice's lucky days start before Bob's, and the opposite.
Segments on the Line
Contest: Mail.Ru Cup 2018 Round 2
Difficulty rating: 2500
Tags: binary search, dp

You are a given a list of integers $$$a_1, a_2, \ldots, a_n$$$ and $$$s$$$ of its segments $$$[l_j; r_j]$$$ (where $$$1 \le l_j \le r_j \le n$$$).

You need to select exactly $$$m$$$ segments in such a way that the $$$k$$$-th order statistic of the multiset of $$$a_i$$$, where $$$i$$$ is contained in at least one segment, is the smallest possible. If it's impossible to select a set of $$$m$$$ segments in such a way that the multiset contains at least $$$k$$$ elements, print -1.

The $$$k$$$-th order statistic of a multiset is the value of the $$$k$$$-th element after sorting the multiset in non-descending order.

Input format:
The first line contains four integers $$$n$$$, $$$s$$$, $$$m$$$ and $$$k$$$ ($$$1 \le m \le s \le 1500$$$, $$$1 \le k \le n \le 1500$$$) — the size of the list, the number of segments, the number of segments to choose and the statistic number.

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — the values of the numbers in the list.

Each of the next $$$s$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — the endpoints of the segments.

It is possible that some segments coincide.

Output format:
Print exactly one integer — the smallest possible $$$k$$$-th order statistic, or -1 if it's impossible to choose segments in a way that the multiset contains at least $$$k$$$ elements.

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

Note:
In the first example, one possible solution is to choose the first and the third segment. Together they will cover three elements of the list (all, except for the third one). This way the $$$2$$$-nd order statistic for the covered elements is $$$2$$$.

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

Example output:
2

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

Example output:
1

Editorial:
Let's find the answer using binary search. Sort segments in the order of increasing right ends. Now we are solving the following problem: how many numbers $$$\le x$$$ we cover by $$$m$$$ segments. This may be solved with a DP along the scan line. We count how many numbers can we cover using at most $$$j$$$ of the first $$$i$$$ segments, making sure that we must always take the $$$i$$$-th segment. There are two options - either the new segment overlaps with the previous one, or not (we will ignore the case that two segments may be inside each other, because in the end it just means we can choose fewer than $$$m$$$ segments). In the case of overlap it's always optimal to choose the previous segment such that it spans as far as possible to the left (i.e. its left end is lowest). Which segment that would be for a given $$$i$$$ is easy to precompute. The case when the segments don't overlap can be implemented by a maintaining prefix maximum for all $$$j$$$. Overall complexity is $$$O(1500^2 \cdot \log 10^9)$$$.
Shell Game
Contest: Codeforces Round 401 (Div. 2)
Difficulty rating: 1000
Tags: constructive algorithms, implementation, math

Bomboslav likes to look out of the window in his room and watch lads outside playing famous shell game. The game is played by two persons: operator and player. Operator takes three similar opaque shells and places a ball beneath one of them. Then he shuffles the shells by swapping some pairs and the player has to guess the current position of the ball.

Bomboslav noticed that guys are not very inventive, so the operator always swaps the left shell with the middle one during odd moves (first, third, fifth, etc.) and always swaps the middle shell with the right one during even moves (second, fourth, etc.).

Let's number shells from 0 to 2 from left to right. Thus the left shell is assigned number 0, the middle shell is 1 and the right shell is 2. Bomboslav has missed the moment when the ball was placed beneath the shell, but he knows that exactly n movements were made by the operator and the ball was under shell x at the end. Now he wonders, what was the initial position of the ball?

Input format:
The first line of the input contains an integer n (1 ≤ n ≤ 2·109) — the number of movements made by the operator.

The second line contains a single integer x (0 ≤ x ≤ 2) — the index of the shell where the ball was found after n movements.

Output format:
Print one integer from 0 to 2 — the index of the shell where the ball was initially placed.

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

Note:
In the first sample, the ball was initially placed beneath the middle shell and the operator completed four movements.

1. During the first move operator swapped the left shell and the middle shell. The ball is now under the left shell.
2. During the second move operator swapped the middle shell and the right one. The ball is still under the left shell.
3. During the third move operator swapped the left shell and the middle shell again. The ball is again in the middle.
4. Finally, the operators swapped the middle shell and the right shell. The ball is now beneath the right shell.

Example input:
4
2

Example output:
1

Example input:
1
1

Example output:
0

Editorial:
Fix the initial numeration of shells. Consider function p(i, j) to be the index of the shell located at position j after i moves.
• p(0) = {0, 1, 2}
• p(1) = {1, 0, 2}
• p(2) = {1, 2, 0}
• p(3) = {2, 1, 0}
• p(4) = {2, 0, 1}
• p(5) = {0, 2, 1}
• p(6) = {0, 1, 2}
Thus, after 6 movements all shells will get back to initial positions. To solve the problem we need to take n modulo 6 and simulate that number of moves.
Game of Credit Cards
Contest: Codeforces Round 401 (Div. 2)
Difficulty rating: 1300
Tags: data structures, dp, greedy, sortings

After the fourth season Sherlock and Moriary have realized the whole foolishness of the battle between them and decided to continue their competitions in peaceful game of Credit Cards.

Rules of this game are simple: each player bring his favourite n-digit credit card. Then both players name the digits written on their cards one by one. If two digits are not equal, then the player, whose digit is smaller gets a flick (knock in the forehead usually made with a forefinger) from the other player. For example, if n = 3, Sherlock's card is 123 and Moriarty's card has number 321, first Sherlock names 1 and Moriarty names 3 so Sherlock gets a flick. Then they both digit 2 so no one gets a flick. Finally, Sherlock names 3, while Moriarty names 1 and gets a flick.

Of course, Sherlock will play honestly naming digits one by one in the order they are given, while Moriary, as a true villain, plans to cheat. He is going to name his digits in some other order (however, he is not going to change the overall number of occurences of each digit). For example, in case above Moriarty could name 1, 2, 3 and get no flicks at all, or he can name 2, 3 and 1 to give Sherlock two flicks.

Your goal is to find out the minimum possible number of flicks Moriarty will get (no one likes flicks) and the maximum possible number of flicks Sherlock can get from Moriarty. Note, that these two goals are different and the optimal result may be obtained by using different strategies.

Input format:
The first line of the input contains a single integer n (1 ≤ n ≤ 1000) — the number of digits in the cards Sherlock and Moriarty are going to use.

The second line contains n digits — Sherlock's credit card number.

The third line contains n digits — Moriarty's credit card number.

Output format:
First print the minimum possible number of flicks Moriarty will get. Then print the maximum possible number of flicks that Sherlock can get from Moriarty.

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

Note:
First sample is elaborated in the problem statement. In the second sample, there is no way Moriarty can avoid getting two flicks.

Example input:
3
123
321

Example output:
0
2

Example input:
2
88
00

Example output:
2
0

Editorial:
First we want to consider a strategy that minimizes the amount of flicks Moriarty will receive from Sherlock. This is similar to loosing as few rounds as possible. He can use digit 0 can be used to not loose against digit 0, digit 1 to not loose against digits 0 and 1 and so on. Thus, Moriarty should try all digits from 0 to 9 and greedily apply them to Sherlock's digits they can beat. If the maximum number of rounds Moriarty can not loose is a the answer for the first question is n - a.
For the second question we need to count the maximum number of rounds Moriarty can win. Now digit 0 is useless, digit 1 wins against digit 0, digit 2 wins against digits 0 and 1, and so on. Thus, Moriarty should consider his digits from 0 to 9 and greedily use them to digits they can beat.
Alyona and Spreadsheet
Contest: Codeforces Round 401 (Div. 2)
Difficulty rating: 1600
Tags: binary search, data structures, dp, greedy, implementation, two pointers

During the lesson small girl Alyona works with one famous spreadsheet computer program and learns how to edit tables.

Now she has a table filled with integers. The table consists of n rows and m columns. By ai, j we will denote the integer located at the i-th row and the j-th column. We say that the table is sorted in non-decreasing order in the column j if ai, j ≤ ai + 1, j for all i from 1 to n - 1.

Teacher gave Alyona k tasks. For each of the tasks two integers l and r are given and Alyona has to answer the following question: if one keeps the rows from l to r inclusive and deletes all others, will the table be sorted in non-decreasing order in at least one column? Formally, does there exist such j that ai, j ≤ ai + 1, j for all i from l to r - 1 inclusive.

Alyona is too small to deal with this task and asks you to help!

Input format:
The first line of the input contains two positive integers n and m (1 ≤ n·m ≤ 100 000) — the number of rows and the number of columns in the table respectively. Note that your are given a constraint that bound the product of these two integers, i.e. the number of elements in the table.

Each of the following n lines contains m integers. The j-th integers in the i of these lines stands for ai, j (1 ≤ ai, j ≤ 109).

The next line of the input contains an integer k (1 ≤ k ≤ 100 000) — the number of task that teacher gave to Alyona.

The i-th of the next k lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n).

Output format:
Print "Yes" to the i-th line of the output if the table consisting of rows from li to ri inclusive is sorted in non-decreasing order in at least one column. Otherwise, print "No".

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

Note:
In the sample, the whole table is not sorted in any column. However, rows 1–3 are sorted in column 1, while rows 4–5 are sorted in column 3.

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

Example output:
Yes
No
Yes
Yes
Yes
No

Editorial:
For each cell (i, j) compute value up(i, j) equal to maximum r, such that table is non-decreasing in row j if we keep only rows from i to r inclusive. This values can be computed in O(nm) time using the following formulas:
• up(i, j) = up(i + 1, j) + 1, if i < n and ai, j < ai + 1, j;
• up(i, j) = 1 otherwise.
To process the query (li, ri) we have to check whether there exists k such that up(li, k) ≥ ri. We will answer this questions using by precomputing maximum values in each row $${ \mathrm { b e s t } } ( i ) = \operatorname* { m a x } _ { j = 1 } ^ { m } u p ( i, j )$$.
Rock-paper-scissors
Contest: School Personal Contest #3 (Winter Computer School 2010/11) - Codeforces Beta Round 45 (ACM-ICPC Rules)
Difficulty rating: 900
Tags: implementation, schedules

Uncle Fyodor, Matroskin the Cat and Sharic the Dog live their simple but happy lives in Prostokvashino. Sometimes they receive parcels from Uncle Fyodor’s parents and sometimes from anonymous benefactors, in which case it is hard to determine to which one of them the package has been sent. A photographic rifle is obviously for Sharic who loves hunting and fish is for Matroskin, but for whom was a new video game console meant? Every one of the three friends claimed that the present is for him and nearly quarreled. Uncle Fyodor had an idea how to solve the problem justly: they should suppose that the console was sent to all three of them and play it in turns. Everybody got relieved but then yet another burning problem popped up — who will play first? This time Matroskin came up with a brilliant solution, suggesting the most fair way to find it out: play rock-paper-scissors together. The rules of the game are very simple. On the count of three every player shows a combination with his hand (or paw). The combination corresponds to one of three things: a rock, scissors or paper. Some of the gestures win over some other ones according to well-known rules: the rock breaks the scissors, the scissors cut the paper, and the paper gets wrapped over the stone. Usually there are two players. Yet there are three friends, that’s why they decided to choose the winner like that: If someone shows the gesture that wins over the other two players, then that player wins. Otherwise, another game round is required. Write a program that will determine the winner by the gestures they have shown.

Input format:
The first input line contains the name of the gesture that Uncle Fyodor showed, the second line shows which gesture Matroskin showed and the third line shows Sharic’s gesture.

Output format:
Print "F" (without quotes) if Uncle Fyodor wins. Print "M" if Matroskin wins and "S" if Sharic wins. If it is impossible to find the winner, print "?".

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

Example input:
rock
rock
rock

Example output:
?

Example input:
paper
rock
rock

Example output:
F

Editorial:
Land Lot
Contest: School Personal Contest #3 (Winter Computer School 2010/11) - Codeforces Beta Round 45 (ACM-ICPC Rules)
Difficulty rating: 1200
Tags: brute force, implementation

Vasya has a beautiful garden where wonderful fruit trees grow and yield fantastic harvest every year. But lately thieves started to sneak into the garden at nights and steal the fruit too often. Vasya can’t spend the nights in the garden and guard the fruit because there’s no house in the garden! Vasya had been saving in for some time and finally he decided to build the house. The rest is simple: he should choose in which part of the garden to build the house. In the evening he sat at his table and drew the garden’s plan. On the plan the garden is represented as a rectangular checkered field n × m in size divided into squares whose side length is 1. In some squares Vasya marked the trees growing there (one shouldn’t plant the trees too close to each other that’s why one square contains no more than one tree). Vasya wants to find a rectangular land lot a × b squares in size to build a house on, at that the land lot border should go along the lines of the grid that separates the squares. All the trees that grow on the building lot will have to be chopped off. Vasya loves his garden very much, so help him choose the building land lot location so that the number of chopped trees would be as little as possible.

Input format:
The first line contains two integers n and m (1 ≤ n, m ≤ 50) which represent the garden location. The next n lines contain m numbers 0 or 1, which describe the garden on the scheme. The zero means that a tree doesn’t grow on this square and the 1 means that there is a growing tree. The last line contains two integers a and b (1 ≤ a, b ≤ 50). Note that Vasya can choose for building an a × b rectangle as well a b × a one, i.e. the side of the lot with the length of a can be located as parallel to the garden side with the length of n, as well as parallel to the garden side with the length of m.

Output format:
Print the minimum number of trees that needs to be chopped off to select a land lot a × b in size to build a house on. It is guaranteed that at least one lot location can always be found, i. e. either a ≤ n and b ≤ m, or a ≤ m и b ≤ n.

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

Note:
In the second example the upper left square is (1,1) and the lower right is (3,2).

Example input:
2 2
1 0
1 1
1 1

Example output:
0

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

Example output:
2

Editorial:
Permutations
Contest: School Personal Contest #3 (Winter Computer School 2010/11) - Codeforces Beta Round 45 (ACM-ICPC Rules)
Difficulty rating: 1500
Tags: greedy

A permutation is a sequence of integers from 1 to n of length n containing each number exactly once. For example, (1), (4, 3, 5, 1, 2), (3, 2, 1) are permutations, and (1, 1), (4, 3, 1), (2, 3, 4) are not.

There are many tasks on permutations. Today you are going to solve one of them. Let’s imagine that somebody took several permutations (perhaps, with a different number of elements), wrote them down consecutively as one array and then shuffled the resulting array. The task is to restore the initial permutations if it is possible.

Input format:
The first line contains an integer n (1 ≤ n ≤ 105). The next line contains the mixed array of n integers, divided with a single space. The numbers in the array are from 1 to 105.

Output format:
If this array can be split into several permutations so that every element of the array belongs to exactly one permutation, print in the first line the number of permutations. The second line should contain n numbers, corresponding to the elements of the given array. If the i-th element belongs to the first permutation, the i-th number should be 1, if it belongs to the second one, then its number should be 2 and so on. The order of the permutations’ numbering is free.

If several solutions are possible, print any one of them. If there’s no solution, print in the first line  - 1.

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

Note:
In the first sample test the array is split into three permutations: (2, 1), (3, 2, 1, 4, 5), (1, 2). The first permutation is formed by the second and the fourth elements of the array, the second one — by the third, the fifth, the sixth, the seventh and the ninth elements, the third one — by the first and the eigth elements. Clearly, there are other splitting variants possible.

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

Example output:
3
3 1 2 1 2 2 2 3 2

Example input:
4
4 3 2 1

Example output:
1
1 1 1 1

Editorial: