1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
The Football Season
Contest: Codeforces Round 592 (Div. 2)
Difficulty rating: 2000
Tags: brute force, math, number theory

The football season has just ended in Berland. According to the rules of Berland football, each match is played between two teams. The result of each match is either a draw, or a victory of one of the playing teams. If a team wins the match, it gets $$$w$$$ points, and the opposing team gets $$$0$$$ points. If the game results in a draw, both teams get $$$d$$$ points.

The manager of the Berland capital team wants to summarize the results of the season, but, unfortunately, all information about the results of each match is lost. The manager only knows that the team has played $$$n$$$ games and got $$$p$$$ points for them.

You have to determine three integers $$$x$$$, $$$y$$$ and $$$z$$$ — the number of wins, draws and loses of the team. If there are multiple answers, print any of them. If there is no suitable triple $$$(x, y, z)$$$, report about it.

Input format:
The first line contains four integers $$$n$$$, $$$p$$$, $$$w$$$ and $$$d$$$ $$$(1 \le n \le 10^{12}, 0 \le p \le 10^{17}, 1 \le d < w \le 10^{5})$$$ — the number of games, the number of points the team got, the number of points awarded for winning a match, and the number of points awarded for a draw, respectively. Note that $$$w > d$$$, so the number of points awarded for winning is strictly greater than the number of points awarded for draw.

Output format:
If there is no answer, print $$$-1$$$.

Otherwise print three non-negative integers $$$x$$$, $$$y$$$ and $$$z$$$ — the number of wins, draws and losses of the team. If there are multiple possible triples $$$(x, y, z)$$$, print any of them. The numbers should meet the following conditions:

- $$$x \cdot w + y \cdot d = p$$$,
- $$$x + y + z = n$$$.

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

Note:
One of the possible answers in the first example — $$$17$$$ wins, $$$9$$$ draws and $$$4$$$ losses. Then the team got $$$17 \cdot 3 + 9 \cdot 1 = 60$$$ points in $$$17 + 9 + 4 = 30$$$ games.

In the second example the maximum possible score is $$$10 \cdot 5 = 50$$$. Since $$$p = 51$$$, there is no answer.

In the third example the team got $$$0$$$ points, so all $$$20$$$ games were lost.

Example input:
30 60 3 1

Example output:
17 9 4

Example input:
10 51 5 4

Example output:
-1

Editorial:
The crucial observation is that $$$d$$$ wins give us the same amount of points as $$$w$$$ draws. Let's use them to solve a problem where we want to minimize the total amount of wins and draws giving $$$p$$$ points (if it is not greater than $$$n$$$, we can just lose all other matches).
If $$$y \ge w$$$, then we can subtract $$$w$$$ from $$$y$$$ and add $$$d$$$ to $$$x$$$, the number of wins and draws will decrease, and the number of points will stay the same. So we can limit the number of draws to $$$w - 1$$$. And the solution is the following: iterate on the number of draws $$$y$$$ from $$$0$$$ to $$$w - 1$$$, and check if the current value of $$$y$$$ gives us the result we need ($$$p - yd$$$ should be non-negative and divisible by $$$w$$$, and $$$\frac{p - yd}{w} + y$$$ should be not greater than $$$n$$$).
On Number of Decompositions into Multipliers
Contest: Codeforces Round 232 (Div. 1)
Tags: combinatorics, math, number theory

You are given an integer m as a product of integers a1, a2, ... an $$(m=\prod_{i=1}^{n}a_{i})$$. Your task is to find the number of distinct decompositions of number m into the product of n ordered positive integers.

Decomposition into n products, given in the input, must also be considered in the answer. As the answer can be very large, print it modulo 1000000007 (109 + 7).

Input format:
The first line contains positive integer n (1 ≤ n ≤ 500). The second line contains space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Output format:
In a single line print a single number k — the number of distinct decompositions of number m into n ordered multipliers modulo 1000000007 (109 + 7).

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

Note:
In the second sample, the get a decomposition of number 2, you need any one number out of three to equal 2, and the rest to equal 1.

In the third sample, the possible ways of decomposing into ordered multipliers are [7,5], [5,7], [1,35], [35,1].

A decomposition of positive integer m into n ordered multipliers is a cortege of positive integers b = {b1, b2, ... bn} such that $$m = \prod_{i=1}^{n} b_i$$. Two decompositions b and c are considered different, if there exists index i such that bi ≠ ci.

Example input:
1
15

Example output:
1

Example input:
3
1 1 2

Example output:
3

Editorial:
On Sum of Fractions
Contest: Codeforces Round 232 (Div. 1)
Tags: math, number theory

Let's assume that

- v(n) is the largest prime number, that does not exceed n;
- u(n) is the smallest prime number strictly greater than n.

Find $$\sum_{i=2}^{n}\frac{1}{v(i)u(i)}$$.

Input format:
The first line contains integer t (1 ≤ t ≤ 500) — the number of testscases.

Each of the following t lines of the input contains integer n (2 ≤ n ≤ 109).

Output format:
Print t lines: the i-th of them must contain the answer to the i-th test as an irreducible fraction "p/q", where p, q are integers, q > 0.

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

Example input:
2
2
3

Example output:
1/6
7/30

Editorial:
On Changing Tree
Contest: Codeforces Round 232 (Div. 1)
Tags: data structures, graphs, trees

You are given a rooted tree consisting of n vertices numbered from 1 to n. The root of the tree is a vertex number 1.

Initially all vertices contain number 0. Then come q queries, each query has one of the two types:

- The format of the query: 1 v x k. In response to the query, you need to add to the number at vertex v number x; to the numbers at the descendants of vertex v at distance 1, add x - k; and so on, to the numbers written in the descendants of vertex v at distance i, you need to add x - (i·k). The distance between two vertices is the number of edges in the shortest path between these vertices.
- The format of the query: 2 v. In reply to the query you should print the number written in vertex v modulo 1000000007 (109 + 7).

Process the queries given in the input.

Input format:
The first line contains integer n (1 ≤ n ≤ 3·105) — the number of vertices in the tree. The second line contains n - 1 integers p2, p3, ... pn (1 ≤ pi < i), where pi is the number of the vertex that is the parent of vertex i in the tree.

The third line contains integer q (1 ≤ q ≤ 3·105) — the number of queries. Next q lines contain the queries, one per line. The first number in the line is type. It represents the type of the query. If type = 1, then next follow space-separated integers v, x, k (1 ≤ v ≤ n; 0 ≤ x < 109 + 7; 0 ≤ k < 109 + 7). If type = 2, then next follows integer v (1 ≤ v ≤ n) — the vertex where you need to find the value of the number.

Output format:
For each query of the second type print on a single line the number written in the vertex from the query. Print the number modulo 1000000007 (109 + 7).

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

Note:
You can read about a rooted tree here: http://en.wikipedia.org/wiki/Tree_(graph_theory).

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

Example output:
2
1

Editorial:
On Sum of Number of Inversions in Permutations
Contest: Codeforces Round 232 (Div. 1)
Tags: combinatorics, math

You are given a permutation p. Calculate the total number of inversions in all permutations that lexicographically do not exceed the given one.

As this number can be very large, print it modulo 1000000007 (109 + 7).

Input format:
The first line contains a single integer n (1 ≤ n ≤ 106) — the length of the permutation. The second line contains n distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n).

Output format:
Print a single number — the answer to the problem modulo 1000000007 (109 + 7).

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

Note:
Permutation p of length n is the sequence that consists of n distinct integers, each of them is from 1 to n.

An inversion of permutation p1, p2, ..., pn is a pair of indexes (i, j), such that i < j and pi > pj.

Permutation a do not exceed permutation b lexicographically, if either a = b or there exists such number i, for which the following logical condition fulfills: $$(\forall j<i,\;a_{j}=b_{j})$$ AND (ai < bi).

Example input:
2
2 1

Example output:
1

Example input:
3
2 1 3

Example output:
2

Editorial:
On Iteration of One Well-Known Function
Contest: Codeforces Round 232 (Div. 1)
Tags: math

Of course, many of you can calculate φ(n) — the number of positive integers that are less than or equal to n, that are coprime with n. But what if we need to calculate φ(φ(...φ(n))), where function φ is taken k times and n is given in the canonical decomposition into prime factors?

You are given n and k, calculate the value of φ(φ(...φ(n))). Print the result in the canonical decomposition into prime factors.

Input format:
The first line contains integer m (1 ≤ m ≤ 105) — the number of distinct prime divisors in the canonical representaion of n.

Each of the next m lines contains a pair of space-separated integers pi, ai (2 ≤ pi ≤ 106; 1 ≤ ai ≤ 1017) — another prime divisor of number n and its power in the canonical representation. The sum of all ai doesn't exceed 1017. Prime divisors in the input follow in the strictly increasing order.

The last line contains integer k (1 ≤ k ≤ 1018).

Output format:
In the first line, print integer w — the number of distinct prime divisors of number φ(φ(...φ(n))), where function φ is taken k times.

Each of the next w lines must contain two space-separated integers qi, bi (bi ≥ 1) — another prime divisor and its power in the canonical representaion of the result. Numbers qi must go in the strictly increasing order.

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

Note:
You can read about canonical representation of a positive integer here: http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic.

You can read about function φ(n) here: http://en.wikipedia.org/wiki/Euler's_totient_function.

Example input:
1
7 1
1

Example output:
2
2 1
3 1

Example input:
1
7 1
2

Example output:
1
2 1

Editorial:
Burenka and Traditions (easy version)
Contest: Codeforces Round 814 (Div. 1)
Difficulty rating: 1800
Tags: dp, greedy

This is the easy version of this problem. The difference between easy and hard versions is only the constraints on $$$a_i$$$ and on $$$n$$$. You can make hacks only if both versions of the problem are solved.

Burenka is the crown princess of Buryatia, and soon she will become the $$$n$$$-th queen of the country. There is an ancient tradition in Buryatia — before the coronation, the ruler must show their strength to the inhabitants. To determine the strength of the $$$n$$$-th ruler, the inhabitants of the country give them an array of $$$a$$$ of exactly $$$n$$$ numbers, after which the ruler must turn all the elements of the array into zeros in the shortest time. The ruler can do the following two-step operation any number of times:

- select two indices $$$l$$$ and $$$r$$$, so that $$$1 \le l \le r \le n$$$ and a non-negative integer $$$x$$$, then
- for all $$$l \leq i \leq r$$$ assign $$$a_i := a_i \oplus x$$$, where $$$\oplus$$$ denotes the bitwise XOR operation. It takes $$$\left\lceil \frac{r-l+1}{2} \right\rceil$$$ seconds to do this operation, where $$$\lceil y \rceil$$$ denotes $$$y$$$ rounded up to the nearest integer.

Help Burenka calculate how much time she will need.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the size of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 5000$$$) — elements of the array.

It is guaranteed that the sum of $$$n$$$ in all tests does not exceed $$$5000$$$.

Output format:
For each test case, output a single number  — the minimum time that Burenka will need.

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

Note:
In the first test case, Burenka can choose segment $$$l = 1$$$, $$$r = 4$$$, and $$$x=5$$$. so it will fill the array with zeros in $$$2$$$ seconds.

In the second test case, Burenka first selects segment $$$l = 1$$$, $$$r = 2$$$, and $$$x = 1$$$, after which $$$a = [0, 2, 2]$$$, and then the segment $$$l = 2$$$, $$$r = 3$$$, and $$$x=2$$$, which fills the array with zeros. In total, Burenka will spend $$$2$$$ seconds.

Example input:
7
4
5 5 5 5
3
1 3 2
2
0 0
3
2 5 7
6
1 2 3 3 2 1
10
27 27 34 32 2 31 23 56 52 4
5
1822 1799 57 23 55

Example output:
2
2
0
2
4
7
4

Editorial:
Burenka and Traditions (hard version)
Contest: Codeforces Round 814 (Div. 1)
Difficulty rating: 1900
Tags: data structures, dp, greedy

This is the hard version of this problem. The difference between easy and hard versions is only the constraints on $$$a_i$$$ and on $$$n$$$. You can make hacks only if both versions of the problem are solved.

Burenka is the crown princess of Buryatia, and soon she will become the $$$n$$$-th queen of the country. There is an ancient tradition in Buryatia — before the coronation, the ruler must show their strength to the inhabitants. To determine the strength of the $$$n$$$-th ruler, the inhabitants of the country give them an array of $$$a$$$ of exactly $$$n$$$ numbers, after which the ruler must turn all the elements of the array into zeros in the shortest time. The ruler can do the following two-step operation any number of times:

- select two indices $$$l$$$ and $$$r$$$, so that $$$1 \le l \le r \le n$$$ and a non-negative integer $$$x$$$, then
- for all $$$l \leq i \leq r$$$ assign $$$a_i := a_i \oplus x$$$, where $$$\oplus$$$ denotes the bitwise XOR operation. It takes $$$\left\lceil \frac{r-l+1}{2} \right\rceil$$$ seconds to do this operation, where $$$\lceil y \rceil$$$ denotes $$$y$$$ rounded up to the nearest integer.

Help Burenka calculate how much time she will need.

Input format:
The first line contains a single integer $$$t$$$ $$$(1 \le t \le 500)$$$  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ - the size of the array

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \cdots , a_n$$$ $$$(0 \le a_i < 2^{30})$$$ — elements of the array.

It is guaranteed that the sum of $$$n$$$ in all tests does not exceed $$$10^5$$$.

Output format:
For each test case, output a single number  — the minimum time that Burenka will need.

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

Note:
In the first test case, Burenka can choose segment $$$l = 1$$$, $$$r = 4$$$, and $$$x=5$$$. so it will fill the array with zeros in $$$2$$$ seconds.

In the second test case, Burenka first selects segment $$$l = 1$$$, $$$r = 2$$$, and $$$x = 1$$$, after which $$$a = [0, 2, 2]$$$, and then the segment $$$l = 2$$$, $$$r = 3$$$, and $$$x=2$$$, which fills the array with zeros. In total, Burenka will spend $$$2$$$ seconds.

Example input:
7
4
5 5 5 5
3
1 3 2
2
0 0
3
2 5 7
6
1 2 3 3 2 1
10
27 27 34 32 2 31 23 56 52 4
5
1822 1799 57 23 55

Example output:
2
2
0
2
4
7
4

Editorial:
Fibonacci Strings
Contest: Codeforces Round 814 (Div. 1)
Difficulty rating: 2000
Tags: greedy, implementation, math, number theory

In all schools in Buryatia, in the $$$1$$$ class, everyone is told the theory of Fibonacci strings.

"A block is a subsegment of a string where all the letters are the same and are bounded on the left and right by the ends of the string or by letters other than the letters in the block. A string is called a Fibonacci string if, when it is divided into blocks, their lengths in the order they appear in the string form the Fibonacci sequence ($$$f_0 = f_1 = 1$$$, $$$f_i = f_{i-2} + f_{i-1}$$$), starting from the zeroth member of this sequence. A string is called semi-Fibonacci if it possible to reorder its letters to get a Fibonacci string."

Burenka decided to enter the Buryat State University, but at the entrance exam she was given a difficult task. She was given a string consisting of the letters of the Buryat alphabet (which contains exactly $$$k$$$ letters), and was asked if the given string is semi-Fibonacci. The string can be very long, so instead of the string, she was given the number of appearances of each letter ($$$c_i$$$ for the $$$i$$$-th letter) in that string. Unfortunately, Burenka no longer remembers the theory of Fibonacci strings, so without your help she will not pass the exam.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The following is a description of the input data sets.

The first line of each test case contains one integer $$$k$$$ ($$$1 \leq k \leq 100$$$) — the number of letters in the alphabet.

The second line of each test case contains $$$k$$$ integers $$$c_1, c_2, \ldots, c_k$$$ ($$$1 \leq c_i \leq 10^9$$$) — the number of occurrences of each letter in the string.

Output format:
For each test case print the string "YES" if the corresponding string is semi-Fibonacci, and "NO" if it is not.

You can print "YES" and "NO" in any case (for example, the strings "yEs", "yes", "Yes" will be recognized as a positive answer).

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

Note:
In the first test case, a one-character string is semi-Fibonacci, being itself a Fibonacci string.

In the second test case, a string of two different characters is Fibonacci.

In the third test case, the string "abb" (let the first of the alphabet letter be a, the second letter b) is not a semi-Fibonacci string, since no permutation of its letters ("abb", "bab", and "bba") is a Fibonacci string.

In the fourth test case, two permutations of the letters of the string "abaccac" (the first letter is a, the second letter is b, the third letter is c) are Fibonacci strings — "abaaccc" and "cbccaaa".

Example input:
6
1
1
2
1 1
2
1 2
3
3 1 3
2
7 5
6
26 8 3 4 13 34

Example output:
YES
YES
NO
YES
NO
YES

Editorial:
Tonya and Burenka-179
Contest: Codeforces Round 814 (Div. 1)
Difficulty rating: 2400
Tags: data structures, greedy, math, number theory

Tonya was given an array of $$$a$$$ of length $$$n$$$ written on a postcard for his birthday. For some reason, the postcard turned out to be a cyclic array, so the index of the element located strictly to the right of the $$$n$$$-th is $$$1$$$. Tonya wanted to study it better, so he bought a robot "Burenka-179".

A program for Burenka is a pair of numbers $$$(s, k)$$$, where $$$1 \leq s \leq n$$$, $$$1 \leq k \leq n-1$$$. Note that $$$k$$$ cannot be equal to $$$n$$$. Initially, Tonya puts the robot in the position of the array $$$s$$$. After that, Burenka makes exactly $$$n$$$ steps through the array. If at the beginning of a step Burenka stands in the position $$$i$$$, then the following happens:

1. The number $$$a_{i}$$$ is added to the usefulness of the program.
2. "Burenka" moves $$$k$$$ positions to the right ($$$i := i + k$$$ is executed, if $$$i$$$ becomes greater than $$$n$$$, then $$$i := i - n$$$).

Help Tonya find the maximum possible usefulness of a program for "Burenka" if the initial usefulness of any program is $$$0$$$.

Also, Tony's friend Ilyusha asks him to change the array $$$q$$$ times. Each time he wants to assign $$$a_p := x$$$ for a given index $$$p$$$ and a value $$$x$$$. You need to find the maximum possible usefulness of the program after each of these changes.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) is the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$0 \le q \le 2 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — elements of the array.

The following $$$q$$$ lines contain changes, each of them contains two integers $$$p$$$ and $$$x$$$ ($$$1 \leq p \leq n$$$, $$$1 \leq x \leq 10^9$$$), meaning you should assign $$$a_p := x$$$.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output $$$q+1$$$ numbers — the maximum usefulness of a program initially and after each of the changes.

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

Note:
In the first test case, initially and after each request, the answer is achieved at $$$s = 1$$$, $$$k = 1$$$ or $$$s = 2$$$, $$$k = 1$$$.

In the second test case, initially, the answer is achieved when $$$s = 1$$$, $$$k = 2$$$ or $$$s = 3$$$, $$$k = 2$$$. After the first request, the answer is achieved at $$$s = 2$$$, $$$k = 2$$$ or $$$s = 4$$$, $$$k = 2$$$.

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

Example output:
3
5
14
16
24
24
24
57
54
36
36
6
18
27
28

Editorial:
Impressionism
Contest: Codeforces Round 814 (Div. 1)
Difficulty rating: 3500
Tags: constructive algorithms, graphs, implementation, math

Burenka has two pictures $$$a$$$ and $$$b$$$, which are tables of the same size $$$n \times m$$$. Each cell of each painting has a color — a number from $$$0$$$ to $$$2 \cdot 10^5$$$, and there are no repeating colors in any row or column of each of the two paintings, except color $$$0$$$.

Burenka wants to get a picture $$$b$$$ from the picture $$$a$$$. To achieve her goal, Burenka can perform one of $$$2$$$ operations: swap any two rows of $$$a$$$ or any two of its columns. Tell Burenka if she can fulfill what she wants, and if so, tell her the sequence of actions.

The rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, the columns are numbered from $$$1$$$ to $$$m$$$ from left to right.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \cdot m \leq 2 \cdot 10^5$$$) — the sizes of the table.

The $$$i$$$-th of the next $$$n$$$ lines contains $$$m$$$ integers $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$$$ ($$$0 \leq a_{i,j} \leq 2 \cdot 10^5$$$) — the colors of the $$$i$$$-th row of picture $$$a$$$. It is guaranteed that there are no identical colors in the same row or column, except color $$$0$$$.

The $$$i$$$-th of the following $$$n$$$ lines contains $$$m$$$ integers $$$b_{i, 1}, b_{i, 2}, \ldots, b_{i, m}$$$ ($$$0 \leq b_{i,j} \leq 2 \cdot 10^5$$$) — the colors of the $$$i$$$-th row of picture $$$b$$$. It is guaranteed that there are no identical colors in the same row or column, except color $$$0$$$.

Output format:
In the first line print the number $$$-1$$$ if it is impossible to achieve what Burenka wants, otherwise print the number of actions in your solution $$$k$$$ ($$$0 \le k \le 2 \cdot 10^5$$$). It can be proved that if a solution exists, then there exists a solution where $$$k \le 2 \cdot 10^5$$$.

In the next $$$k$$$ lines print the operations. First print the type of the operation ($$$1$$$ — swap rows, $$$2$$$ — columns), and then print the two indices of rows or columns to which the operation is applied.

Note that you don't have to minimize the number of operations.

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

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

Example output:
1
1 1 3

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

Example output:
4
1 3 4
2 3 4
2 2 3
2 1 2

Editorial: