1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Sanatorium
Contest: Codeforces Round 377 (Div. 2)
Difficulty rating: 1200
Tags: binary search, constructive algorithms, greedy, implementation, math

Vasiliy spent his vacation in a sanatorium, came back and found that he completely forgot details of his vacation!

Every day there was a breakfast, a dinner and a supper in a dining room of the sanatorium (of course, in this order). The only thing that Vasiliy has now is a card from the dining room contaning notes how many times he had a breakfast, a dinner and a supper (thus, the card contains three integers). Vasiliy could sometimes have missed some meal, for example, he could have had a breakfast and a supper, but a dinner, or, probably, at some days he haven't been at the dining room at all.

Vasiliy doesn't remember what was the time of the day when he arrived to sanatorium (before breakfast, before dinner, before supper or after supper), and the time when he left it (before breakfast, before dinner, before supper or after supper). So he considers any of these options. After Vasiliy arrived to the sanatorium, he was there all the time until he left. Please note, that it's possible that Vasiliy left the sanatorium on the same day he arrived.

According to the notes in the card, help Vasiliy determine the minimum number of meals in the dining room that he could have missed. We shouldn't count as missed meals on the arrival day before Vasiliy's arrival and meals on the departure day after he left.

Input format:
The only line contains three integers b, d and s (0 ≤ b, d, s ≤ 1018,  b + d + s ≥ 1) — the number of breakfasts, dinners and suppers which Vasiliy had during his vacation in the sanatorium.

Output format:
Print single integer — the minimum possible number of meals which Vasiliy could have missed during his vacation.

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

Note:
In the first sample, Vasiliy could have missed one supper, for example, in case he have arrived before breakfast, have been in the sanatorium for two days (including the day of arrival) and then have left after breakfast on the third day.

In the second sample, Vasiliy could have arrived before breakfast, have had it, and immediately have left the sanatorium, not missing any meal.

In the third sample, Vasiliy could have been in the sanatorium for one day, not missing any meal.

Example input:
3 2 1

Example output:
1

Example input:
1 0 0

Example output:
0

Editorial:
Let's iterate on the time of day when Vasiliy arrived at the sanatorium (breakfast, dinner or supper) and on the time when Vasiliy left. We sum the changed values of b, d and s (considering that we take all possible meals during the first and the last day) into the variable sum, find mx — the maximum of these three variables (also changed), and if our current answer is more than 3·mx - sum, we update it with this value. After considering all 9 possible scenarios, we print the answer.
Time complexity: O(const), const = 33.
Exams
Contest: Codeforces Round 377 (Div. 2)
Difficulty rating: 1700
Tags: binary search, greedy, sortings

Vasiliy has an exam period which will continue for n days. He has to pass exams on m subjects. Subjects are numbered from 1 to m.

About every day we know exam for which one of m subjects can be passed on that day. Perhaps, some day you can't pass any exam. It is not allowed to pass more than one exam on any day.

On each day Vasiliy can either pass the exam of that day (it takes the whole day) or prepare all day for some exam or have a rest.

About each subject Vasiliy know a number ai — the number of days he should prepare to pass the exam number i. Vasiliy can switch subjects while preparing for exams, it is not necessary to prepare continuously during ai days for the exam number i. He can mix the order of preparation for exams in any way.

Your task is to determine the minimum number of days in which Vasiliy can pass all exams, or determine that it is impossible. Each exam should be passed exactly one time.

Input format:
The first line contains two integers n and m (1 ≤ n, m ≤ 105) — the number of days in the exam period and the number of subjects.

The second line contains n integers d1, d2, ..., dn (0 ≤ di ≤ m), where di is the number of subject, the exam of which can be passed on the day number i. If di equals 0, it is not allowed to pass any exams on the day number i.

The third line contains m positive integers a1, a2, ..., am (1 ≤ ai ≤ 105), where ai is the number of days that are needed to prepare before passing the exam on the subject i.

Output format:
Print one integer — the minimum number of days in which Vasiliy can pass all exams. If it is impossible, print -1.

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

Note:
In the first example Vasiliy can behave as follows. On the first and the second day he can prepare for the exam number 1 and pass it on the fifth day, prepare for the exam number 2 on the third day and pass it on the fourth day.

In the second example Vasiliy should prepare for the exam number 3 during the first four days and pass it on the fifth day. Then on the sixth day he should prepare for the exam number 2 and then pass it on the seventh day. After that he needs to prepare for the exam number 1 on the eighth day and pass it on the ninth day.

In the third example Vasiliy can't pass the only exam because he hasn't anough time to prepare for it.

Example input:
7 2
0 1 0 2 1 0 2
2 1

Example output:
5

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

Example output:
9

Editorial:
Let's use binary search to find the answer (the latest day when we have passed all the exams). To check whether we can pass all the exams until some fixed day x, we will take all the examples as late as possible. We will prepare to the earliest exam, then to the second earliest, and so on. If we are not ready for some exam or if we don't pass them until the day x ends, then we can't pass all the exams in time. After finishing our binary search we print the answer.
Time complexity: O(mlogn).
Tourist Reform
Contest: Codeforces Round 377 (Div. 2)
Difficulty rating: 2300
Tags: dfs and similar, graphs

Berland is a tourist country! At least, it can become such — the government of Berland is confident about this.

There are n cities in Berland, some pairs of which are connected by two-ways roads. Each road connects two different cities. In Berland there are no roads which connect the same pair of cities. It is possible to get from any city to any other city using given two-ways roads.

According to the reform each road will become one-way. It will be oriented to one of two directions.

To maximize the tourist attraction of Berland, after the reform for each city i the value ri will be calculated. It will equal to the number of cities x for which there is an oriented path from the city i to the city x. In other words, ri will equal the number of cities which can be reached from the city i by roads.

The government is sure that tourist's attention will be focused on the minimum value of ri.

Help the government of Berland make the reform to maximize the minimum of ri.

Input format:
The first line contains two integers n, m (2 ≤ n ≤ 400 000, 1 ≤ m ≤ 400 000) — the number of cities and the number of roads.

The next m lines describe roads in Berland: the j-th of them contains two integers uj and vj (1 ≤ uj, vj ≤ n, uj ≠ vj), where uj and vj are the numbers of cities which are connected by the j-th road.

The cities are numbered from 1 to n. It is guaranteed that it is possible to get from any city to any other by following two-ways roads. In Berland there are no roads which connect the same pair of cities.

Output format:
In the first line print single integer — the maximum possible value min1 ≤ i ≤ n{ri} after the orientation of roads.

The next m lines must contain the description of roads after the orientation: the j-th of them must contain two integers uj, vj, it means that the j-th road will be directed from the city uj to the city vj. Print roads in the same order as they are given in the input data.

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

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

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

Editorial:
Firstly, we have to find all the bridges and divide the graph into 2"=edge"=connected components. Then we calculate the size of each component. It can be easily proved that the answer is equal to size of the largest component. Then we need to orient the edges somehow. Start DFS from any vertex of the largest component. If we traverse the edge (v, to) (coming from vertex v) and it has not been oriented yet, we orient it from to to v, if it's a bridge (so it leads to the largest component) or from v to to otherwise. When all vertices are visited and all edges are oriented, we can print the answer.
Time complexity: O(n + m).
Da Vinci Powers
Contest: April Fools Day Contest 2016
Difficulty rating: 1900
Tags: *special

Input format:
The input contains a single integer a (0 ≤ a ≤ 35).

Output format:
Output a single integer.

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

Example input:
3

Example output:
8

Example input:
10

Example output:
1024

Editorial:
Scrambled
Contest: April Fools Day Contest 2016
Difficulty rating: 1700
Tags: *special, implementation

Btoh yuo adn yuor roomatme lhoate wianshg disehs, btu stlil sdmoeboy msut peorrfm tihs cohre dialy. Oen dya yuo decdie to idourtcne smoe syestm. Yuor rmmotaoe sstgegus teh fooniwllg dael. Yuo argee on tow arayrs of ientgres M adn R, nmebur upmicnog dyas (induiclng teh cunrret oen) wtih sicsescuve irnegets (teh ceurrnt dya is zreo), adn yuo wsah teh diehss on dya D if adn olny if terhe etsixs an iednx i scuh taht D mod M[i] = R[i], otwsehrie yuor rmootmae deos it. Yuo lkie teh cncepot, btu yuor rmotaome's cuinnng simle meaks yuo ssecupt sthnoemig, so yuo itennd to vefriy teh fnerisas of teh aemnrgeet.

Yuo aer geivn ayarrs M adn R. Cuaclatle teh pceanregte of dyas on wchih yuo edn up dnoig teh wisahng. Amsuse taht yuo hvae iiiftlneny mnay dyas aehad of yuo.

Input format:
The first line of input contains a single integer N (1 ≤ N ≤ 16).

The second and third lines of input contain N integers each, all between 0 and 16, inclusive, and represent arrays M and R, respectively. All M[i] are positive, for each i R[i] < M[i].

Output format:
Output a single real number. The answer is considered to be correct if its absolute or relative error does not exceed 10 - 4.

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

Example input:
1
2
0

Example output:
0.500000

Example input:
2
2 3
1 0

Example output:
0.666667

Editorial:
Without Text
Contest: April Fools Day Contest 2016
Difficulty rating: 2000
Tags: *special

You can preview the image in better quality by the link: http://assets.codeforces.com/files/656/without-text.png

Input format:
The only line of the input is a string (between 1 and 50 characters long, inclusive). Each character will be an alphanumeric character or a full stop ".".

Output format:
Output the required answer.

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

Example input:
Codeforces

Example output:
-87

Example input:
APRIL.1st

Example output:
17

Editorial:
Rosetta Problem
Contest: April Fools Day Contest 2016
Difficulty rating: 2100
Tags: *special

Input format:
The input contains a single integer a (0 ≤ a ≤ 1 000 000).

Output format:
Output a single integer.

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

Example input:
129

Example output:
1

Editorial:
Out of Controls
Contest: April Fools Day Contest 2016
Difficulty rating: 2000
Tags: *special

You are given a complete undirected graph. For each pair of vertices you are given the length of the edge that connects them. Find the shortest paths between each pair of vertices in the graph and return the length of the longest of them.

Input format:
The first line of the input contains a single integer N (3 ≤ N ≤ 10).

The following N lines each contain N space-separated integers. jth integer in ith line aij is the length of the edge that connects vertices i and j. aij = aji, aii = 0, 1 ≤ aij ≤ 100 for i ≠ j.

Output format:
Output the maximum length of the shortest path between any pair of vertices in the graph.

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

Note:
You're running short of keywords, so you can't use some of them:

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

Example output:
2

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

Example output:
5

Editorial:
Ace It!
Contest: April Fools Day Contest 2016
Difficulty rating: 1900
Tags: *special

Input format:
The only line of the input is a string of 7 characters. The first character is letter A, followed by 6 digits. The input is guaranteed to be valid (for certain definition of "valid").

Output format:
Output a single integer.

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

Example input:
A221033

Example output:
21

Example input:
A223635

Example output:
22

Editorial:
You're a Professional
Contest: April Fools Day Contest 2016
Difficulty rating: 1900
Tags: *special

A simple recommendation system would recommend a user things liked by a certain number of their friends. In this problem you will implement part of such a system.

You are given user's friends' opinions about a list of items. You are also given a threshold T — the minimal number of "likes" necessary for an item to be recommended to the user.

Output the number of items in the list liked by at least T of user's friends.

Input format:
The first line of the input will contain three space-separated integers: the number of friends F (1 ≤ F ≤ 10), the number of items I (1 ≤ I ≤ 10) and the threshold T (1 ≤ T ≤ F).

The following F lines of input contain user's friends' opinions. j-th character of i-th line is 'Y' if i-th friend likes j-th item, and 'N' otherwise.

Output format:
Output an integer — the number of items liked by at least T of user's friends.

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

Example input:
3 3 2
YYY
NNN
YNY

Example output:
2

Example input:
4 4 1
NNNY
NNYN
NYNN
YNNN

Example output:
4

Editorial:
Ehab Fails to Be Thanos
Contest: Codeforces Round 563 (Div. 2)
Difficulty rating: 1000
Tags: constructive algorithms, greedy, sortings

You're given an array $$$a$$$ of length $$$2n$$$. Is it possible to reorder it in such way so that the sum of the first $$$n$$$ elements isn't equal to the sum of the last $$$n$$$ elements?

Input format:
The first line contains an integer $$$n$$$ ($$$1 \le n \le 1000$$$), where $$$2n$$$ is the number of elements in the array $$$a$$$.

The second line contains $$$2n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{2n}$$$ ($$$1 \le a_i \le 10^6$$$) — the elements of the array $$$a$$$.

Output format:
If there's no solution, print "-1" (without quotes). Otherwise, print a single line containing $$$2n$$$ space-separated integers. They must form a reordering of $$$a$$$. You are allowed to not change the order.

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

Note:
In the first example, the first $$$n$$$ elements have sum $$$2+1+3=6$$$ while the last $$$n$$$ elements have sum $$$1+1+2=4$$$. The sums aren't equal.

In the second example, there's no solution.

Example input:
3
1 2 2 1 3 1

Example output:
2 1 3 1 1 2

Example input:
1
1 1

Example output:
-1

Editorial:
If all elements in the array are equal, there's no solution. Otherwise, sort the array. The sum of the second half will indeed be greater than that of the first half.
Another solution is to see if they already have different sums. If they do, print the array as it is. Otherwise, find any pair of different elements from different halves and swap them.
Code link:
Ehab Is an Odd Person
Contest: Codeforces Round 563 (Div. 2)
Difficulty rating: 1200
Tags: sortings

You're given an array $$$a$$$ of length $$$n$$$. You can perform the following operation on it as many times as you want:

- Pick two integers $$$i$$$ and $$$j$$$ $$$(1 \le i,j \le n)$$$ such that $$$a_i+a_j$$$ is odd, then swap $$$a_i$$$ and $$$a_j$$$.

What is lexicographically the smallest array you can obtain?

An array $$$x$$$ is lexicographically smaller than an array $$$y$$$ if there exists an index $$$i$$$ such that $$$x_i<y_i$$$, and $$$x_j=y_j$$$ for all $$$1 \le j < i$$$. Less formally, at the first index $$$i$$$ in which they differ, $$$x_i<y_i$$$

Input format:
The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of elements in the array $$$a$$$.

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 $$$a$$$.

Output format:
The only line contains $$$n$$$ space-separated integers, the lexicographically smallest array you can obtain.

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

Note:
In the first example, we can swap $$$1$$$ and $$$4$$$ since $$$1+4=5$$$, which is odd.

Example input:
3
4 1 7

Example output:
1 4 7

Example input:
2
1 1

Example output:
1 1

Editorial:
Notice that you can only swap 2 elements if they have different parities. If all elements in the array have the same parity, you can't do any swaps, and the answer will just be like the input. Otherwise, let's prove you can actually swap any pair of elements. Assume you want to swap 2 elements, $$$a$$$ and $$$b$$$, and they have the same parity. There must be a third element $$$c$$$ that has a different parity. Without loss of generality, assume the array is $$$[a,b,c]$$$. You'll do the following swaps:
• Swap $$$a$$$ and $$$c$$$: $$$[c,b,a]$$$.
• Swap $$$b$$$ and $$$c$$$: $$$[b,c,a]$$$.
• Swap $$$a$$$ and $$$c$$$: $$$[b,a,c]$$$.
In other words, you'll use $$$c$$$ as an intermediate element to swap $$$a$$$ and $$$b$$$, and it'll return to its original position afterwards! Since you can swap any pair of elements, you can always sort the array, which is the lexicographically smallest permutation.
Code link:
Time complexity: $$$O(nlog(n))$$$.
Ehab and a Special Coloring Problem
Contest: Codeforces Round 563 (Div. 2)
Difficulty rating: 1300
Tags: constructive algorithms, number theory

You're given an integer $$$n$$$. For every integer $$$i$$$ from $$$2$$$ to $$$n$$$, assign a positive integer $$$a_i$$$ such that the following conditions hold:

- For any pair of integers $$$(i,j)$$$, if $$$i$$$ and $$$j$$$ are coprime, $$$a_i \neq a_j$$$.
- The maximal value of all $$$a_i$$$ should be minimized (that is, as small as possible).

A pair of integers is called coprime if their greatest common divisor is $$$1$$$.

Input format:
The only line contains the integer $$$n$$$ ($$$2 \le n \le 10^5$$$).

Output format:
Print $$$n-1$$$ integers, $$$a_2$$$, $$$a_3$$$, $$$\ldots$$$, $$$a_n$$$ ($$$1 \leq a_i \leq n$$$).

If there are multiple solutions, print any of them.

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

Note:
In the first example, notice that $$$3$$$ and $$$4$$$ are coprime, so $$$a_3 \neq a_4$$$. Also, notice that $$$a=[1,2,3]$$$ satisfies the first condition, but it's not a correct answer because its maximal value is $$$3$$$.

Example input:
4

Example output:
1 2 1

Example input:
3

Example output:
2 1

Editorial:
Let's call the maximum value in the array $$$max$$$. Let the number of primes less than or equal to $$$n$$$ be called $$$p$$$. Then, $$$max \ge p$$$. That's true because a distinct number must be assigned to each prime, since all primes are coprime to each other. Now if we can construct an answer wherein $$$max=p$$$, it'll be optimal. Let's first assign a distinct number to each prime. Then, assign to every composite number the same number as any of its prime divisors. This works because for any pair of numbers $$$(i,j)$$$, $$$i$$$ is given the same number of a divisor and so is $$$j$$$, so if they're coprime (don't share a divisor), they can't be given the same number!
Code link:
Time complexity: $$$O(nlog(n))$$$.
Ehab and the Expected XOR Problem
Contest: Codeforces Round 563 (Div. 2)
Difficulty rating: 1900
Tags: bitmasks, constructive algorithms

Given two integers $$$n$$$ and $$$x$$$, construct an array that satisfies the following conditions:

- for any element $$$a_i$$$ in the array, $$$1 \le a_i<2^n$$$;
- there is no non-empty subsegment with bitwise XOR equal to $$$0$$$ or $$$x$$$,
- its length $$$l$$$ should be maximized.

A sequence $$$b$$$ is a subsegment of a sequence $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input format:
The only line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 18$$$, $$$1 \le x<2^{18}$$$).

Output format:
The first line should contain the length of the array $$$l$$$.

If $$$l$$$ is positive, the second line should contain $$$l$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\dots$$$, $$$a_l$$$ ($$$1 \le a_i < 2^n$$$) — the elements of the array $$$a$$$.

If there are multiple solutions, print any of them.

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

Note:
In the first example, the bitwise XOR of the subsegments are $$$\{6,7,4,1,2,3\}$$$.

Example input:
3 5

Example output:
3
6 1 3

Example input:
2 4

Example output:
3
1 3 1

Editorial:
The main idea is to build the prefix-xor of the array, not the array itself, then build the array from it. Let the prefix-xor array be called $$$b$$$. Now, $$$a_l \oplus a_{l+1} \dots \oplus a_r=b_{l-1} \oplus b_{r}$$$. Thus, the problem becomes: construct an array such that no pair of numbers has bitwise-xor sum equal to 0 or $$$x$$$, and its length should be maximal. Notice that "no pair of numbers has bitwise-xor sum equal to 0" simply means "you can't use the same number twice". If $$$x \ge 2^n$$$, no pair of numbers less than $$$2^n$$$ will have bitwise-xor sum equal to $$$x$$$, so you can just use all the numbers from 1 to $$$2^n-1$$$ in any order. Otherwise, you can think of the numbers forming pairs, where each pair consists of 2 numbers with bitwise-xor sum equal to $$$x$$$. From any pair, if you add one number to the array, you can't add the other. However, the pairs are independent from each other: your choice in one pair doesn't affect any other pair. Thus, you can just choose either number in any pair and add them in any order you want. After you construct $$$b$$$, you can construct $$$a$$$ using the formula: $$$a_i=b_i \oplus b_{i-1}$$$.
Code link:
Time complexity: $$$O(2^n)$$$.
Ehab and the Expected GCD Problem
Contest: Codeforces Round 563 (Div. 2)
Difficulty rating: 2500
Tags: combinatorics, dp, math, number theory

Let's define a function $$$f(p)$$$ on a permutation $$$p$$$ as follows. Let $$$g_i$$$ be the greatest common divisor (GCD) of elements $$$p_1$$$, $$$p_2$$$, ..., $$$p_i$$$ (in other words, it is the GCD of the prefix of length $$$i$$$). Then $$$f(p)$$$ is the number of distinct elements among $$$g_1$$$, $$$g_2$$$, ..., $$$g_n$$$.

Let $$$f_{max}(n)$$$ be the maximum value of $$$f(p)$$$ among all permutations $$$p$$$ of integers $$$1$$$, $$$2$$$, ..., $$$n$$$.

Given an integers $$$n$$$, count the number of permutations $$$p$$$ of integers $$$1$$$, $$$2$$$, ..., $$$n$$$, such that $$$f(p)$$$ is equal to $$$f_{max}(n)$$$. Since the answer may be large, print the remainder of its division by $$$1000\,000\,007 = 10^9 + 7$$$.

Input format:
The only line contains the integer $$$n$$$ ($$$2 \le n \le 10^6$$$) — the length of the permutations.

Output format:
The only line should contain your answer modulo $$$10^9+7$$$.

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

Note:
Consider the second example: these are the permutations of length $$$3$$$:

- $$$[1,2,3]$$$, $$$f(p)=1$$$.
- $$$[1,3,2]$$$, $$$f(p)=1$$$.
- $$$[2,1,3]$$$, $$$f(p)=2$$$.
- $$$[2,3,1]$$$, $$$f(p)=2$$$.
- $$$[3,1,2]$$$, $$$f(p)=2$$$.
- $$$[3,2,1]$$$, $$$f(p)=2$$$.

The maximum value $$$f_{max}(3) = 2$$$, and there are $$$4$$$ permutations $$$p$$$ such that $$$f(p)=2$$$.

Example input:
2

Example output:
1

Example input:
3

Example output:
4

Editorial: