1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Two Heaps
Contest: Codeforces Round 205 (Div. 2)
Difficulty rating: 1900
Tags: combinatorics, constructive algorithms, greedy, implementation, math, sortings

Valera has 2·n cubes, each cube contains an integer from 10 to 99. He arbitrarily chooses n cubes and puts them in the first heap. The remaining cubes form the second heap.

Valera decided to play with cubes. During the game he takes a cube from the first heap and writes down the number it has. Then he takes a cube from the second heap and write out its two digits near two digits he had written (to the right of them). In the end he obtained a single fourdigit integer — the first two digits of it is written on the cube from the first heap, and the second two digits of it is written on the second cube from the second heap.

Valera knows arithmetic very well. So, he can easily count the number of distinct fourdigit numbers he can get in the game. The other question is: how to split cubes into two heaps so that this number (the number of distinct fourdigit integers Valera can get) will be as large as possible?

Input format:
The first line contains integer n (1 ≤ n ≤ 100). The second line contains 2·n space-separated integers ai (10 ≤ ai ≤ 99), denoting the numbers on the cubes.

Output format:
In the first line print a single number — the maximum possible number of distinct four-digit numbers Valera can obtain. In the second line print 2·n numbers bi (1 ≤ bi ≤ 2). The numbers mean: the i-th cube belongs to the bi-th heap in your division.

If there are multiple optimal ways to split the cubes into the heaps, print any of them.

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

Note:
In the first test case Valera can put the first cube in the first heap, and second cube — in second heap. In this case he obtain number 1099. If he put the second cube in the first heap, and the first cube in the second heap, then he can obtain number 9910. In both cases the maximum number of distinct integers is equal to one.

In the second test case Valera can obtain numbers 1313, 1345, 2413, 2445. Note, that if he put the first and the third cubes in the first heap, he can obtain only two numbers 1324 and 1345.

Example input:
1
10 99

Example output:
1
2 1

Example input:
2
13 24 13 45

Example output:
4
1 2 2 1

Editorial:
Find Maximum
Contest: Codeforces Round 205 (Div. 2)
Difficulty rating: 1600
Tags: implementation, math, number theory

Valera has array a, consisting of n integers a0, a1, ..., an - 1, and function f(x), taking an integer from 0 to 2n - 1 as its single argument. Value f(x) is calculated by formula $$f(x) = \sum_{i=0}^{n-1} a_i \cdot bit(i)$$, where value bit(i) equals one if the binary representation of number x contains a 1 on the i-th position, and zero otherwise.

For example, if n = 4 and x = 11 (11 = 20 + 21 + 23), then f(x) = a0 + a1 + a3.

Help Valera find the maximum of function f(x) among all x, for which an inequality holds: 0 ≤ x ≤ m.

Input format:
The first line contains integer n (1 ≤ n ≤ 105) — the number of array elements. The next line contains n space-separated integers a0, a1, ..., an - 1 (0 ≤ ai ≤ 104) — elements of array a.

The third line contains a sequence of digits zero and one without spaces s0s1... sn - 1 — the binary representation of number m. Number m equals $$\sum_{i=0}^{n-1} 2^i \cdot s_i$$.

Output format:
Print a single integer — the maximum value of function f(x) for all $$x \in [0..m]$$.

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

Note:
In the first test case m = 20 = 1, f(0) = 0, f(1) = a0 = 3.

In the second sample m = 20 + 21 + 23 = 11, the maximum value of function equals f(5) = a0 + a2 = 17 + 10 = 27.

Example input:
2
3 8
10

Example output:
3

Example input:
5
17 0 10 2 1
11010

Example output:
27

Editorial:
Queue
Contest: Codeforces Round 205 (Div. 2)
Difficulty rating: 2000
Tags: constructive algorithms, dp

There are n schoolchildren, boys and girls, lined up in the school canteen in front of the bun stall. The buns aren't ready yet and the line is undergoing some changes.

Each second all boys that stand right in front of girls, simultaneously swap places with the girls (so that the girls could go closer to the beginning of the line). In other words, if at some time the i-th position has a boy and the (i + 1)-th position has a girl, then in a second, the i-th position will have a girl and the (i + 1)-th one will have a boy.

Let's take an example of a line of four people: a boy, a boy, a girl, a girl (from the beginning to the end of the line). Next second the line will look like that: a boy, a girl, a boy, a girl. Next second it will be a girl, a boy, a girl, a boy. Next second it will be a girl, a girl, a boy, a boy. The line won't change any more.

Your task is: given the arrangement of the children in the line to determine the time needed to move all girls in front of boys (in the example above it takes 3 seconds). Baking buns takes a lot of time, so no one leaves the line until the line stops changing.

Input format:
The first line contains a sequence of letters without spaces s1s2... sn (1 ≤ n ≤ 106), consisting of capital English letters M and F. If letter si equals M, that means that initially, the line had a boy on the i-th position. If letter si equals F, then initially the line had a girl on the i-th position.

Output format:
Print a single integer — the number of seconds needed to move all the girls in the line in front of the boys. If the line has only boys or only girls, print 0.

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

Note:
In the first test case the sequence of changes looks as follows: MFM  →  FMM.

The second test sample corresponds to the sample from the statement. The sequence of changes is: MMFF  →  MFMF  →  FMFM  →  FFMM.

Example input:
MFM

Example output:
1

Example input:
MMFF

Example output:
3

Editorial:
Antichain
Contest: Codeforces Round 205 (Div. 2)
Difficulty rating: 2200
Tags: dp, graph matchings, greedy

You have a directed acyclic graph G, consisting of n vertexes, numbered from 0 to n - 1. The graph contains n edges numbered from 0 to n - 1. An edge with number i connects vertexes i and (i + 1) mod n, and it can be directed in either direction (from i to (i + 1) mod n, or vise versa).

Operation x mod y means taking the remainder after dividing number x by number y.

Let's call two vertexes u and v in graph G comparable if the graph contains a path either from u to v or from v to u. We'll assume that an antichain is a set of vertexes of graph G, where any two distinct vertexes are not comparable. The size of an antichain is the number of vertexes in the corresponding set. An antichain is maximum if the graph doesn't have antichains of a larger size.

Your task is to find the size of the maximum antichain in graph G.

Input format:
The first line contains the sequence of characters s0s1... sn - 1 (2 ≤ n ≤ 106), consisting of numbers zero and one. The length of the line (number n) corresponds to the number of vertexes and edges in graph G. If character si (i ≥ 0) equals 0, then the edge between vertexes i and (i + 1) mod n is directed from the i-th vertex to the (i + 1) mod n-th one, otherwise — to the opposite point.

It is guaranteed that the given graph is acyclic.

Output format:
Print a single integer — the size of the maximum antichain of graph G.

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

Note:
Consider the first test sample. The graph's G edges are: 0 → 1, 1 → 2, 0 → 2. We can choose the set of vertexes [0] as the maximum antichain. We cannot choose an antichain of larger size.

Example input:
001

Example output:
1

Example input:
110010

Example output:
3

Editorial:
Strange Partition
Contest: Codeforces Round 694 (Div. 2)
Difficulty rating: 900
Tags: greedy, math, number theory

You are given an array $$$a$$$ of length $$$n$$$, and an integer $$$x$$$. You can perform the following operation as many times as you would like (possibly zero): replace two adjacent elements of the array by their sum. For example, if the initial array was $$$[3, 6, 9]$$$, in a single operation one can replace the last two elements by their sum, yielding an array $$$[3, 15]$$$, or replace the first two elements to get an array $$$[9, 9]$$$. Note that the size of the array decreases after each operation.

The beauty of an array $$$b=[b_1, \ldots, b_k]$$$ is defined as $$$\sum_{i=1}^k \left\lceil \frac{b_i}{x} \right\rceil$$$, which means that we divide each element by $$$x$$$, round it up to the nearest integer, and sum up the resulting values. For example, if $$$x = 3$$$, and the array is $$$[4, 11, 6]$$$, the beauty of the array is equal to $$$\left\lceil \frac{4}{3} \right\rceil + \left\lceil \frac{11}{3} \right\rceil + \left\lceil \frac{6}{3} \right\rceil = 2 + 4 + 2 = 8$$$.

Please determine the minimum and the maximum beauty you can get by performing some operations on the original array.

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

The first line of each test case contains two integers $$$n$$$ and $$$x$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq x \leq 10^9$$$).

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), the elements of the array $$$a$$$.

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

Output format:
For each test case output two integers — the minimal and the maximal possible beauty.

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

Note:
In the first test case the beauty of the array does not change if we perform any operations.

In the second example we can leave the array unchanged to attain the maximum beauty, and to get the minimum beauty one can replace two elements $$$4$$$ and $$$11$$$ with their sum, yielding an array $$$[6, 15]$$$, which has its beauty equal to $$$7$$$.

Example input:
2
3 3
3 6 9
3 3
6 4 11

Example output:
6 6
7 8

Editorial:
Note that, $$$\left\lceil \frac{a + b}{x} \right\rceil \leq \left\lceil \frac{a}{x} \right\rceil + \left\lceil \frac{b}{x} \right\rceil$$$. It means that the maximal sum is attained if we do not apply any operations, and the minimal one is attained if we replace all the element with a single one, equal to the sum of all elements.
Minimizing the Sum
Contest: Educational Codeforces Round 165 (Rated for Div. 2)
Difficulty rating: 1700
Tags: dp, implementation

You are given an integer array $$$a$$$ of length $$$n$$$.

You can perform the following operation: choose an element of the array and replace it with any of its neighbor's value.

For example, if $$$a=[3, 1, 2]$$$, you can get one of the arrays $$$[3, 3, 2]$$$, $$$[3, 2, 2]$$$ and $$$[1, 1, 2]$$$ using one operation, but not $$$[2, 1, 2$$$] or $$$[3, 4, 2]$$$.

Your task is to calculate the minimum possible total sum of the array if you can perform the aforementioned operation at most $$$k$$$ times.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$0 \le k \le 10$$$).

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

Additional constraint on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, print a single integer — the minimum possible total sum of the array if you can perform the aforementioned operation at most $$$k$$$ times.

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

Note:
In the first example, one of the possible sequences of operations is the following: $$$[3, 1, 2] \rightarrow [1, 1, 2$$$].

In the second example, you do not need to apply the operation.

In the third example, one of the possible sequences of operations is the following: $$$[2, 2, 1, 3] \rightarrow [2, 1, 1, 3] \rightarrow [2, 1, 1, 1]$$$.

In the fourth example, one of the possible sequences of operations is the following: $$$[4, 1, 2, 2, 4, 3] \rightarrow [1, 1, 2, 2, 4, 3] \rightarrow [1, 1, 1, 2, 4, 3] \rightarrow [1, 1, 1, 2, 2, 3]$$$.

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

Example output:
4
5
5
10

Editorial:
The small values of $$$k$$$ leads to the idea that expected solution is dynamic programming. In fact, we can actually design a dynamic programming solution.
Let $$$dp_{i, j}$$$ be the minimum sum, if we considered the first $$$i$$$ elements and already done $$$j$$$ operations. Note that, we can turn a segment of length $$$d+1$$$ into a minimum on it using $$$d$$$ operations. So the transitions can be done by iterating over the length of the next segment (denote it as $$$d$$$) and we can update $$$dp_{i + d + 1, j + d}$$$ with $$$dp_{i, j} + (d + 1) \cdot x$$$, where $$$x$$$ is the minimum among $$$a_i, a_{i + 1}, \dots, a_{i + d - 1}$$$ (that can be maintained in a single variable during iteration over $$$d$$$).
There are $$$O(nk)$$$ states in the dynamic programming and $$$O(k)$$$ transitions from each of them, so the solution works in $$$O(nk^2)$$$.
Phoenix and Gold
Contest: Codeforces Global Round 14
Difficulty rating: 800
Tags: constructive algorithms, greedy, math

Phoenix has collected $$$n$$$ pieces of gold, and he wants to weigh them together so he can feel rich. The $$$i$$$-th piece of gold has weight $$$w_i$$$. All weights are distinct. He will put his $$$n$$$ pieces of gold on a weight scale, one piece at a time.

The scale has an unusual defect: if the total weight on it is exactly $$$x$$$, it will explode. Can he put all $$$n$$$ gold pieces onto the scale in some order, without the scale exploding during the process? If so, help him find some possible order.

Formally, rearrange the array $$$w$$$ so that for each $$$i$$$ $$$(1 \le i \le n)$$$, $$$\sum\limits_{j = 1}^{i}w_j \ne x$$$.

Input format:
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 100$$$; $$$1 \le x \le 10^4$$$) — the number of gold pieces that Phoenix has and the weight to avoid, respectively.

The second line of each test case contains $$$n$$$ space-separated integers $$$(1 \le w_i \le 100)$$$ — the weights of the gold pieces. It is guaranteed that the weights are pairwise distinct.

Output format:
For each test case, if Phoenix cannot place all $$$n$$$ pieces without the scale exploding, print NO. Otherwise, print YES followed by the rearranged array $$$w$$$. If there are multiple solutions, print any.

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

Note:
In the first test case, Phoenix puts the gold piece with weight $$$3$$$ on the scale first, then the piece with weight $$$2$$$, and finally the piece with weight $$$1$$$. The total weight on the scale is $$$3$$$, then $$$5$$$, then $$$6$$$. The scale does not explode because the total weight on the scale is never $$$2$$$.

In the second test case, the total weight on the scale is $$$8$$$, $$$9$$$, $$$11$$$, $$$14$$$, then $$$18$$$. It is never $$$3$$$.

In the third test case, Phoenix must put the gold piece with weight $$$5$$$ on the scale, and the scale will always explode.

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

Example output:
YES
3 2 1
YES
8 1 2 3 4
NO

Editorial:
Note that if the sum of all the weights is $$$x$$$, the scale will always explode and the answer will be NO. Otherwise, we claim there is always an answer.
Basically, at each point, we choose an arbitrary gold piece to add to the scale so that it doesn't explode. There is always a valid gold piece to add because the weights are distinct.
For example, we can try adding piece $$$1$$$, $$$2$$$, $$$\dots$$$, $$$n$$$, in that order. Suppose we are currently considering the $$$i$$$-th piece. If we can add it to the scale without an explosion, we do it. If we can't, then we can just first add piece $$$i+1$$$, and then piece $$$i$$$ ($$$w_i \neq w_{i+1}$$$ because weights are distinct). $$$i+1$$$ must be less than or equal to $$$n$$$ because otherwise, the total sum of the weights would be $$$x$$$.
Time complexity for each test case: $$$O(n)$$$
Phoenix and Puzzle
Contest: Codeforces Global Round 14
Difficulty rating: 1000
Tags: brute force, geometry, math, number theory

Phoenix is playing with a new puzzle, which consists of $$$n$$$ identical puzzle pieces. Each puzzle piece is a right isosceles triangle as shown below.

A puzzle piece

The goal of the puzzle is to create a square using the $$$n$$$ pieces. He is allowed to rotate and move the pieces around, but none of them can overlap and all $$$n$$$ pieces must be used (of course, the square shouldn't contain any holes as well). Can he do it?

Input format:
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^9$$$) — the number of puzzle pieces.

Output format:
For each test case, if Phoenix can create a square with the $$$n$$$ puzzle pieces, print YES. Otherwise, print NO.

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

Note:
For $$$n=2$$$, Phoenix can create a square like this:

For $$$n=4$$$, Phoenix can create a square like this:

For $$$n=6$$$, it is impossible for Phoenix to create a square.

Example input:
3
2
4
6

Example output:
YES
YES
NO

Editorial:
If $$$n$$$ can be written as $$$2x$$$ or $$$4x$$$, where $$$x$$$ is a square number, then the answer is YES. Otherwise it is NO.
To visualize this construction, we start by first building a smaller square using exactly $$$2$$$ or $$$4$$$ pieces (the drawings are in the sample test explanation). We can just use $$$x$$$ of those smaller squares to build a larger square.
Let's prove that there are no other answers (although this isn't necessary to solve the problem). Let's define each triangle piece to have a short side of length $$$1$$$ and a longer side of length $$$\sqrt{2}$$$. Consider one side of the square, and suppose that it has $$$a$$$ triangles on the short side and $$$b$$$ triangles on the longer side. The side length will be $$$a+\sqrt{2}b$$$. The area of the square is a rational number because the area of each triangle piece is rational. So, $$$(a+\sqrt{2}b)^2$$$ has to be rational, which means either $$$a$$$ is $$$0$$$, or $$$b$$$ is $$$0$$$. If either is $$$0$$$, we can use the construction in the previous paragraph.
Time complexity for each test case: $$$O(\sqrt{n})$$$ or $$$O(\log{n})$$$ (depends on how you check for square numbers)
Phoenix and Towers
Contest: Codeforces Global Round 14
Difficulty rating: 1400
Tags: constructive algorithms, data structures, greedy

Phoenix has $$$n$$$ blocks of height $$$h_1, h_2, \dots, h_n$$$, and all $$$h_i$$$ don't exceed some value $$$x$$$. He plans to stack all $$$n$$$ blocks into $$$m$$$ separate towers. The height of a tower is simply the sum of the heights of its blocks. For the towers to look beautiful, no two towers may have a height difference of strictly more than $$$x$$$.

Please help Phoenix build $$$m$$$ towers that look beautiful. Each tower must have at least one block and all blocks must be used.

Input format:
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$x$$$ ($$$1 \le m \le n \le 10^5$$$; $$$1 \le x \le 10^4$$$) — the number of blocks, the number of towers to build, and the maximum acceptable height difference of any two towers, respectively.

The second line of each test case contains $$$n$$$ space-separated integers ($$$1 \le h_i \le x$$$) — the heights of the blocks.

It is guaranteed that the sum of $$$n$$$ over all the test cases will not exceed $$$10^5$$$.

Output format:
For each test case, if Phoenix cannot build $$$m$$$ towers that look beautiful, print NO. Otherwise, print YES, followed by $$$n$$$ integers $$$y_1, y_2, \dots, y_n$$$, where $$$y_i$$$ ($$$1 \le y_i \le m$$$) is the index of the tower that the $$$i$$$-th block is placed in.

If there are multiple solutions, print any of them.

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

Note:
In the first test case, the first tower has height $$$1+2+3=6$$$ and the second tower has height $$$1+2=3$$$. Their difference is $$$6-3=3$$$ which doesn't exceed $$$x=3$$$, so the towers are beautiful.

In the second test case, the first tower has height $$$1$$$, the second tower has height $$$1+2=3$$$, and the third tower has height $$$3$$$. The maximum height difference of any two towers is $$$3-1=2$$$ which doesn't exceed $$$x=3$$$, so the towers are beautiful.

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

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

Editorial:
Greedily adding blocks to the current shortest tower will always give a valid solution. Let's prove it with contradiction. If the towers weren't beautiful, then some two towers would have a height difference of more than $$$x$$$. Since a single block cannot exceed a height of $$$x$$$, the difference would be more than one block. This is a contradiction with our solution because we always add to the shortest tower.
To implement this, we can use a set-like structure and store pairs of ($$$h_i$$$, $$$i$$$) for each $$$i$$$ ($$$1 \le i \le m)$$$, where $$$h_i$$$ is the current height of the $$$i$$$-th tower (initialized to $$$0$$$). When adding a block, we remove the first element of the sorted set, update the tower height, and add it back into the set.
Time complexity for each test case: $$$O(n \log{n})$$$
Free Cash
Contest: Codeforces Round 147 (Div. 2)
Difficulty rating: 1000
Tags: implementation

Valera runs a 24/7 fast food cafe. He magically learned that next day n people will visit his cafe. For each person we know the arrival time: the i-th person comes exactly at hi hours mi minutes. The cafe spends less than a minute to serve each client, but if a client comes in and sees that there is no free cash, than he doesn't want to wait and leaves the cafe immediately.

Valera is very greedy, so he wants to serve all n customers next day (and get more profit). However, for that he needs to ensure that at each moment of time the number of working cashes is no less than the number of clients in the cafe.

Help Valera count the minimum number of cashes to work at his cafe next day, so that they can serve all visitors.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 105), that is the number of cafe visitors.

Each of the following n lines has two space-separated integers hi and mi (0 ≤ hi ≤ 23; 0 ≤ mi ≤ 59), representing the time when the i-th person comes into the cafe.

Note that the time is given in the chronological order. All time is given within one 24-hour period.

Output format:
Print a single integer — the minimum number of cashes, needed to serve all clients next day.

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

Note:
In the first sample it is not enough one cash to serve all clients, because two visitors will come into cafe in 8:10. Therefore, if there will be one cash in cafe, then one customer will be served by it, and another one will not wait and will go away.

In the second sample all visitors will come in different times, so it will be enough one cash.

Example input:
4
8 0
8 10
8 10
8 45

Example output:
2

Example input:
3
0 12
10 11
22 22

Example output:
1

Editorial: