1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Increasing Subsequences
Contest: Educational Codeforces Round 161 (Rated for Div. 2)
Difficulty rating: 1800
Tags: bitmasks, constructive algorithms, divide and conquer, greedy, math

Let's recall that an increasing subsequence of the array $$$a$$$ is a sequence that can be obtained from it by removing some elements without changing the order of the remaining elements, and the remaining elements are strictly increasing (i. e $$$a_{b_1} < a_{b_2} < \dots < a_{b_k}$$$ and $$$b_1 < b_2 < \dots < b_k$$$). Note that an empty subsequence is also increasing.

You are given a positive integer $$$X$$$. Your task is to find an array of integers of length at most $$$200$$$, such that it has exactly $$$X$$$ increasing subsequences, or report that there is no such array. If there are several answers, you can print any of them.

If two subsequences consist of the same elements, but correspond to different positions in the array, they are considered different (for example, the array $$$[2, 2]$$$ has two different subsequences equal to $$$[2]$$$).

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

The only line of each test case contains a single integer $$$X$$$ ($$$2 \le X \le 10^{18}$$$).

Output format:
For each query, print the answer to it. If it is impossible to find the required array, print -1 on the first line. Otherwise, print a positive integer $$$n$$$ on the first line — the length of the array. On the second line, print $$$n$$$ integers — the required array itself. If there are several answers, you can print any of them. All elements of the array should be in the range $$$[-10^9; 10^9]$$$.

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

Example input:
4
2
5
13
37

Example output:
1
0
3
0 1 0
5
2 2 3 4 2
7
-1 -1 0 0 2 3 -1

Editorial:
Let's consider one of the solutions for constructing the required array.
Let array $$$a$$$ have $$$x$$$ increasing subsequences. If we add a new minimum to the end of the array, the number of increasing subsequences in the new array equals $$$x+1$$$ (since the new element does not form increasing subsequences with other elements, only subsequences consisting of this element will be added). If we add a new maximum to the end of the array, the number of increasing subsequences in the new array equals $$$2x$$$ (since the new element forms increasing subsequences with any other elements).
Using the above facts, let's define a recursive function $$$f(x)$$$, which returns an array with exactly $$$x$$$ increasing subsequences. For an odd value of $$$x$$$, $$$f(x) = f(x-1) + min$$$ (here + denotes adding an element to the end of the array); for an even value of $$$x$$$, $$$f(x) = f(\frac{x}{2}) + max$$$. Now we need to estimate the number of elements in the array obtained by this algorithm. Note that there cannot be two consecutive operations of the first type ($$$x \rightarrow x-1$$$), so every two operations, the value of $$$x$$$ decreases by at least two times. Thus, the size of the array satisfies the limit of $$$200$$$.
Closing ceremony
Contest: Russian Code Cup 2016 - Finals [Unofficial Mirror, Div. 1 Only Recommended]
Difficulty rating: 2000
Tags: greedy

The closing ceremony of Squanch Code Cup is held in the big hall with n × m seats, arranged in n rows, m seats in a row. Each seat has two coordinates (x, y) (1 ≤ x ≤ n, 1 ≤ y ≤ m).

There are two queues of people waiting to enter the hall: k people are standing at (0, 0) and n·m - k people are standing at (0, m + 1). Each person should have a ticket for a specific seat. If person p at (x, y) has ticket for seat (xp, yp) then he should walk |x - xp| + |y - yp| to get to his seat.

Each person has a stamina — the maximum distance, that the person agrees to walk. You should find out if this is possible to distribute all n·m tickets in such a way that each person has enough stamina to get to their seat.

Input format:
The first line of input contains two integers n and m (1 ≤ n·m ≤ 104) — the size of the hall.

The second line contains several integers. The first integer k (0 ≤ k ≤ n·m) — the number of people at (0, 0). The following k integers indicate stamina of each person there.

The third line also contains several integers. The first integer l (l = n·m - k) — the number of people at (0, m + 1). The following l integers indicate stamina of each person there.

The stamina of the person is a positive integer less that or equal to n + m.

Output format:
If it is possible to distribute tickets between people in the described manner print "YES", otherwise print "NO".

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

Example input:
2 2
3 3 3 2
1 3

Example output:
YES

Example input:
2 2
3 2 3 3
1 2

Example output:
NO

Editorial:
Probably the easiest way to solve the problem is greedy. Sort people from the first line by increasing of their stamina. Give them tickets in this order, each time using the place which is furthest away from the other line. After that try to assign people from the second line to the remaining seats by sorting people by stamina and seats by the distance.
The time complexity of your solution must not exceed O((nm)2), however using std::set one can get a solution with complexity of O(nm log(nm)).
Cactusophobia
Contest: Russian Code Cup 2016 - Finals [Unofficial Mirror, Div. 1 Only Recommended]
Difficulty rating: 2400
Tags: dfs and similar, flows

Tree is a connected undirected graph that has no cycles. Edge cactus is a connected undirected graph without loops and parallel edges, such that each edge belongs to at most one cycle.

Vasya has an edge cactus, each edge of this graph has some color.

Vasya would like to remove the minimal number of edges in such way that his cactus turned to a tree. Vasya wants to make it in such a way that there were edges of as many different colors in the resulting tree, as possible. Help him to find how many different colors can the resulting tree have.

Input format:
The first line contains two integers: n, m (2 ≤ n ≤ 10 000) — the number of vertices and the number of edges in Vasya's graph, respectively.

The following m lines contain three integers each: u, v, c (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ c ≤ m) — the numbers of vertices connected by the corresponding edge, and its color. It is guaranteed that the described graph is indeed an edge cactus.

Output format:
Output one integer: the maximal number of different colors that the resulting tree can have.

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

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

Example output:
3

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

Example output:
6

Editorial:
Let us divide the graph to biconnected blocks. Each block is either a bridge, or a cycle. Our goal is to remove one edge from each cycle, so that the number of remaining colors were maximum possible.
Let us build a bipartite graph, one part would be blocks, another one would be colors. For each block put an edge of capacity 1 for each color of an edge in this block (make multiple edges, or bigger capacity if there are several edges of some color). Add two vertices: source and sink, add edges from source to blocks, if the block is a cycle of length l, set its capacity to l - 1, if it is a bridge, set its capacity to 1. Add edges from color vertices to the sink of capacity 1.
It is quite clear that size of the maximum flow in this graph is indeed the answer to the problem.
As a final note, the judges know the solution that runs in O(n) and requires no maximum flow algorithms, challenge yourself to come up with it!
Slalom
Contest: Russian Code Cup 2016 - Finals [Unofficial Mirror, Div. 1 Only Recommended]
Difficulty rating: 3100
Tags: data structures, dp, sortings

Little girl Masha likes winter sports, today she's planning to take part in slalom skiing.

The track is represented as a grid composed of n × m squares. There are rectangular obstacles at the track, composed of grid squares. Masha must get from the square (1, 1) to the square (n, m). She can move from a square to adjacent square: either to the right, or upwards. If the square is occupied by an obstacle, it is not allowed to move to that square.

One can see that each obstacle can actually be passed in two ways: either it is to the right of Masha's path, or to the left. Masha likes to try all ways to do things, so she would like to know how many ways are there to pass the track. Two ways are considered different if there is an obstacle such that it is to the right of the path in one way, and to the left of the path in the other way.

Help Masha to find the number of ways to pass the track. The number of ways can be quite big, so Masha would like to know it modulo 109 + 7.

The pictures below show different ways to pass the track in sample tests.

Input format:
The first line of input data contains three positive integers: n, m and k (3 ≤ n, m ≤ 106, 0 ≤ k ≤ 105) — the size of the track and the number of obstacles.

The following k lines contain four positive integers each: x1, y1, x2, y2 (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m) — coordinates of bottom left, and top right squares of the obstacle.

It is guaranteed that there are no obstacles at squares (1, 1) and (n, m), and no obstacles overlap (but some of them may touch).

Output format:
Output one integer — the number of ways to pass the track modulo 109 + 7.

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

Example input:
3 3 0

Example output:
1

Example input:
4 5 1
2 2 3 4

Example output:
2

Editorial:
First let us consider all paths from the starting square to the finish one. Let us say that two paths are equivalent, if each obstacle is at the same side for both paths. For each class of equivalence let us choose the representative path — the one that tries to go as low as possible, lexicographically minimum.
Let us use dynamic programming. For each square let us count the number of representative paths that go from the starting square to this one. When the obstacle starts, some paths can now separate. The new representatives will pass this obstacle from above (it will be to the right of them). So we add the sum of values for squares below it, but above any other lower obstacle, to the value for the square right above the obstacle.
To overcome the time and memory limits that the naive solution with O(nm) memory and O(nm2) time complexity, we use segment tree for range sum queries with mass update, running scanline and events "start of an obstacle", "end of an obstacle". This leads to the solution with O(m) memory and O(n log m) time complexity.
Cipher
Contest: Russian Code Cup 2016 - Finals [Unofficial Mirror, Div. 1 Only Recommended]
Difficulty rating: 3100
Tags: implementation

Borya has recently found a big electronic display. The computer that manages the display stores some integer number. The number has n decimal digits, the display shows the encoded version of the number, where each digit is shown using some lowercase letter of the English alphabet.

There is a legend near the display, that describes how the number is encoded. For each digit position i and each digit j the character c is known, that encodes this digit at this position. Different digits can have the same code characters.

Each second the number is increased by 1. And one second after a moment when the number reaches the value that is represented as n 9-s in decimal notation, the loud beep sounds.

Andrew knows the number that is stored in the computer. Now he wants to know how many seconds must pass until Borya can definitely tell what was the original number encoded by the display. Assume that Borya can precisely measure time, and that the encoded number will first be increased exactly one second after Borya started watching at the display.

Input format:
Input data contains multiple test cases. The first line of input contains t (1 ≤ t ≤ 100) — the number of test cases.

Each test case is described as follows. The first line of the description contains n (1 ≤ n ≤ 18) — the number of digits in the number. The second line contains n decimal digits without spaces (but possibly with leading zeroes) — the number initially stored in the display computer. The following n lines contain 10 characters each. The j-th character of the i-th of these lines is the code character for a digit j - 1 in position i, most significant digit positions are described first.

Output format:
For each test case print an integer: the number of seconds until Borya definitely knows what was the initial number stored on the display of the computer. Do not print leading zeroes.

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

Example input:
3
2
42
abcdefghij
jihgfedcba
2
42
aaaaaaaaaa
aaaaaaaaaa
1
2
abcdabcdff

Example output:
0
58
2

Editorial:
First let us consider a slow solution. Let us find a condition for each number k after what number of seconds Borya can distinguish it from the given number. Let us look at their initial encoding. Increase both numbers by 1 until the encodings are different (or one of the numbers needs more than n digits to represent in which case the beep allows Borya to distinguish the numbers as well).
Now there are two main ideas that allow us to get a better solution. First, we don't have to check all numbers. We only need to check numbers that differ from the given number in exactly one digit.
Second: to get the time when the numbers can be distinguished we don't need to iterate over all possible values. We just need to try all digit positions and all values for that position, and check only moments when the digit at the position will first have this value in one of the numbers.
So the complexity is now polynomial in n and since n ≤ 18, it easily fits into the time limit.
Array Covering
Contest: Russian Code Cup 2016 - Finals [Unofficial Mirror, Div. 1 Only Recommended]
Difficulty rating: 3100
Tags: data structures

Misha has an array of integers of length n. He wants to choose k different continuous subarrays, so that each element of the array belongs to at least one of the chosen subarrays.

Misha wants to choose the subarrays in such a way that if he calculated the sum of elements for each subarray, and then add up all these sums, the resulting value was maximum possible.

Input format:
The first line of input contains two integers: n, k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ n·(n + 1) / 2) — the number of elements in the array and the number of different subarrays that must be chosen.

The second line contains n integers ai ( - 50 000 ≤ ai ≤ 50 000) — the elements of the array.

Output format:
Output one integer — the maximum possible value Misha can get by choosing k different subarrays.

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

Example input:
5 4
6 -4 -10 -4 7

Example output:
11

Editorial:
We give the outline of the solution, leaving technical details as an excercise.
First note that the answer will always use min(k - n, 0) subarrays with maximal sums. Sof let us find the sum of min(k - n, 0) maximal subarrays, elements that are used in them, and the following min(k, n) subarrays. We can do it using binary search for the border sum, and a data structure similar to Fenwick tree. For the given value of the sum this tree must provide the number of subarrays with greater or equal sum, sum of their sums, and the set of the elements of these subarrays. It should also allow to list all these subarrays in linear time complexity. This part has time complexity O(n log2 n).
Let us now describe how to solve the problem in O(n2 log n). Let us try all values of x — the number of subarrays with maximum sums that we will use in our solution (there are O(n) variants, because top min(k - n, 0) subarrays will definitely be used). Let elements with indices i1, ..., im be the ones that are not used in these subarrays. Now we must add k - x segments that would contain all of these elements. Note that each of these k - x segments must contain at least one of these elements, and no two segments can have a common element among them (in the other case the solution is not optimal). These observations let us greedily choose these k - x segments in O(n log n) and the final solution complexity is O(n2 log n)
To optimize this solution, we keep segments [ij + 1; ij + 1 - 1] in the ordered set. When we iterate over x and increase its value, we remove some of the ij-s, and recalculate the required values for the affected segments. After that we must take k - x maximal values from the set, so since there are O(n) changes in total, this part now works in O(n log n).
Generate superposition of all basis states
Contest: Microsoft Q# Coding Contest - Summer 2018
Difficulty rating: 800
Tags: *special

You are given N qubits (1 ≤ N ≤ 8) in zero state $${\left|0\dots0\right\rangle}$$.

Your task is to generate an equal superposition of all 2N basis vectors on N qubits:

$${ \left| S \right\rangle } = { \frac { 1 } { \sqrt { 2 ^ { N } } } } ( { \left| 0 \ldots 0 \right\rangle } + \ldots + { \left| 1 \ldots 1 \right\rangle } )$$

For example,

- for N = 1, the required state is simply $${ \left| + \right\rangle } = { \frac { 1 } { \sqrt { 2 } } } ( { \left| 0 \right\rangle } + { \left| 1 \right\rangle } )$$,
- for N = 2, the required state is $${ \frac { 1 } { 2 } } ( | 0 0 \rangle + | 0 1 \rangle + | 1 0 \rangle + | 1 1 \rangle )$$.

You have to implement an operation which takes an array of N qubits as an input and has no output. The "output" of the operation is the state in which it leaves the qubits.

Your code should have the following signature:

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

Editorial:
Generate superposition of zero state and a basis state
Contest: Microsoft Q# Coding Contest - Summer 2018
Difficulty rating: 1300
Tags: *special

You are given N qubits (1 ≤ N ≤ 8) in zero state $${\left|0\dots0\right\rangle}$$. You are also given a bitstring bits which describes a non-zero basis state on N qubits $${\left|{\psi}\right\rangle}$$.

Your task is to generate a state which is an equal superposition of $${\left|0\dots0\right\rangle}$$ and the given basis state:

$${ \left| S \right\rangle } = { \frac { 1 } { \sqrt { 2 } } } ( { \left| 0... 0 \right\rangle } + { \left| \psi \right\rangle } )$$

You have to implement an operation which takes the following inputs:

- an array of qubits qs,
- an arrays of boolean values bits representing the basis state $${\left|{\psi}\right\rangle}$$. This array will have the same length as the array of qubits. The first element of this array bits[0] will be true.

The operation doesn't have an output; its "output" is the state in which it leaves the qubits.

An array of boolean values represents a basis state as follows: the i-th element of the array is true if the i-th qubit is in state $$\left|1\right\rangle$$, and false if it is in state $$| 0 \rangle$$. For example, array [true; false] describes 2-qubit state $$|\psi\rangle = |10\rangle$$, and in this case the resulting state should be $${ \frac { 1 } { \sqrt { 2 } } } ( | 0 0 \rangle + | 1 0 \rangle ) = | + \rangle \otimes | 0 \rangle$$.

Your code should have the following signature:

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

Editorial:
Generate superposition of two basis states
Contest: Microsoft Q# Coding Contest - Summer 2018
Difficulty rating: 1500
Tags: *special

You are given N qubits (1 ≤ N ≤ 8) in zero state $${\left|0\dots0\right\rangle}$$. You are also given two bitstrings bits0 and bits1 which describe two different basis states on N qubits $${ \left| \psi _ { 0 } \right> }$$ and $$\left|\psi_{1}\right\rangle$$.

Your task is to generate a state which is an equal superposition of the given basis states:

$${ \left| S \right\rangle } = { \frac { 1 } { \sqrt { 2 } } } ( { \left| \psi _ { 0 } \right\rangle } + { \left| \psi _ { 1 } \right\rangle } )$$

You have to implement an operation which takes the following inputs:

- an array of qubits qs,
- two arrays of Boolean values bits0 and bits1 representing the basis states $${ \left| \psi _ { 0 } \right> }$$ and $$\left|\psi_{1}\right\rangle$$. These arrays will have the same length as the array of qubits. bits0 and bits1 will differ in at least one position.

The operation doesn't have an output; its "output" is the state in which it leaves the qubits.

Your code should have the following signature:

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

Editorial:
Generate W state
Contest: Microsoft Q# Coding Contest - Summer 2018
Difficulty rating: 1900
Tags: *special

You are given N = 2k qubits (0 ≤ k ≤ 4) in zero state $${\left|0\dots0\right\rangle}$$. Your task is to create a generalized W state on them. Generalized W state is an equal superposition of all basis states on N qubits that have Hamming weight equal to 1:

$${ \left| W _ { N } \right\rangle } = { \frac { 1 } { \sqrt { N } } } ( { \left| 1 0 0... 0 \right\rangle } + { \left| 0 1 0... 0 \right\rangle } + \ldots + { \left| 0 0... 0 1 \right\rangle } )$$

For example, for N = 1, $$| W_{1} \rangle = | 1 \rangle$$.

You have to implement an operation which takes an array of N qubits as an input and has no output. The "output" of the operation is the state in which it leaves the qubits.

Your code should have the following signature:

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

Editorial:
Distinguish zero state and W state
Contest: Microsoft Q# Coding Contest - Summer 2018
Difficulty rating: 1300
Tags: *special

You are given N qubits (2 ≤ N ≤ 8) which are guaranteed to be in one of the two states:

- $${\left|0\dots0\right\rangle}$$ state, or
- $${ \left| W \right\rangle } = { \frac { 1 } { \sqrt { N } } } ( { \left| 1 0 0... 0 \right\rangle } + { \left| 0 1 0... 0 \right\rangle } + \ldots + { \left| 0 0... 0 1 \right\rangle } )$$ state. Your task is to perform necessary operations and measurements to figure out which state it was and to return 0 if it was $${\left|0..0\right\rangle}$$ state or 1 if it was W state. The state of the qubits after the operations does not matter.You have to implement an operation which takes an array of N qubits as an input and returns an integer. Your code should have the following signature:namespace Solution {    open Microsoft.Quantum.Primitive;    open Microsoft.Quantum.Canon;    operation Solve (qs : Qubit[]) : Int    {        body        {            // your code here        }    }}

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

Editorial:
Distinguish GHZ state and W state
Contest: Microsoft Q# Coding Contest - Summer 2018
Difficulty rating: 1600
Tags: *special

You are given N qubits (2 ≤ N ≤ 8) which are guaranteed to be in one of the two states:

- $${ \left| GHZ \right\rangle } = { \frac { 1 } { \sqrt { 2 } } } ( { \left| 0 \dots 0 \right\rangle } + { \left| 1 \dots 1 \right\rangle } )$$ state, or
- $${ \left| W \right\rangle } = { \frac { 1 } { \sqrt { N } } } ( { \left| 1 0 0... 0 \right\rangle } + { \left| 0 1 0... 0 \right\rangle } + \ldots + { \left| 0 0... 0 1 \right\rangle } )$$ state. Your task is to perform necessary operations and measurements to figure out which state it was and to return 0 if it was GHZ state or 1 if it was W state. The state of the qubits after the operations does not matter.You have to implement an operation which takes an array of N qubits as an input and returns an integer. Your code should have the following signature:namespace Solution {    open Microsoft.Quantum.Primitive;    open Microsoft.Quantum.Canon;    operation Solve (qs : Qubit[]) : Int    {        body        {            // your code here        }    }}

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

Editorial: