1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Binary Inversions
Contest: Codeforces Round 835 (Div. 4)
Difficulty rating: 1100
Tags: data structures, greedy, math

You are given a binary array$$$^{\dagger}$$$ of length $$$n$$$. You are allowed to perform one operation on it at most once. In an operation, you can choose any element and flip it: turn a $$$0$$$ into a $$$1$$$ or vice-versa.

What is the maximum number of inversions$$$^{\ddagger}$$$ the array can have after performing at most one operation?

$$$^\dagger$$$ A binary array is an array that contains only zeroes and ones.

$$$^\ddagger$$$ The number of inversions in an array is the number of pairs of indices $$$i,j$$$ such that $$$i<j$$$ and $$$a_i > a_j$$$.

Input format:
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — the length of the array.

The following line contains $$$n$$$ space-separated positive integers $$$a_1$$$, $$$a_2$$$,..., $$$a_n$$$ ($$$0 \leq a_i \leq 1$$$) — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output format:
For each test case, output a single integer  — the maximum number of inversions the array can have after performing at most one operation.

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

Note:
For the first test case, the inversions are initially formed by the pairs of indices ($$$1, 2$$$), ($$$1, 4$$$), ($$$3, 4$$$), being a total of $$$3$$$, which already is the maximum possible.

For the second test case, the inversions are initially formed by the pairs of indices ($$$2, 3$$$), ($$$2, 4$$$), ($$$2, 6$$$), ($$$5, 6$$$), being a total of four. But, by flipping the first element, the array becomes $$${1, 1, 0, 0, 1, 0}$$$, which has the inversions formed by the pairs of indices ($$$1, 3$$$), ($$$1, 4$$$), ($$$1, 6$$$), ($$$2, 3$$$), ($$$2, 4$$$), ($$$2, 6$$$), ($$$5, 6$$$) which total to $$$7$$$ inversions which is the maximum possible.

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

Example output:
3
7
1
13
2

Editorial:
Let's find out how to count the number of binary inversions, without flips. This is the number of $$$1$$$s that appear before a $$$0$$$. To do this, iterate through the array and keep a running total $$$k$$$ of the number of $$$1$$$s seen so far. When we see a $$$0$$$, increase the total inversion count by $$$k$$$, since this $$$0$$$ makes $$$k$$$ inversions: one for each of the $$$1$$$s before it.
Now let's see how to maximize the inversions. Consider the flip $$$0 \to 1$$$. We claim that it is best to always flip the earliest $$$0$$$ in the array. It's never optimal to flip a later $$$0$$$, since we have strictly fewer $$$0$$$s after it to form inversions. Similarly, we should flip the latest $$$1$$$ in the array.
Now recalculate the answer for these two choices for flipping, and pick the maximum. The complexity is $$$\mathcal{O}(n)$$$.
Arena
Contest: Educational Codeforces Round 104 (Rated for Div. 2)
Difficulty rating: 800
Tags: implementation, sortings

$$$n$$$ heroes fight against each other in the Arena. Initially, the $$$i$$$-th hero has level $$$a_i$$$.

Each minute, a fight between two different heroes occurs. These heroes can be chosen arbitrarily (it's even possible that it is the same two heroes that were fighting during the last minute).

When two heroes of equal levels fight, nobody wins the fight. When two heroes of different levels fight, the one with the higher level wins, and his level increases by $$$1$$$.

The winner of the tournament is the first hero that wins in at least $$$100^{500}$$$ fights (note that it's possible that the tournament lasts forever if no hero wins this number of fights, then there is no winner). A possible winner is a hero such that there exists a sequence of fights that this hero becomes the winner of the tournament.

Calculate the number of possible winners among $$$n$$$ heroes.

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

Each test case consists of two lines. The first line contains one integer $$$n$$$ ($$$2 \le n \le 100$$$) — the number of heroes. The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$), where $$$a_i$$$ is the initial level of the $$$i$$$-th hero.

Output format:
For each test case, print one integer — the number of possible winners among the given $$$n$$$ heroes.

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

Note:
In the first test case of the example, the only possible winner is the first hero.

In the second test case of the example, each fight between the heroes results in nobody winning it, so the tournament lasts forever and there is no winner.

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

Example output:
1
0
3

Editorial:
If for some hero $$$i$$$, no other hero is weaker than $$$i$$$, then the $$$i$$$-th hero cannot win any fights and is not a possible winner. Otherwise, the hero $$$i$$$ is a possible winner — he may fight the weakest hero $$$100^{500}$$$ times and be declared the winner.
So the solution to the problem is calculating the number of minimum elements in the array $$$a$$$, since all other elements denote possible winners of the tournament.
Pythagorean Triples
Contest: Educational Codeforces Round 104 (Rated for Div. 2)
Difficulty rating: 1500
Tags: binary search, brute force, math, number theory

A Pythagorean triple is a triple of integer numbers $$$(a, b, c)$$$ such that it is possible to form a right triangle with the lengths of the first cathetus, the second cathetus and the hypotenuse equal to $$$a$$$, $$$b$$$ and $$$c$$$, respectively. An example of the Pythagorean triple is $$$(3, 4, 5)$$$.

Vasya studies the properties of right triangles, and he uses a formula that determines if some triple of integers is Pythagorean. Unfortunately, he has forgotten the exact formula; he remembers only that the formula was some equation with squares. So, he came up with the following formula: $$$c = a^2 - b$$$.

Obviously, this is not the right formula to check if a triple of numbers is Pythagorean. But, to Vasya's surprise, it actually worked on the triple $$$(3, 4, 5)$$$: $$$5 = 3^2 - 4$$$, so, according to Vasya's formula, it is a Pythagorean triple.

When Vasya found the right formula (and understood that his formula is wrong), he wondered: how many are there triples of integers $$$(a, b, c)$$$ with $$$1 \le a \le b \le c \le n$$$ such that they are Pythagorean both according to his formula and the real definition? He asked you to count these triples.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of one line containing one integer $$$n$$$ ($$$1 \le n \le 10^9$$$).

Output format:
For each test case, print one integer — the number of triples of integers $$$(a, b, c)$$$ with $$$1 \le a \le b \le c \le n$$$ such that they are Pythagorean according both to the real definition and to the formula Vasya came up with.

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

Note:
The only Pythagorean triple satisfying $$$c = a^2 - b$$$ with $$$1 \le a \le b \le c \le 9$$$ is $$$(3, 4, 5)$$$; that's why the answer for $$$n = 3$$$ is $$$0$$$, and the answer for $$$n = 6$$$ (and for $$$n = 9$$$) is $$$1$$$.

Example input:
3
3
6
9

Example output:
0
1
1

Editorial:
We have to find the number of triples ($$$a, b, c$$$) such that equations $$$a^2+b^2=c^2$$$ and $$$a^2-b=c$$$ are satisfied. Let's subtract one equation from another and get that $$$b^2+b=c^2-c \implies b(b+1)=c(c-1)$$$. So we know that $$$c=b+1$$$ and after substituting, we get that $$$a^2=2b+1$$$. We can see that there is only one correct value of $$$b$$$ (and $$$c$$$) for every odd value of $$$a$$$ (greater than $$$1$$$). So we can iterate over the value of $$$a$$$ and check that the corresponding value of $$$c$$$ doesn't exceed $$$n$$$. This solution works in $$$O(\sqrt{n})$$$ because $$$a \approx \sqrt{c} \le \sqrt{n}$$$, but you can also solve it in $$$O(1)$$$.
Ones
Contest: Educational Codeforces Round 104 (Rated for Div. 2)
Difficulty rating: 2900
Tags: dp, greedy, shortest paths

You are given a positive (greater than zero) integer $$$n$$$.

You have to represent $$$n$$$ as the sum of integers (possibly negative) consisting only of ones (digits '1'). For example, $$$24 = 11 + 11 + 1 + 1$$$ and $$$102 = 111 - 11 + 1 + 1$$$.

Among all possible representations, you have to find the one that uses the minimum number of ones in total.

Input format:
The single line contains one integer $$$n$$$ ($$$1 \le n < 10^{50}$$$).

Output format:
Print one integer $$$x$$$ — the minimum number of ones, such that there exist a representation of $$$n$$$ as the sum of integers (possibly negative) that uses $$$x$$$ ones in total.

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

Example input:
24

Example output:
6

Example input:
102

Example output:
7

Editorial:
Let's build the number from the lowest digit to the highest digit with the following dynamic programming: $$$dp_{i,carry,cp,cn}$$$ — the minimum number of ones, if $$$i$$$ least significant digits are already fixed, the carry to the next digit is $$$carry$$$ (can be negative), there are $$$cp$$$ positive numbers (of the form $$$111 \cdots 111$$$) of length greater than or equal to $$$i$$$ and $$$cn$$$ negative numbers of length greater than or equal to $$$i$$$.
First, consider the transitions when we reduce the values of $$$cp$$$ and/or $$$cn$$$. Such transitions correspond to the fact that in the optimal answer there were several numbers of length exactly $$$i$$$, and they should not be considered further.
If the value of $$$(cp-cn+carry) \mod 10$$$ matches the $$$i$$$-th least significant digit in $$$n$$$, then we can use transition to $$$(i+1)$$$-th state with the new value of $$$carry$$$ and the number of ones in the answer increased by $$$cp+cn$$$.
It remains to estimate what the maximum value of $$$cp$$$ ($$$cn$$$) and $$$carry$$$ we need. The value of $$$cp$$$ doesn't exceed the total number of numbers that we use in the answer. Using at most $$$5$$$ numbers we can decrease the length of $$$n$$$ by at least $$$1$$$. Thus, the maximum value of $$$cp$$$ and $$$cn$$$ is at most $$$5|n|$$$ (where |n| is the length of the number $$$n$$$). For the value of $$$carry$$$, the condition $$$carry \ge \frac{carry+cp}{10}$$$ should be met (similarly for a negative value). Thus, we can assume that the absolute value of $$$carry$$$ doesn't exceed $$$\frac{5|n|}{9}$$$.
The total complexity of this solution is $$$O(|n|^4)$$$, yet with a high constant factor.
Train and Peter
Contest: Codeforces Beta Round 8
Difficulty rating: 1200
Tags: strings

Peter likes to travel by train. He likes it so much that on the train he falls asleep.

Once in summer Peter was going by train from city A to city B, and as usual, was sleeping. Then he woke up, started to look through the window and noticed that every railway station has a flag of a particular colour.

The boy started to memorize the order of the flags' colours that he had seen. But soon he fell asleep again. Unfortunately, he didn't sleep long, he woke up and went on memorizing the colours. Then he fell asleep again, and that time he slept till the end of the journey.

At the station he told his parents about what he was doing, and wrote two sequences of the colours that he had seen before and after his sleep, respectively.

Peter's parents know that their son likes to fantasize. They give you the list of the flags' colours at the stations that the train passes sequentially on the way from A to B, and ask you to find out if Peter could see those sequences on the way from A to B, or from B to A. Remember, please, that Peter had two periods of wakefulness.

Peter's parents put lowercase Latin letters for colours. The same letter stands for the same colour, different letters — for different colours.

Input format:
The input data contains three lines. The first line contains a non-empty string, whose length does not exceed 105, the string consists of lowercase Latin letters — the flags' colours at the stations on the way from A to B. On the way from B to A the train passes the same stations, but in reverse order.

The second line contains the sequence, written by Peter during the first period of wakefulness. The third line contains the sequence, written during the second period of wakefulness. Both sequences are non-empty, consist of lowercase Latin letters, and the length of each does not exceed 100 letters. Each of the sequences is written in chronological order.

Output format:
Output one of the four words without inverted commas:

- «forward» — if Peter could see such sequences only on the way from A to B;
- «backward» — if Peter could see such sequences on the way from B to A;
- «both» — if Peter could see such sequences both on the way from A to B, and on the way from B to A;
- «fantasy» — if Peter could not see such sequences.

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

Note:
It is assumed that the train moves all the time, so one flag cannot be seen twice. There are no flags at stations A and B.

Example input:
atob
a
b

Example output:
forward

Example input:
aaacaaa
aca
aa

Example output:
both

Editorial:
Obsession with Robots
Contest: Codeforces Beta Round 8
Difficulty rating: 1400
Tags: constructive algorithms, graphs, implementation

The whole world got obsessed with robots,and to keep pace with the progress, great Berland's programmer Draude decided to build his own robot. He was working hard at the robot. He taught it to walk the shortest path from one point to another, to record all its movements, but like in many Draude's programs, there was a bug — the robot didn't always walk the shortest path. Fortunately, the robot recorded its own movements correctly. Now Draude wants to find out when his robot functions wrong. Heh, if Draude only remembered the map of the field, where he tested the robot, he would easily say if the robot walked in the right direction or not. But the field map was lost never to be found, that's why he asks you to find out if there exist at least one map, where the path recorded by the robot is the shortest.

The map is an infinite checkered field, where each square is either empty, or contains an obstruction. It is also known that the robot never tries to run into the obstruction. By the recorded robot's movements find out if there exist at least one such map, that it is possible to choose for the robot a starting square (the starting square should be empty) such that when the robot moves from this square its movements coincide with the recorded ones (the robot doesn't run into anything, moving along empty squares only), and the path from the starting square to the end one is the shortest.

In one movement the robot can move into the square (providing there are no obstrutions in this square) that has common sides with the square the robot is currently in.

Input format:
The first line of the input file contains the recording of the robot's movements. This recording is a non-empty string, consisting of uppercase Latin letters L, R, U and D, standing for movements left, right, up and down respectively. The length of the string does not exceed 100.

Output format:
In the first line output the only word OK (if the above described map exists), or BUG (if such a map does not exist).

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

Example input:
LLUUUR

Example output:
OK

Example input:
RRUULLDD

Example output:
BUG

Editorial:
Looking for Order
Contest: Codeforces Beta Round 8
Difficulty rating: 2000
Tags: bitmasks, dp

Girl Lena likes it when everything is in order, and looks for order everywhere. Once she was getting ready for the University and noticed that the room was in a mess — all the objects from her handbag were thrown about the room. Of course, she wanted to put them back into her handbag. The problem is that the girl cannot carry more than two objects at a time, and cannot move the handbag. Also, if he has taken an object, she cannot put it anywhere except her handbag — her inherent sense of order does not let her do so.

You are given the coordinates of the handbag and the coordinates of the objects in some Сartesian coordinate system. It is known that the girl covers the distance between any two objects in the time equal to the squared length of the segment between the points of the objects. It is also known that initially the coordinates of the girl and the handbag are the same. You are asked to find such an order of actions, that the girl can put all the objects back into her handbag in a minimum time period.

Input format:
The first line of the input file contains the handbag's coordinates xs, ys. The second line contains number n (1 ≤ n ≤ 24) — the amount of objects the girl has. The following n lines contain the objects' coordinates. All the coordinates do not exceed 100 in absolute value. All the given positions are different. All the numbers are integer.

Output format:
In the first line output the only number — the minimum time the girl needs to put the objects into her handbag.

In the second line output the possible optimum way for Lena. Each object in the input is described by its index number (from 1 to n), the handbag's point is described by number 0. The path should start and end in the handbag's point. If there are several optimal paths, print any of them.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Example input:
0 0
2
1 1
-1 1

Example output:
8
0 1 2 0

Example input:
1 1
3
4 3
3 4
0 0

Example output:
32
0 1 2 0 3 0

Editorial:
Two Friends
Contest: Codeforces Beta Round 8
Difficulty rating: 2600
Tags: binary search, geometry

Two neighbours, Alan and Bob, live in the city, where there are three buildings only: a cinema, a shop and the house, where they live. The rest is a big asphalt square.

Once they went to the cinema, and the film impressed them so deeply, that when they left the cinema, they did not want to stop discussing it.

Bob wants to get home, but Alan has to go to the shop first, and only then go home. So, they agreed to cover some distance together discussing the film (their common path might pass through the shop, or they might walk circles around the cinema together), and then to part each other's company and go each his own way. After they part, they will start thinking about their daily pursuits; and even if they meet again, they won't be able to go on with the discussion. Thus, Bob's path will be a continuous curve, having the cinema and the house as its ends. Alan's path — a continuous curve, going through the shop, and having the cinema and the house as its ends.

The film ended late, that's why the whole distance covered by Alan should not differ from the shortest one by more than t1, and the distance covered by Bob should not differ from the shortest one by more than t2.

Find the maximum distance that Alan and Bob will cover together, discussing the film.

Input format:
The first line contains two integers: t1, t2 (0 ≤ t1, t2 ≤ 100). The second line contains the cinema's coordinates, the third one — the house's, and the last line — the shop's.

All the coordinates are given in meters, are integer, and do not exceed 100 in absolute magnitude. No two given places are in the same building.

Output format:
In the only line output one number — the maximum distance that Alan and Bob will cover together, discussing the film. Output the answer accurate to not less than 4 decimal places.

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

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

Example output:
1.0000000000

Example input:
0 0
0 0
2 0
1 0

Example output:
2.0000000000

Editorial:
Beads
Contest: Codeforces Beta Round 8
Difficulty rating: 2600
Tags: dp, graphs

One Martian boy called Zorg wants to present a string of beads to his friend from the Earth — Masha. He knows that Masha likes two colours: blue and red, — and right in the shop where he has come, there is a variety of adornments with beads of these two colours. All the strings of beads have a small fastener, and if one unfastens it, one might notice that all the strings of beads in the shop are of the same length. Because of the peculiarities of the Martian eyesight, if Zorg sees one blue-and-red string of beads first, and then the other with red beads instead of blue ones, and blue — instead of red, he regards these two strings of beads as identical. In other words, Zorg regards as identical not only those strings of beads that can be derived from each other by the string turnover, but as well those that can be derived from each other by a mutual replacement of colours and/or by the string turnover.

It is known that all Martians are very orderly, and if a Martian sees some amount of objects, he tries to put them in good order. Zorg thinks that a red bead is smaller than a blue one. Let's put 0 for a red bead, and 1 — for a blue one. From two strings the Martian puts earlier the string with a red bead in the i-th position, providing that the second string has a blue bead in the i-th position, and the first two beads i - 1 are identical.

At first Zorg unfastens all the strings of beads, and puts them into small heaps so, that in each heap strings are identical, in his opinion. Then he sorts out the heaps and chooses the minimum string in each heap, in his opinion. He gives the unnecassary strings back to the shop assistant and says he doesn't need them any more. Then Zorg sorts out the remaining strings of beads and buys the string with index k.

All these manupulations will take Zorg a lot of time, that's why he asks you to help and find the string of beads for Masha.

Input format:
The input file contains two integers n and k (2 ≤ n ≤ 50;1 ≤ k ≤ 1016) —the length of a string of beads, and the index of the string, chosen by Zorg.

Output format:
Output the k-th string of beads, putting 0 for a red bead, and 1 — for a blue one. If it s impossible to find the required string, output the only number -1.

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

Note:
Let's consider the example of strings of length 4 — 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110. Zorg will divide them into heaps: {0001, 0111, 1000, 1110}, {0010, 0100, 1011, 1101}, {0011, 1100}, {0101, 1010}, {0110, 1001}. Then he will choose the minimum strings of beads in each heap: 0001, 0010, 0011, 0101, 0110. The forth string — 0101.

Example input:
4 4

Example output:
0101

Editorial: