1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Playing with Permutations
Contest: Codeforces Round 153 (Div. 1)
Difficulty rating: 1800
Tags: implementation, math

Little Petya likes permutations a lot. Recently his mom has presented him permutation q1, q2, ..., qn of length n.

A permutation a of length n is a sequence of integers a1, a2, ..., an (1 ≤ ai ≤ n), all integers there are distinct.

There is only one thing Petya likes more than permutations: playing with little Masha. As it turns out, Masha also has a permutation of length n. Petya decided to get the same permutation, whatever the cost may be. For that, he devised a game with the following rules:

- Before the beginning of the game Petya writes permutation 1, 2, ..., n on the blackboard. After that Petya makes exactly k moves, which are described below.
- During a move Petya tosses a coin. If the coin shows heads, he performs point 1, if the coin shows tails, he performs point 2.  Let's assume that the board contains permutation p1, p2, ..., pn at the given moment. Then Petya removes the written permutation p from the board and writes another one instead: pq1, pq2, ..., pqn. In other words, Petya applies permutation q (which he has got from his mother) to permutation p.  All actions are similar to point 1, except that Petya writes permutation t on the board, such that: tqi = pi for all i from 1 to n. In other words, Petya applies a permutation that is inverse to q to permutation p.

We know that after the k-th move the board contained Masha's permutation s1, s2, ..., sn. Besides, we know that throughout the game process Masha's permutation never occurred on the board before the k-th move. Note that the game has exactly k moves, that is, throughout the game the coin was tossed exactly k times.

Your task is to determine whether the described situation is possible or else state that Petya was mistaken somewhere. See samples and notes to them for a better understanding.

Input format:
The first line contains two integers n and k (1 ≤ n, k ≤ 100). The second line contains n space-separated integers q1, q2, ..., qn (1 ≤ qi ≤ n) — the permutation that Petya's got as a present. The third line contains Masha's permutation s, in the similar format.

It is guaranteed that the given sequences q and s are correct permutations.

Output format:
If the situation that is described in the statement is possible, print "YES" (without the quotes), otherwise print "NO" (without the quotes).

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

Note:
In the first sample Masha's permutation coincides with the permutation that was written on the board before the beginning of the game. Consequently, that violates the condition that Masha's permutation never occurred on the board before k moves were performed.

In the second sample the described situation is possible, in case if after we toss a coin, we get tails.

In the third sample the possible coin tossing sequence is: heads-tails-tails.

In the fourth sample the possible coin tossing sequence is: heads-heads.

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

Example output:
NO

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

Example output:
YES

Editorial:
Number Transformation
Contest: Codeforces Round 153 (Div. 1)
Difficulty rating: 2000
Tags: dp, greedy, number theory

Little Petya likes positive integers a lot. Recently his mom has presented him a positive integer a. There's only one thing Petya likes more than numbers: playing with little Masha. It turned out that Masha already has a positive integer b. Petya decided to turn his number a into the number b consecutively performing the operations of the following two types:

1. Subtract 1 from his number.
2. Choose any integer x from 2 to k, inclusive. Then subtract number (a mod x) from his number a. Operation a mod x means taking the remainder from division of number a by number x.

Petya performs one operation per second. Each time he chooses an operation to perform during the current move, no matter what kind of operations he has performed by that moment. In particular, this implies that he can perform the same operation any number of times in a row.

Now he wonders in what minimum number of seconds he could transform his number a into number b. Please note that numbers x in the operations of the second type are selected anew each time, independently of each other.

Input format:
The only line contains three integers a, b (1 ≤ b ≤ a ≤ 1018) and k (2 ≤ k ≤ 15).

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

Output format:
Print a single integer — the required minimum number of seconds needed to transform number a into number b.

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

Note:
In the first sample the sequence of numbers that Petya gets as he tries to obtain number b is as follows: 10  →  8  →  6  →  4  →  3  →  2  →  1.

In the second sample one of the possible sequences is as follows: 6  →  4  →  3.

Example input:
10 1 4

Example output:
6

Example input:
6 3 10

Example output:
2

Editorial:
Two Sets
Contest: Codeforces Round 153 (Div. 1)
Difficulty rating: 2700
Tags: bitmasks, math

Little Petya likes numbers a lot. Recently his mother has presented him a collection of n non-negative integers. There's only one thing Petya likes more than numbers: playing with little Masha. He immediately decided to give a part of his new collection to her. To make the game even more interesting, Petya decided to give Masha such collection of numbers for which the following conditions fulfill:

- Let's introduce x1 to denote the xor of all numbers Petya has got left; and let's introduce x2 to denote the xor of all numbers he gave to Masha. Value (x1 + x2) must be as large as possible.
- If there are multiple ways to divide the collection so that the previous condition fulfilled, then Petya minimizes the value x1.

The xor operation is a bitwise excluding "OR", that is denoted as "xor" in the Pascal language and "^" in C/C++/Java.

Help Petya divide the collection as described above. If there are multiple suitable ways to divide it, find any of them. Please note that after Petya gives a part of his numbers to Masha, he may have no numbers left. The reverse situation is also possible, when Petya gives nothing to Masha. In both cases we must assume that the xor of an empty set of numbers equals 0.

Input format:
The first line contains integer n (1 ≤ n ≤ 105), showing how many numbers Petya's mother gave him. The second line contains the actual space-separated numbers. They are all integer, non-negative and do not exceed 1018.

Output format:
Print n space-separated integers, the i-th of them should equal either 1, if Petya keeps the number that follows i-th in his collection, or it should equal 2, if Petya gives the corresponding number to Masha. The numbers are indexed in the order in which they are given in the input.

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

Example input:
6
1 2 3 4 5 6

Example output:
2 2 2 2 2 2

Example input:
3
1000000000000 1000000000000 1000000000000

Example output:
2 2 2

Editorial:
Tree and Table
Contest: Codeforces Round 153 (Div. 1)
Difficulty rating: 3000
Tags: dfs and similar, dp, implementation, trees

Little Petya likes trees a lot. Recently his mother has presented him a tree with 2n nodes. Petya immediately decided to place this tree on a rectangular table consisting of 2 rows and n columns so as to fulfill the following conditions:

1. Each cell of the table corresponds to exactly one tree node and vice versa, each tree node corresponds to exactly one table cell.
2. If two tree nodes are connected by an edge, then the corresponding cells have a common side.

Now Petya wonders how many ways are there to place his tree on the table. He calls two placements distinct if there is a tree node which corresponds to distinct table cells in these two placements. Since large numbers can scare Petya, print the answer modulo 1000000007 (109 + 7).

Input format:
The first line contains a single integer n (1 ≤ n ≤ 105). Next (2n - 1) lines contain two integers each ai and bi (1 ≤ ai, bi ≤ 2n; ai ≠ bi) that determine the numbers of the vertices connected by the corresponding edge.

Consider the tree vertexes numbered by integers from 1 to 2n. It is guaranteed that the graph given in the input is a tree, that is, a connected acyclic undirected graph.

Output format:
Print a single integer — the required number of ways to place the tree on the table modulo 1000000007 (109 + 7).

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

Note:
Note to the first sample (all 12 variants to place the tree on the table are given below):

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

Example output:
12

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

Example output:
28

Editorial:
Peter and Snow Blower
Contest: Codeforces Round 339 (Div. 1)
Difficulty rating: 1900
Tags: binary search, geometry, ternary search

Peter got a new snow blower as a New Year present. Of course, Peter decided to try it immediately. After reading the instructions he realized that it does not work like regular snow blowing machines. In order to make it work, you need to tie it to some point that it does not cover, and then switch it on. As a result it will go along a circle around this point and will remove all the snow from its path.

Formally, we assume that Peter's machine is a polygon on a plane. Then, after the machine is switched on, it will make a circle around the point to which Peter tied it (this point lies strictly outside the polygon). That is, each of the points lying within or on the border of the polygon will move along the circular trajectory, with the center of the circle at the point to which Peter tied his machine.

Peter decided to tie his car to point P and now he is wondering what is the area of ​​the region that will be cleared from snow. Help him.

Input format:
The first line of the input contains three integers — the number of vertices of the polygon n ($$3 \leq n \leq 100\ 000$$), and coordinates of point P.

Each of the next n lines contains two integers — coordinates of the vertices of the polygon in the clockwise or counterclockwise order. It is guaranteed that no three consecutive vertices lie on a common straight line.

All the numbers in the input are integers that do not exceed 1 000 000 in their absolute value.

Output format:
Print a single real value number — the area of the region that will be cleared. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$.

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

Note:
In the first sample snow will be removed from that area:

Example input:
3 0 0
0 1
-1 2
1 2

Example output:
12.566370614359172464

Example input:
4 1 -1
0 0
1 2
2 0
1 1

Example output:
21.991148575128551812

Editorial:
Skills
Contest: Codeforces Round 339 (Div. 1)
Difficulty rating: 1900
Tags: binary search, brute force, dp, greedy, sortings, two pointers

Lesha plays the recently published new version of the legendary game hacknet. In this version character skill mechanism was introduced. Now, each player character has exactly n skills. Each skill is represented by a non-negative integer ai — the current skill level. All skills have the same maximum level A.

Along with the skills, global ranking of all players was added. Players are ranked according to the so-called Force. The Force of a player is the sum of the following values:

- The number of skills that a character has perfected (i.e., such that ai = A), multiplied by coefficient cf.
- The minimum skill level among all skills (min ai), multiplied by coefficient cm.

Now Lesha has m hacknetian currency units, which he is willing to spend. Each currency unit can increase the current level of any skill by 1 (if it's not equal to A yet). Help him spend his money in order to achieve the maximum possible value of the Force.

Input format:
The first line of the input contains five space-separated integers n, A, cf, cm and m (1 ≤ n ≤ 100 000, 1 ≤ A ≤ 109, 0 ≤ cf, cm ≤ 1000, 0 ≤ m ≤ 1015).

The second line contains exactly n integers ai (0 ≤ ai ≤ A), separated by spaces, — the current levels of skills.

Output format:
On the first line print the maximum value of the Force that the character can achieve using no more than m currency units.

On the second line print n integers a'i (ai ≤ a'i ≤ A), skill levels which one must achieve in order to reach the specified value of the Force, while using no more than m currency units. Numbers should be separated by spaces.

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

Note:
In the first test the optimal strategy is to increase the second skill to its maximum, and increase the two others by 1.

In the second test one should increase all skills to maximum.

Example input:
3 5 10 1 5
1 3 1

Example output:
12
2 5 2

Example input:
3 5 10 1 339
1 3 1

Example output:
35
5 5 5

Editorial:
Necklace
Contest: Codeforces Round 339 (Div. 1)
Difficulty rating: 2500
Tags: constructive algorithms, math

Ivan wants to make a necklace as a present to his beloved girl. A necklace is a cyclic sequence of beads of different colors. Ivan says that necklace is beautiful relative to the cut point between two adjacent beads, if the chain of beads remaining after this cut is a palindrome (reads the same forward and backward).

Ivan has beads of n colors. He wants to make a necklace, such that it's beautiful relative to as many cuts as possible. He certainly wants to use all the beads. Help him to make the most beautiful necklace.

Input format:
The first line of the input contains a single number n (1 ≤ n ≤ 26) — the number of colors of beads. The second line contains after n positive integers ai   — the quantity of beads of i-th color. It is guaranteed that the sum of ai is at least 2 and does not exceed 100 000.

Output format:
In the first line print a single number — the maximum number of beautiful cuts that a necklace composed from given beads may have. In the second line print any example of such necklace.

Each color of the beads should be represented by the corresponding lowercase English letter (starting with a). As the necklace is cyclic, print it starting from any point.

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

Note:
In the first sample a necklace can have at most one beautiful cut. The example of such a necklace is shown on the picture.

In the second sample there is only one way to compose a necklace.

Example input:
3
4 2 1

Example output:
1
abacaba

Example input:
1
4

Example output:
4
aaaa

Editorial:
Kingdom and its Cities
Contest: Codeforces Round 339 (Div. 1)
Difficulty rating: 2800
Tags: dfs and similar, divide and conquer, dp, graphs, sortings, trees

Meanwhile, the kingdom of K is getting ready for the marriage of the King's daughter. However, in order not to lose face in front of the relatives, the King should first finish reforms in his kingdom. As the King can not wait for his daughter's marriage, reforms must be finished as soon as possible.

The kingdom currently consists of n cities. Cities are connected by n - 1 bidirectional road, such that one can get from any city to any other city. As the King had to save a lot, there is only one path between any two cities.

What is the point of the reform? The key ministries of the state should be relocated to distinct cities (we call such cities important). However, due to the fact that there is a high risk of an attack by barbarians it must be done carefully. The King has made several plans, each of which is described by a set of important cities, and now wonders what is the best plan.

Barbarians can capture some of the cities that are not important (the important ones will have enough protection for sure), after that the captured city becomes impassable. In particular, an interesting feature of the plan is the minimum number of cities that the barbarians need to capture in order to make all the important cities isolated, that is, from all important cities it would be impossible to reach any other important city.

Help the King to calculate this characteristic for each of his plan.

Input format:
The first line of the input contains integer n (1 ≤ n ≤ 100 000) — the number of cities in the kingdom.

Each of the next n - 1 lines contains two distinct integers ui, vi (1 ≤ ui, vi ≤ n) — the indices of the cities connected by the i-th road. It is guaranteed that you can get from any city to any other one moving only along the existing roads.

The next line contains a single integer q (1 ≤ q ≤ 100 000) — the number of King's plans.

Each of the next q lines looks as follows: first goes number ki — the number of important cities in the King's plan, (1 ≤ ki ≤ n), then follow exactly ki space-separated pairwise distinct numbers from 1 to n — the numbers of important cities in this plan.

The sum of all ki's does't exceed 100 000.

Output format:
For each plan print a single integer — the minimum number of cities that the barbarians need to capture, or print  - 1 if all the barbarians' attempts to isolate important cities will not be effective.

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

Note:
In the first sample, in the first and the third King's plan barbarians can capture the city 3, and that will be enough. In the second and the fourth plans all their attempts will not be effective.

In the second sample the cities to capture are 3 and 5.

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

Example output:
1
-1
1
-1

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

Example output:
2

Editorial:
Puzzle Lover
Contest: Codeforces Round 339 (Div. 1)
Difficulty rating: 3200
Tags: dp, hashing, strings

Oleg Petrov loves crossword puzzles and every Thursday he buys his favorite magazine with crosswords and other word puzzles. In the last magazine Oleg found a curious puzzle, and the magazine promised a valuable prize for it's solution. We give a formal description of the problem below.

The puzzle field consists of two rows, each row contains n cells. Each cell contains exactly one small English letter. You also are given a word w, which consists of k small English letters. A solution of the puzzle is a sequence of field cells c1, ..., ck, such that:

- For all i from 1 to k the letter written in the cell ci matches the letter wi;
- All the cells in the sequence are pairwise distinct;
- For all i from 1 to k - 1 cells ci and ci + 1 have a common side.

Oleg Petrov quickly found a solution for the puzzle. Now he wonders, how many distinct solutions are there for this puzzle. Oleg Petrov doesn't like too large numbers, so calculate the answer modulo 109 + 7.

Two solutions ci and c'i are considered distinct if the sequences of cells do not match in at least one position, that is there is such j in range from 1 to k, such that cj ≠ c'j.

Input format:
The first two lines contain the state of the field for the puzzle. Each of these non-empty lines contains exactly n small English letters.

The next line is left empty.

The next line is non-empty and contains word w, consisting of small English letters.

The length of each line doesn't exceed 2 000.

Output format:
Print a single integer — the number of distinct solutions for the puzzle modulo 109 + 7.

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

Example input:
code
edoc
code

Example output:
4

Example input:
aaa
aaa
aa

Example output:
14

Editorial:
Sea Battle
Contest: Codeforces Round 541 (Div. 2)
Difficulty rating: 800
Tags: math

In order to make the "Sea Battle" game more interesting, Boris decided to add a new ship type to it. The ship consists of two rectangles. The first rectangle has a width of $$$w_1$$$ and a height of $$$h_1$$$, while the second rectangle has a width of $$$w_2$$$ and a height of $$$h_2$$$, where $$$w_1 \ge w_2$$$. In this game, exactly one ship is used, made up of two rectangles. There are no other ships on the field.

The rectangles are placed on field in the following way:

- the second rectangle is on top the first rectangle;
- they are aligned to the left, i.e. their left sides are on the same line;
- the rectangles are adjacent to each other without a gap.

See the pictures in the notes: the first rectangle is colored red, the second rectangle is colored blue.

Formally, let's introduce a coordinate system. Then, the leftmost bottom cell of the first rectangle has coordinates $$$(1, 1)$$$, the rightmost top cell of the first rectangle has coordinates $$$(w_1, h_1)$$$, the leftmost bottom cell of the second rectangle has coordinates $$$(1, h_1 + 1)$$$ and the rightmost top cell of the second rectangle has coordinates $$$(w_2, h_1 + h_2)$$$.

After the ship is completely destroyed, all cells neighboring by side or a corner with the ship are marked. Of course, only cells, which don't belong to the ship are marked. On the pictures in the notes such cells are colored green.

Find out how many cells should be marked after the ship is destroyed. The field of the game is infinite in any direction.

Input format:
Four lines contain integers $$$w_1, h_1, w_2$$$ and $$$h_2$$$ ($$$1 \leq w_1, h_1, w_2, h_2 \leq 10^8$$$, $$$w_1 \ge w_2$$$) — the width of the first rectangle, the height of the first rectangle, the width of the second rectangle and the height of the second rectangle. You can't rotate the rectangles.

Output format:
Print exactly one integer — the number of cells, which should be marked after the ship is destroyed.

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

Note:
In the first example the field looks as follows (the first rectangle is red, the second rectangle is blue, green shows the marked squares):

In the second example the field looks as:

Example input:
2 1 2 1

Example output:
12

Example input:
2 2 1 2

Example output:
16

Editorial:
Let's classify marked squares to two groups. First group will consist of cells that are neighboring by corner to ship. There are exactly $$$5$$$ such corners. Second group will consist of cells that are neighboring by side to ship. Number of such squares is equal to length of perimeter of a ship.
Thus answer is equal to $$$2 \cdot (w_1 + h1 + h2) + 4$$$.