1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Zero-Sum Prefixes
Contest: Codeforces Round 833 (Div. 2)
Difficulty rating: 1600
Tags: brute force, data structures, dp, greedy, implementation

The score of an array $$$v_1,v_2,\ldots,v_n$$$ is defined as the number of indices $$$i$$$ ($$$1 \le i \le n$$$) such that $$$v_1+v_2+\ldots+v_i = 0$$$.

You are given an array $$$a_1,a_2,\ldots,a_n$$$ of length $$$n$$$. You can perform the following operation multiple times:

- select an index $$$i$$$ ($$$1 \le i \le n$$$) such that $$$a_i=0$$$;
- then replace $$$a_i$$$ by an arbitrary integer.

What is the maximum possible score of $$$a$$$ that can be obtained by performing a sequence of such operations?

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

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.

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

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

Output format:
For each test case, print the maximum possible score of the array $$$a$$$ after performing a sequence of operations.

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

Note:
In the first test case, it is optimal to change the value of $$$a_2$$$ to $$$-2$$$ in one operation.

The resulting array $$$a$$$ will be $$$[2,-2,1,-1,0]$$$, with a score of $$$3$$$:

- $$$a_1+a_2=2-2=0$$$;
- $$$a_1+a_2+a_3+a_4=2-2+1-1=0$$$;
- $$$a_1+a_2+a_3+a_4+a_5=2-2+1-1+0=0$$$.

In the second test case, it is optimal to change the value of $$$a_3$$$ to $$$-2\,000\,000\,000$$$, giving us an array with a score of $$$1$$$.

In the third test case, it is not necessary to perform any operations.

Example input:
5
5
2 0 1 -1 0
3
1000000000 1000000000 0
4
0 0 0 0
8
3 0 2 -10 10 -30 30 0
9
1 0 0 1 -1 0 1 0 -1

Example output:
3
1
4
4
5

Editorial:
Editorial link: https://codeforces.com/blog/entry/108319
ConstructOR
Contest: Codeforces Round 833 (Div. 2)
Difficulty rating: 2100
Tags: bitmasks, chinese remainder theorem, combinatorics, constructive algorithms, math, number theory

You are given three integers $$$a$$$, $$$b$$$, and $$$d$$$. Your task is to find any integer $$$x$$$ which satisfies all of the following conditions, or determine that no such integers exist:

- $$$0 \le x \lt 2^{60}$$$;
- $$$a|x$$$ is divisible by $$$d$$$;
- $$$b|x$$$ is divisible by $$$d$$$.

Here, $$$|$$$ denotes the bitwise OR operation.

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

Each test case consists of one line, containing three integers $$$a$$$, $$$b$$$, and $$$d$$$ ($$$1 \le a,b,d \lt 2^{30}$$$).

Output format:
For each test case print one integer. If there exists an integer $$$x$$$ which satisfies all of the conditions from the statement, print $$$x$$$. Otherwise, print $$$-1$$$.

If there are multiple solutions, you may print any of them.

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

Note:
In the first test case, $$$x=18$$$ is one of the possible solutions, since $$$39|18=55$$$ and $$$12|18=30$$$, both of which are multiples of $$$d=5$$$.

In the second test case, $$$x=14$$$ is one of the possible solutions, since $$$8|14=6|14=14$$$, which is a multiple of $$$d=14$$$.

In the third and fourth test cases, we can show that there are no solutions.

Example input:
8
12 39 5
6 8 14
100 200 200
3 4 6
2 2 2
18 27 3
420 666 69
987654321 123456789 999999999

Example output:
18
14
-1
-1
0
11
25599
184470016815529983

Editorial:
Editorial link: https://codeforces.com/blog/entry/108319
Yet Another Array Counting Problem
Contest: Codeforces Round 833 (Div. 2)
Difficulty rating: 2300
Tags: binary search, data structures, divide and conquer, dp, flows, math, trees

The position of the leftmost maximum on the segment $$$[l; r]$$$ of array $$$x = [x_1, x_2, \ldots, x_n]$$$ is the smallest integer $$$i$$$ such that $$$l \le i \le r$$$ and $$$x_i = \max(x_l, x_{l+1}, \ldots, x_r)$$$.

You are given an array $$$a = [a_1, a_2, \ldots, a_n]$$$ of length $$$n$$$. Find the number of integer arrays $$$b = [b_1, b_2, \ldots, b_n]$$$ of length $$$n$$$ that satisfy the following conditions:

- $$$1 \le b_i \le m$$$ for all $$$1 \le i \le n$$$;
- for all pairs of integers $$$1 \le l \le r \le n$$$, the position of the leftmost maximum on the segment $$$[l; r]$$$ of the array $$$b$$$ is equal to the position of the leftmost maximum on the segment $$$[l; r]$$$ of the array $$$a$$$.

Since the answer might be very large, print its remainder modulo $$$10^9+7$$$.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases.

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

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

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases doesn't exceed $$$10^6$$$.

Output format:
For each test case print one integer — the number of arrays $$$b$$$ that satisfy the conditions from the statement, modulo $$$10^9+7$$$.

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

Note:
In the first test case, the following $$$8$$$ arrays satisfy the conditions from the statement:

- $$$[1,2,1]$$$;
- $$$[1,2,2]$$$;
- $$$[1,3,1]$$$;
- $$$[1,3,2]$$$;
- $$$[1,3,3]$$$;
- $$$[2,3,1]$$$;
- $$$[2,3,2]$$$;
- $$$[2,3,3]$$$.

In the second test case, the following $$$5$$$ arrays satisfy the conditions from the statement:

- $$$[1,1,1,1]$$$;
- $$$[2,1,1,1]$$$;
- $$$[2,2,1,1]$$$;
- $$$[2,2,2,1]$$$;
- $$$[2,2,2,2]$$$.

Example input:
4
3 3
1 3 2
4 2
2 2 2 2
6 9
6 9 6 9 6 9
9 100
10 40 20 20 100 60 80 60 60

Example output:
8
5
11880
351025663

Editorial:
Editorial link: https://codeforces.com/blog/entry/108319
Circular Xor Reversal
Contest: Codeforces Round 833 (Div. 2)
Difficulty rating: 3000
Tags: bitmasks, constructive algorithms

You have an array $$$a_0, a_1, \ldots, a_{n-1}$$$ of length $$$n$$$. Initially, $$$a_i = 2^i$$$ for all $$$0 \le i \lt n$$$. Note that array $$$a$$$ is zero-indexed.

You want to reverse this array (that is, make $$$a_i$$$ equal to $$$2^{n-1-i}$$$ for all $$$0 \le i \lt n$$$). To do this, you can perform the following operation no more than $$$250\,000$$$ times:

- Select an integer $$$i$$$ ($$$0 \le i \lt n$$$) and replace $$$a_i$$$ by $$$a_i \oplus a_{(i+1)\bmod n}$$$.

Here, $$$\oplus$$$ denotes the bitwise XOR operation.

Your task is to find any sequence of operations that will result in the array $$$a$$$ being reversed. It can be shown that under the given constraints, a solution always exists.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 400$$$) — the length of the array $$$a$$$.

Output format:
On the first line print one integer $$$k$$$ ($$$0 \le k \le 250\,000$$$) — the number of operations performed.

On the second line print $$$k$$$ integers $$$i_1,i_2,\ldots,i_k$$$ ($$$0 \le i_j \lt n$$$). Here, $$$i_j$$$ should be the integer selected on the $$$j$$$-th operation.

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

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

Note:
In the notes, the elements on which the operations are performed are colored red.

In the first test case, array $$$a$$$ will change in the following way:

$$$[1,\color{red}{2}] \rightarrow [\color{red}{1},3] \rightarrow [2,\color{red}{3}] \rightarrow [2,1]$$$.

In the second test case, array $$$a$$$ will change in the following way:

$$$[1,\color{red}{2},4] \rightarrow [\color{red}{1},6,4] \rightarrow [7,\color{red}{6},4] \rightarrow [\color{red}{7},2,4] \rightarrow [5,2,\color{red}{4}] \rightarrow [5,\color{red}{2},1] \rightarrow [\color{red}{5},3,1] \rightarrow [6,\color{red}{3},1] \rightarrow [\color{red}{6},2,1] \rightarrow [4,2,1]$$$.

Example input:
2

Example output:
3
1 0 1

Example input:
3

Example output:
9
1 0 1 0 2 1 0 1 0

Editorial:
Editorial link: https://codeforces.com/blog/entry/108319
Lucky Conversion
Contest: Codeforces Round 104 (Div. 1)
Difficulty rating: 1200
Tags: greedy, implementation

Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya has two strings a and b of the same length n. The strings consist only of lucky digits. Petya can perform operations of two types:

- replace any one digit from string a by its opposite (i.e., replace 4 by 7 and 7 by 4);
- swap any pair of digits in string a.

Petya is interested in the minimum number of operations that are needed to make string a equal to string b. Help him with the task.

Input format:
The first and the second line contains strings a and b, correspondingly. Strings a and b have equal lengths and contain only lucky digits. The strings are not empty, their length does not exceed 105.

Output format:
Print on the single line the single number — the minimum number of operations needed to convert string a into string b.

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

Note:
In the first sample it is enough simply to swap the first and the second digit.

In the second sample we should replace the second digit with its opposite.

In the third number we should replace all three digits with their opposites.

Example input:
47
74

Example output:
1

Example input:
774
744

Example output:
1

Editorial:
Lucky Number 2
Contest: Codeforces Round 104 (Div. 1)
Difficulty rating: 1800
Tags: constructive algorithms

Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya loves long lucky numbers very much. He is interested in the minimum lucky number d that meets some condition. Let cnt(x) be the number of occurrences of number x in number d as a substring. For example, if d = 747747, then cnt(4) = 2, cnt(7) = 4, cnt(47) = 2, cnt(74) = 2. Petya wants the following condition to fulfil simultaneously: cnt(4) = a1, cnt(7) = a2, cnt(47) = a3, cnt(74) = a4. Petya is not interested in the occurrences of other numbers. Help him cope with this task.

Input format:
The single line contains four integers a1, a2, a3 and a4 (1 ≤ a1, a2, a3, a4 ≤ 106).

Output format:
On the single line print without leading zeroes the answer to the problem — the minimum lucky number d such, that cnt(4) = a1, cnt(7) = a2, cnt(47) = a3, cnt(74) = a4. If such number does not exist, print the single number "-1" (without the quotes).

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

Example input:
2 2 1 1

Example output:
4774

Example input:
4 7 3 1

Example output:
-1

Editorial:
Lucky Subsequence
Contest: Codeforces Round 104 (Div. 1)
Difficulty rating: 2100
Tags: combinatorics, dp, math

Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya has sequence a consisting of n integers.

The subsequence of the sequence a is such subsequence that can be obtained from a by removing zero or more of its elements.

Two sequences are considered different if index sets of numbers included in them are different. That is, the values ​of the elements ​do not matter in the comparison of subsequences. In particular, any sequence of length n has exactly 2n different subsequences (including an empty subsequence).

A subsequence is considered lucky if it has a length exactly k and does not contain two identical lucky numbers (unlucky numbers can be repeated any number of times).

Help Petya find the number of different lucky subsequences of the sequence a. As Petya's parents don't let him play with large numbers, you should print the result modulo prime number 1000000007 (109 + 7).

Input format:
The first line contains two integers n and k (1 ≤ k ≤ n ≤ 105). The next line contains n integers ai (1 ≤ ai ≤ 109) — the sequence a.

Output format:
On the single line print the single number — the answer to the problem modulo prime number 1000000007 (109 + 7).

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

Note:
In the first sample all 3 subsequences of the needed length are considered lucky.

In the second sample there are 4 lucky subsequences. For them the sets of indexes equal (the indexation starts from 1): {1, 3}, {1, 4}, {2, 3} and {2, 4}.

Example input:
3 2
10 10 10

Example output:
3

Example input:
4 2
4 4 7 7

Example output:
4

Editorial:
Lucky Pair
Contest: Codeforces Round 104 (Div. 1)
Difficulty rating: 2900
Tags: combinatorics, data structures, implementation

Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya has an array a of n integers. The numbers in the array are numbered starting from 1. Unfortunately, Petya has been misbehaving and so, his parents don't allow him play with arrays that have many lucky numbers. It is guaranteed that no more than 1000 elements in the array a are lucky numbers.

Petya needs to find the number of pairs of non-intersecting segments [l1;r1] and [l2;r2] (1 ≤ l1 ≤ r1 < l2 ≤ r2 ≤ n, all four numbers are integers) such that there's no such lucky number that occurs simultaneously in the subarray a[l1..r1] and in the subarray a[l2..r2]. Help Petya count the number of such pairs.

Input format:
The first line contains an integer n (2 ≤ n ≤ 105) — the size of the array a. The second line contains n space-separated integers ai (1 ≤ ai ≤ 109) — array a. It is guaranteed that no more than 1000 elements in the array a are lucky numbers.

Output format:
On the single line print the only number — the answer to the problem.

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

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

Note:
The subarray a[l..r] is an array that consists of elements al, al + 1, ..., ar.

In the first sample there are 9 possible pairs that satisfy the condition: [1, 1] and [2, 2], [1, 1] and [2, 3], [1, 1] and [2, 4], [1, 1] and [3, 3], [1, 1] and [3, 4], [1, 1] and [4, 4], [1, 2] and [3, 3], [2, 2] and [3, 3], [3, 3] and [4, 4].

In the second sample there is only one pair of segments — [1;1] and [2;2] and it satisfies the condition.

Example input:
4
1 4 2 4

Example output:
9

Example input:
2
4 7

Example output:
1

Editorial:
Lucky Queries
Contest: Codeforces Round 104 (Div. 1)
Difficulty rating: 2400
Tags: data structures

Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya brought home string s with the length of n. The string only consists of lucky digits. The digits are numbered from the left to the right starting with 1. Now Petya should execute m queries of the following form:

- switch l r — "switch" digits (i.e. replace them with their opposites) at all positions with indexes from l to r, inclusive: each digit 4 is replaced with 7 and each digit 7 is replaced with 4 (1 ≤ l ≤ r ≤ n);
- count — find and print on the screen the length of the longest non-decreasing subsequence of string s.

Subsequence of a string s is a string that can be obtained from s by removing zero or more of its elements. A string is called non-decreasing if each successive digit is not less than the previous one.

Help Petya process the requests.

Input format:
The first line contains two integers n and m (1 ≤ n ≤ 106, 1 ≤ m ≤ 3·105) — the length of the string s and the number of queries correspondingly. The second line contains n lucky digits without spaces — Petya's initial string. Next m lines contain queries in the form described in the statement.

Output format:
For each query count print an answer on a single line.

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

Note:
In the first sample the chronology of string s after some operations are fulfilled is as follows (the sought maximum subsequence is marked with bold):

1. 47
2. 74
3. 74

1. 747
2. 447
3. 447
4. 774
5. 774

Example input:
2 3
47
count
switch 1 2
count

Example output:
2
1

Example input:
3 5
747
count
switch 1 1
count
switch 1 3
count

Example output:
2
3
2

Editorial:
Make it Increasing
Contest: Codeforces Round 783 (Div. 1)
Difficulty rating: 1300
Tags: brute force, greedy, math

You are given an array $$$a$$$ consisting of $$$n$$$ positive integers, and an array $$$b$$$, with length $$$n$$$. Initially $$$b_i=0$$$ for each $$$1 \leq i \leq n$$$.

In one move you can choose an integer $$$i$$$ ($$$1 \leq i \leq n$$$), and add $$$a_i$$$ to $$$b_i$$$ or subtract $$$a_i$$$ from $$$b_i$$$. What is the minimum number of moves needed to make $$$b$$$ increasing (that is, every element is strictly greater than every element before it)?

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 5000$$$).

The second line contains $$$n$$$ integers, $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the elements of the array $$$a$$$.

Output format:
Print a single integer, the minimum number of moves to make $$$b$$$ increasing.

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

Note:
Example $$$1$$$: you can subtract $$$a_1$$$ from $$$b_1$$$, and add $$$a_3$$$, $$$a_4$$$, and $$$a_5$$$ to $$$b_3$$$, $$$b_4$$$, and $$$b_5$$$ respectively. The final array will be [$$$-1$$$, $$$0$$$, $$$3$$$, $$$4$$$, $$$5$$$] after $$$4$$$ moves.

Example $$$2$$$: you can reach [$$$-3$$$, $$$-2$$$, $$$-1$$$, $$$0$$$, $$$1$$$, $$$2$$$, $$$3$$$] in $$$10$$$ moves.

Example input:
5
1 2 3 4 5

Example output:
4

Example input:
7
1 2 1 2 1 2 1

Example output:
10

Editorial:
If the final array, is $$$b_1$$$, $$$b_2$$$ ... $$$b_n$$$, than the solution is surely unoptimal if there is an $$$2≤i≤n$$$, when $$$b_i>0$$$, and $$$b_i-a_i>b_{i-1}$$$, or $$$b_1>0$$$. Because there was one unnecessary move on $$$b_i$$$ or on $$$b_1$$$.
Similarly it is unoptimal, if $$$b_i<0$$$ and $$$b_i+a_i$$$ or $$$b_n<0$$$.
We can see, that there will be a $$$0$$$ in the final array. If we fix the position of the $$$0$$$ element, than we can set the other values greadily: find the smallest value for each element, which is bigger than the previous one, and similarly before the $$$0$$$.
We can fix each element, and calculate the answer for that in $$$O(n)$$$ time. The minimum of these values will be the final answer. So the final complexity is $$$O(n^2)$$$.
Half Queen Cover
Contest: Codeforces Round 783 (Div. 1)
Difficulty rating: 2400
Tags: constructive algorithms, math

You are given a board with $$$n$$$ rows and $$$n$$$ columns, numbered from $$$1$$$ to $$$n$$$. The intersection of the $$$a$$$-th row and $$$b$$$-th column is denoted by $$$(a, b)$$$.

A half-queen attacks cells in the same row, same column, and on one diagonal. More formally, a half-queen on $$$(a, b)$$$ attacks the cell $$$(c, d)$$$ if $$$a=c$$$ or $$$b=d$$$ or $$$a-b=c-d$$$.

The blue cells are under attack.

Construct an optimal solution.

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

Output format:
In the first line print a single integer $$$k$$$ — the minimum number of half-queens.

In each of the next $$$k$$$ lines print two integers $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — the position of the $$$i$$$-th half-queen.

If there are multiple solutions, print any.

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

Note:
Example $$$1$$$: one half-queen is enough. Note: a half-queen on $$$(1, 1)$$$ attacks $$$(1, 1)$$$.

Example $$$2$$$: one half-queen is enough too. $$$(1, 2)$$$ or $$$(2, 1)$$$ would be wrong solutions, because a half-queen on $$$(1, 2)$$$ does not attack the cell $$$(2, 1)$$$ and vice versa. $$$(2, 2)$$$ is also a valid solution.

Example $$$3$$$: it is impossible to cover the board with one half queen. There are multiple solutions for $$$2$$$ half-queens; you can print any of them.

Example input:
1

Example output:
1
1 1

Example input:
2

Example output:
1
1 1

Editorial:
Let's assume that there is a solution for $$$k$$$ half-queens. There are at least $$$n-k$$$ rows, and columns, which contains no half-queen.
If the uncovered rows are $$$r_1, r_2, ... r_a$$$, and the columns are $$$c_1, c_2, ... c_b$$$, (in increasing order), each diagonal (when the difference is a constant) contains at most one of the following $$$a+b-1$$$ squares: $$$(r_a, c_1), (r_a-1, c_1), ... (r_1, c_1), (r_1, c_2), ... (r_1, c_b)$$$. So a different half-queen attacks these cells.
We know that: $$$a+b-1≤k, n-k≤a, n-k≤b$$$, so $$$2 \cdot n≤3 \cdot k+1$$$. We have a lower bound for $$$k$$$. It turns out, that there is a consturction, for this $$$k$$$.
For $$$n=3 \cdot x+2$$$, $$$k=2 \cdot x+1$$$, and we can place $$$x+1$$$ in the top left corner, diagonally, and $$$x$$$ half queens in the bottom right corner diagonally.
Example for $$$n=8$$$ (top left corner is $$$(1, 1)$$$)
If $$$n=3 \cdot x$$$, or $$$n=3 \cdot x+1$$$ we can put one or two half-queens, in the bottom right corner, and use the previous consruction.