1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Work Group
Contest: VK Cup 2015 - Round 2
Difficulty rating: 2000

One Big Software Company has n employees numbered from 1 to n. The director is assigned number 1. Every employee of the company except the director has exactly one immediate superior. The director, of course, doesn't have a superior.

We will call person a a subordinates of another person b, if either b is an immediate supervisor of a, or the immediate supervisor of a is a subordinate to person b. In particular, subordinates of the head are all other employees of the company.

To solve achieve an Important Goal we need to form a workgroup. Every person has some efficiency, expressed by a positive integer ai, where i is the person's number. The efficiency of the workgroup is defined as the total efficiency of all the people included in it.

The employees of the big software company are obsessed with modern ways of work process organization. Today pair programming is at the peak of popularity, so the workgroup should be formed with the following condition. Each person entering the workgroup should be able to sort all of his subordinates who are also in the workgroup into pairs. In other words, for each of the members of the workgroup the number of his subordinates within the workgroup should be even.

Your task is to determine the maximum possible efficiency of the workgroup formed at observing the given condition. Any person including the director of company can enter the workgroup.

Input format:
The first line contains integer n (1 ≤ n ≤ 2·105) — the number of workers of the Big Software Company.

Then n lines follow, describing the company employees. The i-th line contains two integers pi, ai (1 ≤ ai ≤ 105) — the number of the person who is the i-th employee's immediate superior and i-th employee's efficiency. For the director p1 =  - 1, for all other people the condition 1 ≤ pi < i is fulfilled.

Output format:
Print a single integer — the maximum possible efficiency of the workgroup.

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

Note:
In the sample test the most effective way is to make a workgroup from employees number 1, 2, 4, 5, 6.

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

Example output:
17

Editorial:
This problem can be solved by using dynamic programming over subtrees of company ierarchy. Denote as D[v][e] maximum possible efficiency that can be obtained by taking several people from subtree of v so that pairity of their number is e in order condition from statement is fullfilled for all already taken people. Then it is easy to calculate D[v][e] from values of children of v by considering intermediate value T[i][e] — maximum possible efficiency that we can obtain by using first i subtrees of v with overall pairity e.
It's important to not to forget that there are two cases: we may take v itself or we may decide to not take it. In first case it is important that all subtrees have overall even number of taken people. In the second case there is no such restriction.
Board Game
Contest: VK Cup 2015 - Round 2
Difficulty rating: 1700

Polycarp and Vasiliy love simple logical games. Today they play a game with infinite chessboard and one pawn for each player. Polycarp and Vasiliy move in turns, Polycarp starts. In each turn Polycarp can move his pawn from cell (x, y) to (x - 1, y) or (x, y - 1). Vasiliy can move his pawn from (x, y) to one of cells: (x - 1, y), (x - 1, y - 1) and (x, y - 1). Both players are also allowed to skip move.

There are some additional restrictions — a player is forbidden to move his pawn to a cell with negative x-coordinate or y-coordinate or to the cell containing opponent's pawn The winner is the first person to reach cell (0, 0).

You are given the starting coordinates of both pawns. Determine who will win if both of them play optimally well.

Input format:
The first line contains four integers: xp, yp, xv, yv (0 ≤ xp, yp, xv, yv ≤ 105) — Polycarp's and Vasiliy's starting coordinates.

It is guaranteed that in the beginning the pawns are in different cells and none of them is in the cell (0, 0).

Output format:
Output the name of the winner: "Polycarp" or "Vasiliy".

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

Note:
In the first sample test Polycarp starts in (2, 1) and will move to (1, 1) in the first turn. No matter what his opponent is doing, in the second turn Polycarp can move to (1, 0) and finally to (0, 0) in the third turn.

Example input:
2 1 2 2

Example output:
Polycarp

Example input:
4 7 7 4

Example output:
Vasiliy

Editorial:
We will consider three cases:
1) xp + yp ≤ max(xv, yv). In this case Polycarp can be in (0, 0) after xp + yp moves and Vasiliy will always be ,,behind". It's enough for Polycarp to make any move and he is always able to do it. It makes Polycarp closer to (0, 0) and after Vasiliy's move we again have xp + yp ≤ max(xv, yv) condition fulfilled and in some moment Polycarp will reach (0, 0). It's impossible that Vasiliy wins because our condition would be unfulfilled.
2) xp ≤ xv, yp ≤ yv. In this scenario Polycarp must block Vasiliy somehow. He must make such a move that after any Vasiliy's response condition will be fulfilled again.
• If xp = xv > 0 he goes to (xp - 1, yp).
• If yp = yv > 0 he goes to (xp, yp - 1).
• Otherwise he makes any move.
With this strategy Vasiliy is unable to get out of our new condition.
3) Otherwise we can consider any shortest path to (0, 0) for Vasiliy. Lenght of it is max(xv, yv). For any cell on this path Polycarp has greater distance than Vasiliy to it so he can't be there before Vasiliy and he can't block him. Vasiliy wins. Alternative explanation: after any possible Polycarp move Vasiliy can make a move that none of conditions (1) and (2) aren't fulfilled.
Correcting Mistakes
Contest: VK Cup 2015 - Round 2
Difficulty rating: 1800

Analyzing the mistakes people make while typing search queries is a complex and an interesting work. As there is no guaranteed way to determine what the user originally meant by typing some query, we have to use different sorts of heuristics.

Polycarp needed to write a code that could, given two words, check whether they could have been obtained from the same word as a result of typos. Polycarpus suggested that the most common typo is skipping exactly one letter as you type a word.

Implement a program that can, given two distinct words S and T of the same length n determine how many words W of length n + 1 are there with such property that you can transform W into both S, and T by deleting exactly one character. Words S and T consist of lowercase English letters. Word W also should consist of lowercase English letters.

Input format:
The first line contains integer n (1 ≤ n ≤ 100 000) — the length of words S and T.

The second line contains word S.

The third line contains word T.

Words S and T consist of lowercase English letters. It is guaranteed that S and T are distinct words.

Output format:
Print a single integer — the number of distinct words W that can be transformed to S and T due to a typo.

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

Note:
In the first sample test the two given words could be obtained only from word "treading" (the deleted letters are marked in bold).

In the second sample test the two given words couldn't be obtained from the same word by removing one letter.

In the third sample test the two given words could be obtained from either word "tory" or word "troy".

Example input:
7
reading
trading

Example output:
1

Example input:
5
sweet
sheep

Example output:
0

Editorial:
Suppose that S is obtained from W by deleteing the earlier symbol than T. Then it is true that W = A + x + B + y + C, S = A + x + B + C, T = A + B + y + C, where x and y are deleted symbols and A, B и C are some (possibly, empty) strings.
Let's calculate A as a longest common prefix of S and T and C as a longest common suffix. Remove both of them from strings. Now we now that x and y are respectively the first letter of string S and last letter of string T. Remove them too. The only thing left is to check if remaining parts of strings are equal.
Perform such operation for S and T and for T and S.
Required Remainder
Contest: Codeforces Round 653 (Div. 3)
Difficulty rating: 800
Tags: math

You are given three integers $$$x, y$$$ and $$$n$$$. Your task is to find the maximum integer $$$k$$$ such that $$$0 \le k \le n$$$ that $$$k \bmod x = y$$$, where $$$\bmod$$$ is modulo operation. Many programming languages use percent operator % to implement it.

In other words, with given $$$x, y$$$ and $$$n$$$ you need to find the maximum possible integer from $$$0$$$ to $$$n$$$ that has the remainder $$$y$$$ modulo $$$x$$$.

You have to answer $$$t$$$ independent test cases. It is guaranteed that such $$$k$$$ exists for each test case.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — the number of test cases. The next $$$t$$$ lines contain test cases.

The only line of the test case contains three integers $$$x, y$$$ and $$$n$$$ ($$$2 \le x \le 10^9;~ 0 \le y < x;~ y \le n \le 10^9$$$).

It can be shown that such $$$k$$$ always exists under the given constraints.

Output format:
For each test case, print the answer — maximum non-negative integer $$$k$$$ such that $$$0 \le k \le n$$$ and $$$k \bmod x = y$$$. It is guaranteed that the answer always exists.

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

Note:
In the first test case of the example, the answer is $$$12339 = 7 \cdot 1762 + 5$$$ (thus, $$$12339 \bmod 7 = 5$$$). It is obvious that there is no greater integer not exceeding $$$12345$$$ which has the remainder $$$5$$$ modulo $$$7$$$.

Example input:
7
7 5 12345
5 0 4
10 5 15
17 8 54321
499999993 9 1000000000
10 5 187
2 0 999999999

Example output:
12339
0
15
54306
999999995
185
999999998

Editorial:
There are two cases in this problem. If we try to maximize the answer, we need to consider only two integers: $$$n - n \bmod x + y$$$ and $$$n - n \bmod x - (x - y)$$$. Of course, the first one is better (we get rid of the existing remainder and trying to add $$$y$$$ to this number). If it's too big, then we can and need to take the second one (this number is just the first one but decreased by $$$x$$$). The answer can be always found between these numbers.
Time complexity: $$$O(1)$$$.
Multiply by 2, divide by 6
Contest: Codeforces Round 653 (Div. 3)
Difficulty rating: 900
Tags: math

You are given an integer $$$n$$$. In one move, you can either multiply $$$n$$$ by two or divide $$$n$$$ by $$$6$$$ (if it is divisible by $$$6$$$ without the remainder).

Your task is to find the minimum number of moves needed to obtain $$$1$$$ from $$$n$$$ or determine if it's impossible to do that.

You have to answer $$$t$$$ independent test cases.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The only line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 10^9$$$).

Output format:
For each test case, print the answer — the minimum number of moves needed to obtain $$$1$$$ from $$$n$$$ if it's possible to do that or -1 if it's impossible to obtain $$$1$$$ from $$$n$$$.

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

Note:
Consider the sixth test case of the example. The answer can be obtained by the following sequence of moves from the given integer $$$15116544$$$:

1. Divide by $$$6$$$ and get $$$2519424$$$;
2. divide by $$$6$$$ and get $$$419904$$$;
3. divide by $$$6$$$ and get $$$69984$$$;
4. divide by $$$6$$$ and get $$$11664$$$;
5. multiply by $$$2$$$ and get $$$23328$$$;
6. divide by $$$6$$$ and get $$$3888$$$;
7. divide by $$$6$$$ and get $$$648$$$;
8. divide by $$$6$$$ and get $$$108$$$;
9. multiply by $$$2$$$ and get $$$216$$$;
10. divide by $$$6$$$ and get $$$36$$$;
11. divide by $$$6$$$ and get $$$6$$$;
12. divide by $$$6$$$ and get $$$1$$$.

Example input:
7
1
2
3
12
12345
15116544
387420489

Example output:
0
-1
2
-1
-1
12
36

Editorial:
If the number consists of other primes than $$$2$$$ and $$$3$$$ then the answer is -1. Otherwise, let $$$cnt_2$$$ be the number of twos in the factorization of $$$n$$$ and $$$cnt_3$$$ be the number of threes in the factorization of $$$n$$$. If $$$cnt_2 > cnt_3$$$ then the answer is -1 because we can't get rid of all twos. Otherwise, the answer is $$$(cnt_3 - cnt_2) + cnt_3$$$.
Time complexity: $$$O(\log{n})$$$.
Move Brackets
Contest: Codeforces Round 653 (Div. 3)
Difficulty rating: 1000
Tags: greedy, strings

You are given a bracket sequence $$$s$$$ of length $$$n$$$, where $$$n$$$ is even (divisible by two). The string $$$s$$$ consists of $$$\frac{n}{2}$$$ opening brackets '(' and $$$\frac{n}{2}$$$ closing brackets ')'.

In one move, you can choose exactly one bracket and move it to the beginning of the string or to the end of the string (i.e. you choose some index $$$i$$$, remove the $$$i$$$-th character of $$$s$$$ and insert it before or after all remaining characters of $$$s$$$).

Your task is to find the minimum number of moves required to obtain regular bracket sequence from $$$s$$$. It can be proved that the answer always exists under the given constraints.

Recall what the regular bracket sequence is:

- "()" is regular bracket sequence;
- if $$$s$$$ is regular bracket sequence then "(" + $$$s$$$ + ")" is regular bracket sequence;
- if $$$s$$$ and $$$t$$$ are regular bracket sequences then $$$s$$$ + $$$t$$$ is regular bracket sequence.

For example, "()()", "(())()", "(())" and "()" are regular bracket sequences, but ")(", "()(" and ")))" are not.

You have to answer $$$t$$$ independent test cases.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2000$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of the test case contains one integer $$$n$$$ ($$$2 \le n \le 50$$$) — the length of $$$s$$$. It is guaranteed that $$$n$$$ is even. The second line of the test case containg the string $$$s$$$ consisting of $$$\frac{n}{2}$$$ opening and $$$\frac{n}{2}$$$ closing brackets.

Output format:
For each test case, print the answer — the minimum number of moves required to obtain regular bracket sequence from $$$s$$$. It can be proved that the answer always exists under the given constraints.

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

Note:
In the first test case of the example, it is sufficient to move the first bracket to the end of the string.

In the third test case of the example, it is sufficient to move the last bracket to the beginning of the string.

In the fourth test case of the example, we can choose last three openning brackets, move them to the beginning of the string and obtain "((()))(())".

Example input:
4
2
)(
4
()()
8
())()()(
10
)))((((())

Example output:
1
0
1
3

Editorial:
Let's go from left to right over characters of $$$s$$$ maintaining the current bracket balance (for the position $$$i$$$ the balance is the number of opening brackets on the prefix till the $$$i$$$-th character minus the number of closing brackets on the same prefix).
If the current balance becomes less than zero, then let's just take some opening bracket after the current position (it obviously exists because the number of opening equals the number of closing brackets) and move it to the beginning (so the negative balance becomes zero again and the answer increases by one). Or we can move the current closing bracket to the end of the string because it leads to the same result.
Time complexity: $$$O(n)$$$.
Laptops
Contest: Codeforces Round 260 (Div. 2)
Difficulty rating: 1100
Tags: sortings

One day Dima and Alex had an argument about the price and quality of laptops. Dima thinks that the more expensive a laptop is, the better it is. Alex disagrees. Alex thinks that there are two laptops, such that the price of the first laptop is less (strictly smaller) than the price of the second laptop but the quality of the first laptop is higher (strictly greater) than the quality of the second laptop.

Please, check the guess of Alex. You are given descriptions of n laptops. Determine whether two described above laptops exist.

Input format:
The first line contains an integer n (1 ≤ n ≤ 105) — the number of laptops.

Next n lines contain two integers each, ai and bi (1 ≤ ai, bi ≤ n), where ai is the price of the i-th laptop, and bi is the number that represents the quality of the i-th laptop (the larger the number is, the higher is the quality).

All ai are distinct. All bi are distinct.

Output format:
If Alex is correct, print "Happy Alex", otherwise print "Poor Alex" (without the quotes).

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

Example input:
2
1 2
2 1

Example output:
Happy Alex

Editorial:
Fedya and Maths
Contest: Codeforces Round 260 (Div. 2)
Difficulty rating: 1200
Tags: math, number theory

Fedya studies in a gymnasium. Fedya's maths hometask is to calculate the following expression:

(1n + 2n + 3n + 4n) mod 5

for given value of n. Fedya managed to complete the task. Can you? Note that given number n can be extremely large (e.g. it can exceed any integer type of your programming language).

Input format:
The single line contains a single integer n (0 ≤ n ≤ 10105). The number doesn't contain any leading zeroes.

Output format:
Print the value of the expression without leading zeros.

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

Note:
Operation x mod y means taking remainder after division x by y.

Note to the first sample:

$$( 1 ^ { 4 } + 2 ^ { 4 } + 3 ^ { 4 } + 4 ^ { 4 } ) \bmod 5 = ( 1 + 1 6 + 8 1 + 2 5 6 ) \bmod 5 = 4$$

Example input:
4

Example output:
4

Example input:
124356983594583453458888889

Example output:
0

Editorial:
Dice Rolling
Contest: Educational Codeforces Round 56 (Rated for Div. 2)
Difficulty rating: 800
Tags: math

Mishka got a six-faced dice. It has integer numbers from $$$2$$$ to $$$7$$$ written on its faces (all numbers on faces are different, so this is an almost usual dice).

Mishka wants to get exactly $$$x$$$ points by rolling his dice. The number of points is just a sum of numbers written at the topmost face of the dice for all the rolls Mishka makes.

Mishka doesn't really care about the number of rolls, so he just wants to know any number of rolls he can make to be able to get exactly $$$x$$$ points for them. Mishka is very lucky, so if the probability to get $$$x$$$ points with chosen number of rolls is non-zero, he will be able to roll the dice in such a way. Your task is to print this number. It is guaranteed that at least one answer exists.

Mishka is also very curious about different number of points to score so you have to answer $$$t$$$ independent queries.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of queries.

Each of the next $$$t$$$ lines contains one integer each. The $$$i$$$-th line contains one integer $$$x_i$$$ ($$$2 \le x_i \le 100$$$) — the number of points Mishka wants to get.

Output format:
Print $$$t$$$ lines. In the $$$i$$$-th line print the answer to the $$$i$$$-th query (i.e. any number of rolls Mishka can make to be able to get exactly $$$x_i$$$ points for them). It is guaranteed that at least one answer exists.

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

Note:
In the first query Mishka can roll a dice once and get $$$2$$$ points.

In the second query Mishka can roll a dice $$$3$$$ times and get points $$$5$$$, $$$5$$$ and $$$3$$$ (for example).

In the third query Mishka can roll a dice $$$8$$$ times and get $$$5$$$ points $$$7$$$ times and $$$2$$$ points with the remaining roll.

In the fourth query Mishka can roll a dice $$$27$$$ times and get $$$2$$$ points $$$11$$$ times, $$$3$$$ points $$$6$$$ times and $$$6$$$ points $$$10$$$ times.

Example input:
4
2
13
37
100

Example output:
1
3
8
27

Editorial:
It is enough to print $$$\lfloor\frac{x_i}{2}\rfloor$$$ for each query, where $$$\lfloor\frac{x}{y}\rfloor$$$ is $$$x$$$ divided by $$$y$$$ rounded down.
Letters Rearranging
Contest: Educational Codeforces Round 56 (Rated for Div. 2)
Difficulty rating: 900
Tags: constructive algorithms, greedy, sortings, strings

You are given a string $$$s$$$ consisting only of lowercase Latin letters.

You can rearrange all letters of this string as you wish. Your task is to obtain a good string by rearranging the letters of the given string or report that it is impossible to do it.

Let's call a string good if it is not a palindrome. Palindrome is a string which is read from left to right the same as from right to left. For example, strings "abacaba", "aa" and "z" are palindromes and strings "bba", "xd" are not.

You have to answer $$$t$$$ independent queries.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — number of queries.

Each of the next $$$t$$$ lines contains one string. The $$$i$$$-th line contains a string $$$s_i$$$ consisting only of lowercase Latin letter. It is guaranteed that the length of $$$s_i$$$ is from $$$1$$$ to $$$1000$$$ (inclusive).

Output format:
Print $$$t$$$ lines. In the $$$i$$$-th line print the answer to the $$$i$$$-th query: -1 if it is impossible to obtain a good string by rearranging the letters of $$$s_i$$$ and any good string which can be obtained from the given one (by rearranging the letters) otherwise.

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

Note:
In the first query we cannot rearrange letters to obtain a good string.

Other examples (not all) of correct answers to the second query: "ababaca", "abcabaa", "baacaba".

In the third query we can do nothing to obtain a good string.

Example input:
3
aa
abacaba
xdd

Example output:
-1
abaacba
xdd

Editorial:
The only case when the answer is -1 is when all letters of the string are equal. Why is it so? Because if we have at least two different letters we can place the first one at the first position of the string and the second one at the last position of the string. Then it is clearly that the obtained string is good. We can implement this solution by the following way: sort $$$s_i$$$ and if $$$s_{i, 1} = s_{i, |s_i|}$$$ (the first letter equals to the last one) then the answer is -1 otherwise the answer is $$$s_i$$$.