1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Chessboard unitary
Contest: Microsoft Q# Coding Contest - Winter 2019 - Warmup
Difficulty rating: 1600
Tags: *special

Implement a unitary operation on $$$N$$$ qubits which is represented by a square matrix of size $$$2^N$$$ in which zero and non-zero elements form a chessboard pattern with alternating 2x2 squares (top left square formed by non-zero elements).

For example, for $$$N = 3$$$ the matrix of the operation should have the following shape:

Here X denotes a "non-zero" element of the matrix (a complex number which has the square of the absolute value greater than or equal to $$$10^{-5}$$$), and . denotes a "zero" element of the matrix (a complex number which has the square of the absolute value less than $$$10^{-5}$$$).

The row and column indices of the matrix follow little endian format: the least significant bit of the index is stored first in the qubit array. Thus, the first column of the matrix gives you the coefficients of the basis states you'll get if you apply the unitary to the $$$|00..0\rangle$$$ basis state, the second column - to the $$$|10..0\rangle$$$ basis state etc. You can use the DumpUnitary tool to get the coefficients of the matrix your unitary implements (up to relative phases between columns) and the corresponding pattern of Xs and .s.

You have to implement an operation which takes an array of $$$N$$$ ($$$2 \le N \le 5$$$) qubits as an input and applies the unitary transformation with the matrix of the described shape to it. If there are multiple unitaries which satisfy the requirements, you can implement any of them. The "output" of your operation is the pattern of the matrix coefficients implemented by it; you can see the testing harness in the UnitaryPatterns kata.

Your code should have the following signature:

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

Editorial:
Block unitary
Contest: Microsoft Q# Coding Contest - Winter 2019 - Warmup
Difficulty rating: 1700
Tags: *special

Implement a unitary operation on $$$N$$$ qubits which is represented by the following square matrix of size $$$2^N$$$:

- top right and bottom left quarters are filled with zero elements,
- top left quarter is an anti-diagonal matrix of size $$$2^{N-1}$$$,
- bottom right quarter is filled with non-zero elements.

For example, for $$$N = 2$$$ the matrix of the operation should have the following shape:

Here X denotes a "non-zero" element of the matrix (a complex number which has the square of the absolute value greater than or equal to $$$10^{-5}$$$), and . denotes a "zero" element of the matrix (a complex number which has the square of the absolute value less than $$$10^{-5}$$$).

The row and column indices of the matrix follow little endian format: the least significant bit of the index is stored first in the qubit array. Thus, the first column of the matrix gives you the coefficients of the basis states you'll get if you apply the unitary to the $$$|00..0\rangle$$$ basis state, the second column - to the $$$|10..0\rangle$$$ basis state etc. You can use the DumpUnitary tool to get the coefficients of the matrix your unitary implements (up to relative phases between columns) and the corresponding pattern of Xs and .s.

You have to implement an operation which takes an array of $$$N$$$ ($$$2 \le N \le 5$$$) qubits as an input and applies the unitary transformation with the matrix of the described shape to it. If there are multiple unitaries which satisfy the requirements, you can implement any of them. The "output" of your operation is the pattern of the matrix coefficients implemented by it; you can see the testing harness in the UnitaryPatterns kata.

Your code should have the following signature:

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

Editorial:
Voting for Photos
Contest: VK Cup 2016 - Qualification Round 1
Difficulty rating: 1000
Tags: *special, constructive algorithms, implementation

After celebrating the midcourse the students of one of the faculties of the Berland State University decided to conduct a vote for the best photo. They published the photos in the social network and agreed on the rules to choose a winner: the photo which gets most likes wins. If multiple photoes get most likes, the winner is the photo that gets this number first.

Help guys determine the winner photo by the records of likes.

Input format:
The first line of the input contains a single integer n (1 ≤ n ≤ 1000) — the total likes to the published photoes.

The second line contains n positive integers a1, a2, ..., an (1 ≤ ai ≤ 1 000 000), where ai is the identifier of the photo which got the i-th like.

Output format:
Print the identifier of the photo which won the elections.

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

Note:
In the first test sample the photo with id 1 got two likes (first and fifth), photo with id 2 got two likes (third and fourth), and photo with id 3 got one like (second).

Thus, the winner is the photo with identifier 2, as it got:

- more likes than the photo with id 3;
- as many likes as the photo with id 1, but the photo with the identifier 2 got its second like earlier.

Example input:
5
1 3 2 2 1

Example output:
2

Example input:
9
100 200 300 200 100 300 300 100 200

Example output:
300

Editorial:
Chat Order
Contest: VK Cup 2016 - Qualification Round 1
Difficulty rating: 1200
Tags: *special, binary search, constructive algorithms, data structures, sortings

Polycarp is a big lover of killing time in social networks. A page with a chatlist in his favourite network is made so that when a message is sent to some friend, his friend's chat rises to the very top of the page. The relative order of the other chats doesn't change. If there was no chat with this friend before, then a new chat is simply inserted to the top of the list.

Assuming that the chat list is initially empty, given the sequence of Polycaprus' messages make a list of chats after all of his messages are processed. Assume that no friend wrote any message to Polycarpus.

Input format:
The first line contains integer n (1 ≤ n ≤ 200 000) — the number of Polycarpus' messages. Next n lines enlist the message recipients in the order in which the messages were sent. The name of each participant is a non-empty sequence of lowercase English letters of length at most 10.

Output format:
Print all the recipients to who Polycarp talked to in the order of chats with them, from top to bottom.

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

Note:
In the first test case Polycarpus first writes to friend by name "alex", and the list looks as follows:

1. alex

Then Polycarpus writes to friend by name "ivan" and the list looks as follows:

1. ivan
2. alex

Polycarpus writes the third message to friend by name "roman" and the list looks as follows:

1. roman
2. ivan
3. alex

Polycarpus writes the fourth message to friend by name "ivan", to who he has already sent a message, so the list of chats changes as follows:

1. ivan
2. roman
3. alex

Example input:
4
alex
ivan
roman
ivan

Example output:
ivan
roman
alex

Example input:
8
alina
maria
ekaterina
darya
darya
ekaterina
maria
alina

Example output:
alina
maria
ekaterina
darya

Editorial:
Promocodes with Mistakes
Contest: VK Cup 2016 - Qualification Round 1
Difficulty rating: 1400
Tags: *special, brute force, constructive algorithms, implementation

During a New Year special offer the "Sudislavl Bars" offered n promo codes. Each promo code consists of exactly six digits and gives right to one free cocktail at the bar "Mosquito Shelter". Of course, all the promocodes differ.

As the "Mosquito Shelter" opens only at 9, and partying in Sudislavl usually begins at as early as 6, many problems may arise as to how to type a promotional code without errors. It is necessary to calculate such maximum k, that the promotional code could be uniquely identified if it was typed with no more than k errors. At that, k = 0 means that the promotional codes must be entered exactly.

A mistake in this problem should be considered as entering the wrong numbers. For example, value "123465" contains two errors relative to promocode "123456". Regardless of the number of errors the entered value consists of exactly six digits.

Input format:
The first line of the output contains number n (1 ≤ n ≤ 1000) — the number of promocodes.

Each of the next n lines contains a single promocode, consisting of exactly 6 digits. It is guaranteed that all the promocodes are distinct. Promocodes can start from digit "0".

Output format:
Print the maximum k (naturally, not exceeding the length of the promocode), such that any promocode can be uniquely identified if it is typed with at most k mistakes.

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

Note:
In the first sample k < 3, so if a bar customer types in value "090909", then it will be impossible to define which promocode exactly corresponds to it.

Example input:
2
000000
999999

Example output:
2

Example input:
6
211111
212111
222111
111111
112111
121111

Example output:
0

Editorial:
Running with Obstacles
Contest: VK Cup 2016 - Qualification Round 1
Difficulty rating: 1600
Tags: *special, data structures, dp, greedy

A sportsman starts from point xstart = 0 and runs to point with coordinate xfinish = m (on a straight line). Also, the sportsman can jump — to jump, he should first take a run of length of not less than s meters (in this case for these s meters his path should have no obstacles), and after that he can jump over a length of not more than d meters. Running and jumping is permitted only in the direction from left to right. He can start andfinish a jump only at the points with integer coordinates in which there are no obstacles. To overcome some obstacle, it is necessary to land at a point which is strictly to the right of this obstacle.

On the way of an athlete are n obstacles at coordinates x1, x2, ..., xn. He cannot go over the obstacles, he can only jump over them. Your task is to determine whether the athlete will be able to get to the finish point.

Input format:
The first line of the input containsd four integers n, m, s and d (1 ≤ n ≤ 200 000, 2 ≤ m ≤ 109, 1 ≤ s, d ≤ 109) — the number of obstacles on the runner's way, the coordinate of the finishing point, the length of running before the jump and the maximum length of the jump, correspondingly.

The second line contains a sequence of n integers a1, a2, ..., an (1 ≤ ai ≤ m - 1) — the coordinates of the obstacles. It is guaranteed that the starting and finishing point have no obstacles, also no point can have more than one obstacle, The coordinates of the obstacles are given in an arbitrary order.

Output format:
If the runner cannot reach the finishing point, print in the first line of the output "IMPOSSIBLE" (without the quotes).

If the athlete can get from start to finish, print any way to do this in the following format:

- print a line of form "RUN X>" (where "X" should be a positive integer), if the athlete should run for "X" more meters;
- print a line of form "JUMP Y" (where "Y" should be a positive integer), if the sportsman starts a jump and should remain in air for "Y" more meters.

All commands "RUN" and "JUMP" should strictly alternate, starting with "RUN", besides, they should be printed chronologically. It is not allowed to jump over the finishing point but it is allowed to land there after a jump. The athlete should stop as soon as he reaches finish.

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

Example input:
3 10 1 3
3 4 7

Example output:
RUN 2
JUMP 3
RUN 1
JUMP 2
RUN 2

Example input:
2 9 2 3
6 4

Example output:
IMPOSSIBLE

Editorial:
Automatic Door
Contest: 2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)
Difficulty rating: 2200
Tags: implementation

There is an automatic door at the entrance of a factory. The door works in the following way:

- when one or several people come to the door and it is closed, the door immediately opens automatically and all people immediately come inside,
- when one or several people come to the door and it is open, all people immediately come inside,
- opened door immediately closes in d seconds after its opening,
- if the door is closing and one or several people are coming to the door at the same moment, then all of them will have enough time to enter and only after that the door will close.

For example, if d = 3 and four people are coming at four different moments of time t1 = 4, t2 = 7, t3 = 9 and t4 = 13 then the door will open three times: at moments 4, 9 and 13. It will close at moments 7 and 12.

It is known that n employees will enter at moments a, 2·a, 3·a, ..., n·a (the value a is positive integer). Also m clients will enter at moments t1, t2, ..., tm.

Write program to find the number of times the automatic door will open. Assume that the door is initially closed.

Input format:
The first line contains four integers n, m, a and d (1 ≤ n, a ≤ 109, 1 ≤ m ≤ 105, 1 ≤ d ≤ 1018) — the number of the employees, the number of the clients, the moment of time when the first employee will come and the period of time in which the door closes.

The second line contains integer sequence t1, t2, ..., tm (1 ≤ ti ≤ 1018) — moments of time when clients will come. The values ti are given in non-decreasing order.

Output format:
Print the number of times the door will open.

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

Note:
In the first example the only employee will come at moment 3. At this moment the door will open and will stay open until the moment 7. At the same moment of time the client will come, so at first he will enter and only after it the door will close. Thus the door will open one time.

Example input:
1 1 3 4
7

Example output:
1

Example input:
4 3 4 2
7 9 11

Example output:
4

Editorial:
Berland Army
Contest: 2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)
Difficulty rating: 2600
Tags: constructive algorithms, graphs, greedy

There are n military men in the Berland army. Some of them have given orders to other military men by now. Given m pairs (xi, yi), meaning that the military man xi gave the i-th order to another military man yi.

It is time for reform! The Berland Ministry of Defence plans to introduce ranks in the Berland army. Each military man should be assigned a rank — integer number between 1 and k, inclusive. Some of them have been already assigned a rank, but the rest of them should get a rank soon.

Help the ministry to assign ranks to the rest of the army so that:

- for each of m orders it is true that the rank of a person giving the order (military man xi) is strictly greater than the rank of a person receiving the order (military man yi);
- for each rank from 1 to k there is at least one military man with this rank.

Input format:
The first line contains three integers n, m and k (1 ≤ n ≤ 2·105, 0 ≤ m ≤ 2·105, 1 ≤ k ≤ 2·105) — number of military men in the Berland army, number of orders and number of ranks.

The second line contains n integers r1, r2, ..., rn, where ri > 0 (in this case 1 ≤ ri ≤ k) means that the i-th military man has been already assigned the rank ri; ri = 0 means the i-th military man doesn't have a rank yet.

The following m lines contain orders one per line. Each order is described with a line containing two integers xi, yi (1 ≤ xi, yi ≤ n, xi ≠ yi). This line means that the i-th order was given by the military man xi to the military man yi. For each pair (x, y) of military men there could be several orders from x to y.

Output format:
Print n integers, where the i-th number is the rank of the i-th military man. If there are many solutions, print any of them.

If there is no solution, print the only number -1.

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

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

Example output:
1 3 3 2 2

Example input:
7 6 5
0 4 5 4 1 0 0
6 1
3 6
3 1
7 5
7 1
7 4

Example output:
2 4 5 4 1 3 5

Editorial:
Lost in Transliteration
Contest: 2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)
Difficulty rating: 1300
Tags: implementation

There are some ambiguities when one writes Berland names with the letters of the Latin alphabet.

For example, the Berland sound u can be written in the Latin alphabet as "u", and can be written as "oo". For this reason, two words "ulyana" and "oolyana" denote the same name.

The second ambiguity is about the Berland sound h: one can use both "h" and "kh" to write it. For example, the words "mihail" and "mikhail" denote the same name.

There are n users registered on the Polycarp's website. Each of them indicated a name represented by the Latin letters. How many distinct names are there among them, if two ambiguities described above are taken into account?

Formally, we assume that two words denote the same name, if using the replacements "u" $$\text{The formula used to produce the text is not provided in the image.}$$ "oo" and "h" $$\text{The formula used to produce the text is not provided in the image.}$$ "kh", you can make the words equal. One can make replacements in both directions, in any of the two words an arbitrary number of times. A letter that resulted from the previous replacement can participate in the next replacements.

For example, the following pairs of words denote the same name:

- "koouper" and "kuooper". Making the replacements described above, you can make both words to be equal: "koouper" $$\rightarrow$$ "kuuper" and "kuooper" $$\rightarrow$$ "kuuper".
- "khun" and "kkkhoon". With the replacements described above you can make both words to be equal: "khun" $$\rightarrow$$ "khoon" and "kkkhoon" $$\rightarrow$$ "kkhoon" $$\rightarrow$$ "khoon".

For a given list of words, find the minimal number of groups where the words in each group denote the same name.

Input format:
The first line contains integer number n (2 ≤ n ≤ 400) — number of the words in the list.

The following n lines contain words, one word per line. Each word consists of only lowercase Latin letters. The length of each word is between 1 and 20 letters inclusive.

Output format:
Print the minimal number of groups where the words in each group denote the same name.

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

Note:
There are four groups of words in the first example. Words in each group denote same name:

1. "mihail", "mikhail"
2. "oolyana", "ulyana"
3. "kooooper", "koouper"
4. "hoon", "khun", "kkkhoon"

There are five groups of words in the second example. Words in each group denote same name:

1. "hariton", "kkkhariton", "khariton"
2. "hkariton"
3. "buoi", "boooi", "boui"
4. "bui"
5. "boi"

In the third example the words are equal, so they denote the same name.

Example input:
10
mihail
oolyana
kooooper
hoon
ulyana
koouper
mikhail
khun
kuooper
kkkhoon

Example output:
4

Example input:
9
hariton
hkariton
buoi
kkkhariton
boooi
bui
khariton
boui
boi

Example output:
5

Editorial:
Orientation of Edges
Contest: 2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)
Difficulty rating: 1900
Tags: dfs and similar, graphs

Vasya has a graph containing both directed (oriented) and undirected (non-oriented) edges. There can be multiple edges between a pair of vertices.

Vasya has picked a vertex s from the graph. Now Vasya wants to create two separate plans:

1. to orient each undirected edge in one of two possible directions to maximize number of vertices reachable from vertex s;
2. to orient each undirected edge in one of two possible directions to minimize number of vertices reachable from vertex s.

In each of two plans each undirected edge must become directed. For an edge chosen directions can differ in two plans.

Help Vasya find the plans.

Input format:
The first line contains three integers n, m and s (2 ≤ n ≤ 3·105, 1 ≤ m ≤ 3·105, 1 ≤ s ≤ n) — number of vertices and edges in the graph, and the vertex Vasya has picked.

The following m lines contain information about the graph edges. Each line contains three integers ti, ui and vi (1 ≤ ti ≤ 2, 1 ≤ ui, vi ≤ n, ui ≠ vi) — edge type and vertices connected by the edge. If ti = 1 then the edge is directed and goes from the vertex ui to the vertex vi. If ti = 2 then the edge is undirected and it connects the vertices ui and vi.

It is guaranteed that there is at least one undirected edge in the graph.

Output format:
The first two lines should describe the plan which maximizes the number of reachable vertices. The lines three and four should describe the plan which minimizes the number of reachable vertices.

A description of each plan should start with a line containing the number of reachable vertices. The second line of a plan should consist of f symbols '+' and '-', where f is the number of undirected edges in the initial graph. Print '+' as the j-th symbol of the string if the j-th undirected edge (u, v) from the input should be oriented from u to v. Print '-' to signify the opposite direction (from v to u). Consider undirected edges to be numbered in the same order they are given in the input.

If there are multiple solutions, print any of them.

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

Example input:
2 2 1
1 1 2
2 2 1

Example output:
2
-
2
+

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

Example output:
6
++-
2
+-+

Editorial:
Palindromic Cut
Contest: 2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)
Difficulty rating: 1800
Tags: brute force, implementation, strings

Kolya has a string s of length n consisting of lowercase and uppercase Latin letters and digits.

He wants to rearrange the symbols in s and cut it into the minimum number of parts so that each part is a palindrome and all parts have the same lengths. A palindrome is a string which reads the same backward as forward, such as madam or racecar.

Your task is to help Kolya and determine the minimum number of palindromes of equal lengths to cut s into, if it is allowed to rearrange letters in s before cuttings.

Input format:
The first line contains an integer n (1 ≤ n ≤ 4·105) — the length of string s.

The second line contains a string s of length n consisting of lowercase and uppercase Latin letters and digits.

Output format:
Print to the first line an integer k — minimum number of palindromes into which you can cut a given string.

Print to the second line k strings — the palindromes themselves. Separate them by a space. You are allowed to print palindromes in arbitrary order. All of them should have the same length.

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

Example input:
6
aabaac

Example output:
2
aba aca

Example input:
8
0rTrT022

Example output:
1
02TrrT20

Editorial: