1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Team Arrangement
Contest: Codeforces Beta Round 55 (Div. 2)
Difficulty rating: 2000
Tags: constructive algorithms, greedy, implementation

Recently personal training sessions have finished in the Berland State University Olympiad Programmer Training Centre. By the results of these training sessions teams are composed for the oncoming team contest season. Each team consists of three people. All the students of the Centre possess numbers from 1 to 3n, and all the teams possess numbers from 1 to n. The splitting of students into teams is performed in the following manner: while there are people who are not part of a team, a person with the best total score is chosen among them (the captain of a new team), this person chooses for himself two teammates from those who is left according to his list of priorities. The list of every person's priorities is represented as a permutation from the rest of 3n - 1 students who attend the centre, besides himself.

You are given the results of personal training sessions which are a permutation of numbers from 1 to 3n, where the i-th number is the number of student who has won the i-th place. No two students share a place. You are also given the arrangement of the already formed teams in the order in which they has been created. Your task is to determine the list of priorities for the student number k. If there are several priority lists, choose the lexicographically minimal one.

Input format:
The first line contains an integer n (1 ≤ n ≤ 105) which is the number of resulting teams. The second line contains 3n space-separated integers from 1 to 3n which are the results of personal training sessions. It is guaranteed that every student appears in the results exactly once.

Then follow n lines each containing three integers from 1 to 3n — each line describes the members of a given team. The members of one team can be listed in any order, but the teams themselves are listed in the order in which they were created. It is guaranteed that the arrangement is correct, that is that every student is a member of exactly one team and those teams could really be created from the given results using the method described above.

The last line contains number k (1 ≤ k ≤ 3n) which is the number of a student for who the list of priorities should be found.

Output format:
Print 3n - 1 numbers — the lexicographically smallest list of priorities for the student number k.

The lexicographical comparison is performed by the standard < operator in modern programming languages. The list a is lexicographically less that the list b if exists such an i (1 ≤ i ≤ 3n), that ai < bi, and for any j (1 ≤ j < i) aj = bj. Note, that the list 1 9 10 is lexicographically less than the list 1 10 9. That is, the comparison of lists is different from the comparison of lines.

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

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

Example output:
2 3 5 6 9 1 7 8

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

Example output:
1 2 3 4 5 6 7 9

Editorial:
Shortest Path
Contest: Codeforces Beta Round 55 (Div. 2)
Difficulty rating: 2000
Tags: graphs, shortest paths

In Ancient Berland there were n cities and m two-way roads of equal length. The cities are numbered with integers from 1 to n inclusively. According to an ancient superstition, if a traveller visits three cities ai, bi, ci in row, without visiting other cities between them, a great disaster awaits him. Overall there are k such city triplets. Each triplet is ordered, which means that, for example, you are allowed to visit the cities in the following order: ai, ci, bi. Vasya wants to get from the city 1 to the city n and not fulfil the superstition. Find out which minimal number of roads he should take. Also you are required to find one of his possible path routes.

Input format:
The first line contains three integers n, m, k (2 ≤ n ≤ 3000, 1 ≤ m ≤ 20000, 0 ≤ k ≤ 105) which are the number of cities, the number of roads and the number of the forbidden triplets correspondingly.

Then follow m lines each containing two integers xi, yi (1 ≤ xi, yi ≤ n) which are the road descriptions. The road is described by the numbers of the cities it joins. No road joins a city with itself, there cannot be more than one road between a pair of cities.

Then follow k lines each containing three integers ai, bi, ci (1 ≤ ai, bi, ci ≤ n) which are the forbidden triplets. Each ordered triplet is listed mo more than one time. All three cities in each triplet are distinct.

City n can be unreachable from city 1 by roads.

Output format:
If there are no path from 1 to n print -1. Otherwise on the first line print the number of roads d along the shortest path from the city 1 to the city n. On the second line print d + 1 numbers — any of the possible shortest paths for Vasya. The path should start in the city 1 and end in the city n.

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

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

Example output:
2
1 3 4

Example input:
3 1 0
1 2

Example output:
-1

Editorial:
Two Bases
Contest: Codeforces Round 333 (Div. 2)
Difficulty rating: 1100
Tags: brute force, implementation

After seeing the "ALL YOUR BASE ARE BELONG TO US" meme for the first time, numbers X and Y realised that they have different bases, which complicated their relations.

You're given a number X represented in base bx and a number Y represented in base by. Compare those two numbers.

Input format:
The first line of the input contains two space-separated integers n and bx (1 ≤ n ≤ 10, 2 ≤ bx ≤ 40), where n is the number of digits in the bx-based representation of X.

The second line contains n space-separated integers x1, x2, ..., xn (0 ≤ xi < bx) — the digits of X. They are given in the order from the most significant digit to the least significant one.

The following two lines describe Y in the same way: the third line contains two space-separated integers m and by (1 ≤ m ≤ 10, 2 ≤ by ≤ 40, bx ≠ by), where m is the number of digits in the by-based representation of Y, and the fourth line contains m space-separated integers y1, y2, ..., ym (0 ≤ yi < by) — the digits of Y.

There will be no leading zeroes. Both X and Y will be positive. All digits of both numbers are given in the standard decimal numeral system.

Output format:
Output a single character (quotes for clarity):

- '<' if X < Y
- '>' if X > Y
- '=' if X = Y

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

Note:
In the first sample, X = 1011112 = 4710 = Y.

In the second sample, X = 1023 = 215 and Y = 245 = 1123, thus X < Y.

In the third sample, $$X = \text{FF4007A}_{16}$$ and Y = 48031509. We may notice that X starts with much larger digits and bx is much larger than by, so X is clearly larger than Y.

Example input:
6 2
1 0 1 1 1 1
2 10
4 7

Example output:
=

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

Example output:
<

Editorial:
Approximating a Constant Range
Contest: Codeforces Round 333 (Div. 2)
Difficulty rating: 1400
Tags: dp, implementation, two pointers

When Xellos was doing a practice course in university, he once had to measure the intensity of an effect that slowly approached equilibrium. A good way to determine the equilibrium intensity would be choosing a sufficiently large number of consecutive data points that seems as constant as possible and taking their average. Of course, with the usual sizes of data, it's nothing challenging — but why not make a similar programming contest problem while we're at it?

You're given a sequence of n data points a1, ..., an. There aren't any big jumps between consecutive data points — for each 1 ≤ i < n, it's guaranteed that |ai + 1 - ai| ≤ 1.

A range [l, r] of data points is said to be almost constant if the difference between the largest and the smallest value in that range is at most 1. Formally, let M be the maximum and m the minimum value of ai for l ≤ i ≤ r; the range [l, r] is almost constant if M - m ≤ 1.

Find the length of the longest almost constant range.

Input format:
The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of data points.

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

Output format:
Print a single number — the maximum length of an almost constant range of the given sequence.

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

Note:
In the first sample, the longest almost constant range is [2, 5]; its length (the number of data points in it) is 4.

In the second sample, there are three almost constant ranges of length 4: [1, 4], [6, 9] and [7, 10]; the only almost constant range of the maximum length 5 is [6, 10].

Example input:
5
1 2 3 3 2

Example output:
4

Example input:
11
5 4 5 5 6 7 8 8 8 7 6

Example output:
5

Editorial:
Mahmoud and Longest Uncommon Subsequence
Contest: Codeforces Round 396 (Div. 2)
Difficulty rating: 1000
Tags: constructive algorithms, strings

While Mahmoud and Ehab were practicing for IOI, they found a problem which name was Longest common subsequence. They solved it, and then Ehab challenged Mahmoud with another problem.

Given two strings a and b, find the length of their longest uncommon subsequence, which is the longest string that is a subsequence of one of them and not a subsequence of the other.

A subsequence of some string is a sequence of characters that appears in the same order in the string, The appearances don't have to be consecutive, for example, strings "ac", "bc", "abc" and "a" are subsequences of string "abc" while strings "abbc" and "acb" are not. The empty string is a subsequence of any string. Any string is a subsequence of itself.

Input format:
The first line contains string a, and the second line — string b. Both of these strings are non-empty and consist of lowercase letters of English alphabet. The length of each string is not bigger than 105 characters.

Output format:
If there's no uncommon subsequence, print "-1". Otherwise print the length of the longest uncommon subsequence of a and b.

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

Note:
In the first example: you can choose "defgh" from string b as it is the longest subsequence of string b that doesn't appear as a subsequence of string a.

Example input:
abcd
defgh

Example output:
5

Example input:
a
a

Example output:
-1

Editorial:
If the strings are the same, Any subsequence of a is indeed a subsequence of b so the answer is "-1", Otherwise the longer string can't be a subsequence of the other (If they are equal in length and aren't the same, No one can be a subsequence of the other) so the answer is maximum of their lengths.
Code : http://pastebin.com/aJbeTTjw
Time complexity : O(|a| + |b|).
Problem author : me.
Solution author : me.
Testers : me and [user:mahmoudbadawy,2017-02-07].
Mahmoud and a Triangle
Contest: Codeforces Round 396 (Div. 2)
Difficulty rating: 1000
Tags: constructive algorithms, geometry, greedy, math, number theory, sortings

Mahmoud has n line segments, the i-th of them has length ai. Ehab challenged him to use exactly 3 line segments to form a non-degenerate triangle. Mahmoud doesn't accept challenges unless he is sure he can win, so he asked you to tell him if he should accept the challenge. Given the lengths of the line segments, check if he can choose exactly 3 of them to form a non-degenerate triangle.

Mahmoud should use exactly 3 line segments, he can't concatenate two line segments or change any length. A non-degenerate triangle is a triangle with positive area.

Input format:
The first line contains single integer n (3 ≤ n ≤ 105) — the number of line segments Mahmoud has.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the lengths of line segments Mahmoud has.

Output format:
In the only line print "YES" if he can choose exactly three line segments and form a non-degenerate triangle with them, and "NO" otherwise.

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

Note:
For the first example, he can use line segments with lengths 2, 4 and 5 to form a non-degenerate triangle.

Example input:
5
1 5 3 2 4

Example output:
YES

Example input:
3
4 1 2

Example output:
NO

Editorial:
#### First solution :- Let x, y and z be the lengths of 3 line segments such that x ≤ y ≤ z, If they can't form a non-degenerate triangle, Line segments of lengths x - 1, y and z or x, y and z + 1 can't form a non-degenerate triangle, So we don't need to try all the combinations, If we try y as the middle one, We need to try the maximum x that is less than or equal to y and the minimum z that is greater than or equal to y, The easiest way to do so is to sort the line segments and try every consecutive 3.
Code : http://pastebin.com/NsCkbQFS
Time complexity : O(nlog(n)).
#### Second solution :- Depending on the note from the first solution, If we try to generate a sequence such that after sorting, Every consecutive 3 line segments will form a degenerate triangle, It will be 1 1 2 3 5 8 13 ... which is Fibonacci sequence, Fibonacci is a fast growing sequence, fib(45) = 1134903170, Notice that Fibonacci makes maximum n with "NO" as the answer, That means the answer is indeed "YES" for n ≥ 45, For n < 45, You can do the naive O(n3) solution or the first solution.
Code : http://pastebin.com/82XcJfgp
Let x be the number that satisfies these inequalities:-
fib(x) ≤ maxAi.
fib(x + 1) > maxAi.
Time complexity : O(x3) or O(xlog(x)).
Problem author : me.
Solutions author : me.
Testers : me and [user:mahmoudbadawy,2017-02-03].
Любимые числа Поликарпа
Contest: Технокубок 2016 - Отборочный Раунд 2
Difficulty rating: 1000
Tags: constructive algorithms, implementation

Поликарп мечтает стать программистом и фанатеет от степеней двойки. Среди двух чисел ему больше нравится то, которое делится на большую степень числа 2.

По заданной последовательности целых положительных чисел a1, a2, ..., an требуется найти r — максимальную степень числа 2, на которую делится хотя бы одно из чисел последовательности. Кроме того, требуется вывести количество чисел ai, которые делятся на r.

Input format:
В первой строке записано целое число n (1 ≤ n ≤ 100) — длина последовательности a.

Во второй строке записана последовательность целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109).

Output format:
Выведите два числа:

- r — максимальную степень двойки, на которую делится хотя бы одно из чисел заданной последовательности,
- количество элементов последовательности, которые делятся на r.

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

Note:
В первом тестовом примере максимальная степень двойки, на которую делится хотя бы одно число, равна 16 = 24, на неё делятся числа 80, 16 и 48.

Во втором тестовом примере все четыре числа нечётные, поэтому делятся только на 1 = 20. Это и будет максимальной степенью двойки для данного примера.

Example input:
5
80 7 16 4 48

Example output:
16 3

Example input:
4
21 5 3 33

Example output:
1 4

Editorial:
Этажи
Contest: Технокубок 2016 - Отборочный Раунд 2
Difficulty rating: 1400
Tags: constructive algorithms

Есть n-подъездный дом, в каждом подъезде по m этажей, и на каждом этаже каждого подъезда ровно k квартир. Таким образом, в доме всего n·m·k квартир. Они пронумерованы естественным образом от 1 до n·m·k, то есть первая квартира на первом этаже в первом подъезде имеет номер 1, первая квартира на втором этаже первого подъезда имеет номер k + 1 и так далее. Особенность этого дома состоит в том, что он круглый. То есть если обходить его по часовой стрелке, то после подъезда номер 1 следует подъезд номер 2, затем подъезд номер 3 и так далее до подъезда номер n. После подъезда номер n снова идёт подъезд номер 1.

Эдвард живёт в квартире номер a, а Наташа — в квартире номер b. Переход на 1 этаж вверх или вниз по лестнице занимает 5 секунд, переход от двери подъезда к двери соседнего подъезда — 15 секунд, а переход в пределах одного этажа одного подъезда происходит мгновенно. Также в каждом подъезде дома есть лифт. Он устроен следующим образом: он всегда приезжает ровно через 10 секунд после вызова, а чтобы переместить пассажира на один этаж вверх или вниз, лифт тратит ровно 1 секунду. Посадка и высадка происходят мгновенно.

Помогите Эдварду найти минимальное время, за которое он сможет добраться до квартиры Наташи. Считайте, что Эдвард может выйти из подъезда только с первого этажа соответствующего подъезда (это происходит мгновенно). Если Эдвард стоит перед дверью какого-то подъезда, он может зайти в него и сразу окажется на первом этаже этого подъезда (это также происходит мгновенно). Эдвард может выбирать, в каком направлении идти вокруг дома.

Input format:
В первой строке входных данных следуют три числа n, m, k (1 ≤ n, m, k ≤ 1000) — количество подъездов в доме, количество этажей в каждом подъезде и количество квартир на каждом этаже каждого подъезда соответственно.

Во второй строке входных данных записаны два числа a и b (1 ≤ a, b ≤ n·m·k) — номера квартир, в которых живут Эдвард и Наташа, соответственно. Гарантируется, что эти номера различны.

Output format:
Выведите единственное целое число — минимальное время (в секундах), за которое Эдвард сможет добраться от своей квартиры до квартиры Наташи.

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

Note:
В первом тестовом примере Эдвард находится в 4 подъезде на 10 этаже, а Наташа находится в 1 подъезде на 2 этаже. Поэтому Эдварду выгодно сначала спуститься на лифте на первый этаж (на это он потратит 19 секунд, из которых 10 — на ожидание и 9 — на поездку на лифте), затем обойти дом против часовой стрелки до подъезда номер 1 (на это он потратит 15 секунд), и наконец подняться по лестнице на этаж номер 2 (на это он потратит 5 секунд). Таким образом, ответ равен 19 + 15 + 5 = 39.

Во втором тестовом примере Эдвард живёт в подъезде 2 на этаже 1, а Наташа находится в подъезде 1 на этаже 1. Поэтому Эдварду выгодно просто обойти дом по часовой стрелке до подъезда 1, на это он потратит 15 секунд.

Example input:
4 10 5
200 6

Example output:
39

Example input:
3 1 5
7 2

Example output:
15

Editorial:
Печать условий
Contest: Технокубок 2016 - Отборочный Раунд 2
Difficulty rating: 1500
Tags: constructive algorithms, greedy, sortings

На тренировку по подготовке к соревнованиям по программированию пришли n команд. Тренер для каждой команды подобрал тренировку, комплект задач для i-й команды занимает ai страниц. В распоряжении тренера есть x листов бумаги, у которых обе стороны чистые, и y листов, у которых только одна сторона чистая. При печати условия на листе первого типа можно напечатать две страницы из условий задач, а при печати на листе второго типа — только одну. Конечно, на листе нельзя печатать условия из двух разных комплектов задач. Обратите внимание, что при использовании листов, у которых обе стороны чистые, не обязательно печатать условие на обеих сторонах, одна из них может остаться чистой.

Вам предстоит определить максимальное количество команд, которым тренер сможет напечатать комплекты задач целиком.

Input format:
В первой строке входных данных следуют три целых числа n, x и y (1 ≤ n ≤ 200 000, 0 ≤ x, y ≤ 109) — количество команд, количество листов бумаги с двумя чистыми сторонами и количество листов бумаги с одной чистой стороной.

Во второй строке входных данных следует последовательность из n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 10 000), где i-е число равно количеству страниц в комплекте задач для i-й команды.

Output format:
Выведите единственное целое число — максимальное количество команд, которым тренер сможет напечатать комплекты задач целиком.

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

Note:
В первом тестовом примере можно напечатать оба комплекта задач. Один из возможных ответов — напечатать весь первый комплект задач на листах с одной чистой стороной (после этого останется 3 листа с двумя чистыми сторонами и 1 лист с одной чистой стороной), а второй комплект напечатать на трех листах с двумя чистыми сторонами.

Во втором тестовом примере можно напечатать оба комплекта задач. Один из возможных ответов — напечатать первый комплект задач на двух листах с двумя чистыми сторонами (после этого останется 1 лист с двумя чистыми сторонами и 5 листов с одной чистой стороной), а второй комплект напечатать на одном листе с двумя чистыми сторонами и на пяти листах с одной чистой стороной. Таким образом, тренер использует все листы для печати.

В третьем тестовом примере можно напечатать только один комплект задач (любой из трёх 11-страничных). Для печати 11-страничного комплекта задач будет израсходована вся бумага.

Example input:
2 3 5
4 6

Example output:
2

Example input:
2 3 5
4 7

Example output:
2

Editorial:
Дефрагментация памяти
Contest: Технокубок 2016 - Отборочный Раунд 2
Difficulty rating: 1600
Tags: constructive algorithms, greedy, implementation

Память компьютера состоит из n ячеек, которые выстроены в ряд. Пронумеруем ячейки от 1 до n слева направо. Про каждую ячейку известно, свободна она или принадлежит какому-либо процессу (в таком случае известен процесс, которому она принадлежит).

Для каждого процесса известно, что принадлежащие ему ячейки занимают в памяти непрерывный участок. С помощью операций вида «переписать данные из занятой ячейки в свободную, а занятую теперь считать свободной» требуется расположить все принадлежащие процессам ячейки в начале памяти компьютера. Другими словами, любая свободная ячейка должна располагаться правее (иметь больший номер) любой занятой.

Вам необходимо найти минимальное количество операций переписывания данных из одной ячейки в другую, с помощью которых можно достичь описанных условий. Допустимо, что относительный порядок ячеек в памяти для каждого из процессов изменится после дефрагментации, но относительный порядок самих процессов должен остаться без изменений. Это значит, что если все ячейки, принадлежащие процессу i, находились в памяти раньше всех ячеек процесса j, то и после перемещений это условие должно выполняться.

Считайте, что номера всех процессов уникальны, хотя бы одна ячейка памяти занята каким-либо процессом.

Input format:
В первой строке входных данных записано число n (1 ≤ n ≤ 200 000) — количество ячеек в памяти компьютера.

Во второй строке входных данных следуют n целых чисел a1, a2, ..., an (1 ≤ ai ≤ n), где ai равно либо 0 (это означает, что i-я ячейка памяти свободна), либо номеру процесса, которому принадлежит i-я ячейка памяти. Гарантируется, что хотя бы одно значение ai не равно 0.

Процессы пронумерованы целыми числами от 1 до n в произвольном порядке. При этом процессы не обязательно пронумерованы последовательными числами.

Output format:
Выведите одно целое число — минимальное количество операций, которое нужно сделать для дефрагментации памяти.

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

Note:
В первом тестовом примере достаточно двух операций:

1. Переписать данные из третьей ячейки в первую. После этого память компьютера примет вид: 2 2 0 1.
2. Переписать данные из четвертой ячейки в третью. После этого память компьютера примет вид: 2 2 1 0.

Example input:
4
0 2 2 1

Example output:
2

Example input:
8
0 8 8 8 0 4 4 2

Example output:
4

Editorial: