1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Fair Game
Contest: Codeforces Round 436 (Div. 2)
Difficulty rating: 1000
Tags: implementation, sortings

Petya and Vasya decided to play a game. They have n cards (n is an even number). A single integer is written on each card.

Before the game Petya will choose an integer and after that Vasya will choose another integer (different from the number that Petya chose). During the game each player takes all the cards with number he chose. For example, if Petya chose number 5 before the game he will take all cards on which 5 is written and if Vasya chose number 10 before the game he will take all cards on which 10 is written.

The game is considered fair if Petya and Vasya can take all n cards, and the number of cards each player gets is the same.

Determine whether Petya and Vasya can choose integer numbers before the game so that the game is fair.

Input format:
The first line contains a single integer n (2 ≤ n ≤ 100) — number of cards. It is guaranteed that n is an even number.

The following n lines contain a sequence of integers a1, a2, ..., an (one integer per line, 1 ≤ ai ≤ 100) — numbers written on the n cards.

Output format:
If it is impossible for Petya and Vasya to choose numbers in such a way that the game will be fair, print "NO" (without quotes) in the first line. In this case you should not print anything more.

In the other case print "YES" (without quotes) in the first line. In the second line print two distinct integers — number that Petya should choose and the number that Vasya should choose to make the game fair. If there are several solutions, print any of them.

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

Note:
In the first example the game will be fair if, for example, Petya chooses number 11, and Vasya chooses number 27. Then the will take all cards — Petya will take cards 1 and 4, and Vasya will take cards 2 and 3. Thus, each of them will take exactly two cards.

In the second example fair game is impossible because the numbers written on the cards are equal, but the numbers that Petya and Vasya should choose should be distinct.

In the third example it is impossible to take all cards. Petya and Vasya can take at most five cards — for example, Petya can choose number 10 and Vasya can choose number 20. But for the game to be fair it is necessary to take 6 cards.

Example input:
4
11
27
27
11

Example output:
YES
11 27

Example input:
2
6
6

Example output:
NO

Editorial:
This problem has many different solutions. Let's consider one of them.
At first sort all numbers in non-descending order. Then the first n / 2 numbers must be equal to each other, the following n / 2 numbers must be equal to each other, and the number from the first half must be different from the number from the second half. So, if all conditions:
• a[1] = a[n / 2]
• a[n / 2 + 1] = a[n]
• a[1] ≠ a[n]
are met after sorting, the answer is «YES». Vasya must choose before the game number a[1] and Petya — a[n] (or vice versa). If at least one from the described conditions is failed, the answer is «NO».
Polycarp and Letters
Contest: Codeforces Round 436 (Div. 2)
Difficulty rating: 1000
Tags: brute force, implementation, strings

Polycarp loves lowercase letters and dislikes uppercase ones. Once he got a string s consisting only of lowercase and uppercase Latin letters.

Let A be a set of positions in the string. Let's call it pretty if following conditions are met:

- letters on positions from A in the string are all distinct and lowercase;
- there are no uppercase letters in the string which are situated between positions from A (i.e. there is no such j that s[j] is an uppercase letter, and a1 < j < a2 for some a1 and a2 from A).

Write a program that will determine the maximum number of elements in a pretty set of positions.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 200) — length of string s.

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

Output format:
Print maximum number of elements in pretty set of positions for string s.

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

Note:
In the first example the desired positions might be 6 and 8 or 7 and 8. Positions 6 and 7 contain letters 'a', position 8 contains letter 'b'. The pair of positions 1 and 8 is not suitable because there is an uppercase letter 'B' between these position.

In the second example desired positions can be 7, 8 and 11. There are other ways to choose pretty set consisting of three elements.

In the third example the given string s does not contain any lowercase letters, so the answer is 0.

Example input:
11
aaaaBaabAbA

Example output:
2

Example input:
12
zACaAbbaazzC

Example output:
3

Editorial:
Let's solve the given problem in the following way. We will iterate through the letters in the string in order from left to right.
If we are in position pos and the next letter is uppercase we skip it. In the other case, we need to create set and put letter spos in it. After that we iterate through string to the right until we do not met uppercase letter or until the string does not ended. We put in set each new lowercase letter. After we met uppercase letter (let position of this letter is p), or string is ended, we update the answer with the number of elements in set, and repeat described algorithm starting from position p.
Make a Permutation!
Contest: Codeforces Round 436 (Div. 2)
Difficulty rating: 1500
Tags: greedy, implementation, math

Ivan has an array consisting of n elements. Each of the elements is an integer from 1 to n.

Recently Ivan learned about permutations and their lexicographical order. Now he wants to change (replace) minimum number of elements in his array in such a way that his array becomes a permutation (i.e. each of the integers from 1 to n was encountered in his array exactly once). If there are multiple ways to do it he wants to find the lexicographically minimal permutation among them.

Thus minimizing the number of changes has the first priority, lexicographical minimizing has the second priority.

In order to determine which of the two permutations is lexicographically smaller, we compare their first elements. If they are equal — compare the second, and so on. If we have two permutations x and y, then x is lexicographically smaller if xi < yi, where i is the first index in which the permutations x and y differ.

Determine the array Ivan will obtain after performing all the changes.

Input format:
The first line contains an single integer n (2 ≤ n ≤ 200 000) — the number of elements in Ivan's array.

The second line contains a sequence of integers a1, a2, ..., an (1 ≤ ai ≤ n) — the description of Ivan's array.

Output format:
In the first line print q — the minimum number of elements that need to be changed in Ivan's array in order to make his array a permutation. In the second line, print the lexicographically minimal permutation which can be obtained from array with q changes.

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

Note:
In the first example Ivan needs to replace number three in position 1 with number one, and number two in position 3 with number four. Then he will get a permutation [1, 2, 4, 3] with only two changed numbers — this permutation is lexicographically minimal among all suitable.

In the second example Ivan does not need to change anything because his array already is a permutation.

Example input:
4
3 2 2 3

Example output:
2
1 2 4 3

Example input:
6
4 5 6 3 2 1

Example output:
0
4 5 6 3 2 1

Editorial:
We will use an array cnt where we will store how many times the numbers from 1 to n met in the given array a. Put all numbers that never occur in the array a in a vector need — we must add this numbers in the array a to make a permutation.
We will add numbers from need in ascending order because we want to get lexicographically minimal permutation. Let pos is a pointer on the current number needpos which we need to add on the current move. Initially, pos = 0.
We will iterate through the array a. Let the current number equals to ai. If cntai = 1, we move to the next number in the array. If we added not all numbers from need, and ai > needpos or there already was ai on the prefix of the array (to check it we can use, for example, boolean array), then we put needpos in the current position, decrease cntai on one, increase pos and answer on one. If we do not change anything on that step we mark that ai already was on the prefix of the array. After that we move to the next number in array a.
Fire
Contest: Codeforces Round 436 (Div. 2)
Difficulty rating: 2000
Tags: dp, sortings

Polycarp is in really serious trouble — his house is on fire! It's time to save the most valuable items. Polycarp estimated that it would take ti seconds to save i-th item. In addition, for each item, he estimated the value of di — the moment after which the item i will be completely burned and will no longer be valuable for him at all. In particular, if ti ≥ di, then i-th item cannot be saved.

Given the values pi for each of the items, find a set of items that Polycarp can save such that the total value of this items is maximum possible. Polycarp saves the items one after another. For example, if he takes item a first, and then item b, then the item a will be saved in ta seconds, and the item b — in ta + tb seconds after fire started.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 100) — the number of items in Polycarp's house.

Each of the following n lines contains three integers ti, di, pi (1 ≤ ti ≤ 20, 1 ≤ di ≤ 2 000, 1 ≤ pi ≤ 20) — the time needed to save the item i, the time after which the item i will burn completely and the value of item i.

Output format:
In the first line print the maximum possible total value of the set of saved items. In the second line print one integer m — the number of items in the desired set. In the third line print m distinct integers — numbers of the saved items in the order Polycarp saves them. Items are 1-indexed in the same order in which they appear in the input. If there are several answers, print any of them.

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

Note:
In the first example Polycarp will have time to save any two items, but in order to maximize the total value of the saved items, he must save the second and the third item. For example, he can firstly save the third item in 3 seconds, and then save the second item in another 2 seconds. Thus, the total value of the saved items will be 6 + 5 = 11.

In the second example Polycarp can save only the first item, since even if he immediately starts saving the second item, he can save it in 3 seconds, but this item will already be completely burned by this time.

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

Example output:
11
2
2 3

Example input:
2
5 6 1
3 3 5

Example output:
1
1
1

Editorial:
If Polycarp will save two items, it is more profitable to first save the one whose d parameter is less. So, you can sort items by the parameter d.
Let dpi, j be the maximum total value of items Polycarp can save by checking first i - 1 items in j seconds. Here are two types of transitions. Polycarp can either save current item or skip it:
• dpi + 1, j + ti = max(dpi + 1, j + ti, dpi, j + pi), if j + ti < di
• dpi + 1, j = max(dpi + 1, j, dpi, j)
To restore the sequence of items Polycarp can save you can remember for each pair (i, j) whether you took a thing with the number i - 1 when updating the value dpi, j.
Overall complexity: O(n·max1 ≤ i ≤ ndi).
Big Problems for Organizers
Contest: RCC 2014 Warmup (Div. 1)
Difficulty rating: 2800
Tags: data structures, graphs, trees

The Finals of the "Russian Code Cup" 2214 will be held in n hotels. Two hotels (let's assume that they are the main hotels), will host all sorts of events, and the remaining hotels will accommodate the participants. The hotels are connected by n - 1 roads, you can get from any hotel to any other one.

The organizers wonder what is the minimum time all the participants need to get to the main hotels, if each participant goes to the main hotel that is nearest to him and moving between two hotels connected by a road takes one unit of time.

The hosts consider various options for the location of the main hotels. For each option help the organizers to find minimal time.

Input format:
The first line contains an integer n (2 ≤ n ≤ 100000) — the number of hotels. The next n - 1 lines contain two integers each  — the numbers of the hotels that have a road between them. Consider hotels are numbered from 1 to n.

The next line contains an integer m (1 ≤ m ≤ 100000) — the number of queries. The following m lines contains two distinct integers each — the numbers of the hotels we assume to be the main.

Output format:
For each request of the organizers print a single integer — the time that all participants need to reach the main hotels.

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

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

Example output:
1
1
1

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

Example output:
2
1
2

Editorial:
Tricky Password
Contest: RCC 2014 Warmup (Div. 1)
Difficulty rating: 3100
Tags: data structures

In order to ensure confidentiality, the access to the "Russian Code Cup" problems is password protected during the problem development process.

To select a password, the jury can generate a special table that contains n columns and the infinite number of rows. To construct a table, the first row is fixed, and all the others are obtained by the following rule:

In the row i at position p there is a number equal to the number of times a[i - 1][p] occurs on the prefix a[i - 1][1... p].

To ensure the required level of confidentiality, the jury must be able to perform the following operations:

- Replace number a[1][p] by v and rebuild the table.
- Find the number a[x][y], which will be the new password.

Doing all these steps manually is very tedious, so the jury asks you to help him. Write a program that responds to the request of the jury.

Input format:
The first line contains an integer n (1 ≤ n ≤ 100000) — the number of columns. The second line contains the description of the first row of the table, that is, n integers, which are not less than 1 and do not exceed 109.

The third line of the input contains an integer m (1 ≤ m ≤ 100000) — the number of requests.

Next, each row contains a description of the request, which consists of three integers:

- If the first number is equal to 1, then the remaining two numbers are v, p (1 ≤ v ≤ 109; 1 ≤ p ≤ n). So, you should put value v in the position p in the first row.
- If the first number is equal to 2, then the remaining two numbers are x, y (1 ≤ x ≤ 105; 1 ≤ y ≤ n) — the row and column of the table cell from which you want to get value.

Output format:
Print an answer for each request of the second type in the order you receive them.

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

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

Example output:
2
1

Editorial:
Arrival of the General
Contest: Codeforces Round 103 (Div. 2)
Difficulty rating: 800
Tags: implementation

A Ministry for Defense sent a general to inspect the Super Secret Military Squad under the command of the Colonel SuperDuper. Having learned the news, the colonel ordered to all n squad soldiers to line up on the parade ground.

By the military charter the soldiers should stand in the order of non-increasing of their height. But as there's virtually no time to do that, the soldiers lined up in the arbitrary order. However, the general is rather short-sighted and he thinks that the soldiers lined up correctly if the first soldier in the line has the maximum height and the last soldier has the minimum height. Please note that the way other solders are positioned does not matter, including the case when there are several soldiers whose height is maximum or minimum. Only the heights of the first and the last soldier are important.

For example, the general considers the sequence of heights (4, 3, 4, 2, 1, 1) correct and the sequence (4, 3, 1, 2, 2) wrong.

Within one second the colonel can swap any two neighboring soldiers. Help him count the minimum time needed to form a line-up which the general will consider correct.

Input format:
The first input line contains the only integer n (2 ≤ n ≤ 100) which represents the number of soldiers in the line. The second line contains integers a1, a2, ..., an (1 ≤ ai ≤ 100) the values of the soldiers' heights in the order of soldiers' heights' increasing in the order from the beginning of the line to its end. The numbers are space-separated. Numbers a1, a2, ..., an are not necessarily different.

Output format:
Print the only integer — the minimum number of seconds the colonel will need to form a line-up the general will like.

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

Note:
In the first sample the colonel will need to swap the first and second soldier and then the third and fourth soldier. That will take 2 seconds. The resulting position of the soldiers is (44, 33, 22, 11).

In the second sample the colonel may swap the soldiers in the following sequence:

1. (10, 10, 58, 31, 63, 40, 76)
2. (10, 58, 10, 31, 63, 40, 76)
3. (10, 58, 10, 31, 63, 76, 40)
4. (10, 58, 10, 31, 76, 63, 40)
5. (10, 58, 31, 10, 76, 63, 40)
6. (10, 58, 31, 76, 10, 63, 40)
7. (10, 58, 31, 76, 63, 10, 40)
8. (10, 58, 76, 31, 63, 10, 40)
9. (10, 76, 58, 31, 63, 10, 40)
10. (76, 10, 58, 31, 63, 10, 40)
11. (76, 10, 58, 31, 63, 40, 10)

Example input:
4
33 44 11 22

Example output:
2

Example input:
7
10 10 58 31 63 40 76

Example output:
10

Editorial:
Meeting
Contest: Codeforces Round 103 (Div. 2)
Difficulty rating: 1300
Tags: implementation

The Super Duper Secret Meeting of the Super Duper Secret Military Squad takes place in a Super Duper Secret Place. The place is an infinite plane with introduced Cartesian coordinate system. The meeting table is represented as a rectangle whose sides are parallel to the coordinate axes and whose vertexes are located at the integer points of the plane. At each integer point which belongs to the table perimeter there is a chair in which a general sits.

Some points on the plane contain radiators for the generals not to freeze in winter. Each radiator is characterized by the number ri — the radius of the area this radiator can heat. That is, if the distance between some general and the given radiator is less than or equal to ri, than the general feels comfortable and warm. Here distance is defined as Euclidean distance, so the distance between points (x1, y1) and (x2, y2) is $$\sqrt{(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}}$$

Each general who is located outside the radiators' heating area can get sick. Thus, you should bring him a warm blanket. Your task is to count the number of warm blankets you should bring to the Super Duper Secret Place.

The generals who are already comfortable do not need a blanket. Also the generals never overheat, ever if they are located in the heating area of several radiators. The radiators can be located at any integer points on the plane, even inside the rectangle (under the table) or on the perimeter (directly under some general). Even in this case their radius does not change.

Input format:
The first input line contains coordinates of two opposite table corners xa, ya, xb, yb (xa ≠ xb, ya ≠ yb). The second line contains integer n — the number of radiators (1 ≤ n ≤ 103). Then n lines contain the heaters' coordinates as "xi yi ri", the numbers are separated by spaces. All input data numbers are integers. The absolute value of all coordinates does not exceed 1000, 1 ≤ ri ≤ 1000. Several radiators can be located at the same point.

Output format:
Print the only number — the number of blankets you should bring.

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

Note:
In the first sample the generals are sitting at points: (2, 2), (2, 3), (2, 4), (2, 5), (3, 2), (3, 5), (4, 2), (4, 3), (4, 4), (4, 5). Among them, 4 generals are located outside the heating range. They are the generals at points: (2, 5), (3, 5), (4, 4), (4, 5).

In the second sample the generals are sitting at points: (5, 2), (5, 3), (6, 2), (6, 3). All of them are located inside the heating range.

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

Example output:
4

Example input:
5 2 6 3
2
6 2 2
6 5 3

Example output:
0

Editorial:
Anagram Search
Contest: Codeforces Round 103 (Div. 2)
Difficulty rating: 1500
Tags: implementation, strings

A string t is called an anagram of the string s, if it is possible to rearrange letters in t so that it is identical to the string s. For example, the string "aab" is an anagram of the string "aba" and the string "aaa" is not.

The string t is called a substring of the string s if it can be read starting from some position in the string s. For example, the string "aba" has six substrings: "a", "b", "a", "ab", "ba", "aba".

You are given a string s, consisting of lowercase Latin letters and characters "?". You are also given a string p, consisting of lowercase Latin letters only. Let's assume that a string is good if you can obtain an anagram of the string p from it, replacing the "?" characters by Latin letters. Each "?" can be replaced by exactly one character of the Latin alphabet. For example, if the string p = «aba», then the string "a??" is good, and the string «?bc» is not.

Your task is to find the number of good substrings of the string s (identical substrings must be counted in the answer several times).

Input format:
The first line is non-empty string s, consisting of no more than 105 lowercase Latin letters and characters "?". The second line is non-empty string p, consisting of no more than 105 lowercase Latin letters. Please note that the length of the string p can exceed the length of the string s.

Output format:
Print the single number representing the number of good substrings of string s.

Two substrings are considered different in their positions of occurrence are different. Thus, if some string occurs several times, then it should be counted the same number of times.

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

Note:
Consider the first sample test. Here the string s has two good substrings: "b??" (after we replace the question marks we get "baa"), "???" (after we replace the question marks we get "baa").

Let's consider the second sample test. Here the string s has two good substrings: "ab?" ("?" can be replaced by "c"), "b?c" ("?" can be replaced by "a").

Example input:
bb??x???
aab

Example output:
2

Example input:
ab?c
acb

Example output:
2

Editorial: