1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Exposition
Contest: Codeforces Beta Round 6 (Div. 2 Only)
Difficulty rating: 1900
Tags: binary search, data structures, dsu, trees, two pointers

There are several days left before the fiftieth birthday of a famous Berland's writer Berlbury. In this connection the local library decided to make an exposition of the works of this famous science-fiction writer. It was decided as well that it is necessary to include into the exposition only those books that were published during a particular time period. It is obvious that if the books differ much in size, the visitors will not like it. That was why the organizers came to the opinion, that the difference between the highest and the lowest books in the exposition should be not more than k millimeters.

The library has n volumes of books by Berlbury, arranged in chronological order of their appearance. The height of each book in millimeters is know, it is hi. As Berlbury is highly respected in the city, the organizers want to include into the exposition as many books as possible, and to find out what periods of his creative work they will manage to cover. You are asked to help the organizers cope with this hard task.

Input format:
The first line of the input data contains two integer numbers separated by a space n (1 ≤ n ≤ 105) and k (0 ≤ k ≤ 106) — the amount of books by Berlbury in the library, and the maximum allowed height difference between the lowest and the highest books. The second line contains n integer numbers separated by a space. Each number hi (1 ≤ hi ≤ 106) is the height of the i-th book in millimeters.

Output format:
In the first line of the output data print two numbers a and b (separate them by a space), where a is the maximum amount of books the organizers can include into the exposition, and b — the amount of the time periods, during which Berlbury published a books, and the height difference between the lowest and the highest among these books is not more than k milllimeters.

In each of the following b lines print two integer numbers separated by a space — indexes of the first and the last volumes from each of the required time periods of Berlbury's creative work.

Constraints:
Time limit: 1.5 s
Memory limit: 64.0 MB

Example input:
3 3
14 12 10

Example output:
2 2
1 2
2 3

Example input:
2 0
10 10

Example output:
2 1
1 2

Editorial:
Keyboard
Contest: Codeforces Round 271 (Div. 2)
Difficulty rating: 900
Tags: implementation

Our good friend Mole is trying to code a big message. He is typing on an unusual keyboard with characters arranged in following way:

Unfortunately Mole is blind, so sometimes it is problem for him to put his hands accurately. He accidentally moved both his hands with one position to the left or to the right. That means that now he presses not a button he wants, but one neighboring button (left or right, as specified in input).

We have a sequence of characters he has typed and we want to find the original message.

Input format:
First line of the input contains one letter describing direction of shifting ('L' or 'R' respectively for left or right).

Second line contains a sequence of characters written by Mole. The size of this sequence will be no more than 100. Sequence contains only symbols that appear on Mole's keyboard. It doesn't contain spaces as there is no space on Mole's keyboard.

It is guaranteed that even though Mole hands are moved, he is still pressing buttons on keyboard and not hitting outside it.

Output format:
Print a line that contains the original message.

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

Example input:
R
s;;upimrrfod;pbr

Example output:
allyouneedislove

Editorial:
Worms
Contest: Codeforces Round 271 (Div. 2)
Difficulty rating: 1200
Tags: binary search, implementation

It is lunch time for Mole. His friend, Marmot, prepared him a nice game for lunch.

Marmot brought Mole n ordered piles of worms such that i-th pile contains ai worms. He labeled all these worms with consecutive integers: worms in first pile are labeled with numbers 1 to a1, worms in second pile are labeled with numbers a1 + 1 to a1 + a2 and so on. See the example for a better understanding.

Mole can't eat all the worms (Marmot brought a lot) and, as we all know, Mole is blind, so Marmot tells him the labels of the best juicy worms. Marmot will only give Mole a worm if Mole says correctly in which pile this worm is contained.

Poor Mole asks for your help. For all juicy worms said by Marmot, tell Mole the correct answers.

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

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 103, a1 + a2 + ... + an ≤ 106), where ai is the number of worms in the i-th pile.

The third line contains single integer m (1 ≤ m ≤ 105), the number of juicy worms said by Marmot.

The fourth line contains m integers q1, q2, ..., qm (1 ≤ qi ≤ a1 + a2 + ... + an), the labels of the juicy worms.

Output format:
Print m lines to the standard output. The i-th line should contain an integer, representing the number of the pile where the worm labeled with the number qi is.

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

Note:
For the sample input:

- The worms with labels from [1, 2] are in the first pile.
- The worms with labels from [3, 9] are in the second pile.
- The worms with labels from [10, 12] are in the third pile.
- The worms with labels from [13, 16] are in the fourth pile.
- The worms with labels from [17, 25] are in the fifth pile.

Example input:
5
2 7 3 4 9
3
1 25 11

Example output:
1
5
3

Editorial:
Captain Marmot
Contest: Codeforces Round 271 (Div. 2)
Difficulty rating: 2000
Tags: brute force, geometry

Captain Marmot wants to prepare a huge and important battle against his enemy, Captain Snake. For this battle he has n regiments, each consisting of 4 moles.

Initially, each mole i (1 ≤ i ≤ 4n) is placed at some position (xi, yi) in the Cartesian plane. Captain Marmot wants to move some moles to make the regiments compact, if it's possible.

Each mole i has a home placed at the position (ai, bi). Moving this mole one time means rotating his position point (xi, yi) 90 degrees counter-clockwise around it's home point (ai, bi).

A regiment is compact only if the position points of the 4 moles form a square with non-zero area.

Help Captain Marmot to find out for each regiment the minimal number of moves required to make that regiment compact, if it's possible.

Input format:
The first line contains one integer n (1 ≤ n ≤ 100), the number of regiments.

The next 4n lines contain 4 integers xi, yi, ai, bi ( - 104 ≤ xi, yi, ai, bi ≤ 104).

Output format:
Print n lines to the standard output. If the regiment i can be made compact, the i-th line should contain one integer, the minimal number of required moves. Otherwise, on the i-th line print "-1" (without quotes).

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

Note:
In the first regiment we can move once the second or the third mole.

We can't make the second regiment compact.

In the third regiment, from the last 3 moles we can move once one and twice another one.

In the fourth regiment, we can move twice the first mole and once the third mole.

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

Example output:
1
-1
3
3

Editorial:
Flowers
Contest: Codeforces Round 271 (Div. 2)
Difficulty rating: 1700
Tags: dp

We saw the little game Marmot made for Mole's lunch. Now it's Marmot's dinner time and, as we all know, Marmot eats flowers. At every dinner he eats some red and white flowers. Therefore a dinner can be represented as a sequence of several flowers, some of them white and some of them red.

But, for a dinner to be tasty, there is a rule: Marmot wants to eat white flowers only in groups of size k.

Now Marmot wonders in how many ways he can eat between a and b flowers. As the number of ways could be very large, print it modulo 1000000007 (109 + 7).

Input format:
Input contains several test cases.

The first line contains two integers t and k (1 ≤ t, k ≤ 105), where t represents the number of test cases.

The next t lines contain two integers ai and bi (1 ≤ ai ≤ bi ≤ 105), describing the i-th test.

Output format:
Print t lines to the standard output. The i-th line should contain the number of ways in which Marmot can eat between ai and bi flowers at dinner modulo 1000000007 (109 + 7).

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

Note:
- For K = 2 and length 1 Marmot can eat (R).
- For K = 2 and length 2 Marmot can eat (RR) and (WW).
- For K = 2 and length 3 Marmot can eat (RRR), (RWW) and (WWR).
- For K = 2 and length 4 Marmot can eat, for example, (WWWW) or (RWWR), but for example he can't eat (WWWR).

Example input:
3 2
1 3
2 3
4 4

Example output:
6
5
5

Editorial:
Pillars
Contest: Codeforces Round 271 (Div. 2)
Difficulty rating: 2000
Tags: binary search, data structures, dp, sortings, trees

Marmot found a row with n pillars. The i-th pillar has the height of hi meters. Starting from one pillar i1, Marmot wants to jump on the pillars i2, ..., ik. (1 ≤ i1 < i2 < ... < ik ≤ n). From a pillar i Marmot can jump on a pillar j only if i < j and |hi - hj| ≥ d, where |x| is the absolute value of the number x.

Now Marmot is asking you find out a jump sequence with maximal length and print it.

Input format:
The first line contains two integers n and d (1 ≤ n ≤ 105, 0 ≤ d ≤ 109).

The second line contains n numbers h1, h2, ..., hn (1 ≤ hi ≤ 1015).

Output format:
The first line should contain one integer k, the maximal length of a jump sequence.

The second line should contain k integers i1, i2, ..., ik (1 ≤ i1 < i2 < ... < ik ≤ n), representing the pillars' indices from the maximal length jump sequence.

If there is more than one maximal length jump sequence, print any.

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

Note:
In the first example Marmot chooses the pillars 1, 2, 3, 5 with the heights 1, 3, 6, 4. Another jump sequence of length 4 is 1, 2, 4, 5.

Example input:
5 2
1 3 6 7 4

Example output:
4
1 2 3 5

Example input:
10 3
2 1 3 6 9 11 7 3 20 18

Example output:
6
1 4 6 7 8 9

Editorial:
Ant colony
Contest: Codeforces Round 271 (Div. 2)
Difficulty rating: 2100
Tags: data structures, math, number theory

Mole is hungry again. He found one ant colony, consisting of n ants, ordered in a row. Each ant i (1 ≤ i ≤ n) has a strength si.

In order to make his dinner more interesting, Mole organizes a version of «Hunger Games» for the ants. He chooses two numbers l and r (1 ≤ l ≤ r ≤ n) and each pair of ants with indices between l and r (inclusively) will fight. When two ants i and j fight, ant i gets one battle point only if si divides sj (also, ant j gets one battle point only if sj divides si).

After all fights have been finished, Mole makes the ranking. An ant i, with vi battle points obtained, is going to be freed only if vi = r - l, or in other words only if it took a point in every fight it participated. After that, Mole eats the rest of the ants. Note that there can be many ants freed or even none.

In order to choose the best sequence, Mole gives you t segments [li, ri] and asks for each of them how many ants is he going to eat if those ants fight.

Input format:
The first line contains one integer n (1 ≤ n ≤ 105), the size of the ant colony.

The second line contains n integers s1, s2, ..., sn (1 ≤ si ≤ 109), the strengths of the ants.

The third line contains one integer t (1 ≤ t ≤ 105), the number of test cases.

Each of the next t lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n), describing one query.

Output format:
Print to the standard output t lines. The i-th line contains number of ants that Mole eats from the segment [li, ri].

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

Note:
In the first test battle points for each ant are v = [4, 0, 2, 0, 2], so ant number 1 is freed. Mole eats the ants 2, 3, 4, 5.

In the second test case battle points are v = [0, 2, 0, 2], so no ant is freed and all of them are eaten by Mole.

In the third test case battle points are v = [2, 0, 2], so ants number 3 and 5 are freed. Mole eats only the ant 4.

In the fourth test case battle points are v = [0, 1], so ant number 5 is freed. Mole eats the ant 4.

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

Example output:
4
4
1
1

Editorial:
Distinguish I from X
Contest: Microsoft Q# Coding Contest - Summer 2020 - Warmup
Tags: *special

You are given an operation that implements a single-qubit unitary transformation: either the identity (I gate) or the X gate. The operation will have Adjoint and Controlled variants defined.

Your task is to perform necessary operations and measurements to figure out which unitary it was and to return 0 if it was the I gate or 1 if it was the X gate.

You are allowed to apply the given operation and its adjoint/controlled variants exactly once.

You have to implement an operation which takes a single-qubit operation as an input and returns an integer. Your code should have the following signature:

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

Editorial:
Distinguish I from Z
Contest: Microsoft Q# Coding Contest - Summer 2020 - Warmup
Tags: *special

You are given an operation that implements a single-qubit unitary transformation: either the identity (I gate) or the Z gate. The operation will have Adjoint and Controlled variants defined.

Your task is to perform necessary operations and measurements to figure out which unitary it was and to return 0 if it was the I gate or 1 if it was the Z gate.

You are allowed to apply the given operation and its adjoint/controlled variants exactly once.

You have to implement an operation which takes a single-qubit operation as an input and returns an integer. Your code should have the following signature:

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

Editorial:
Distinguish Z from S
Contest: Microsoft Q# Coding Contest - Summer 2020 - Warmup
Tags: *special

You are given an operation that implements a single-qubit unitary transformation: either the Z gate or the S gate. The operation will have Adjoint and Controlled variants defined.

Your task is to perform necessary operations and measurements to figure out which unitary it was and to return 0 if it was the Z gate or 1 if it was the S gate.

You are allowed to apply the given operation and its adjoint/controlled variants exactly twice.

You have to implement an operation which takes a single-qubit operation as an input and returns an integer. Your code should have the following signature:

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

Editorial:
Distinguish I ⊗ X from CNOT
Contest: Microsoft Q# Coding Contest - Summer 2020 - Warmup
Tags: *special

You are given an operation that implements a two-qubit unitary transformation: either $$$I \otimes X$$$ (the X gate applied to the second qubit and no effect on the first qubit) or the CNOT gate with the first qubit as control and the second qubit as target. The operation will have Adjoint and Controlled variants defined.

Your task is to perform necessary operations and measurements to figure out which unitary it was and to return 0 if it was $$$I \otimes X$$$ or 1 if it was the CNOT gate.

You are allowed to apply the given operation and its adjoint/controlled variants exactly once.

You have to implement an operation which takes a two-qubit operation unitary as an input and returns an integer. The operation unitary will accept an array of qubits as input, but it will fail if the array is empty or has one or more than two qubits. Your code should have the following signature:

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

Editorial:
Distinguish Z from -Z
Contest: Microsoft Q# Coding Contest - Summer 2020 - Warmup
Tags: *special

You are given an operation that implements a single-qubit unitary transformation: either the Z gate or the -Z gate (i.e., the $$$-|0\rangle\langle0| + |1\rangle\langle1|$$$ gate: $$$(-Z)(\alpha|0\rangle + \beta|1\rangle) = -\alpha|0\rangle + \beta|1\rangle$$$). The operation will have Adjoint and Controlled variants defined.

Your task is to perform necessary operations and measurements to figure out which unitary it was and to return 0 if it was the Z gate or 1 if it was the -Z gate.

You are allowed to apply the given operation and its adjoint/controlled variants exactly once.

You have to implement an operation which takes a single-qubit operation as an input and returns an integer. Your code should have the following signature:

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

Editorial:
Increment
Contest: Microsoft Q# Coding Contest - Summer 2020 - Warmup
Tags: *special

Implement a unitary operation on a register of $$$N$$$ qubits that increments the number written in the register modulo $$$2^N$$$.

Your operation should take a register of type LittleEndian - an array of qubits that encodes an unsigned integer in little-endian format, with the least significant bit written first (corresponding to the array element with index 0). The "output" of your solution is the state in which it left the input qubits.

For example, if the qubits passed to your operation are in the state $$$\frac{1}{\sqrt{2}}(|11\rangle + |10\rangle) = \frac{1}{\sqrt{2}}(|3\rangle + |1\rangle)$$$, they should be transformed to the state $$$\frac{1}{\sqrt{2}}(|(3+1) \mod 2^2\rangle + |(1+1) \mod 2^2\rangle) = \frac{1}{\sqrt{2}}(|0\rangle + |2\rangle) = \frac{1}{\sqrt{2}}(|00\rangle + |01\rangle)$$$.

Your code should have the following signature (note that your operation should have Adjoint and Controlled variants defined for it; is Adj+Ctl in the operation signature will generate them automatically based on your code):

Your code is not allowed to use measurements or arbitrary rotation gates (so, for example, using the library operation IncrementByInteger will cause runtime error). This operation can be implemented using just the X gate and its controlled variants.

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

Editorial:
Decrement
Contest: Microsoft Q# Coding Contest - Summer 2020 - Warmup
Tags: *special

Implement a unitary operation on a register of $$$N$$$ qubits that decrements the number written in the register modulo $$$2^N$$$.

Your operation should take a register of type LittleEndian - an array of qubits that encodes an unsigned integer in little-endian format, with the least significant bit written first (corresponding to the array element with index 0). The "output" of your solution is the state in which it left the input qubits.

For example, if the qubits passed to your operation are in the state $$$\frac{1}{\sqrt{2}}(|00\rangle + |01\rangle) = \frac{1}{\sqrt{2}}(|0\rangle + |2\rangle)$$$, they should be transformed to the state $$$\frac{1}{\sqrt{2}}(|(0-1) \mod 2^2\rangle + |(2-1) \mod 2^2\rangle) = \frac{1}{\sqrt{2}}(|3\rangle + |1\rangle) = \frac{1}{\sqrt{2}}(|11\rangle + |10\rangle)$$$.

Your code should have the following signature (note that your operation should have Adjoint and Controlled variants defined for it; is Adj+Ctl in the operation signature will generate them automatically based on your code):

Your code is not allowed to use measurements or arbitrary rotation gates (so, for example, using the library operation IncrementByInteger will cause runtime error). This operation can be implemented using just the X gate and its controlled variants.

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

Editorial:
Prepare state |01⟩ + |10⟩ + |11⟩
Contest: Microsoft Q# Coding Contest - Summer 2020 - Warmup
Tags: *special

You are given two qubits in state $$$|00 \rangle$$$. Your task is to prepare the following state on them:

$$$$$$\frac{1}{\sqrt{3}} \big( |01 \rangle + |10 \rangle + |11 \rangle)$$$$$$

This task is very similar to problem A1 of the Winter 2019 contest, but this time you are not allowed to use any gates except the Pauli gates (X, Y and Z), the Hadamard gate and the controlled versions of those. However, you are allowed to use measurements.

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

Your code should have the following signature:

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

Editorial:
Quantum Classification - 1
Contest: Microsoft Q# Coding Contest - Summer 2020 - Warmup
Tags: *special

You are given a training dataset, in which each entry is a features vector (an array of 2 real numbers) and a label 0 or 1 indicating the class to which this vector belongs.

Your goal is to use this dataset to train a quantum classification model that will accurately classify a validation dataset - a different dataset generated using the same data distribution as the training one. The error rate of classifying the validation dataset using your model (the percentage of incorrectly classified samples) should be less than 5

- The quantum classification library that will use your model to classify the data is documented here.
- This tutorial has an end-to-end example of training a model using this library as a Python notebook.
- You can find examples of training a model and using it for classification here.

Input format:
Your code will not be given any inputs. Instead, you should use the provided dataset file to train your model.

The training dataset is represented as a JSON file and consists of two arrays, "Features" and "Labels". Each array has exactly 200 elements. Each element of the "Features" array is an array with 2 elements, each of them a floating-point number between -1 and 1. Each element of the "Labels" array is the label of the class to which the corresponding element of the "Features" array belongs, 0 or 1.

Output format:
Your code should return the description of the model you'd like to use in the following format:

- The model is described using a tuple (ControlledRotation[], (Double[], Double)).
- The first element of the tuple describes circuit geometry of the model as an array of controlled rotation gates.
- The second element of the tuple describes numeric parameters of the model and is a tuple of an array of rotation angles used by the gates and the bias used to decide the class of the model.

Your code should have the following signature:

Please refer to the documentation and examples for details on each parameter.

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

Note:
Note that majority of the data analysis is going to happen "offline" before you submit the solution. The solution has to contain only the description of the trained model, not the training code itself - if you attempt to train the model "online" in your submitted code during the evaluation process, it will very likely time out.

Training your model offline is likely to involve:

- Defining the circuit structure that your model will use.
- Generating several parameter seed vectors - the values from which training the model will start.
- Selecting appropriate hyperparameters of the training process (learning rate, batch size, tolerance, maximal number of iterations etc.)
- Training a number of classification models (one per each seed vector and hyperparameter combination)
- Selecting the best trained model and submitting it.

Editorial: