1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Hockey
Contest: Codeforces Beta Round 77 (Div. 1 Only)
Difficulty rating: 1600
Tags: implementation, strings

Petya loves hockey very much. One day, as he was watching a hockey match, he fell asleep. Petya dreamt of being appointed to change a hockey team's name. Thus, Petya was given the original team name w and the collection of forbidden substrings s1, s2, ..., sn. All those strings consist of uppercase and lowercase Latin letters. String w has the length of |w|, its characters are numbered from 1 to |w|.

First Petya should find all the occurrences of forbidden substrings in the w string. During the search of substrings the case of letter shouldn't be taken into consideration. That is, strings "aBC" and "ABc" are considered equal.

After that Petya should perform the replacement of all letters covered by the occurrences. More formally: a letter in the position i should be replaced by any other one if for position i in string w there exist pair of indices l, r (1 ≤ l ≤ i ≤ r ≤ |w|) such that substring w[l ... r] is contained in the collection s1, s2, ..., sn, when using case insensitive comparison. During the replacement the letter's case should remain the same. Petya is not allowed to replace the letters that aren't covered by any forbidden substring.

Letter letter (uppercase or lowercase) is considered lucky for the hockey players. That's why Petya should perform the changes so that the letter occurred in the resulting string as many times as possible. Help Petya to find such resulting string. If there are several such strings, find the one that comes first lexicographically.

Note that the process of replacements is not repeated, it occurs only once. That is, if after Petya's replacements the string started to contain new occurrences of bad substrings, Petya pays no attention to them.

Input format:
The first line contains the only integer n (1 ≤ n ≤ 100) — the number of forbidden substrings in the collection. Next n lines contain these substrings. The next line contains string w. All those n + 1 lines are non-empty strings consisting of uppercase and lowercase Latin letters whose length does not exceed 100. The last line contains a lowercase letter letter.

Output format:
Output the only line — Petya's resulting string with the maximum number of letters letter. If there are several answers then output the one that comes first lexicographically.

The lexicographical comparison is performed by the standard < operator in modern programming languages. The line a is lexicographically smaller than the line b, if a is a prefix of b, or there exists such an i (1 ≤ i ≤ |a|), that ai < bi, and for any j (1 ≤ j < i) aj = bj. |a| stands for the length of string a.

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

Example input:
3
bers
ucky
elu
PetrLoveLuckyNumbers
t

Example output:
PetrLovtTttttNumtttt

Example input:
4
hello
party
abefglghjdhfgj
IVan
petrsmatchwin
a

Example output:
petrsmatchwin

Editorial:
Lucky Numbers
Contest: Codeforces Beta Round 77 (Div. 1 Only)
Difficulty rating: 1800
Tags: dp, greedy

Petya loves lucky numbers. Everybody knows that positive integers are lucky if their decimal representation doesn't contain digits other than 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Lucky number is super lucky if it's decimal representation contains equal amount of digits 4 and 7. For example, numbers 47, 7744, 474477 are super lucky and 4, 744, 467 are not.

One day Petya came across a positive integer n. Help him to find the least super lucky number which is not less than n.

Input format:
The only line contains a positive integer n (1 ≤ n ≤ 10100000). This number doesn't have leading zeroes.

Output format:
Output the least super lucky number that is more than or equal to n.

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

Example input:
4500

Example output:
4747

Example input:
47

Example output:
47

Editorial:
Volleyball
Contest: Codeforces Beta Round 77 (Div. 1 Only)
Difficulty rating: 1900
Tags: shortest paths

Petya loves volleyball very much. One day he was running late for a volleyball match. Petya hasn't bought his own car yet, that's why he had to take a taxi. The city has n junctions, some of which are connected by two-way roads. The length of each road is defined by some positive integer number of meters; the roads can have different lengths.

Initially each junction has exactly one taxi standing there. The taxi driver from the i-th junction agrees to drive Petya (perhaps through several intermediate junctions) to some other junction if the travel distance is not more than ti meters. Also, the cost of the ride doesn't depend on the distance and is equal to ci bourles. Taxis can't stop in the middle of a road. Each taxi can be used no more than once. Petya can catch taxi only in the junction, where it stands initially.

At the moment Petya is located on the junction x and the volleyball stadium is on the junction y. Determine the minimum amount of money Petya will need to drive to the stadium.

Input format:
The first line contains two integers n and m (1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000). They are the number of junctions and roads in the city correspondingly. The junctions are numbered from 1 to n, inclusive. The next line contains two integers x and y (1 ≤ x, y ≤ n). They are the numbers of the initial and final junctions correspondingly. Next m lines contain the roads' description. Each road is described by a group of three integers ui, vi, wi (1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 109) — they are the numbers of the junctions connected by the road and the length of the road, correspondingly. The next n lines contain n pairs of integers ti and ci (1 ≤ ti, ci ≤ 109), which describe the taxi driver that waits at the i-th junction — the maximum distance he can drive and the drive's cost. The road can't connect the junction with itself, but between a pair of junctions there can be more than one road. All consecutive numbers in each line are separated by exactly one space character.

Output format:
If taxis can't drive Petya to the destination point, print "-1" (without the quotes). Otherwise, print the drive's minimum cost.

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specificator.

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

Note:
An optimal way — ride from the junction 1 to 2 (via junction 4), then from 2 to 3. It costs 7+2=9 bourles.

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

Example output:
9

Editorial:
Horse Races
Contest: Codeforces Beta Round 77 (Div. 1 Only)
Difficulty rating: 2500
Tags: dp, math

Petya likes horse racing very much. Horses numbered from l to r take part in the races. Petya wants to evaluate the probability of victory; for some reason, to do that he needs to know the amount of nearly lucky horses' numbers. A nearly lucky number is an integer number that has at least two lucky digits the distance between which does not exceed k. Petya learned from some of his mates from Lviv that lucky digits are digits 4 and 7. The distance between the digits is the absolute difference between their positions in the number of a horse. For example, if k = 2, then numbers 412395497, 404, 4070400000070004007 are nearly lucky and numbers 4, 4123954997, 4007000040070004007 are not.

Petya prepared t intervals [li, ri] and invented number k, common for all of them. Your task is to find how many nearly happy numbers there are in each of these segments. Since the answers can be quite large, output them modulo 1000000007 (109 + 7).

Input format:
The first line contains two integers t and k (1 ≤ t, k ≤ 1000) — the number of segments and the distance between the numbers correspondingly. Next t lines contain pairs of integers li and ri (1 ≤ l ≤ r ≤ 101000). All numbers are given without the leading zeroes. Numbers in each line are separated by exactly one space character.

Output format:
Output t lines. In each line print one integer — the answer for the corresponding segment modulo 1000000007 (109 + 7).

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

Note:
In the first sample, the four nearly lucky numbers are 44, 47, 74, 77.

In the second sample, only 74 and 77 are in the given segment.

Example input:
1 2
1 100

Example output:
4

Example input:
1 2
70 77

Example output:
2

Editorial:
Lucky Country
Contest: Codeforces Beta Round 77 (Div. 1 Only)
Difficulty rating: 2500
Tags: dp, dsu, graphs

Petya loves lucky numbers. Everybody knows that positive integers are lucky if their decimal representation doesn't contain digits other than 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

One night Petya was sleeping. He was dreaming of being the president of some island country. The country is represented by islands connected by two-way roads. Between some islands there is no road way, even through other islands, that's why the country is divided into several regions. More formally, each island belongs to exactly one region, there is a path between any two islands located in the same region; there is no path between any two islands from different regions. A region is lucky if the amount of islands in it is a lucky number.

As a real president, Petya first decided to build a presidential palace. Being a lucky numbers' fan, Petya wants to position his palace in one of the lucky regions. However, it is possible that initially the country has no such regions. In this case Petya can build additional roads between different regions, thus joining them. Find the minimum number of roads needed to build to create a lucky region.

Input format:
The first line contains two integers n and m (1 ≤ n, m ≤ 105). They are the number of islands and the number of roads correspondingly. Next m lines contain road descriptions. Each road is defined by the numbers of islands that it connects: that is, by two integers u and v (1 ≤ u, v ≤ n). Some roads can connect an island with itself; there can be more than one road between a pair of islands. Numbers in each line are separated by exactly one space character.

Output format:
If there's no solution, output the only number "-1" (without the quotes). Otherwise, output the minimum number of roads r that need to be built to get a lucky region.

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

Example input:
4 3
1 2
2 3
1 3

Example output:
1

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

Example output:
-1

Editorial:
Clique in the Divisibility Graph
Contest: VK Cup 2015 - Finals
Difficulty rating: 1500
Tags: dp, math, number theory

As you must know, the maximum clique problem in an arbitrary graph is NP-hard. Nevertheless, for some graphs of specific kinds it can be solved effectively.

Just in case, let us remind you that a clique in a non-directed graph is a subset of the vertices of a graph, such that any two vertices of this subset are connected by an edge. In particular, an empty set of vertexes and a set consisting of a single vertex, are cliques.

Let's define a divisibility graph for a set of positive integers A = {a1, a2, ..., an} as follows. The vertices of the given graph are numbers from set A, and two numbers ai and aj (i ≠ j) are connected by an edge if and only if either ai is divisible by aj, or aj is divisible by ai.

You are given a set of non-negative integers A. Determine the size of a maximum clique in a divisibility graph for set A.

Input format:
The first line contains integer n (1 ≤ n ≤ 106), that sets the size of set A.

The second line contains n distinct positive integers a1, a2, ..., an (1 ≤ ai ≤ 106) — elements of subset A. The numbers in the line follow in the ascending order.

Output format:
Print a single number — the maximum size of a clique in a divisibility graph for set A.

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

Note:
In the first sample test a clique of size 3 is, for example, a subset of vertexes {3, 6, 18}. A clique of a larger size doesn't exist in this graph.

Example input:
8
3 4 6 8 10 18 21 24

Example output:
3

Editorial:
Restoring Map
Contest: VK Cup 2015 - Finals
Difficulty rating: 3200

Archaeologists found some information about an ancient land of Treeland. We know for sure that the Treeland consisted of n cities connected by the n - 1 road, such that you can get from each city to any other one along the roads. However, the information about the specific design of roads in Treeland has been lost. The only thing that the archaeologists can use is the preserved information about near cities.

Two cities of Treeland were called near, if it were possible to move from one city to the other one by moving through at most two roads. Also, a city is considered near to itself. During the recent excavations archaeologists found a set of n notes, each of them represents a list of cities, near to some of the n cities of the country. However, unfortunately, none of the found records lets you understand in what order the cities go in the list and for which city in the list the near to it cities were listed.

Help the archaeologists and restore any variant of the map of Treeland that meets the found information.

Input format:
The first line contains integer n (2 ≤ n ≤ 1000) — the number of cities in the country.

Next n lines describe the found lists of near cities. Each list starts from number k (1 ≤ k ≤ n), representing the number of cities in the list followed by k city numbers. All numbers in each list are distinct.

It is guaranteed that the given information determines at least one possible road map.

Output format:
Print n - 1 pairs of numbers representing the roads of the country. The i-th line must contain two integers ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi), showing that there is a road between cities ai and bi.

The answer you print must satisfy the description of close cities from the input. You may print the roads of the countries in any order. The cities that are connected by a road may also be printed in any order.

If there are multiple good answers, you may print any of them.

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

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

Example output:
1 4
1 2
1 3
4 5

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

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

Editorial:
Restructuring Company
Contest: VK Cup 2015 - Finals
Difficulty rating: 1900
Tags: data structures, dsu

Even the most successful company can go through a crisis period when you have to make a hard decision — to restructure, discard and merge departments, fire employees and do other unpleasant stuff. Let's consider the following model of a company.

There are n people working for the Large Software Company. Each person belongs to some department. Initially, each person works on his own project in his own department (thus, each company initially consists of n departments, one person in each).

However, harsh times have come to the company and the management had to hire a crisis manager who would rebuild the working process in order to boost efficiency. Let's use team(person) to represent a team where person person works. A crisis manager can make decisions of two types:

1. Merge departments team(x) and team(y) into one large department containing all the employees of team(x) and team(y), where x and y (1 ≤ x, y ≤ n) — are numbers of two of some company employees. If team(x) matches team(y), then nothing happens.
2. Merge departments team(x), team(x + 1), ..., team(y), where x and y (1 ≤ x ≤ y ≤ n) — the numbers of some two employees of the company.

At that the crisis manager can sometimes wonder whether employees x and y (1 ≤ x, y ≤ n) work at the same department.

Help the crisis manager and answer all of his queries.

Input format:
The first line of the input contains two integers n and q (1 ≤ n ≤ 200 000, 1 ≤ q ≤ 500 000) — the number of the employees of the company and the number of queries the crisis manager has.

Next q lines contain the queries of the crisis manager. Each query looks like type x y, where $$type \in \{1, 2, 3\}$$. If type = 1 or type = 2, then the query represents the decision of a crisis manager about merging departments of the first and second types respectively. If type = 3, then your task is to determine whether employees x and y work at the same department. Note that x can be equal to y in the query of any type.

Output format:
For each question of type 3 print "YES" or "NO" (without the quotes), depending on whether the corresponding people work in the same department.

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

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

Example output:
NO
YES
YES

Editorial:
Max and Min
Contest: VK Cup 2015 - Finals
Difficulty rating: 2500
Tags: geometry

Two kittens, Max and Min, play with a pair of non-negative integers x and y. As you can guess from their names, kitten Max loves to maximize and kitten Min loves to minimize. As part of this game Min wants to make sure that both numbers, x and y became negative at the same time, and kitten Max tries to prevent him from doing so.

Each kitten has a set of pairs of integers available to it. Kitten Max has n pairs of non-negative integers (ai, bi) (1 ≤ i ≤ n), and kitten Min has m pairs of non-negative integers (cj, dj) (1 ≤ j ≤ m). As kitten Max makes a move, it can take any available pair (ai, bi) and add ai to x and bi to y, and kitten Min can take any available pair (cj, dj) and subtract cj from x and dj from y. Each kitten can use each pair multiple times during distinct moves.

Max moves first. Kitten Min is winning if at some moment both numbers a, b are negative simultaneously. Otherwise, the winner of the game is kitten Max. Determine which kitten wins if both of them play optimally.

Input format:
The first line contains two integers, n and m (1 ≤ n, m ≤ 100 000) — the number of pairs of numbers available to Max and Min, correspondingly.

The second line contains two integers x, y (1 ≤ x, y ≤ 109) — the initial values of numbers with which the kittens are playing.

Next n lines contain the pairs of numbers ai, bi (1 ≤ ai, bi ≤ 109) — the pairs available to Max.

The last m lines contain pairs of numbers cj, dj (1 ≤ cj, dj ≤ 109) — the pairs available to Min.

Output format:
Print «Max» (without the quotes), if kitten Max wins, or "Min" (without the quotes), if kitten Min wins.

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

Note:
In the first test from the statement Min can respond to move (2, 3) by move (3, 10), and to move (3, 2) by move (10, 3). Thus, for each pair of Max and Min's moves the values of both numbers x and y will strictly decrease, ergo, Min will win sooner or later.

In the second sample test after each pair of Max and Min's moves both numbers x and y only increase, thus none of them will become negative.

Example input:
2 2
42 43
2 3
3 2
3 10
10 3

Example output:
Min

Example input:
1 1
1 1
3 4
1 1

Example output:
Max

Editorial:
Matching Names
Contest: VK Cup 2015 - Finals
Difficulty rating: 2300

Teachers of one programming summer school decided to make a surprise for the students by giving them names in the style of the "Hobbit" movie. Each student must get a pseudonym maximally similar to his own name. The pseudonym must be a name of some character of the popular saga and now the teachers are busy matching pseudonyms to student names.

There are n students in a summer school. Teachers chose exactly n pseudonyms for them. Each student must get exactly one pseudonym corresponding to him. Let us determine the relevance of a pseudonym b to a student with name a as the length of the largest common prefix a and b. We will represent such value as $$\operatorname{lcp}(a,b)$$. Then we can determine the quality of matching of the pseudonyms to students as a sum of relevances of all pseudonyms to the corresponding students.

Find the matching between students and pseudonyms with the maximum quality.

Input format:
The first line contains number n (1 ≤ n ≤ 100 000) — the number of students in the summer school.

Next n lines contain the name of the students. Each name is a non-empty word consisting of lowercase English letters. Some names can be repeating.

The last n lines contain the given pseudonyms. Each pseudonym is a non-empty word consisting of small English letters. Some pseudonyms can be repeating.

The total length of all the names and pseudonyms doesn't exceed 800 000 characters.

Output format:
In the first line print the maximum possible quality of matching pseudonyms to students.

In the next n lines describe the optimal matching. Each line must have the form a b (1 ≤ a, b ≤ n), that means that the student who was number a in the input, must match to the pseudonym number b in the input.

The matching should be a one-to-one correspondence, that is, each student and each pseudonym should occur exactly once in your output. If there are several optimal answers, output any.

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

Note:
The first test from the statement the match looks as follows:

- bill  →  bilbo (lcp = 3)
- galya  →  galadriel (lcp = 3)
- gennady  →  gendalf (lcp = 3)
- toshik  →  torin (lcp = 2)
- boris  →  smaug (lcp = 0)

Example input:
5
gennady
galya
boris
bill
toshik
bilbo
torin
gendalf
smaug
galadriel

Example output:
11
4 1
2 5
1 3
5 2
3 4

Editorial:
Ehab and another construction problem
Contest: Codeforces Round 525 (Div. 2)
Difficulty rating: 800
Tags: brute force, constructive algorithms

Given an integer $$$x$$$, find 2 integers $$$a$$$ and $$$b$$$ such that:

- $$$1 \le a,b \le x$$$
- $$$b$$$ divides $$$a$$$ ($$$a$$$ is divisible by $$$b$$$).
- $$$a \cdot b>x$$$.
- $$$\frac{a}{b}<x$$$.

Input format:
The only line contains the integer $$$x$$$ $$$(1 \le x \le 100)$$$.

Output format:
You should output two integers $$$a$$$ and $$$b$$$, satisfying the given conditions, separated by a space. If no pair of integers satisfy the conditions above, print "-1" (without quotes).

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

Example input:
10

Example output:
6 3

Example input:
1

Example output:
-1

Editorial:
Ehab and subtraction
Contest: Codeforces Round 525 (Div. 2)
Difficulty rating: 1000
Tags: implementation, sortings

You're given an array $$$a$$$. You should repeat the following operation $$$k$$$ times: find the minimum non-zero element in the array, print it, and then subtract it from all the non-zero elements of the array. If all the elements are 0s, just print 0.

Input format:
The first line contains integers $$$n$$$ and $$$k$$$ $$$(1 \le n,k \le 10^5)$$$, the length of the array and the number of operations you should perform.

The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$, the elements of the array.

Output format:
Print the minimum non-zero element before each operation in a new line.

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

Note:
In the first sample:

In the first step: the array is $$$[1,2,3]$$$, so the minimum non-zero element is 1.

In the second step: the array is $$$[0,1,2]$$$, so the minimum non-zero element is 1.

In the third step: the array is $$$[0,0,1]$$$, so the minimum non-zero element is 1.

In the fourth and fifth step: the array is $$$[0,0,0]$$$, so we printed 0.

In the second sample:

In the first step: the array is $$$[10,3,5,3]$$$, so the minimum non-zero element is 3.

In the second step: the array is $$$[7,0,2,0]$$$, so the minimum non-zero element is 2.

Example input:
3 5
1 2 3

Example output:
1
1
1
0
0

Example input:
4 2
10 3 5 3

Example output:
3
2

Editorial: