1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Xor-tree
Contest: Codeforces Round 245 (Div. 1)
Difficulty rating: 1300
Tags: dfs and similar, trees

Iahub is very proud of his recent discovery, propagating trees. Right now, he invented a new tree, called xor-tree. After this new revolutionary discovery, he invented a game for kids which uses xor-trees.

The game is played on a tree having n nodes, numbered from 1 to n. Each node i has an initial value initi, which is either 0 or 1. The root of the tree is node 1.

One can perform several (possibly, zero) operations on the tree during the game. The only available type of operation is to pick a node x. Right after someone has picked node x, the value of node x flips, the values of sons of x remain the same, the values of sons of sons of x flips, the values of sons of sons of sons of x remain the same and so on.

The goal of the game is to get each node i to have value goali, which can also be only 0 or 1. You need to reach the goal of the game by using minimum number of operations.

Input format:
The first line contains an integer n (1 ≤ n ≤ 105). Each of the next n - 1 lines contains two integers ui and vi (1 ≤ ui, vi ≤ n; ui ≠ vi) meaning there is an edge between nodes ui and vi.

The next line contains n integer numbers, the i-th of them corresponds to initi (initi is either 0 or 1). The following line also contains n integer numbers, the i-th number corresponds to goali (goali is either 0 or 1).

Output format:
In the first line output an integer number cnt, representing the minimal number of operations you perform. Each of the next cnt lines should contain an integer xi, representing that you pick a node xi.

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

Example input:
10
2 1
3 1
4 2
5 1
6 2
7 5
8 6
9 8
10 5
1 0 1 1 0 1 0 1 0 1
1 0 1 0 0 1 1 1 0 1

Example output:
2
4
7

Editorial:
Working out
Contest: Codeforces Round 245 (Div. 1)
Difficulty rating: 1600
Tags: dp

Summer is coming! It's time for Iahub and Iahubina to work out, as they both want to look hot at the beach. The gym where they go is a matrix a with n lines and m columns. Let number a[i][j] represents the calories burned by performing workout at the cell of gym in the i-th line and the j-th column.

Iahub starts with workout located at line 1 and column 1. He needs to finish with workout a[n][m]. After finishing workout a[i][j], he can go to workout a[i + 1][j] or a[i][j + 1]. Similarly, Iahubina starts with workout a[n][1] and she needs to finish with workout a[1][m]. After finishing workout from cell a[i][j], she goes to either a[i][j + 1] or a[i - 1][j].

There is one additional condition for their training. They have to meet in exactly one cell of gym. At that cell, none of them will work out. They will talk about fast exponentiation (pretty odd small talk) and then both of them will move to the next workout.

If a workout was done by either Iahub or Iahubina, it counts as total gain. Please plan a workout for Iahub and Iahubina such as total gain to be as big as possible. Note, that Iahub and Iahubina can perform workouts with different speed, so the number of cells that they use to reach meet cell may differs.

Input format:
The first line of the input contains two integers n and m (3 ≤ n, m ≤ 1000). Each of the next n lines contains m integers: j-th number from i-th line denotes element a[i][j] (0 ≤ a[i][j] ≤ 105).

Output format:
The output contains a single number — the maximum total gain possible.

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

Note:
Iahub will choose exercises a[1][1] → a[1][2] → a[2][2] → a[3][2] → a[3][3]. Iahubina will choose exercises a[3][1] → a[2][1] → a[2][2] → a[2][3] → a[1][3].

Example input:
3 3
100 100 100
100 1 100
100 100 100

Example output:
800

Editorial:
Guess the Tree
Contest: Codeforces Round 245 (Div. 1)
Difficulty rating: 2300
Tags: bitmasks, constructive algorithms, dp, greedy, trees

Iahub and Iahubina went to a picnic in a forest full of trees. Less than 5 minutes passed before Iahub remembered of trees from programming. Moreover, he invented a new problem and Iahubina has to solve it, otherwise Iahub won't give her the food.

Iahub asks Iahubina: can you build a rooted tree, such that

- each internal node (a node with at least one son) has at least two sons;
- node i has ci nodes in its subtree?

Iahubina has to guess the tree. Being a smart girl, she realized that it's possible no tree can follow Iahub's restrictions. In this way, Iahub will eat all the food. You need to help Iahubina: determine if there's at least one tree following Iahub's restrictions. The required tree must contain n nodes.

Input format:
The first line of the input contains integer n (1 ≤ n ≤ 24). Next line contains n positive integers: the i-th number represents ci (1 ≤ ci ≤ n).

Output format:
Output on the first line "YES" (without quotes) if there exist at least one tree following Iahub's restrictions, otherwise output "NO" (without quotes).

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

Example input:
4
1 1 1 4

Example output:
YES

Example input:
5
1 1 5 2 1

Example output:
NO

Editorial:
Tricky Function
Contest: Codeforces Round 245 (Div. 1)
Difficulty rating: 2200
Tags: data structures, divide and conquer, geometry

Iahub and Sorin are the best competitive programmers in their town. However, they can't both qualify to an important contest. The selection will be made with the help of a single problem. Blatnatalag, a friend of Iahub, managed to get hold of the problem before the contest. Because he wants to make sure Iahub will be the one qualified, he tells Iahub the following task.

You're given an (1-based) array a with n elements. Let's define function f(i, j) (1 ≤ i, j ≤ n) as (i - j)2 + g(i, j)2. Function g is calculated by the following pseudo-code:

Find a value mini ≠ j  f(i, j).

Probably by now Iahub already figured out the solution to this problem. Can you?

Input format:
The first line of input contains a single integer n (2 ≤ n ≤ 100000). Next line contains n integers a[1], a[2], ..., a[n] ( - 104 ≤ a[i] ≤ 104).

Output format:
Output a single integer — the value of mini ≠ j  f(i, j).

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

Example input:
4
1 0 0 -1

Example output:
1

Example input:
2
1 -1

Example output:
2

Editorial:
Points and Segments
Contest: Codeforces Round 245 (Div. 1)
Difficulty rating: 3000
Tags: graphs

Iahub isn't well prepared on geometry problems, but he heard that this year there will be a lot of geometry problems on the IOI selection camp. Scared, Iahub locked himself in the basement and started thinking of new problems of this kind. One of them is the following.

Iahub wants to draw n distinct segments [li, ri] on the OX axis. He can draw each segment with either red or blue. The drawing is good if and only if the following requirement is met: for each point x of the OX axis consider all the segments that contains point x; suppose, that rx red segments and bx blue segments contain point x; for each point x inequality |rx - bx| ≤ 1 must be satisfied.

A segment [l, r] contains a point x if and only if l ≤ x ≤ r.

Iahub gives you the starting and ending points of all the segments. You have to find any good drawing for him.

Input format:
The first line of input contains integer n (1 ≤ n ≤ 105) — the number of segments. The i-th of the next n lines contains two integers li and ri (0 ≤ li ≤ ri ≤ 109) — the borders of the i-th segment.

It's guaranteed that all the segments are distinct.

Output format:
If there is no good drawing for a given test, output a single integer -1. Otherwise output n integers; each integer must be 0 or 1. The i-th number denotes the color of the i-th segment (0 is red and 1 is blue).

If there are multiple good drawings you can output any of them.

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

Example input:
2
0 2
2 3

Example output:
0 1

Example input:
6
1 5
1 3
3 5
2 10
11 11
12 12

Example output:
0 1 0 1 0 0

Editorial:
Friends Meeting
Contest: Codeforces Round 468 (Div. 2, based on Technocup 2018 Final Round)
Difficulty rating: 800
Tags: brute force, greedy, implementation, math

Two friends are on the coordinate axis Ox in points with integer coordinates. One of them is in the point x1 = a, another one is in the point x2 = b.

Each of the friends can move by one along the line in any direction unlimited number of times. When a friend moves, the tiredness of a friend changes according to the following rules: the first move increases the tiredness by 1, the second move increases the tiredness by 2, the third — by 3 and so on. For example, if a friend moves first to the left, then to the right (returning to the same point), and then again to the left his tiredness becomes equal to 1 + 2 + 3 = 6.

The friends want to meet in a integer point. Determine the minimum total tiredness they should gain, if they meet in the same point.

Input format:
The first line contains a single integer a (1 ≤ a ≤ 1000) — the initial position of the first friend.

The second line contains a single integer b (1 ≤ b ≤ 1000) — the initial position of the second friend.

It is guaranteed that a ≠ b.

Output format:
Print the minimum possible total tiredness if the friends meet in the same point.

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

Note:
In the first example the first friend should move by one to the right (then the meeting happens at point 4), or the second friend should move by one to the left (then the meeting happens at point 3). In both cases, the total tiredness becomes 1.

In the second example the first friend should move by one to the left, and the second friend should move by one to the right. Then they meet in the point 100, and the total tiredness becomes 1 + 1 = 2.

In the third example one of the optimal ways is the following. The first friend should move three times to the right, and the second friend — two times to the left. Thus the friends meet in the point 8, and the total tiredness becomes 1 + 2 + 3 + 1 + 2 = 9.

Example input:
3
4

Example output:
1

Example input:
101
99

Example output:
2

Editorial:
Anton and Polyhedrons
Contest: Codeforces Round 404 (Div. 2)
Difficulty rating: 800
Tags: implementation, strings

Anton's favourite geometric figures are regular polyhedrons. Note that there are five kinds of regular polyhedrons:

- Tetrahedron. Tetrahedron has 4 triangular faces.
- Cube. Cube has 6 square faces.
- Octahedron. Octahedron has 8 triangular faces.
- Dodecahedron. Dodecahedron has 12 pentagonal faces.
- Icosahedron. Icosahedron has 20 triangular faces.

All five kinds of polyhedrons are shown on the picture below:

Anton has a collection of n polyhedrons. One day he decided to know, how many faces his polyhedrons have in total. Help Anton and find this number!

Input format:
The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of polyhedrons in Anton's collection.

Each of the following n lines of the input contains a string si — the name of the i-th polyhedron in Anton's collection. The string can look like this:

- "Tetrahedron" (without quotes), if the i-th polyhedron in Anton's collection is a tetrahedron.
- "Cube" (without quotes), if the i-th polyhedron in Anton's collection is a cube.
- "Octahedron" (without quotes), if the i-th polyhedron in Anton's collection is an octahedron.
- "Dodecahedron" (without quotes), if the i-th polyhedron in Anton's collection is a dodecahedron.
- "Icosahedron" (without quotes), if the i-th polyhedron in Anton's collection is an icosahedron.

Output format:
Output one number — the total number of faces in all the polyhedrons in Anton's collection.

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

Note:
In the first sample Anton has one icosahedron, one cube, one tetrahedron and one dodecahedron. Icosahedron has 20 faces, cube has 6 faces, tetrahedron has 4 faces and dodecahedron has 12 faces. In total, they have 20 + 6 + 4 + 12 = 42 faces.

Example input:
4
Icosahedron
Cube
Tetrahedron
Dodecahedron

Example output:
42

Example input:
3
Dodecahedron
Octahedron
Octahedron

Example output:
28

Editorial:
I think there's nothing to explain in this problem. Just check the polyhedron type, determine its number of faces and sum these numbers.
Time complexity is $${\mathcal{O}}(n)$$.
Add on a Tree
Contest: Codeforces Round 572 (Div. 1)
Difficulty rating: 1600
Tags: trees

Note that this is the first problem of the two similar problems. You can hack this problem only if you solve both problems.

You are given a tree with $$$n$$$ nodes. In the beginning, $$$0$$$ is written on all edges. In one operation, you can choose any $$$2$$$ distinct leaves $$$u$$$, $$$v$$$ and any real number $$$x$$$ and add $$$x$$$ to values written on all edges on the simple path between $$$u$$$ and $$$v$$$.

For example, on the picture below you can see the result of applying two operations to the graph: adding $$$2$$$ on the path from $$$7$$$ to $$$6$$$, and then adding $$$-0.5$$$ on the path from $$$4$$$ to $$$5$$$.

Is it true that for any configuration of real numbers written on edges, we can achieve it with a finite number of operations?

Leaf is a node of a tree of degree $$$1$$$. Simple path is a path that doesn't contain any node twice.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of nodes.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$), meaning that there is an edge between nodes $$$u$$$ and $$$v$$$. It is guaranteed that these edges form a tree.

Output format:
If there is a configuration of real numbers written on edges of the tree that we can't achieve by performing the operations, output "NO".

Otherwise, output "YES".

You can print each letter in any case (upper or lower).

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

Note:
In the first example, we can add any real $$$x$$$ to the value written on the only edge $$$(1, 2)$$$.

In the second example, one of configurations that we can't reach is $$$0$$$ written on $$$(1, 2)$$$ and $$$1$$$ written on $$$(2, 3)$$$.

Below you can see graphs from examples $$$3$$$, $$$4$$$:

Example input:
2
1 2

Example output:
YES

Example input:
3
1 2
2 3

Example output:
NO

Editorial:
Count Pairs
Contest: Codeforces Round 572 (Div. 1)
Difficulty rating: 2300
Tags: math, matrices, number theory, two pointers

You are given a prime number $$$p$$$, $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, and an integer $$$k$$$.

Find the number of pairs of indexes $$$(i, j)$$$ ($$$1 \le i < j \le n$$$) for which $$$(a_i + a_j)(a_i^2 + a_j^2) \equiv k \bmod p$$$.

Input format:
The first line contains integers $$$n, p, k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$2 \le p \le 10^9$$$, $$$0 \le k \le p-1$$$). $$$p$$$ is guaranteed to be prime.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le p-1$$$). It is guaranteed that all elements are different.

Output format:
Output a single integer — answer to the problem.

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

Note:
In the first example:

$$$(0+1)(0^2 + 1^2) = 1 \equiv 1 \bmod 3$$$.

$$$(0+2)(0^2 + 2^2) = 8 \equiv 2 \bmod 3$$$.

$$$(1+2)(1^2 + 2^2) = 15 \equiv 0 \bmod 3$$$.

So only $$$1$$$ pair satisfies the condition.

In the second example, there are $$$3$$$ such pairs: $$$(1, 5)$$$, $$$(2, 3)$$$, $$$(4, 6)$$$.

Example input:
3 3 0
0 1 2

Example output:
1

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

Example output:
3

Editorial:
Let's transform condtition a ittle bit. $$$a_i - a_j \not\equiv 0$$$ $$$mod$$$ $$$p$$$, so condtition is equivalent:
$$$(a_i - a_j)(a_i + a_j)(a^2_{i} + a^2_{j}) \equiv (a_i - a_j)k \Leftrightarrow a^4_{i} - a^4_{j} \equiv ka_i - ka_j \Leftrightarrow a^4_{i} - ka_i \equiv a^4_{j} - ka_j$$$.
That's why we just need to count number of pairs of equal numbers in the array $$$b_i = (a^4_{i} - ka_i)$$$ $$$mod$$$ $$$p$$$. It's easy to do it, for example, using map. Complexity $$$O(n)$$$ or $$$O(nlog(n))$$$.
// code
$$$\textbf{Challenge}$$$
Solve the task, if numbers are not necessarily different.
Make Equal
Contest: Codeforces Round 572 (Div. 1)
Difficulty rating: 3100
Tags: dp

You are given $$$n$$$ numbers $$$a_1, a_2, \dots, a_n$$$. In one operation we can add to any one of those numbers a nonnegative integer power of $$$2$$$.

What is the smallest number of operations we need to perform to make all $$$n$$$ numbers equal? It can be proved that under given constraints it doesn't exceed $$$10^{18}$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^{17}$$$).

Output format:
Output exactly one integer — the smallest number of operations we need to perform to make all $$$n$$$ numbers equal.

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

Note:
In the first example, all numbers are already equal. So the needed number of operation is $$$0$$$.

In the second example, we can apply the operation $$$3$$$ times: add $$$8$$$ to first $$$2$$$, add $$$8$$$ to second $$$2$$$, add $$$2$$$ to $$$8$$$, making all numbers equal to $$$10$$$. It can be proved that we can't make all numbers equal in less than $$$3$$$ operations.

Example input:
4
228 228 228 228

Example output:
0

Example input:
3
2 2 8

Example output:
3

Editorial:
Problem from Red Panda
Contest: Codeforces Round 572 (Div. 1)
Difficulty rating: 3300
Tags: combinatorics

At Moscow Workshops ICPC team gets a balloon for each problem they solved first. Team MSU Red Panda got so many balloons that they didn't know how to spend them. So they came up with a problem with them.

There are several balloons, not more than $$$10^6$$$ in total, each one is colored in one of $$$k$$$ colors. We can perform the following operation: choose $$$k-1$$$ balloons such that they are of $$$k-1$$$ different colors, and recolor them all into remaining color. We can perform this operation any finite number of times (for example, we can only perform the operation if there are at least $$$k-1$$$ different colors among current balls).

How many different balloon configurations can we get? Only number of balloons of each color matters, configurations differing only by the order of balloons are counted as equal. As this number can be very large, output it modulo $$$998244353$$$.

Input format:
The first line contains a single integer $$$k$$$ ($$$2 \le k \le 10^5$$$) —the number of colors.

The second line contains $$$k$$$ integers $$$a_1, a_2, \ldots, a_k$$$ ($$$0 \le a_i$$$) —initial configuration of balloons. $$$a_i$$$ is number of balloons of color $$$i$$$. The total number of balloons doesn't exceed $$$10^6$$$. In other words,

$$$a_1 + a_2 + a_3 + \ldots + a_k \le 10^6$$$.

Output format:
Output number of possible configurations modulo $$$998244353$$$.

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

Note:
In the first example, there are $$$3$$$ configurations we can get: $$$[0, 1, 2]$$$, $$$[2, 0, 1]$$$, $$$[1, 2, 0]$$$.

In the second example, we can apply the operation not more than once, and possible configurations are: $$$[1, 1, 1, 1]$$$, $$$[0, 0, 0, 4]$$$, $$$[0, 0, 4, 0]$$$, $$$[0, 4, 0, 0]$$$, $$$[4, 0, 0, 0]$$$.

In the third example, we can't apply any operations, so the only achievable configuration is the starting one.

Example input:
3
0 1 2

Example output:
3

Example input:
4
1 1 1 1

Example output:
5

Editorial:
Appleman and Easy Task
Contest: Codeforces Round 263 (Div. 2)
Difficulty rating: 1000
Tags: brute force, implementation

Toastman came up with a very easy task. He gives it to Appleman, but Appleman doesn't know how to solve it. Can you help him?

Given a n × n checkerboard. Each cell of the board has either character 'x', or character 'o'. Is it true that each cell of the board has even number of adjacent cells with 'o'? Two cells of the board are adjacent if they share a side.

Input format:
The first line contains an integer n (1 ≤ n ≤ 100). Then n lines follow containing the description of the checkerboard. Each of them contains n characters (either 'x' or 'o') without spaces.

Output format:
Print "YES" or "NO" (without the quotes) depending on the answer to the problem.

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

Example input:
3
xxo
xox
oxx

Example output:
YES

Example input:
4
xxxo
xoxo
oxox
xxxx

Example output:
NO

Editorial:
Appleman and Card Game
Contest: Codeforces Round 263 (Div. 2)
Difficulty rating: 1300
Tags: greedy

Appleman has n cards. Each card has an uppercase letter written on it. Toastman must choose k cards from Appleman's cards. Then Appleman should give Toastman some coins depending on the chosen cards. Formally, for each Toastman's card i you should calculate how much Toastman's cards have the letter equal to letter on ith, then sum up all these quantities, such a number of coins Appleman should give to Toastman.

Given the description of Appleman's cards. What is the maximum number of coins Toastman can get?

Input format:
The first line contains two integers n and k (1 ≤ k ≤ n ≤ 105). The next line contains n uppercase letters without spaces — the i-th letter describes the i-th card of the Appleman.

Output format:
Print a single integer – the answer to the problem.

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

Note:
In the first test example Toastman can choose nine cards with letter D and one additional card with any letter. For each card with D he will get 9 coins and for the additional card he will get 1 coin.

Example input:
15 10
DZFDFZDFDDDDDDF

Example output:
82

Example input:
6 4
YJSNPI

Example output:
4

Editorial:
Mr. Kitayuta's Colorful Graph
Contest: Codeforces Round 286 (Div. 1)
Difficulty rating: 2400
Tags: brute force, dfs and similar, dsu, graphs

Mr. Kitayuta has just bought an undirected graph with n vertices and m edges. The vertices of the graph are numbered from 1 to n. Each edge, namely edge i, has a color ci, connecting vertex ai and bi.

Mr. Kitayuta wants you to process the following q queries.

In the i-th query, he gives you two integers - ui and vi.

Find the number of the colors that satisfy the following condition: the edges of that color connect vertex ui and vertex vi directly or indirectly.

Input format:
The first line of the input contains space-separated two integers - n and m(2 ≤ n ≤ 105, 1 ≤ m ≤ 105), denoting the number of the vertices and the number of the edges, respectively.

The next m lines contain space-separated three integers - ai, bi(1 ≤ ai < bi ≤ n) and ci(1 ≤ ci ≤ m). Note that there can be multiple edges between two vertices. However, there are no multiple edges of the same color between two vertices, that is, if i ≠ j, (ai, bi, ci) ≠ (aj, bj, cj).

The next line contains a integer- q(1 ≤ q ≤ 105), denoting the number of the queries.

Then follows q lines, containing space-separated two integers - ui and vi(1 ≤ ui, vi ≤ n). It is guaranteed that ui ≠ vi.

Output format:
For each query, print the answer in a separate line.

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

Note:
Let's consider the first sample.

The figure above shows the first sample.

- Vertex 1 and vertex 2 are connected by color 1 and 2.
- Vertex 3 and vertex 4 are connected by color 3.
- Vertex 1 and vertex 4 are not connected by any single color.

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

Example output:
2
1
0

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

Example output:
1
1
1
1
2

Editorial: