1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Soap Time! - 2
Contest: Codeforces Round 118 (Div. 1)
Difficulty rating: 3000
Tags: binary search, data structures

Imagine the Cartesian coordinate system. There are k different points containing subway stations. One can get from any subway station to any one instantly. That is, the duration of the transfer between any two subway stations can be considered equal to zero. You are allowed to travel only between subway stations, that is, you are not allowed to leave the subway somewhere in the middle of your path, in-between the stations.

There are n dwarves, they are represented by their coordinates on the plane. The dwarves want to come together and watch a soap opera at some integer point on the plane. For that, they choose the gathering point and start moving towards it simultaneously. In one second a dwarf can move from point (x, y) to one of the following points: (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1). Besides, the dwarves can use the subway as many times as they want (the subway transfers the dwarves instantly). The dwarves do not interfere with each other as they move (that is, the dwarves move simultaneously and independently from each other).

Help the dwarves and find the minimum time they need to gather at one point.

Input format:
The first line contains two integers n and k (1 ≤ n ≤ 105; 0 ≤ k ≤ 105) — the number of dwarves and the number of subway stations, correspondingly.

The next n lines contain the coordinates of the dwarves. The i-th line contains two space-separated integers xi and yi (|xi|, |yi| ≤ 108) — the coordinates of the i-th dwarf. It is guaranteed that all dwarves are located at different points.

The next k lines contain the coordinates of the subway stations. The t-th line contains two space-separated integers xt and yt (|xt|, |yt| ≤ 108) — the coordinates of the t-th subway station. It is guaranteed that all subway stations are located at different points.

Output format:
Print a single number — the minimum time, in which all dwarves can gather together at one point to watch the soap.

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

Example input:
1 0
2 -2

Example output:
0

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

Example output:
6

Editorial:
Shifts
Contest: Codeforces Round 142 (Div. 1)
Difficulty rating: 1500
Tags: brute force, two pointers

You are given a table consisting of n rows and m columns. Each cell of the table contains a number, 0 or 1. In one move we can choose some row of the table and cyclically shift its values either one cell to the left, or one cell to the right.

To cyclically shift a table row one cell to the right means to move the value of each cell, except for the last one, to the right neighboring cell, and to move the value of the last cell to the first cell. A cyclical shift of a row to the left is performed similarly, but in the other direction. For example, if we cyclically shift a row "00110" one cell to the right, we get a row "00011", but if we shift a row "00110" one cell to the left, we get a row "01100".

Determine the minimum number of moves needed to make some table column consist only of numbers 1.

Input format:
The first line contains two space-separated integers: n (1 ≤ n ≤ 100) — the number of rows in the table and m (1 ≤ m ≤ 104) — the number of columns in the table. Then n lines follow, each of them contains m characters "0" or "1": the j-th character of the i-th line describes the contents of the cell in the i-th row and in the j-th column of the table.

It is guaranteed that the description of the table contains no other characters besides "0" and "1".

Output format:
Print a single number: the minimum number of moves needed to get only numbers 1 in some column of the table. If this is impossible, print -1.

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

Note:
In the first sample one way to achieve the goal with the least number of moves is as follows: cyclically shift the second row to the right once, then shift the third row to the left twice. Then the table column before the last one will contain only 1s.

In the second sample one can't shift the rows to get a column containing only 1s.

Example input:
3 6
101010
000100
100000

Example output:
3

Example input:
2 3
111
000

Example output:
-1

Editorial:
Triangles
Contest: Codeforces Round 142 (Div. 1)
Difficulty rating: 1900
Tags: combinatorics, graphs, math

Alice and Bob don't play games anymore. Now they study properties of all sorts of graphs together. Alice invented the following task: she takes a complete undirected graph with n vertices, chooses some m edges and keeps them. Bob gets the $${ \frac { n ( n - 1 ) } { 2 } } - m$$ remaining edges.

Alice and Bob are fond of "triangles" in graphs, that is, cycles of length 3. That's why they wonder: what total number of triangles is there in the two graphs formed by Alice and Bob's edges, correspondingly?

Input format:
The first line contains two space-separated integers n and m (1 ≤ n ≤ 106, 0 ≤ m ≤ 106) — the number of vertices in the initial complete graph and the number of edges in Alice's graph, correspondingly. Then m lines follow: the i-th line contains two space-separated integers ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi), — the numbers of the two vertices connected by the i-th edge in Alice's graph. It is guaranteed that Alice's graph contains no multiple edges and self-loops. It is guaranteed that the initial complete graph also contains no multiple edges and self-loops.

Consider the graph vertices to be indexed in some way from 1 to n.

Output format:
Print a single number — the total number of cycles of length 3 in Alice and Bob's graphs together.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is advised 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 Alice has 2 triangles: (1, 2, 3) and (2, 3, 4). Bob's graph has only 1 triangle : (1, 4, 5). That's why the two graphs in total contain 3 triangles.

In the second sample Alice's graph has only one triangle: (1, 2, 3). Bob's graph has three triangles: (1, 4, 5), (2, 4, 5) and (3, 4, 5). In this case the answer to the problem is 4.

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

Example output:
3

Example input:
5 3
1 2
2 3
1 3

Example output:
4

Editorial:
Towers
Contest: Codeforces Round 142 (Div. 1)
Difficulty rating: 2100
Tags: dp, greedy, two pointers

The city of D consists of n towers, built consecutively on a straight line. The height of the tower that goes i-th (from left to right) in the sequence equals hi. The city mayor decided to rebuild the city to make it beautiful. In a beautiful city all towers are are arranged in non-descending order of their height from left to right.

The rebuilding consists of performing several (perhaps zero) operations. An operation constitutes using a crane to take any tower and put it altogether on the top of some other neighboring tower. In other words, we can take the tower that stands i-th and put it on the top of either the (i - 1)-th tower (if it exists), or the (i + 1)-th tower (of it exists). The height of the resulting tower equals the sum of heights of the two towers that were put together. After that the two towers can't be split by any means, but more similar operations can be performed on the resulting tower. Note that after each operation the total number of towers on the straight line decreases by 1.

Help the mayor determine the minimum number of operations required to make the city beautiful.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 5000) — the number of towers in the city. The next line contains n space-separated integers: the i-th number hi (1 ≤ hi ≤ 105) determines the height of the tower that is i-th (from left to right) in the initial tower sequence.

Output format:
Print a single integer — the minimum number of operations needed to make the city beautiful.

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

Example input:
5
8 2 7 3 1

Example output:
3

Example input:
3
5 2 1

Example output:
2

Editorial:
Gifts
Contest: Codeforces Round 142 (Div. 1)
Difficulty rating: 2600
Tags: combinatorics, dp, math, probabilities

Once upon a time an old man and his wife lived by the great blue sea. One day the old man went fishing and caught a real live gold fish. The fish said: "Oh ye, old fisherman! Pray set me free to the ocean and I will grant you with n gifts, any gifts you wish!". Then the fish gave the old man a list of gifts and their prices. Some gifts on the list can have the same names but distinct prices. However, there can't be two gifts with the same names and the same prices. Also, there can be gifts with distinct names and the same prices. The old man can ask for n names of items from the list. If the fish's list has p occurrences of the given name, then the old man can't ask for this name of item more than p times.

The old man knows that if he asks for s gifts of the same name, the fish will randomly (i.e. uniformly amongst all possible choices) choose s gifts of distinct prices with such name from the list. The old man wants to please his greedy wife, so he will choose the n names in such a way that he can get n gifts with the maximum price. Besides, he isn't the brightest of fishermen, so if there are several such ways, he chooses one of them uniformly.

The old man wondered, what is the probability that he can get n most expensive gifts. As the old man isn't good at probability theory, he asks you to help him.

Input format:
The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 1000) — the number of the old man's wishes and the number of distinct names in the goldfish's list, correspondingly. Then m lines follow: the i-th line first contains integer ki (ki > 0) — the number of distinct prices of gifts with the i-th name, then ki distinct space-separated integers cij (1 ≤ cij ≤ 109), the gifts' prices.

It is guaranteed that the sum of all ki doesn't exceed 1000. It is guaranteed that n is not greater than the total number of the gifts.

Output format:
On a single line print one real number — the probability of getting n most valuable gifts. The answer will be considered correct if its absolute or relative error does not exceed 10 - 9.

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

Example input:
3 1
3 10 20 30

Example output:
1.000000000

Example input:
3 2
1 40
4 10 20 30 40

Example output:
0.166666667

Editorial:
Little Nikita
Contest: Codeforces Round 948 (Div. 2)
Difficulty rating: 800
Tags: math

The little boy Nikita was given some cubes as a present. He decided to build a tower out of them.

Initially, the tower doesn't have any cubes. In one move, Nikita either puts exactly $$$1$$$ cube on top of the tower or removes exactly $$$1$$$ cube from the top of the tower. Is it possible that after $$$n$$$ moves, the resulting tower has exactly $$$m$$$ cubes?

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

The only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 100$$$).

Output format:
For each test case, output "Yes" (without quotes) if Nikita can obtain a tower with $$$m$$$ cubes, and "No" (without quotes) otherwise.

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

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

Note:
In the first test case, Nikita can put $$$1$$$ cube on top of the tower $$$3$$$ times in a row, so the answer is "Yes".

In the second test case, Nikita can only end up with either a tower with no blocks or a tower with $$$2$$$ blocks, so the answer is "No".

Example input:
3
3 3
2 4
5 3

Example output:
Yes
No
Yes

Editorial:
Заметим, что одно действие с кубиком меняет четность количества кубиков в башне. Тогда если четности $$$n$$$ и $$$m$$$ не совпадают, то нельзя построить башню. Также если $$$n < m$$$ то башню тоже нельзя построить. В остальных случаях можно построить башню высоты $$$m$$$ за $$$m$$$ операций, а потом добавлять и удалять кубик, пока операции не закончатся.
Binary Colouring
Contest: Codeforces Round 948 (Div. 2)
Difficulty rating: 1100
Tags: bitmasks, constructive algorithms, greedy, math

You are given a positive integer $$$x$$$. Find any array of integers $$$a_0, a_1, \ldots, a_{n-1}$$$ for which the following holds:

- $$$1 \le n \le 32$$$,
- $$$a_i$$$ is $$$1$$$, $$$0$$$, or $$$-1$$$ for all $$$0 \le i \le n - 1$$$,
- $$$x = \displaystyle{\sum_{i=0}^{n - 1}{a_i \cdot 2^i}}$$$,
- There does not exist an index $$$0 \le i \le n - 2$$$ such that both $$$a_{i} \neq 0$$$ and $$$a_{i + 1} \neq 0$$$.

It can be proven that under the constraints of the problem, a valid array always exists.

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

The only line of each test case contains a single positive integer $$$x$$$ ($$$1 \le x < 2^{30}$$$).

Output format:
For each test case, output two lines.

On the first line, output an integer $$$n$$$ ($$$1 \le n \le 32$$$) — the length of the array $$$a_0, a_1, \ldots, a_{n-1}$$$.

On the second line, output the array $$$a_0, a_1, \ldots, a_{n-1}$$$.

If there are multiple valid arrays, you can output any of them.

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

Note:
In the first test case, one valid array is $$$[1]$$$, since $$$(1) \cdot 2^0 = 1$$$.

In the second test case, one possible valid array is $$$[0,-1,0,0,1]$$$, since $$$(0) \cdot 2^0 + (-1) \cdot 2^1 + (0) \cdot 2^2 + (0) \cdot 2^3 + (1) \cdot 2^4 = -2 + 16 = 14$$$.

Example input:
7
1
14
24
15
27
11
19

Example output:
1
1
5
0 -1 0 0 1
6
0 0 0 -1 0 1
5
-1 0 0 0 1
6
-1 0 -1 0 0 1
5
-1 0 -1 0 1
5
-1 0 1 0 1

Editorial:
Будем перебирать префикс из $$$i$$$ бит и строить корректный ответ для числа образованного префиксом бит числа $$$x$$$. Нам интересно рассматривать только единичные биты, так как только они влияют на значение числа $$$x$$$.
Если в ответе мы уже поставили на место $$$i$$$ единицу, то нам нужно еще как-то получить к числу + $$$2^i$$$. Тогда просто обнулим $$$i$$$ бит в ответе и поставим его в $$$i + 1$$$  — как раз прибавится $$$2 \cdot 2^i = 2^{i+1}$$$.
Теперь на $$$i$$$ месте в ответе стоит 0. Рассмотрим что мы ставили в ответе на $$$i-1$$$ месте. Если 0, то все хорошо, просто поставим 1 на позицию $$$i$$$. Если стоит 1, то возникла ситуация [$$$1$$$ $$$1$$$], исправим ее, сделав [$$$-1$$$ $$$0$$$ $$$1$$$]  — на место $$$i-1$$$ поставим -1, на $$$i$$$ оставим 0, на $$$i+1$$$ поставим 1. К сумме прибавится $$$2^i$$$ так как $$$2^i + 2^{i-1}= 2^{i+1} - 2^{i-1}$$$ Теперь осталось разобрать случай когда на $$$i-1$$$ месте стоит -1. Но он невозможен, так как нашими операциями вперед мы ставим только единицы, а -1 ставятся позади.
Итоговая асимптотика O(log $$$x$$$) на 1 тестовый случай.
Nikita and LCM
Contest: Codeforces Round 948 (Div. 2)
Difficulty rating: 1900
Tags: brute force, data structures, dp, greedy, math, number theory, sortings

Nikita is a student passionate about number theory and algorithms. He faces an interesting problem related to an array of numbers.

Suppose Nikita has an array of integers $$$a$$$ of length $$$n$$$. He will call a subsequence$$$^\dagger$$$ of the array special if its least common multiple (LCM) is not contained in $$$a$$$. The LCM of an empty subsequence is equal to $$$0$$$.

Nikita wonders: what is the length of the longest special subsequence of $$$a$$$? Help him answer this question!

$$$^\dagger$$$ A sequence $$$b$$$ is a subsequence of $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by the deletion of several (possibly, zero or all) elements, without changing the order of the remaining elements. For example, $$$[5,2,3]$$$ is a subsequence of $$$[1,5,7,8,2,4,3]$$$.

Input format:
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 2000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

Output format:
For each test case, output a single integer — the length of the longest special subsequence of $$$a$$$.

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

Note:
In the first test case, the LCM of any non-empty subsequence is contained in $$$a$$$, so the answer is $$$0$$$.

In the second test case, we can take the subsequence $$$[3, 2, 10, 1]$$$, its LCM is equal to $$$30$$$, which is not contained in $$$a$$$.

In the third test case, we can take the subsequence $$$[2, 3, 6, 100\,003]$$$, its LCM is equal to $$$600\,018$$$, which is not contained in $$$a$$$.

Example input:
6
5
1 2 4 8 16
6
3 2 10 20 60 1
7
2 3 4 6 12 100003 1200036
9
2 42 7 3 6 7 7 1 6
8
4 99 57 179 10203 2 11 40812
1
1

Example output:
0
4
4
5
8
0

Editorial:
Сначала поймем, можно ли взять в качестве особенной подпоследовательности весь массив $$$a$$$. Для этого найдем LCM($$$a_1, a_2, \dots, a_n$$$). Если он больше, чем max($$$a_1, a_2, \dots, a_n$$$), то очевидно такого числа нет в подпоследовательности, так как $$$LCM \geq max$$$. После этой проверки про массив $$$a$$$ становится известно, что каждый $$$a_i \ | \ max(a_1, a_2, \dots, a_n)$$$. Тогда переберем делители максимума и жадно проверим наличие подпоследовательности с таким LCM.
Если делать это наивно, то будет $$$O(\sqrt{C} + n \cdot d(C) \cdot log(C))$$$.
Заметим, что можно подсчитать вхождение каждого числа и проверять только различные числа. Тогда асимптотика будет $$$O(\sqrt{C} + d(C)^2 \cdot log(C))$$$.
XORificator
Contest: Codeforces Round 948 (Div. 2)
Difficulty rating: 2300
Tags: bitmasks, brute force, greedy, hashing

You are given a binary (consisting only of 0s and 1s) $$$n \times m$$$ matrix. You are also given a XORificator, using which you can invert all the values in a chosen row (i.e. replace 0 with 1 and 1 with 0).

A column in the matrix is considered special if it contains exactly one 1. Your task is to find the maximum number of columns that can be made special at the same time, and the set of rows the XORificator should be used on to achieve that.

Input format:
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 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 $$$m$$$ ($$$1 \leq n, m \leq 3 \cdot 10^5$$$, $$$n \cdot m \leq 3 \cdot 10^5$$$).

Each of the following $$$n$$$ lines of the test case contains a binary string of length $$$m$$$.

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

Output format:
For each test case, output two lines.

In the first line, output the maximum number of special columns that is possible to get simultaneously.

In the second line, output a binary string of length $$$n$$$, where the $$$i$$$-th character is 0, if you don't use the XORificator on the $$$i$$$-th row, and 1, if you use the XORificator on the $$$i$$$-th row.

If there are multiple valid XORificator configurations that achieve the optimal answer, you can output any of them.

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

Note:
In the first test case, you can use the XORificator on the second row to make the columns $$$2$$$, $$$3$$$, and $$$4$$$ special.

In the second test case, the only column is already special, so you don't need to use the XORificator.

Example input:
5
3 4
1010
0110
0100
1 1
1
1 1
0
2 5
00101
10110
3 3
101
111
000

Example output:
3
010
1
0
1
1
3
00
2
010

Editorial:
Let's assume that the value in the $$$i$$$-th row and $$$j$$$-th column is strictly one and it is the only one in the column. Then the entire table is uniquely determined, as well as the $$$XOR$$$ificator. For each possible state of the XORificator that constructs the required table, let's maintain a counter. Then the state that maximizes the number of columns with exactly one 1 has the maximum counter. To efficiently maintain the counter, it is necessary to maintain the hash of the XORificator and quickly recalculate it when moving to the next row. The answer can be easily reconstructed by traversing the table again and counting the hash. If the desired hash is obtained, simply output the state of the XORificator. The final time complexity is $$$O(nm \log{(nm)})$$$ or $$$O(nm)$$$ if a hash map is used.
New Year and Days
Contest: Good Bye 2015
Difficulty rating: 900
Tags: implementation

Today is Wednesday, the third day of the week. What's more interesting is that tomorrow is the last day of the year 2015.

Limak is a little polar bear. He enjoyed this year a lot. Now, he is so eager to the coming year 2016.

Limak wants to prove how responsible a bear he is. He is going to regularly save candies for the entire year 2016! He considers various saving plans. He can save one candy either on some fixed day of the week or on some fixed day of the month.

Limak chose one particular plan. He isn't sure how many candies he will save in the 2016 with his plan. Please, calculate it and tell him.

Input format:
The only line of the input is in one of the following two formats:

- "x of week" where x (1 ≤ x ≤ 7) denotes the day of the week. The 1-st day is Monday and the 7-th one is Sunday.
- "x of month" where x (1 ≤ x ≤ 31) denotes the day of the month.

Output format:
Print one integer — the number of candies Limak will save in the year 2016.

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

Note:
Polar bears use the Gregorian calendar. It is the most common calendar and you likely use it too. You can read about it on Wikipedia if you want to – https://en.wikipedia.org/wiki/Gregorian_calendar. The week starts with Monday.

In the first sample Limak wants to save one candy on each Thursday (the 4-th day of the week). There are 52 Thursdays in the 2016. Thus, he will save 52 candies in total.

In the second sample Limak wants to save one candy on the 30-th day of each month. There is the 30-th day in exactly 11 months in the 2016 — all months but February. It means that Limak will save 11 candies in total.

Example input:
4 of week

Example output:
52

Example input:
30 of month

Example output:
11

Editorial:
New Year and Old Property
Contest: Good Bye 2015
Difficulty rating: 1300
Tags: bitmasks, brute force, implementation

The year 2015 is almost over.

Limak is a little polar bear. He has recently learnt about the binary system. He noticed that the passing year has exactly one zero in its representation in the binary system — 201510 = 111110111112. Note that he doesn't care about the number of zeros in the decimal representation.

Limak chose some interval of years. He is going to count all years from this interval that have exactly one zero in the binary representation. Can you do it faster?

Assume that all positive integers are always written without leading zeros.

Input format:
The only line of the input contains two integers a and b (1 ≤ a ≤ b ≤ 1018) — the first year and the last year in Limak's interval respectively.

Output format:
Print one integer – the number of years Limak will count in his chosen interval.

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

Note:
In the first sample Limak's interval contains numbers 510 = 1012, 610 = 1102, 710 = 1112, 810 = 10002, 910 = 10012 and 1010 = 10102. Two of them (1012 and 1102) have the described property.

Example input:
5 10

Example output:
2

Example input:
2015 2015

Example output:
1

Editorial: