1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Messenger in MAC
Contest: Codeforces Round 932 (Div. 2)
Difficulty rating: 1800
Tags: binary search, brute force, constructive algorithms, data structures, dp, greedy, sortings

In the new messenger for the students of the Master's Assistance Center, Keftemerum, an update is planned, in which developers want to optimize the set of messages shown to the user. There are a total of $$$n$$$ messages. Each message is characterized by two integers $$$a_i$$$ and $$$b_i$$$. The time spent reading the set of messages with numbers $$$p_1, p_2, \ldots, p_k$$$ ($$$1 \le p_i \le n$$$, all $$$p_i$$$ are distinct) is calculated by the formula:

$$$$$$\Large \sum_{i=1}^{k} a_{p_i} + \sum_{i=1}^{k - 1} |b_{p_i} - b_{p_{i+1}}|$$$$$$

Note that the time to read a set of messages consisting of one message with number $$$p_1$$$ is equal to $$$a_{p_1}$$$. Also, the time to read an empty set of messages is considered to be $$$0$$$.

The user can determine the time $$$l$$$ that he is willing to spend in the messenger. The messenger must inform the user of the maximum possible size of the set of messages, the reading time of which does not exceed $$$l$$$. Note that the maximum size of the set of messages can be equal to $$$0$$$.

The developers of the popular messenger failed to implement this function, so they asked you to solve this problem.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$l$$$ ($$$1 \leq n \leq 2000$$$, $$$1 \leq l \leq 10^9$$$) — the number of messages and the time the user is willing to spend in the messenger.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^9$$$) — characteristics of the $$$i$$$-th message.

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$4 \cdot 10^6$$$.

Output format:
For each test case, output a single integer — the maximum possible size of a set of messages, the reading time of which does not exceed $$$l$$$.

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

Note:
In the first test case, you can take a set of three messages with numbers $$$p_1 = 3$$$, $$$p_2 = 2$$$, and $$$p_3 = 5$$$. The time spent reading this set is equal to $$$a_3 + a_2 + a_5 + |b_3 - b_2| + |b_2 - b_5| = 2 + 1 + 2 + |4 - 5| + |5 - 3| = 8$$$.

In the second test case, you can take a set of one message with number $$$p_1 = 1$$$. The time spent reading this set is equal to $$$a_1 = 4$$$.

In the fifth test case, it can be shown that there is no such non-empty set of messages, the reading time of which does not exceed $$$l$$$.

Example input:
5
5 8
4 3
1 5
2 4
4 3
2 3
1 6
4 10
3 12
4 8
2 1
2 12
5 26
24 7
8 28
30 22
3 8
17 17
5 14
15 3
1000000000 998244353
179 239
228 1337
993 1007

Example output:
3
1
2
1
0

Editorial:
Exam in MAC
Contest: Codeforces Round 932 (Div. 2)
Difficulty rating: 1800
Tags: binary search, combinatorics, implementation, math

The Master's Assistance Center has announced an entrance exam, which consists of the following.

The candidate is given a set $$$s$$$ of size $$$n$$$ and some strange integer $$$c$$$. For this set, it is needed to calculate the number of pairs of integers $$$(x, y)$$$ such that $$$0 \leq x \leq y \leq c$$$, $$$x + y$$$ is not contained in the set $$$s$$$, and also $$$y - x$$$ is not contained in the set $$$s$$$.

Your friend wants to enter the Center. Help him pass the exam!

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$c$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$, $$$1 \leq c \leq 10^9$$$) — the size of the set and the strange integer.

The second line of each test case contains $$$n$$$ integers $$$s_1, s_2, \ldots, s_{n}$$$ ($$$0 \leq s_1 < s_2 < \ldots < s_{n} \leq c$$$) — the elements of the set $$$s$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the number of suitable pairs of integers.

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

Note:
In the first test case, the following pairs are suitable: $$$(0, 0)$$$, $$$(2, 2)$$$, $$$(3, 3)$$$.

In the third test case, the following pairs are suitable: $$$(0, 1)$$$, $$$(0, 2)$$$, $$$(0, 4)$$$, $$$(1, 3)$$$, $$$(2, 6)$$$, $$$(3, 4)$$$, $$$(3, 5)$$$, $$$(4, 5)$$$, $$$(4, 6)$$$, $$$(5, 6)$$$.

Example input:
8
3 3
1 2 3
1 179
57
4 6
0 3 5 6
1 1
1
5 10
0 2 4 8 10
5 10
1 3 5 7 9
4 10
2 4 6 7
3 1000000000
228 1337 998244353

Example output:
3
16139
10
2
33
36
35
499999998999122959

Editorial:
Window Signals (hard version)
Contest: VK Cup 2022 - Отборочный раунд (Engine)
Difficulty rating: 3500

This is the hard version of the problem. In this version, the constraints on $$$h$$$ and $$$w$$$ are higher.

A house at the sea has $$$h$$$ floors, all of the same height. The side of the house facing the sea has $$$w$$$ windows at equal distances from each other on every floor. Thus, the windows are positioned in cells of a rectangular grid of size $$$h \times w$$$.

In every window, the light can be turned either on or off, except for the given $$$k$$$ (at most $$$2$$$) windows. In these $$$k$$$ windows the light can not be turned on, because it is broken.

In the dark, we can send a signal to a ship at sea using a configuration of lights turned on and off. However, the ship can not see the position of the lights with respect to the house. Thus, if one configuration of windows with lights on can be transformed into another using parallel translation, these configurations are considered equal. Note that only parallel translation is allowed, but neither rotations nor flips are. Moreover, a configuration without any light at all is not considered valid.

Find how many different signals the ship can receive and print this number modulo $$$998\,244\,353$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$h$$$, $$$w$$$, and $$$k$$$ ($$$1 \le h, w \le 200$$$; $$$0 \le k \le \min(h \cdot w, 2)$$$) — the height of the house, the number of windows on each floor, and the number of windows with broken lights.

If $$$k > 0$$$, each of the next $$$k$$$ lines contains two integers $$$r_i$$$ and $$$c_i$$$ ($$$1 \le r_i \le h$$$; $$$1 \le c_i \le w$$$) — the floor number and the window number with the broken light. The floors are numbered $$$1$$$ to $$$h$$$ from bottom to top, and the windows are numbered $$$1$$$ to $$$w$$$ from left to right. If $$$k = 2$$$, then either $$$r_1 \ne r_2$$$ or $$$c_1 \ne c_2$$$.

It is guaranteed that the sum of $$$h \cdot w$$$ over all test cases does not exceed $$$40\,000$$$.

Output format:
For each test case, print a single integer — the number of signals the ship can receive, modulo $$$998\,244\,353$$$.

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

Note:
In the first test case, the ship can receive four different signals: all lights on; lights on in two neighboring windows; lights on in the leftmost and the rightmost windows; or light on in any single window.

Example input:
10
1 3 0
2 2 0
3 2 0
4 5 0
12 7 0
1 1 1
1 1
1 3 1
1 2
3 4 1
3 4
2 3 2
1 1
2 1
4 5 2
2 3
4 2

Example output:
4
10
44
954368
34903934
0
2
1696
10
253144

Editorial:
Magnets
Contest: Codeforces Round 200 (Div. 2)
Difficulty rating: 800
Tags: implementation

Mad scientist Mike entertains himself by arranging rows of dominoes. He doesn't need dominoes, though: he uses rectangular magnets instead. Each magnet has two poles, positive (a "plus") and negative (a "minus"). If two magnets are put together at a close distance, then the like poles will repel each other and the opposite poles will attract each other.

Mike starts by laying one magnet horizontally on the table. During each following step Mike adds one more magnet horizontally to the right end of the row. Depending on how Mike puts the magnet on the table, it is either attracted to the previous one (forming a group of multiple magnets linked together) or repelled by it (then Mike lays this magnet at some distance to the right from the previous one). We assume that a sole magnet not linked to others forms a group of its own.

Mike arranged multiple magnets in a row. Determine the number of groups that the magnets formed.

Input format:
The first line of the input contains an integer n (1 ≤ n ≤ 100000) — the number of magnets. Then n lines follow. The i-th line (1 ≤ i ≤ n) contains either characters "01", if Mike put the i-th magnet in the "plus-minus" position, or characters "10", if Mike put the magnet in the "minus-plus" position.

Output format:
On the single line of the output print the number of groups of magnets.

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

Note:
The first testcase corresponds to the figure. The testcase has three groups consisting of three, one and two magnets.

The second testcase has two groups, each consisting of two magnets.

Example input:
6
10
10
10
01
10
10

Example output:
3

Example input:
4
01
01
10
10

Example output:
2

Editorial:
Simple Molecules
Contest: Codeforces Round 200 (Div. 2)
Difficulty rating: 1200
Tags: brute force, graphs, math

Mad scientist Mike is busy carrying out experiments in chemistry. Today he will attempt to join three atoms into one molecule.

A molecule consists of atoms, with some pairs of atoms connected by atomic bonds. Each atom has a valence number — the number of bonds the atom must form with other atoms. An atom can form one or multiple bonds with any other atom, but it cannot form a bond with itself. The number of bonds of an atom in the molecule must be equal to its valence number.

Mike knows valence numbers of the three atoms. Find a molecule that can be built from these atoms according to the stated rules, or determine that it is impossible.

Input format:
The single line of the input contains three space-separated integers a, b and c (1 ≤ a, b, c ≤ 106) — the valence numbers of the given atoms.

Output format:
If such a molecule can be built, print three space-separated integers — the number of bonds between the 1-st and the 2-nd, the 2-nd and the 3-rd, the 3-rd and the 1-st atoms, correspondingly. If there are multiple solutions, output any of them. If there is no solution, print "Impossible" (without the quotes).

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

Note:
The first sample corresponds to the first figure. There are no bonds between atoms 1 and 2 in this case.

The second sample corresponds to the second figure. There is one or more bonds between each pair of atoms.

The third sample corresponds to the third figure. There is no solution, because an atom cannot form bonds with itself.

The configuration in the fourth figure is impossible as each atom must have at least one atomic bond.

Example input:
1 1 2

Example output:
0 1 1

Example input:
3 4 5

Example output:
1 3 2

Editorial:
Little Elephant and Problem
Contest: Codeforces Round 136 (Div. 1)
Difficulty rating: 1300
Tags: implementation, sortings

The Little Elephant has got a problem — somebody has been touching his sorted by non-decreasing array a of length n and possibly swapped some elements of the array.

The Little Elephant doesn't want to call the police until he understands if he could have accidentally changed the array himself. He thinks that he could have accidentally changed array a, only if array a can be sorted in no more than one operation of swapping elements (not necessarily adjacent). That is, the Little Elephant could have accidentally swapped some two elements.

Help the Little Elephant, determine if he could have accidentally changed the array a, sorted by non-decreasing, himself.

Input format:
The first line contains a single integer n (2 ≤ n ≤ 105) — the size of array a. The next line contains n positive integers, separated by single spaces and not exceeding 109, — array a.

Note that the elements of the array are not necessarily distinct numbers.

Output format:
In a single line print "YES" (without the quotes) if the Little Elephant could have accidentally changed the array himself, and "NO" (without the quotes) otherwise.

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

Note:
In the first sample the array has already been sorted, so to sort it, we need 0 swap operations, that is not more than 1. Thus, the answer is "YES".

In the second sample we can sort the array if we swap elements 1 and 3, so we need 1 swap operation to sort the array. Thus, the answer is "YES".

In the third sample we can't sort the array in more than one swap operation, so the answer is "NO".

Example input:
2
1 2

Example output:
YES

Example input:
3
3 2 1

Example output:
YES

Editorial:
Little Elephant and Array
Contest: Codeforces Round 136 (Div. 1)
Difficulty rating: 1800
Tags: constructive algorithms, data structures

The Little Elephant loves playing with arrays. He has array a, consisting of n positive integers, indexed from 1 to n. Let's denote the number with index i as ai.

Additionally the Little Elephant has m queries to the array, each query is characterised by a pair of integers lj and rj (1 ≤ lj ≤ rj ≤ n). For each query lj, rj the Little Elephant has to count, how many numbers x exist, such that number x occurs exactly x times among numbers alj, alj + 1, ..., arj.

Help the Little Elephant to count the answers to all queries.

Input format:
The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 105) — the size of array a and the number of queries to it. The next line contains n space-separated positive integers a1, a2, ..., an (1 ≤ ai ≤ 109). Next m lines contain descriptions of queries, one per line. The j-th of these lines contains the description of the j-th query as two space-separated integers lj and rj (1 ≤ lj ≤ rj ≤ n).

Output format:
In m lines print m integers — the answers to the queries. The j-th line should contain the answer to the j-th query.

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

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

Example output:
3
1

Editorial:
Little Elephant and Shifts
Contest: Codeforces Round 136 (Div. 1)
Difficulty rating: 2100
Tags: data structures

The Little Elephant has two permutations a and b of length n, consisting of numbers from 1 to n, inclusive. Let's denote the i-th (1 ≤ i ≤ n) element of the permutation a as ai, the j-th (1 ≤ j ≤ n) element of the permutation b — as bj.

The distance between permutations a and b is the minimum absolute value of the difference between the positions of the occurrences of some number in a and in b. More formally, it's such minimum |i - j|, that ai = bj.

A cyclic shift number i (1 ≤ i ≤ n) of permutation b consisting from n elements is a permutation bibi + 1... bnb1b2... bi - 1. Overall a permutation has n cyclic shifts.

The Little Elephant wonders, for all cyclic shifts of permutation b, what is the distance between the cyclic shift and permutation a?

Input format:
The first line contains a single integer n (1 ≤ n ≤ 105) — the size of the permutations. The second line contains permutation a as n distinct numbers from 1 to n, inclusive. The numbers are separated with single spaces. The third line contains permutation b in the same format.

Output format:
In n lines print n integers — the answers for cyclic shifts. Print the answers to the shifts in the order of the shifts' numeration in permutation b, that is, first for the 1-st cyclic shift, then for the 2-nd, and so on.

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

Example input:
2
1 2
2 1

Example output:
1
0

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

Example output:
2
1
0
1

Editorial:
Little Elephant and Triangle
Contest: Codeforces Round 136 (Div. 1)
Difficulty rating: 2500
Tags: geometry, math

The Little Elephant is playing with the Cartesian coordinates' system. Most of all he likes playing with integer points. The Little Elephant defines an integer point as a pair of integers (x; y), such that 0 ≤ x ≤ w and 0 ≤ y ≤ h. Thus, the Little Elephant knows only (w + 1)·(h + 1) distinct integer points.

The Little Elephant wants to paint a triangle with vertexes at integer points, the triangle's area must be a positive integer. For that, he needs to find the number of groups of three points that form such triangle. At that, the order of points in a group matters, that is, the group of three points (0;0), (0;2), (2;2) isn't equal to the group (0;2), (0;0), (2;2).

Help the Little Elephant to find the number of groups of three integer points that form a nondegenerate triangle with integer area.

Input format:
A single line contains two integers w and h (1 ≤ w, h ≤ 4000).

Output format:
In a single output line print an integer — the remainder of dividing the answer to the problem by 1000000007 (109 + 7).

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

Example input:
2 1

Example output:
36

Example input:
2 2

Example output:
240

Editorial:
Little Elephant and Inversions
Contest: Codeforces Round 136 (Div. 1)
Difficulty rating: 2400
Tags: data structures, two pointers

The Little Elephant has array a, consisting of n positive integers, indexed from 1 to n. Let's denote the number with index i as ai.

The Little Elephant wants to count, how many pairs of integers l and r are there, such that 1 ≤ l < r ≤ n and sequence b = a1a2... alarar + 1... an has no more than k inversions.

An inversion in sequence b is a pair of elements of the sequence b, that change their relative order after a stable sorting of the sequence. In other words, an inversion is a pair of integers i and j, such that 1 ≤ i < j ≤ |b| and bi > bj, where |b| is the length of sequence b, and bj is its j-th element.

Help the Little Elephant and count the number of the described pairs.

Input format:
The first line contains two integers n and k (2 ≤ n ≤ 105, 0 ≤ k ≤ 1018) — the size of array a and the maximum allowed number of inversions respectively. The next line contains n positive integers, separated by single spaces, a1, a2, ..., an (1 ≤ ai ≤ 109) — elements of array a.

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

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

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

Example input:
3 1
1 3 2

Example output:
3

Example input:
5 2
1 3 2 1 7

Example output:
6

Editorial:
Slime Combining
Contest: Wunder Fund Round 2016 (Div. 1 + Div. 2 combined)
Difficulty rating: 800
Tags: implementation

Your friend recently gave you some slimes for your birthday. You have n slimes all initially with value 1.

You are going to play a game with these slimes. Initially, you put a single slime by itself in a row. Then, you will add the other n - 1 slimes one by one. When you add a slime, you place it at the right of all already placed slimes. Then, while the last two slimes in the row have the same value v, you combine them together to create a slime with value v + 1.

You would like to see what the final state of the row is after you've added all n slimes. Please print the values of the slimes in the row from left to right.

Input format:
The first line of the input will contain a single integer, n (1 ≤ n ≤ 100 000).

Output format:
Output a single line with k integers, where k is the number of slimes in the row after you've finished the procedure described in the problem statement. The i-th of these numbers should be the value of the i-th slime from the left.

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

Note:
In the first sample, we only have a single slime with value 1. The final state of the board is just a single slime with value 1.

In the second sample, we perform the following steps:

Initially we place a single slime in a row by itself. Thus, row is initially 1.

Then, we will add another slime. The row is now 1 1. Since two rightmost slimes have the same values, we should replace these slimes with one with value 2. Thus, the final state of the board is 2.

In the third sample, after adding the first two slimes, our row is 2. After adding one more slime, the row becomes 2 1.

In the last sample, the steps look as follows:

1. 1
2. 2
3. 2 1
4. 3
5. 3 1
6. 3 2
7. 3 2 1
8. 4

Example input:
1

Example output:
1

Example input:
2

Example output:
2

Editorial:
Answer is index of 1 bits in binary representation of n. You can also simulate this.
Guess the Permutation
Contest: Wunder Fund Round 2016 (Div. 1 + Div. 2 combined)
Difficulty rating: 1100
Tags: constructive algorithms

Bob has a permutation of integers from 1 to n. Denote this permutation as p. The i-th element of p will be denoted as pi. For all pairs of distinct integers i, j between 1 and n, he wrote the number ai, j = min(pi, pj). He writes ai, i = 0 for all integer i from 1 to n.

Bob gave you all the values of ai, j that he wrote down. Your job is to reconstruct any permutation that could have generated these values. The input will be formed so that it is guaranteed that there is at least one solution that is consistent with the information given.

Input format:
The first line of the input will contain a single integer n (2 ≤ n ≤ 50).

The next n lines will contain the values of ai, j. The j-th number on the i-th line will represent ai, j. The i-th number on the i-th line will be 0. It's guaranteed that ai, j = aj, i and there is at least one solution consistent with the information given.

Output format:
Print n space separated integers, which represents a permutation that could have generated these values. If there are multiple possible solutions, print any of them.

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

Note:
In the first case, the answer can be {1, 2} or {2, 1}.

In the second case, another possible answer is {2, 4, 5, 1, 3}.

Example input:
2
0 1
1 0

Example output:
2 1

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

Example output:
2 5 4 1 3

Editorial: