1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Quantum Classification - 2
Contest: Microsoft Q# Coding Contest - Summer 2020 - Warmup
Tags: *special

This problem statement is exactly the same as in the problem "Quantum Classification - 1"; the only difference is the training dataset used (and the model you need to train on it).

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:
Lucky Year
Contest: Educational Codeforces Round 21
Difficulty rating: 900
Tags: implementation

Apart from having lots of holidays throughout the year, residents of Berland also have whole lucky years. Year is considered lucky if it has no more than 1 non-zero digit in its number. So years 100, 40000, 5 are lucky and 12, 3001 and 12345 are not.

You are given current year in Berland. Your task is to find how long will residents of Berland wait till the next lucky year.

Input format:
The first line contains integer number n (1 ≤ n ≤ 109) — current year in Berland.

Output format:
Output amount of years from the current year to the next lucky one.

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

Note:
In the first example next lucky year is 5. In the second one — 300. In the third — 5000.

Example input:
4

Example output:
1

Example input:
201

Example output:
99

Editorial:
Notice that the next lucky year always looks like (first digit of the current + 1) · 10^(number of digits of the current - 1). It holds also for numbers starting with 9, it will be 10 · 10^(number of digits - 1). The answer is the difference between the next lucky year and current year.
Average Sleep Time
Contest: Educational Codeforces Round 21
Difficulty rating: 1300
Tags: data structures, implementation, math

It's been almost a week since Polycarp couldn't get rid of insomnia. And as you may already know, one week in Berland lasts k days!

When Polycarp went to a doctor with his problem, the doctor asked him about his sleeping schedule (more specifically, the average amount of hours of sleep per week). Luckily, Polycarp kept records of sleep times for the last n days. So now he has a sequence a1, a2, ..., an, where ai is the sleep time on the i-th day.

The number of records is so large that Polycarp is unable to calculate the average value by himself. Thus he is asking you to help him with the calculations. To get the average Polycarp is going to consider k consecutive days as a week. So there will be n - k + 1 weeks to take into consideration. For example, if k = 2, n = 3 and a = [3, 4, 7], then the result is $$( 3 + 4 ) + ( 4 + 7 ) \over 2 = 9$$.

You should write a program which will calculate average sleep times of Polycarp over all weeks.

Input format:
The first line contains two integer numbers n and k (1 ≤ k ≤ n ≤ 2·105).

The second line contains n integer numbers a1, a2, ..., an (1 ≤ ai ≤ 105).

Output format:
Output average sleeping time over all weeks.

The answer is considered to be correct if its absolute or relative error does not exceed 10 - 6. In particular, it is enough to output real number with at least 6 digits after the decimal point.

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

Note:
In the third example there are n - k + 1 = 7 weeks, so the answer is sums of all weeks divided by 7.

Example input:
3 2
3 4 7

Example output:
9.0000000000

Example input:
1 1
10

Example output:
10.0000000000

Editorial:
To get the sum for i-th week you need to take sum of (i - 1)-th week, subtract first element of (i - 1)-th week from it and add up last element of i-th week. All common elements will remain.
Thus by moving right week by week calculate sum of all weeks and divide it by n - k + 1.
Overall complexity: O(n).
Tea Party
Contest: Educational Codeforces Round 21
Difficulty rating: 1400
Tags: constructive algorithms, greedy, sortings

Polycarp invited all his friends to the tea party to celebrate the holiday. He has n cups, one for each of his n friends, with volumes a1, a2, ..., an. His teapot stores w milliliters of tea (w ≤ a1 + a2 + ... + an). Polycarp wants to pour tea in cups in such a way that:

- Every cup will contain tea for at least half of its volume
- Every cup will contain integer number of milliliters of tea
- All the tea from the teapot will be poured into cups
- All friends will be satisfied.

Friend with cup i won't be satisfied, if there exists such cup j that cup i contains less tea than cup j but ai > aj.

For each cup output how many milliliters of tea should be poured in it. If it's impossible to pour all the tea and satisfy all conditions then output -1.

Input format:
The first line contains two integer numbers n and w (1 ≤ n ≤ 100, $$1 \leq w \leq \sum_{i=1}^{n} a_i$$).

The second line contains n numbers a1, a2, ..., an (1 ≤ ai ≤ 100).

Output format:
Output how many milliliters of tea every cup should contain. If there are multiple answers, print any of them.

If it's impossible to pour all the tea and satisfy all conditions then output -1.

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

Note:
In the third example you should pour to the first cup at least 5 milliliters, to the second one at least 4, to the third one at least 5. It sums up to 14, which is greater than 10 milliliters available.

Example input:
2 10
8 7

Example output:
6 4

Example input:
4 4
1 1 1 1

Example output:
1 1 1 1

Editorial:
At first, let's pour minimal amount of tea in each cup, that is $$\prod \frac{a_i}{2}$$. If it requires more tea than available then it's -1.
Now let's sort cups in non-increasing order by volume and start filling up them until we run out of tea in the teapot.
It's easy to see that everyone will be satisfied that way. If sequence of ai is non-increasing then sequence of $$\prod \frac{a_i}{2}$$ is also non-increasing. So we can't make someone unsatisfied by filling the cup with maximal possible volume.
And finally get the right order of cups back and print the answer.
Overall complexity: $$O(n \log n)$$.
Array Division
Contest: Educational Codeforces Round 21
Difficulty rating: 1900
Tags: binary search, data structures, implementation

Vasya has an array a consisting of positive integer numbers. Vasya wants to divide this array into two non-empty consecutive parts (the prefix and the suffix) so that the sum of all elements in the first part equals to the sum of elements in the second part. It is not always possible, so Vasya will move some element before dividing the array (Vasya will erase some element and insert it into an arbitrary position).

Inserting an element in the same position he was erased from is also considered moving.

Can Vasya divide the array after choosing the right element to move and its new position?

Input format:
The first line contains single integer n (1 ≤ n ≤ 100000) — the size of the array.

The second line contains n integers a1, a2... an (1 ≤ ai ≤ 109) — the elements of the array.

Output format:
Print YES if Vasya can divide the array after moving one element. Otherwise print NO.

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

Note:
In the first example Vasya can move the second element to the end of the array.

In the second example no move can make the division possible.

In the third example Vasya can move the fourth element by one position to the left.

Example input:
3
1 3 2

Example output:
YES

Example input:
5
1 2 3 4 5

Example output:
NO

Editorial:
Suppose we want to move an element from the prefix to the suffix (if we need to move an element from the suffix to the prefix, we can just reverse the array and do the same thing).
Suppose the resulting prefix will contain m elements. Then we need to check that the prefix with m + 1 elements contains an element such that the sum of this prefix without this element is equal to the half of the sum of the whole array (and then we can move this element to the suffix).
To check all the prefixes, we can scan the array from left to right while maintaining the set of elements on the prefix and the sum of these elements.
Selling Souvenirs
Contest: Educational Codeforces Round 21
Difficulty rating: 2300
Tags: binary search, dp, greedy, ternary search

After several latest reforms many tourists are planning to visit Berland, and Berland people understood that it's an opportunity to earn money and changed their jobs to attract tourists. Petya, for example, left the IT corporation he had been working for and started to sell souvenirs at the market.

This morning, as usual, Petya will come to the market. Petya has n different souvenirs to sell; ith souvenir is characterised by its weight wi and cost ci. Petya knows that he might not be able to carry all the souvenirs to the market. So Petya wants to choose a subset of souvenirs such that its total weight is not greater than m, and total cost is maximum possible.

Help Petya to determine maximum possible total cost.

Input format:
The first line contains two integers n and m (1 ≤ n ≤ 100000, 1 ≤ m ≤ 300000) — the number of Petya's souvenirs and total weight that he can carry to the market.

Then n lines follow. ith line contains two integers wi and ci (1 ≤ wi ≤ 3, 1 ≤ ci ≤ 109) — the weight and the cost of ith souvenir.

Output format:
Print one number — maximum possible total cost of souvenirs that Petya can carry to the market.

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

Example input:
1 1
2 1

Example output:
0

Example input:
2 2
1 3
2 2

Example output:
3

Editorial:
There are lots of different solutions for this problem.
We can iterate on the number of 3-elements we will take (in this editorial k-element is a souvenir with weight k). When fixing the number of 3-elements (let it be x), we want to know the best possible answer for the weight m - 3x, while taking into account only 1-elements and 2-elements.
To answer these queries, we can precalculate the values dp[w] — triples (cost, cnt1, cnt2), where cost is the best possible answer for the weight w, and cnt1 and cnt2 is the number of 1-elements and 2-elements we are taking to get this answer. Of course, dp[0] = (0, 0, 0), and we can update dp[i + 1] and dp[i + 2] using value of dp[i]. After precalculating dp[w] for each possible w we can iterate on the number of 3-elements.
There are also several binary/ternary search solutions.
Card Game
Contest: Educational Codeforces Round 21
Difficulty rating: 2400
Tags: binary search, flows, graphs

Digital collectible card games have become very popular recently. So Vova decided to try one of these.

Vova has n cards in his collection. Each of these cards is characterised by its power pi, magic number ci and level li. Vova wants to build a deck with total power not less than k, but magic numbers may not allow him to do so — Vova can't place two cards in a deck if the sum of the magic numbers written on these cards is a prime number. Also Vova cannot use a card if its level is greater than the level of Vova's character.

At the moment Vova's character's level is 1. Help Vova to determine the minimum level he needs to reach in order to build a deck with the required total power.

Input format:
The first line contains two integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 100000).

Then n lines follow, each of these lines contains three numbers that represent the corresponding card: pi, ci and li (1 ≤ pi ≤ 1000, 1 ≤ ci ≤ 100000, 1 ≤ li ≤ n).

Output format:
If Vova won't be able to build a deck with required power, print  - 1. Otherwise print the minimum level Vova has to reach in order to build a deck.

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

Example input:
5 8
5 5 1
1 5 4
4 6 3
1 12 4
3 12 1

Example output:
4

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

Example output:
2

Editorial:
The most tricky part of the problem is how to check if some set of cards allows us to build a deck with the required power (not taking the levels of cards into account).
Suppose we have not more than one card with magic number 1 (if there are multiple cards with this magic number, then we obviously can use only one of these). Then two cards may conflict only if one of them has an odd magic number, and another has an even magic number — otherwise their sum is even and not less than 4, so it's not a prime number.
This allows us to solve this problem as follows:
Construct a bipartite graph: each vertex represents a card, and two vertices are connected by an edge if the corresponding pair of cards can't be put in a deck. Then we have to find the maximum weight of independent set in this graph. This can be solved using maximum flow algorithm: construct a network where source is connected with every "odd" vertex (a vertex that represents a card with an odd magic number) by an edge with capacity equal to the power of this card; then connect every "odd" vertex to all "even" vertices that are conflicting with this vertex by edges with infinite capacities; and then connect every "even" vertex to the sink by an edge with capacity equal to the power of the card (all edges have to be directed). Then the maximum power of the deck is equal to sum - mincut, where sum is the sum of all powers and mincut is the minimum cut value between the source and the sink (which is equal to the maximum flow).
This allows us to check if we can build a deck of required power using only some set of cards (for example, only cards with level less than or equal to some x).
Anthem of Berland
Contest: Educational Codeforces Round 21
Difficulty rating: 2300
Tags: dp, strings

Berland has a long and glorious history. To increase awareness about it among younger citizens, King of Berland decided to compose an anthem.

Though there are lots and lots of victories in history of Berland, there is the one that stand out the most. King wants to mention it in the anthem as many times as possible.

He has already composed major part of the anthem and now just needs to fill in some letters. King asked you to help him with this work.

The anthem is the string s of no more than 105 small Latin letters and question marks. The most glorious victory is the string t of no more than 105 small Latin letters. You should replace all the question marks with small Latin letters in such a way that the number of occurrences of string t in string s is maximal.

Note that the occurrences of string t in s can overlap. Check the third example for clarification.

Input format:
The first line contains string of small Latin letters and question marks s (1 ≤ |s| ≤ 105).

The second line contains string of small Latin letters t (1 ≤ |t| ≤ 105).

Product of lengths of strings |s|·|t| won't exceed 107.

Output format:
Output the maximum number of occurrences of string t you can achieve by replacing all the question marks in string s with small Latin letters.

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

Note:
In the first example the resulting string s is "winlosewinwinlwinwin"

In the second example the resulting string s is "glorytoreorand". The last letter of the string can be arbitrary.

In the third example occurrences of string t are overlapping. String s with maximal number of occurrences of t is "abcabcab".

Example input:
winlose???winl???w??
win

Example output:
5

Example input:
glo?yto?e??an?
or

Example output:
3

Editorial:
Let's denote the string obtained by concatenation t + # + s (where # is some dividing character that isn't a part of the alphabet) as ts. Recall that KMP algorithm builds the prefix function for this string.
We can calculate dp[i][j] on this string, where i is the position in this string and j is the value of prefix function in this position. The value of dp[i][j] is the maximum number of occurences of t found so far (or  - 1 if this situation is impossible). If (i + 1)th character is a Latin letter, then we just recalculate prefix function for this position (the fact that in KMP the value of prefix function won't exceed |t| allows us to do so). If (i + 1)th character is a question mark, then we check all 26 possible characters and recalculate prefix function for all of these characters (and update the corresponding dp values). The size of s and t is pretty big, so we need to recalculate these values in O(1) time; this can be done by precalculating the values of next[i][j] (i is the value of prefix function, j is a new character and next[i][j] is the value of prefix function after adding this character).
Fox And Snake
Contest: Codeforces Round 290 (Div. 2)
Difficulty rating: 800
Tags: implementation

Fox Ciel starts to learn programming. The first task is drawing a fox! However, that turns out to be too hard for a beginner, so she decides to draw a snake instead.

A snake is a pattern on a n by m table. Denote c-th cell of r-th row as (r, c). The tail of the snake is located at (1, 1), then it's body extends to (1, m), then goes down 2 rows to (3, m), then goes left to (3, 1) and so on.

Your task is to draw this snake for Fox Ciel: the empty cells should be represented as dot characters ('.') and the snake cells should be filled with number signs ('#').

Consider sample tests in order to understand the snake pattern.

Input format:
The only line contains two integers: n and m (3 ≤ n, m ≤ 50).

n is an odd number.

Output format:
Output n lines. Each line should contain a string consisting of m characters. Do not output spaces.

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

Example input:
3 3

Example output:
###
..#
###

Example input:
3 4

Example output:
####
...#
####

Editorial:
Fox And Two Dots
Contest: Codeforces Round 290 (Div. 2)
Difficulty rating: 1500
Tags: dfs and similar

Fox Ciel is playing a mobile puzzle game called "Two Dots". The basic levels are played on a board of size n × m cells, like this:

Each cell contains a dot that has some color. We will use different uppercase Latin characters to express different colors.

The key of this game is to find a cycle that contain dots of same color. Consider 4 blue dots on the picture forming a circle as an example. Formally, we call a sequence of dots d1, d2, ..., dk a cycle if and only if it meets the following condition:

1. These k dots are different: if i ≠ j then di is different from dj.
2. k is at least 4.
3. All dots belong to the same color.
4. For all 1 ≤ i ≤ k - 1: di and di + 1 are adjacent. Also, dk and d1 should also be adjacent. Cells x and y are called adjacent if they share an edge.

Determine if there exists a cycle on the field.

Input format:
The first line contains two integers n and m (2 ≤ n, m ≤ 50): the number of rows and columns of the board.

Then n lines follow, each line contains a string consisting of m characters, expressing colors of dots in each line. Each character is an uppercase Latin letter.

Output format:
Output "Yes" if there exists a cycle, and "No" otherwise.

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

Note:
In first sample test all 'A' form a cycle.

In second sample there is no such cycle.

The third sample is displayed on the picture above ('Y' = Yellow, 'B' = Blue, 'R' = Red).

Example input:
3 4
AAAA
ABCA
AAAA

Example output:
Yes

Example input:
3 4
AAAA
ABCA
AADA

Example output:
No

Editorial:
Fox And Names
Contest: Codeforces Round 290 (Div. 2)
Difficulty rating: 1600
Tags: dfs and similar, graphs, sortings

Fox Ciel is going to publish a paper on FOCS (Foxes Operated Computer Systems, pronounce: "Fox"). She heard a rumor: the authors list on the paper is always sorted in the lexicographical order.

After checking some examples, she found out that sometimes it wasn't true. On some papers authors' names weren't sorted in lexicographical order in normal sense. But it was always true that after some modification of the order of letters in alphabet, the order of authors becomes lexicographical!

She wants to know, if there exists an order of letters in Latin alphabet such that the names on the paper she is submitting are following in the lexicographical order. If so, you should find out any such order.

Lexicographical order is defined in following way. When we compare s and t, first we find the leftmost position with differing characters: si ≠ ti. If there is no such position (i. e. s is a prefix of t or vice versa) the shortest string is less. Otherwise, we compare characters si and ti according to their order in alphabet.

Input format:
The first line contains an integer n (1 ≤ n ≤ 100): number of names.

Each of the following n lines contain one string namei (1 ≤ |namei| ≤ 100), the i-th name. Each name contains only lowercase Latin letters. All names are different.

Output format:
If there exists such order of letters that the given names are sorted lexicographically, output any such order as a permutation of characters 'a'–'z' (i. e. first output the first letter of the modified alphabet, then the second, and so on).

Otherwise output a single word "Impossible" (without quotes).

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

Example input:
3
rivest
shamir
adleman

Example output:
bcdefghijklmnopqrsatuvwxyz

Example input:
10
tourist
petr
wjmzbmr
yeputons
vepifanov
scottwu
oooooooooooooooo
subscriber
rowdark
tankengineer

Example output:
Impossible

Editorial: