1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Distinguish four 2-qubit states
Contest: Microsoft Q# Coding Contest - Summer 2018
Difficulty rating: 1600
Tags: *special

You are given 2 qubits which are guaranteed to be in one of the four orthogonal states:

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

Your task is to perform necessary operations and measurements to figure out which state it was and to return the index of that state (0 for $${ \left| S_{0} \right\rangle }$$, 1 for $$\left|S_{1}\right\rangle$$ etc.). The state of the qubits after the operations does not matter.

You have to implement an operation which takes an array of 2 qubits 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 four 2-qubit states - 2
Contest: Microsoft Q# Coding Contest - Summer 2018
Difficulty rating: 1700
Tags: *special

You are given 2 qubits which are guaranteed to be in one of the four orthogonal states:

- $${ \left| S _ { 0 } \right\rangle } = { \frac { 1 } { 2 } } { \Big ( } - { \left| 0 0 \right\rangle } - { \left| 0 1 \right\rangle } - { \left| 1 0 \right\rangle } - { \left| 1 1 \right\rangle } { \Big ) }$$
- $${ \left| S _ { 1 } \right\rangle } = { \frac { 1 } { 2 } } { \Big ( } - { \left| 0 0 \right\rangle } + { \left| 0 1 \right\rangle } - { \left| 1 0 \right\rangle } - { \left| 1 1 \right\rangle } { \Big ) }$$
- $${ \left| S _ { 2 } \right\rangle } = { \frac { 1 } { 2 } } { \Big ( } - { \left| 0 0 \right\rangle } - { \left| 0 1 \right\rangle } + { \left| 1 0 \right\rangle } - { \left| 1 1 \right\rangle } { \Big ) }$$
- $${ \left| S _ { 3 } \right\rangle } = { \frac { 1 } { 2 } } { \Big ( } - { \left| 0 0 \right\rangle } - { \left| 0 1 \right\rangle } - { \left| 1 0 \right\rangle } + { \left| 1 1 \right\rangle } { \Big ) }$$

Your task is to perform necessary operations and measurements to figure out which state it was and to return the index of that state (0 for $${ \left| S_{0} \right\rangle }$$, 1 for $$\left|S_{1}\right\rangle$$ etc.). The state of the qubits after the operations does not matter.

You have to implement an operation which takes an array of 2 qubits 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 zero state and plus state with minimum error
Contest: Microsoft Q# Coding Contest - Summer 2018
Difficulty rating: 1700
Tags: *special

You are given a qubit which is guaranteed to be either in $$| 0 \rangle$$ state or in $${ \left| + \right\rangle } = { \frac { 1 } { \sqrt { 2 } } } ( { \left| 0 \right\rangle } + { \left| 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 a $$| 0 \rangle$$ state or 1 if it was $$|+\rangle$$ state. The state of the qubit after the operations does not matter.

Note that these states are not orthogonal, and thus can not be distinguished perfectly. In each test your solution will be called 1000 times, and your goal is to get a correct answer at least 80% of the times. In each test $$| 0 \rangle$$ and $$|+\rangle$$ states will be provided with 50% probability.

You have to implement an operation which takes a qubit as an input and returns an integer.

Your code should have the following signature:

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

Editorial:
Distinguish zero state and plus state without errors
Contest: Microsoft Q# Coding Contest - Summer 2018
Difficulty rating: 1800
Tags: *special

You are given a qubit which is guaranteed to be either in $$| 0 \rangle$$ state or in $${ \left| + \right\rangle } = { \frac { 1 } { \sqrt { 2 } } } ( { \left| 0 \right\rangle } + { \left| 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 a $$| 0 \rangle$$ state, 1 if it was $$|+\rangle$$ state or -1 if you can not decide, i.e., an "inconclusive" result. The state of the qubit after the operations does not matter.

Note that these states are not orthogonal, and thus can not be distinguished perfectly. In each test your solution will be called 10000 times, and your goals are:

- never give 0 or 1 answer incorrectly (i.e., never return 0 if input state was $$|+\rangle$$ and never return 1 if input state was $$| 0 \rangle$$),
- give -1 answer at most 80% of the times,
- correctly identify $$| 0 \rangle$$ state at least 10% of the times,
- correctly identify $$|+\rangle$$ state at least 10% of the times.

In each test $$| 0 \rangle$$ and $$|+\rangle$$ states will be provided with 50% probability.

You have to implement an operation which takes a qubit as an input and returns an integer.

Your code should have the following signature:

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

Editorial:
Oracle for f(x) = b * x mod 2
Contest: Microsoft Q# Coding Contest - Summer 2018
Difficulty rating: 1200
Tags: *special

Implement a quantum oracle on N qubits which implements the following function: $$f(\vec{x}) = \vec{b} \cdot \vec{x} \mod 2 = \sum_{k=0}^{N-1} b_k x_k \mod 2$$, where $$\vec{b} \in \{0, 1\}^N$$ (a vector of N integers, each of which can be 0 or 1).

For an explanation on how this type of quantum oracles works, see Introduction to quantum oracles.

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

- an array of N qubits x in arbitrary state (input register), 1 ≤ N ≤ 8,
- a qubit y in arbitrary state (output qubit),
- an array of N integers b, representing the vector $$\overrightarrow{b}$$. Each element of b will be 0 or 1.

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:
Oracle for f(x) = b * x + (1 - b) * (1 - x) mod 2
Contest: Microsoft Q# Coding Contest - Summer 2018
Difficulty rating: 1300
Tags: *special

Implement a quantum oracle on N qubits which implements the following function:

$$f(\vec{x}) = (\vec{b} \cdot \vec{x} + (\vec{1} - \vec{b}) \cdot (\vec{1} - \vec{x})) \mod 2 = \sum_{k=0}^{N-1} (b_k x_k + (1 - b_k) \cdot (1 - x_k)) \mod 2$$

Here $$\vec{b} \in \{0, 1\}^N$$ (a vector of N integers, each of which can be 0 or 1), and $$\overrightarrow{a}$$ is a vector of N 1s.

For an explanation on how this type of quantum oracles works, see Introduction to quantum oracles.

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

- an array of N qubits x in arbitrary state (input register), 1 ≤ N ≤ 8,
- a qubit y in arbitrary state (output qubit),
- an array of N integers b, representing the vector $$\overrightarrow{b}$$. Each element of b will be 0 or 1.

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:
Oracle for majority function
Contest: Microsoft Q# Coding Contest - Summer 2018
Difficulty rating: 1600
Tags: *special

Implement a quantum oracle on 3 qubits which implements a majority function. Majority function on 3-bit vectors is defined as follows: $$f(\vec{x}) = 1$$ if vector $$\overrightarrow{\tau}$$ has two or three 1s, and 0 if it has zero or one 1s.

For an explanation on how this type of quantum oracles works, see Introduction to quantum oracles.

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

- an array of 3 qubits x in arbitrary state (input register),
- a qubit y in arbitrary state (output qubit).

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:
Bernstein-Vazirani algorithm
Contest: Microsoft Q# Coding Contest - Summer 2018
Difficulty rating: 1500
Tags: *special

You are given a quantum oracle - an operation on N + 1 qubits which implements a function $$f: \{0, 1\}^N \to \{0, 1\}$$. You are guaranteed that the function f implemented by the oracle is scalar product function (oracle from problem D1):

$$f(\vec{x}) = \vec{b} \cdot \vec{x} \mod 2 = \sum_{k=0}^{N-1} b_k x_k \mod 2$$

Here $$\vec{b} \in \{0, 1\}^N$$ (an array of N integers, each of which can be 0 or 1).

Your task is to reconstruct the array $$\overrightarrow{b}$$. Your code is allowed to call the given oracle only once.

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

- an integer N - the number of qubits in the oracle input (1 ≤ N ≤ 8),
- an oracle Uf, implemented as an operation with signature ((Qubit[], Qubit) => ()), i.e., an operation which takes as input an array of qubits and an output qubit and has no output.

The return of your operation is an array of integers of length N, each of them 0 or 1.

Your code should have the following signature:

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

Editorial:
Another array reconstruction algorithm
Contest: Microsoft Q# Coding Contest - Summer 2018
Difficulty rating: 1900
Tags: *special

You are given a quantum oracle - an operation on N + 1 qubits which implements a function $$f: \{0, 1\}^N \to \{0, 1\}$$. You are guaranteed that the function f implemented by the oracle can be represented in the following form (oracle from problem D2):

$$f(\vec{x}) = (\vec{b} \cdot \vec{x} + (\vec{1} - \vec{b}) \cdot (\vec{1} - \vec{x})) \mod 2 = \sum_{k=0}^{N-1} (b_k x_k + (1 - b_k) \cdot (1 - x_k)) \mod 2$$

Here $$\vec{b} \in \{0, 1\}^N$$ (a vector of N integers, each of which can be 0 or 1), and $$\overrightarrow{a}$$ is a vector of N 1s.

Your task is to reconstruct the array $$\overrightarrow{b}$$ which could produce the given oracle. Your code is allowed to call the given oracle only once.

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

- an integer N - the number of qubits in the oracle input (1 ≤ N ≤ 8),
- an oracle Uf, implemented as an operation with signature ((Qubit[], Qubit) => ()), i.e., an operation which takes as input an array of qubits and an output qubit and has no output.

The return of your operation is an array of integers of length N, each of them 0 or 1.

Note that in this problem we're comparing the oracle generated by your return to the oracle Uf, instead of comparing your return to the (hidden) value of $$\overrightarrow{b}$$ used to generate Uf. This means that any kind of incorrect return results in "Runtime Error" verdict, as well as actual runtime errors like releasing qubits in non-zero state.

Your code should have the following signature:

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

Editorial:
All the Vowels Please
Contest: Codeforces Round 561 (Div. 2)
Difficulty rating: 1100
Tags: constructive algorithms, math, number theory

Tom loves vowels, and he likes long words with many vowels. His favorite words are vowelly words. We say a word of length $$$k$$$ is vowelly if there are positive integers $$$n$$$ and $$$m$$$ such that $$$n\cdot m = k$$$ and when the word is written by using $$$n$$$ rows and $$$m$$$ columns (the first row is filled first, then the second and so on, with each row filled from left to right), every vowel of the English alphabet appears at least once in every row and every column.

You are given an integer $$$k$$$ and you must either print a vowelly word of length $$$k$$$ or print $$$-1$$$ if no such word exists.

In this problem the vowels of the English alphabet are 'a', 'e', 'i', 'o' ,'u'.

Input format:
Input consists of a single line containing the integer $$$k$$$ ($$$1\leq k \leq 10^4$$$) — the required length.

Output format:
The output must consist of a single line, consisting of a vowelly word of length $$$k$$$ consisting of lowercase English letters if it exists or $$$-1$$$ if it does not.

If there are multiple possible words, you may output any of them.

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

Note:
In the second example, the word "agoeuioaeiruuimaeoieauoweouoiaouimae" can be arranged into the following $$$6 \times 6$$$ grid:

It is easy to verify that every row and every column contain all the vowels.

Example input:
7

Example output:
-1

Example input:
36

Example output:
agoeuioaeiruuimaeoieauoweouoiaouimae

Editorial:
First, which boards could we feasibly fill with characters satisfying that every row and column contains one vowel at least once? Well, if we have a board with less than $$$5$$$ rows, then each column contains less than $$$5$$$ characters, so we cannot have every vowel on each column, and we can't fill the board. Similarly, we can't fill a board with less than $$$5$$$ columns.
Ok, so say now that we have a board with at least $$$5$$$ rows and at least $$$5$$$ columns. Can we fill it? Yes we can! It's enough to fill it by diagonals, as shown in the following picture:
Now we can easily solve the problem. If $$$n \cdot m = k$$$, then $$$n$$$ must divide $$$k$$$ and $$$m = \frac{k}{n}$$$. So we can iterate over all possible $$$n$$$ from $$$5$$$ to $$$k$$$, check whether $$$n$$$ divides $$$k$$$ and in that case, check whether $$$m = \frac{k}{n}$$$ is at least $$$5$$$. If this works for at least one value of $$$n$$$ then we can fill the $$$n \cdot m$$$ board by diagonals as shown before, and obtain our vowelly word by reading the characters row by row. If we don't find any values of $$$n$$$ satisfying this, then no vowelly word exists.
Complexity: $$$\mathcal{O}(k)$$$.
Parliament of Berland
Contest: CROC 2016 - Qualification
Difficulty rating: 1000
Tags: *special, constructive algorithms

There are n parliamentarians in Berland. They are numbered with integers from 1 to n. It happened that all parliamentarians with odd indices are Democrats and all parliamentarians with even indices are Republicans.

New parliament assembly hall is a rectangle consisting of a × b chairs — a rows of b chairs each. Two chairs are considered neighbouring if they share as side. For example, chair number 5 in row number 2 is neighbouring to chairs number 4 and 6 in this row and chairs with number 5 in rows 1 and 3. Thus, chairs have four neighbours in general, except for the chairs on the border of the hall

We know that if two parliamentarians from one political party (that is two Democrats or two Republicans) seat nearby they spent all time discussing internal party issues.

Write the program that given the number of parliamentarians and the sizes of the hall determine if there is a way to find a seat for any parliamentarian, such that no two members of the same party share neighbouring seats.

Input format:
The first line of the input contains three integers n, a and b (1 ≤ n ≤ 10 000, 1 ≤ a, b ≤ 100) — the number of parliamentarians, the number of rows in the assembly hall and the number of seats in each row, respectively.

Output format:
If there is no way to assigns seats to parliamentarians in a proper way print -1.

Otherwise print the solution in a lines, each containing b integers. The j-th integer of the i-th line should be equal to the index of parliamentarian occupying this seat, or 0 if this seat should remain empty. If there are multiple possible solution, you may print any of them.

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

Note:
In the first sample there are many other possible solutions. For example,

and

The following assignment

is incorrect, because parliamentarians 1 and 3 are both from Democrats party but will occupy neighbouring seats.

Example input:
3 2 2

Example output:
0 3
1 2

Example input:
8 4 3

Example output:
7 8 3
0 1 4
6 0 5
0 2 0

Editorial:
Hostname Aliases
Contest: CROC 2016 - Qualification
Difficulty rating: 2100
Tags: *special, binary search, data structures, implementation, sortings, strings

There are some websites that are accessible through several different addresses. For example, for a long time Codeforces was accessible with two hostnames codeforces.com and codeforces.ru.

You are given a list of page addresses being queried. For simplicity we consider all addresses to have the form http://<hostname>[/<path>], where:

- <hostname> — server name (consists of words and maybe some dots separating them),
- /<path> — optional part, where <path> consists of words separated by slashes.

We consider two <hostname> to correspond to one website if for each query to the first <hostname> there will be exactly the same query to the second one and vice versa — for each query to the second <hostname> there will be the same query to the first one. Take a look at the samples for further clarifications.

Your goal is to determine the groups of server names that correspond to one website. Ignore groups consisting of the only server name.

Please note, that according to the above definition queries http://<hostname> and http://<hostname>/ are different.

Input format:
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of page queries. Then follow n lines each containing exactly one address. Each address is of the form http://<hostname>[/<path>], where:

- <hostname> consists of lowercase English letters and dots, there are no two consecutive dots, <hostname> doesn't start or finish with a dot. The length of <hostname> is positive and doesn't exceed 20.
- <path> consists of lowercase English letters, dots and slashes. There are no two consecutive slashes, <path> doesn't start with a slash and its length doesn't exceed 20.

Addresses are not guaranteed to be distinct.

Output format:
First print k — the number of groups of server names that correspond to one website. You should count only groups of size greater than one.

Next k lines should contain the description of groups, one group per line. For each group print all server names separated by a single space. You are allowed to print both groups and names inside any group in arbitrary order.

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

Example input:
10
http://abacaba.ru/test
http://abacaba.ru/
http://abacaba.com
http://abacaba.com/test
http://abacaba.de/
http://abacaba.ru/test
http://abacaba.de/test
http://abacaba.com/
http://abacaba.com/t
http://abacaba.com/test

Example output:
1
http://abacaba.de http://abacaba.ru

Example input:
14
http://c
http://ccc.bbbb/aba..b
http://cba.com
http://a.c/aba..b/a
http://abc/
http://a.c/
http://ccc.bbbb
http://ab.ac.bc.aa/
http://a.a.a/
http://ccc.bbbb/
http://cba.com/
http://cba.com/aba..b
http://a.a.a/aba..b/a
http://abc/aba..b/a

Example output:
2
http://cba.com http://ccc.bbbb
http://a.a.a http://a.c http://abc

Editorial:
Fingerprints
Contest: Codeforces Round 488 by NEAR (Div. 2)
Difficulty rating: 800
Tags: implementation

You are locked in a room with a door that has a keypad with 10 keys corresponding to digits from 0 to 9. To escape from the room, you need to enter a correct code. You also have a sequence of digits.

Some keys on the keypad have fingerprints. You believe the correct code is the longest not necessarily contiguous subsequence of the sequence you have that only contains digits with fingerprints on the corresponding keys. Find such code.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10$$$) representing the number of digits in the sequence you have and the number of keys on the keypad that have fingerprints.

The next line contains $$$n$$$ distinct space-separated integers $$$x_1, x_2, \ldots, x_n$$$ ($$$0 \le x_i \le 9$$$) representing the sequence.

The next line contains $$$m$$$ distinct space-separated integers $$$y_1, y_2, \ldots, y_m$$$ ($$$0 \le y_i \le 9$$$) — the keys with fingerprints.

Output format:
In a single line print a space-separated sequence of integers representing the code. If the resulting sequence is empty, both printing nothing and printing a single line break is acceptable.

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

Note:
In the first example, the only digits with fingerprints are $$$1$$$, $$$2$$$ and $$$7$$$. All three of them appear in the sequence you know, $$$7$$$ first, then $$$1$$$ and then $$$2$$$. Therefore the output is 7 1 2. Note that the order is important, and shall be the same as the order in the original sequence.

In the second example digits $$$0$$$, $$$1$$$, $$$7$$$ and $$$9$$$ have fingerprints, however only $$$0$$$ and $$$1$$$ appear in the original sequence. $$$1$$$ appears earlier, so the output is 1 0. Again, the order is important.

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

Example output:
7 1 2

Example input:
4 4
3 4 1 0
0 1 7 9

Example output:
1 0

Editorial:
The problem can be solved by iterating over every number of the sequence, then iterating over the sequence of fingerprints to check if the number corresponds to a key with a fingerprint, resulting in an $$$O(n \times m)$$$ solution.
Knights of a Polygonal Table
Contest: Codeforces Round 488 by NEAR (Div. 2)
Difficulty rating: 1400
Tags: greedy, implementation, sortings

Unlike Knights of a Round Table, Knights of a Polygonal Table deprived of nobility and happy to kill each other. But each knight has some power and a knight can kill another knight if and only if his power is greater than the power of victim. However, even such a knight will torment his conscience, so he can kill no more than $$$k$$$ other knights. Also, each knight has some number of coins. After a kill, a knight can pick up all victim's coins.

Now each knight ponders: how many coins he can have if only he kills other knights?

You should answer this question for each knight.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ $$$(1 \le n \le 10^5, 0 \le k \le \min(n-1,10))$$$ — the number of knights and the number $$$k$$$ from the statement.

The second line contains $$$n$$$ integers $$$p_1, p_2 ,\ldots,p_n$$$ $$$(1 \le p_i \le 10^9)$$$ — powers of the knights. All $$$p_i$$$ are distinct.

The third line contains $$$n$$$ integers $$$c_1, c_2 ,\ldots,c_n$$$ $$$(0 \le c_i \le 10^9)$$$ — the number of coins each knight has.

Output format:
Print $$$n$$$ integers — the maximum number of coins each knight can have it only he kills other knights.

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

Note:
Consider the first example.

- The first knight is the weakest, so he can't kill anyone. That leaves him with the only coin he initially has.
- The second knight can kill the first knight and add his coin to his own two.
- The third knight is the strongest, but he can't kill more than $$$k = 2$$$ other knights. It is optimal to kill the second and the fourth knights: $$$2+11+33 = 46$$$.
- The fourth knight should kill the first and the second knights: $$$33+1+2 = 36$$$.

In the second example the first knight can't kill anyone, while all the others should kill the one with the index less by one than their own.

In the third example there is only one knight, so he can't kill anyone.

Example input:
4 2
4 5 9 7
1 2 11 33

Example output:
1 3 46 36

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

Example output:
1 3 5 7 9

Editorial:
Sort the knights by increasing the power. Now we can iterate over an array and greedy store set of $$$k$$$ prevous knights with maximum if coins. After handling knight, if set contains less than $$$k$$$ elements, we add current knight in set. Else if number of coins from current knight greater than from knight with minimum coins in set, we can replace this knight with current knight. You can store the set in vector, multiset or priority_queue. Be careful with overflowing and corner case $$$k=0$$$.
Time complexity is $$$O(n \cdot k)$$$ or $$$O(n \cdot \log(k))$$$.