1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Juju and Binary String
Contest: Codeforces Round 779 (Div. 2)
Difficulty rating: 2700
Tags: brute force, constructive algorithms, greedy, math

The cuteness of a binary string is the number of $$$\texttt{1}$$$s divided by the length of the string. For example, the cuteness of $$$\texttt{01101}$$$ is $$$\frac{3}{5}$$$.

Juju has a binary string $$$s$$$ of length $$$n$$$. She wants to choose some non-intersecting subsegments of $$$s$$$ such that their concatenation has length $$$m$$$ and it has the same cuteness as the string $$$s$$$.

More specifically, she wants to find two arrays $$$l$$$ and $$$r$$$ of equal length $$$k$$$ such that $$$1 \leq l_1 \leq r_1 < l_2 \leq r_2 < \ldots < l_k \leq r_k \leq n$$$, and also:

- $$$\sum\limits_{i=1}^k (r_i - l_i + 1) = m$$$;
- The cuteness of $$$s[l_1,r_1]+s[l_2,r_2]+\ldots+s[l_k,r_k]$$$ is equal to the cuteness of $$$s$$$, where $$$s[x, y]$$$ denotes the subsegment $$$s_x s_{x+1} \ldots s_y$$$, and $$$+$$$ denotes string concatenation.

Juju does not like splitting the string into many parts, so she also wants to minimize the value of $$$k$$$. Find the minimum value of $$$k$$$ such that there exist $$$l$$$ and $$$r$$$ that satisfy the constraints above or determine that it is impossible to find such $$$l$$$ and $$$r$$$ for any $$$k$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq m \leq n \leq 2 \cdot 10^5$$$).

The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$.

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

Output format:
For each test case, if there is no valid pair of $$$l$$$ and $$$r$$$, print $$$-1$$$.

Otherwise, print $$$k + 1$$$ lines.

In the first line, print a number $$$k$$$ ($$$1 \leq k \leq m$$$) — the minimum number of subsegments required.

Then print $$$k$$$ lines, the $$$i$$$-th should contain $$$l_i$$$ and $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$) — the range of the $$$i$$$-th subsegment. Note that you should output the subsegments such that the inequality $$$l_1 \leq r_1 < l_2 \leq r_2 < \ldots < l_k \leq r_k$$$ is true.

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

Note:
In the first example, the cuteness of $$$\texttt{0011}$$$ is the same as the cuteness of $$$\texttt{01}$$$.

In the second example, the cuteness of $$$\texttt{11000011}$$$ is $$$\frac{1}{2}$$$ and there is no subsegment of size $$$6$$$ with the same cuteness. So we must use $$$2$$$ disjoint subsegments $$$\texttt{10}$$$ and $$$\texttt{0011}$$$.

In the third example, there are $$$8$$$ ways to split the string such that $$$\sum\limits_{i=1}^k (r_i - l_i + 1) = 3$$$ but none of them has the same cuteness as $$$\texttt{0101}$$$.

In the last example, we don't have to split the string.

Example input:
4
4 2
0011
8 6
11000011
4 3
0101
5 5
11111

Example output:
1
2 3
2
2 3
5 8
-1
1
1 5

Editorial:
Long Comparison
Contest: Educational Codeforces Round 118 (Rated for Div. 2)
Difficulty rating: 900
Tags: implementation, math

Monocarp wrote down two numbers on a whiteboard. Both numbers follow a specific format: a positive integer $$$x$$$ with $$$p$$$ zeros appended to its end.

Now Monocarp asks you to compare these two numbers. Can you help him?

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

The first line of each testcase contains two integers $$$x_1$$$ and $$$p_1$$$ ($$$1 \le x_1 \le 10^6; 0 \le p_1 \le 10^6$$$) — the description of the first number.

The second line of each testcase contains two integers $$$x_2$$$ and $$$p_2$$$ ($$$1 \le x_2 \le 10^6; 0 \le p_2 \le 10^6$$$) — the description of the second number.

Output format:
For each testcase print the result of the comparison of the given two numbers. If the first number is smaller than the second one, print '<'. If the first number is greater than the second one, print '>'. If they are equal, print '='.

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

Note:
The comparisons in the example are: $$$20 > 19$$$, $$$1000 = 1000$$$, $$$1999 < 2000$$$, $$$1 = 1$$$, $$$99 < 100$$$.

Example input:
5
2 1
19 0
10 2
100 1
1999 0
2 3
1 0
1 0
99 0
1 2

Example output:
>
=
<
=
<

Editorial:
First, let's say that appending the number with $$$p$$$ zeros is the same as multiplying it by $$$10^p$$$.
The given numbers are so large that they can't fit into any reasonable integer type. Even if you use a language with unlimited length integers (python, for example) or store the numbers in strings, you should still face the time limit issue. So let's learn to shrink the numbers a bit.
Note that the result of the comparison of two numbers doesn't change if you divide both numbers by the same positive number. So we can keep dividing both numbers by $$$10$$$ until one of them is not divisible anymore. Let's also ignore the trailing zeros in $$$x_1$$$ and $$$x_2$$$ and leave them as is. If the first number is appended with $$$p_1$$$ zeros and the second numbers is appended with $$$p_2$$$ zeros, we can subtract $$$min(p_1, p_2)$$$ from both values, effectively dividing both numbers by $$$10^{min(p_1, p_2)}$$$.
This way, one of the numbers becomes short enough to fit into an integer type (because it has $$$p=0$$$ and $$$x$$$ is only up to $$$10^6$$$). The other number might still be large enough.
However, if it's really large, we can instantly say that it's larger than another one. Say, if its $$$p$$$ is at least $$$7$$$. This number it at least $$$10^7$$$ and the other number is at most $$$10^6$$$.
Otherwise, we can calculate this number as well and compare the values normally.
Overall complexity: $$$O(1)$$$ per testcase.
Absent Remainder
Contest: Educational Codeforces Round 118 (Rated for Div. 2)
Difficulty rating: 1000
Tags: greedy, implementation, sortings

You are given a sequence $$$a_1, a_2, \dots, a_n$$$ consisting of $$$n$$$ pairwise distinct positive integers.

Find $$$\left\lfloor \frac n 2 \right\rfloor$$$ different pairs of integers $$$x$$$ and $$$y$$$ such that:

- $$$x \neq y$$$;
- $$$x$$$ and $$$y$$$ appear in $$$a$$$;
- $$$x~mod~y$$$ doesn't appear in $$$a$$$.

Note that some $$$x$$$ or $$$y$$$ can belong to multiple pairs.

$$$\lfloor x \rfloor$$$ denotes the floor function — the largest integer less than or equal to $$$x$$$. $$$x~mod~y$$$ denotes the remainder from dividing $$$x$$$ by $$$y$$$.

If there are multiple solutions, print any of them. It can be shown that at least one solution always exists.

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

The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of the sequence.

The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

All numbers in the sequence are pairwise distinct. The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
The answer for each testcase should contain $$$\left\lfloor \frac n 2 \right\rfloor$$$ different pairs of integers $$$x$$$ and $$$y$$$ such that $$$x \neq y$$$, $$$x$$$ and $$$y$$$ appear in $$$a$$$ and $$$x~mod~y$$$ doesn't appear in $$$a$$$. Print the pairs one after another.

You can print the pairs in any order. However, the order of numbers in the pair should be exactly such that the first number is $$$x$$$ and the second number is $$$y$$$. All pairs should be pairwise distinct.

If there are multiple solutions, print any of them.

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

Note:
In the first testcase there are only two pairs: $$$(1, 4)$$$ and $$$(4, 1)$$$. $$$\left\lfloor \frac 2 2 \right\rfloor=1$$$, so we have to find one pair. $$$1~mod~4=1$$$, and $$$1$$$ appears in $$$a$$$, so that pair is invalid. Thus, the only possible answer is a pair $$$(4, 1)$$$.

In the second testcase, we chose pairs $$$8~mod~2=0$$$ and $$$8~mod~4=0$$$. $$$0$$$ doesn't appear in $$$a$$$, so that answer is valid. There are multiple possible answers for that testcase.

In the third testcase, the chosen pairs are $$$9~mod~5=4$$$ and $$$7~mod~5=2$$$. Neither $$$4$$$, nor $$$2$$$, appears in $$$a$$$, so that answer is valid.

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

Example output:
4 1
8 2
8 4
9 5
7 5
8 7
4 3
5 2

Editorial:
There is one important observation: $$$x~mod~y<y$$$.
Thus, you can obtain at least $$$n-1$$$ pair by choosing $$$y$$$ as the minimum number in the sequence and $$$x$$$ as anything else. $$$n-1 \ge \left\lfloor \frac n 2 \right\rfloor$$$ for any positive $$$n$$$.
Overall complexity: $$$O(n)$$$ per testcase.
cAPS lOCK
Contest: Codeforces Beta Round 95 (Div. 2)
Difficulty rating: 1000
Tags: implementation, strings

wHAT DO WE NEED cAPS LOCK FOR?

Caps lock is a computer keyboard key. Pressing it sets an input mode in which typed letters are capital by default. If it is pressed by accident, it leads to accidents like the one we had in the first passage.

Let's consider that a word has been typed with the Caps lock key accidentally switched on, if:

- either it only contains uppercase letters;
- or all letters except for the first one are uppercase.

In this case we should automatically change the case of all letters. For example, the case of the letters that form words "hELLO", "HTTP", "z" should be changed.

Write a program that applies the rule mentioned above. If the rule cannot be applied, the program should leave the word unchanged.

Input format:
The first line of the input data contains a word consisting of uppercase and lowercase Latin letters. The word's length is from 1 to 100 characters, inclusive.

Output format:
Print the result of the given word's processing.

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

Example input:
cAPS

Example output:
Caps

Example input:
Lock

Example output:
Lock

Editorial:
Opposites Attract
Contest: Codeforces Beta Round 95 (Div. 2)
Difficulty rating: 1200
Tags: implementation, math

Everybody knows that opposites attract. That is the key principle of the "Perfect Matching" dating agency. The "Perfect Matching" matchmakers have classified each registered customer by his interests and assigned to the i-th client number ti ( - 10 ≤ ti ≤ 10). Of course, one number can be assigned to any number of customers.

"Perfect Matching" wants to advertise its services and publish the number of opposite couples, that is, the couples who have opposite values of t. Each couple consists of exactly two clients. The customer can be included in a couple an arbitrary number of times. Help the agency and write the program that will find the sought number by the given sequence t1, t2, ..., tn. For example, if t = (1,  - 1, 1,  - 1), then any two elements ti and tj form a couple if i and j have different parity. Consequently, in this case the sought number equals 4.

Of course, a client can't form a couple with him/herself.

Input format:
The first line of the input data contains an integer n (1 ≤ n ≤ 105) which represents the number of registered clients of the "Couple Matching". The second line contains a sequence of integers t1, t2, ..., tn ( - 10 ≤ ti ≤ 10), ti — is the parameter of the i-th customer that has been assigned to the customer by the result of the analysis of his interests.

Output format:
Print the number of couples of customs with opposite t. The opposite number for x is number  - x (0 is opposite to itself). Couples that only differ in the clients' order are considered the same.

Note that the answer to the problem can be large enough, so you must use the 64-bit integer type for calculations. Please, do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specificator.

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

Note:
In the first sample the couples of opposite clients are: (1,2), (1,5) и (3,4).

In the second sample any couple of clients is opposite.

Example input:
5
-3 3 0 0 3

Example output:
3

Example input:
3
0 0 0

Example output:
3

Editorial:
The World is a Theatre
Contest: Codeforces Beta Round 95 (Div. 2)
Difficulty rating: 1400
Tags: combinatorics, math

There are n boys and m girls attending a theatre club. To set a play "The Big Bang Theory", they need to choose a group containing exactly t actors containing no less than 4 boys and no less than one girl. How many ways are there to choose a group? Of course, the variants that only differ in the composition of the troupe are considered different.

Perform all calculations in the 64-bit type: long long for С/С++, int64 for Delphi and long for Java.

Input format:
The only line of the input data contains three integers n, m, t (4 ≤ n ≤ 30, 1 ≤ m ≤ 30, 5 ≤ t ≤ n + m).

Output format:
Find the required number of ways.

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

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

Example input:
5 2 5

Example output:
10

Example input:
4 3 5

Example output:
3

Editorial:
Subway
Contest: Codeforces Beta Round 95 (Div. 2)
Difficulty rating: 1600
Tags: dfs and similar, graphs

A subway scheme, classic for all Berland cities is represented by a set of n stations connected by n passages, each of which connects exactly two stations and does not pass through any others. Besides, in the classic scheme one can get from any station to any other one along the passages. The passages can be used to move in both directions. Between each pair of stations there is no more than one passage.

Berland mathematicians have recently proved a theorem that states that any classic scheme has a ringroad. There can be only one ringroad. In other words, in any classic scheme one can find the only scheme consisting of stations (where any two neighbouring ones are linked by a passage) and this cycle doesn't contain any station more than once.

This invention had a powerful social impact as now the stations could be compared according to their distance from the ringroad. For example, a citizen could say "I live in three passages from the ringroad" and another one could reply "you loser, I live in one passage from the ringroad". The Internet soon got filled with applications that promised to count the distance from the station to the ringroad (send a text message to a short number...).

The Berland government decided to put an end to these disturbances and start to control the situation. You are requested to write a program that can determine the remoteness from the ringroad for each station by the city subway scheme.

Input format:
The first line contains an integer n (3 ≤ n ≤ 3000), n is the number of stations (and trains at the same time) in the subway scheme. Then n lines contain descriptions of the trains, one per line. Each line contains a pair of integers xi, yi (1 ≤ xi, yi ≤ n) and represents the presence of a passage from station xi to station yi. The stations are numbered from 1 to n in an arbitrary order. It is guaranteed that xi ≠ yi and that no pair of stations contain more than one passage. The passages can be used to travel both ways. It is guaranteed that the given description represents a classic subway scheme.

Output format:
Print n numbers. Separate the numbers by spaces, the i-th one should be equal to the distance of the i-th station from the ringroad. For the ringroad stations print number 0.

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

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

Example output:
0 0 0 0

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

Example output:
0 0 0 1 1 2

Editorial:
Yet Another Task with Queens
Contest: Codeforces Beta Round 95 (Div. 2)
Difficulty rating: 1700
Tags: sortings

A queen is the strongest chess piece. In modern chess the queen can move any number of squares in any horizontal, vertical or diagonal direction (considering that there're no other pieces on its way). The queen combines the options given to the rook and the bishop.

There are m queens on a square n × n chessboard. You know each queen's positions, the i-th queen is positioned in the square (ri, ci), where ri is the board row number (numbered from the top to the bottom from 1 to n), and ci is the board's column number (numbered from the left to the right from 1 to n). No two queens share the same position.

For each queen one can count w — the number of other queens that the given queen threatens (attacks). For a fixed attack direction only the first queen in this direction is under attack if there are many queens are on the ray of the attack. Obviously, for any queen w is between 0 and 8, inclusive.

Print the sequence t0, t1, ..., t8, where ti is the number of queens that threaten exactly i other queens, i.e. the number of queens that their w equals i.

Input format:
The first line of the input contains a pair of integers n, m (1 ≤ n, m ≤ 105), where n is the size of the board and m is the number of queens on the board. Then m following lines contain positions of the queens, one per line. Each line contains a pair of integers ri, ci (1 ≤ ri, ci ≤ n) — the queen's position. No two queens stand on the same square.

Output format:
Print the required sequence t0, t1, ..., t8, separating the numbers with spaces.

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

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

Example output:
0 3 0 1 0 0 0 0 0

Example input:
10 3
1 1
1 2
1 3

Example output:
0 2 1 0 0 0 0 0 0

Editorial:
Present to Mom
Contest: Codeforces Beta Round 95 (Div. 2)
Difficulty rating: 2000
Tags: binary search, two pointers

How many stars are there in the sky? A young programmer Polycarpus can't get this question out of his head! He took a photo of the starry sky using his digital camera and now he analyzes the resulting monochrome digital picture. The picture is represented by a rectangular matrix consisting of n lines each containing m characters. A character equals '1', if the corresponding photo pixel is white and '0', if it is black.

Polycarpus thinks that he has found a star on the photo if he finds a white pixel surrounded by four side-neighboring pixels that are also white:

1 111 1  a star on the photo

Polycarpus whats to cut out a rectangular area from the photo and give his mom as a present. This area should contain no less than k stars. The stars can intersect, have shared white pixels on the photo. The boy will cut out the rectangular area so that its borders will be parallel to the sides of the photo and the cuts will go straight between the pixel borders.

Now Polycarpus keeps wondering how many ways there are to cut an area out of the photo so that it met the conditions given above. Help Polycarpus find this number.

Input format:
The first line of the input data contains three integers n, m and k (1 ≤ n, m ≤ 500;1 ≤ k ≤ nm). Then follow n lines, containing the description of the given photo as a sequence of lines. Each line contains m characters '0' or '1'.

Output format:
Print the required number of areas on the given photo.

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

Note:
We'll number the rows and columns below starting from 1, the coordinates (p, q) will denote a cell in row p, column q.

In the first sample Polycarpus should cut out any area containing a rectangle whose opposite corners lie in cells (1, 1) and (3, 4). Only rectangles with opposite corners in (1, 1) and (x, y), where x ≥ 3 and y ≥ 4 fit the conditions.

In the second sample any rectangle whose each side is no less than four, will do. The possible rectangle sizes are 4 × 4, 4 × 5, 5 × 4 and 5 × 5. Such figures can be cut in 4 ways, 2 ways, 2 ways and 1 way correspondingly.

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

Example input:
4 6 2
111000
111100
011011
000111

Example output:
6

Example input:
5 5 4
11111
11111
11111
11111
11111

Example output:
9

Editorial:
Everybody Likes Good Arrays!
Contest: Codeforces Round 845 (Div. 2) and ByteRace 2023
Difficulty rating: 800
Tags: greedy, math

An array $$$a$$$ is good if for all pairs of adjacent elements, $$$a_i$$$ and $$$a_{i+1}$$$ ($$$1\le i \lt n$$$) are of different parity. Note that an array of size $$$1$$$ is trivially good.

You are given an array of size $$$n$$$.

In one operation you can select any pair of adjacent elements in which both elements are of the same parity, delete them, and insert their product in the same position.

Find the minimum number of operations to form a good array.

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 100$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^{9}$$$).

Output format:
For each test case print an integer, the minimum number of operations required to form a good array.

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

Note:
Consider the first test case. Select the $$$2$$$-nd and the $$$3$$$-rd integers and apply the operation on them. The array changes from $$$[1, \color{red}{7}, \color{red}{11}, 2, 13]$$$ to $$$[1, \color{red}{77}, 2, 13]$$$. Next, select the $$$1$$$-st and the $$$2$$$-nd integers, array changes from $$$[\color{red}{1}, \color{red}{77}, 2, 13]$$$ to $$$[\color{red}{77}, 2, 13]$$$. Thus we require $$$2$$$ operations. It can be proved that this is the minimum number of operations.

In the second test case, the given array is already good. So we require $$$0$$$ operations.

Example input:
3
5
1 7 11 2 13
4
1 2 3 4
6
1 1 1 2 2 3

Example output:
2
0
3

Editorial:
Solution Replace even numbers with $$$0$$$ and odd numbers with $$$1$$$ in the array $$$a$$$. Now we observe that the given operation is equivalent to selecting two equal adjacent elements and deleting one of them.
Now the array can be visualized as strips of zeros (in green) and ones (in red) like this $$$[\color{green}{0,0,0},\color{red}{1,1,1,1},\color{green}{0},\color{red}{1,1}]$$$. Note that since the number of adjacent elements ($$$a[i],a[i+1])$$$ such that $$$a[i] \ne a[i+1]$$$ remains constant (nice invariant!), every strip can be handled independently. The size of every strip must be $$$1$$$ in the final array and performing an operation reduces the size of the corresponding strip by $$$1$$$.
So, for a strip of length $$$L$$$, it would require $$$L-1$$$ operations to reduce its size to $$$1$$$. So, every strip would contribute $$$-1$$$ to the number of operations apart from its length. So, the answer is ($$$n - $$$ total no. of strips) which also equals ($$$n - x - 1$$$) where x is number of adjacent elements ($$$a[i],a[i+1]$$$) such that ($$$a[i] \ne a[i+1]$$$).