1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Increasing by Modulo
Contest: Codeforces Round 562 (Div. 1)
Difficulty rating: 1700
Tags: binary search, greedy

Toad Zitz has an array of integers, each integer is between $$$0$$$ and $$$m-1$$$ inclusive. The integers are $$$a_1, a_2, \ldots, a_n$$$.

In one operation Zitz can choose an integer $$$k$$$ and $$$k$$$ indices $$$i_1, i_2, \ldots, i_k$$$ such that $$$1 \leq i_1 < i_2 < \ldots < i_k \leq n$$$. He should then change $$$a_{i_j}$$$ to $$$((a_{i_j}+1) \bmod m)$$$ for each chosen integer $$$i_j$$$. The integer $$$m$$$ is fixed for all operations and indices.

Here $$$x \bmod y$$$ denotes the remainder of the division of $$$x$$$ by $$$y$$$.

Zitz wants to make his array non-decreasing with the minimum number of such operations. Find this minimum number of operations.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 300\,000$$$) — the number of integers in the array and the parameter $$$m$$$.

The next line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < m$$$) — the given array.

Output format:
Output one integer: the minimum number of described operations Zitz needs to make his array non-decreasing. If no operations required, print $$$0$$$.

It is easy to see that with enough operations Zitz can always make his array non-decreasing.

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

Note:
In the first example, the array is already non-decreasing, so the answer is $$$0$$$.

In the second example, you can choose $$$k=2$$$, $$$i_1 = 2$$$, $$$i_2 = 5$$$, the array becomes $$$[0,0,1,3,3]$$$. It is non-decreasing, so the answer is $$$1$$$.

Example input:
5 3
0 0 0 1 2

Example output:
0

Example input:
5 7
0 6 1 3 2

Example output:
1

Editorial:
Let's check that the answer to the problem is $$$\leq x$$$.
Then, for each element, you have some interval (interval on the "circle" of remainders modulo $$$m$$$) of values, that it can be equal to.
So you need to check that you can pick in each interval some point, to make all these values non-decrease.
You can do it with greedy! Each time, let's take the smallest element from the interval, that is at least the previously chosen value.
And after this, let's make the binary search on $$$x$$$.
So we have the solution in $$$O(n \log m)$$$.
This solution
Good Triple
Contest: Codeforces Round 562 (Div. 1)
Difficulty rating: 1900
Tags: brute force, two pointers

Toad Rash has a binary string $$$s$$$. A binary string consists only of zeros and ones.

Let $$$n$$$ be the length of $$$s$$$.

Rash needs to find the number of such pairs of integers $$$l$$$, $$$r$$$ that $$$1 \leq l \leq r \leq n$$$ and there is at least one pair of integers $$$x$$$, $$$k$$$ such that $$$1 \leq x, k \leq n$$$, $$$l \leq x < x + 2k \leq r$$$, and $$$s_x = s_{x+k} = s_{x+2k}$$$.

Find this number of pairs for Rash.

Input format:
The first line contains the string $$$s$$$ ($$$1 \leq |s| \leq 300\,000$$$), consisting of zeros and ones.

Output format:
Output one integer: the number of such pairs of integers $$$l$$$, $$$r$$$ that $$$1 \leq l \leq r \leq n$$$ and there is at least one pair of integers $$$x$$$, $$$k$$$ such that $$$1 \leq x, k \leq n$$$, $$$l \leq x < x + 2k \leq r$$$, and $$$s_x = s_{x+k} = s_{x+2k}$$$.

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

Note:
In the first example, there are three $$$l$$$, $$$r$$$ pairs we need to count: $$$1$$$, $$$6$$$; $$$2$$$, $$$6$$$; and $$$1$$$, $$$5$$$.

In the second example, there are no values $$$x$$$, $$$k$$$ for the initial string, so the answer is $$$0$$$.

Example input:
010101

Example output:
3

Example input:
11001100

Example output:
0

Editorial:
Lemma: there are no strings without such $$$x,k$$$ of length at least 9.
In fact, you just can write brute force to find all "good" strings and then realize that they all are small.
Ok, so with this you can just write some sort of "naive" solution, for each $$$l$$$ find the largest $$$r$$$, such that $$$l \ldots r$$$ is a "good" string, and then add $$$n - r$$$ to the answer. You can do it in $$$9 \cdot 9 \cdot n$$$ or in $$$9 \cdot n$$$, as I do in my solution. Check it out!
And Reachability
Contest: Codeforces Round 562 (Div. 1)
Difficulty rating: 2200
Tags: bitmasks, dp

Toad Pimple has an array of integers $$$a_1, a_2, \ldots, a_n$$$.

We say that $$$y$$$ is reachable from $$$x$$$ if $$$x<y$$$ and there exists an integer array $$$p$$$ such that $$$x = p_1 < p_2 < \ldots < p_k=y$$$, and $$$a_{p_i}\, \&\, a_{p_{i+1}} > 0$$$ for all integers $$$i$$$ such that $$$1 \leq i < k$$$.

Here $$$\&$$$ denotes the bitwise AND operation.

You are given $$$q$$$ pairs of indices, check reachability for each of them.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n \leq 300\,000$$$, $$$1 \leq q \leq 300\,000$$$) — the number of integers in the array and the number of queries you need to answer.

The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 300\,000$$$) — the given array.

The next $$$q$$$ lines contain two integers each. The $$$i$$$-th of them contains two space-separated integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i < y_i \leq n$$$). You need to check if $$$y_i$$$ is reachable from $$$x_i$$$.

Output format:
Output $$$q$$$ lines. In the $$$i$$$-th of them print "Shi" if $$$y_i$$$ is reachable from $$$x_i$$$, otherwise, print "Fou".

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

Note:
In the first example, $$$a_3 = 0$$$. You can't reach it, because AND with it is always zero. $$$a_2\, \&\, a_4 > 0$$$, so $$$4$$$ is reachable from $$$2$$$, and to go from $$$1$$$ to $$$4$$$ you can use $$$p = [1, 2, 4]$$$.

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

Example output:
Fou
Shi
Shi

Editorial:
Let's calculate $$$go_{i, k}$$$ — the smallest $$$j$$$, such that $$$a_j$$$ contains bit $$$k$$$, which is reachable from $$$i$$$.
How to recalculate it? Let $$$last_{i,k}$$$ is the smallest $$$j > i$$$, such that $$$a_j$$$ contains bit $$$k$$$.
Then, I claim that $$$go_{i,k}$$$ is equal to the $$$i$$$ or to the $$$\min{(go_{last_{i,j},k})}$$$ for all bits $$$j$$$ that $$$a_i$$$ contains.
Why? Because if you go from $$$i$$$ to some number, which has bit $$$j$$$ in the intersection, it is useless to go to the number which is not equal to $$$last_{i,j}$$$, because from $$$last_{i,j}$$$ you can go to all numbers that have bit $$$j$$$ and that positioned farther.
So in $$$O(n \log )$$$ you can calculate all these values, and then to answer the query you can check that there exists some bit $$$j$$$ in $$$a_y$$$ such that $$$go_{x, j} \leq y$$$.
This solution
Increasing Sequence
Contest: Codeforces Beta Round 11
Difficulty rating: 900
Tags: constructive algorithms, implementation, math

A sequence a0, a1, ..., at - 1 is called increasing if ai - 1 < ai for each i: 0 < i < t.

You are given a sequence b0, b1, ..., bn - 1 and a positive integer d. In each move you may choose one element of the given sequence and add d to it. What is the least number of moves required to make the given sequence increasing?

Input format:
The first line of the input contains two integer numbers n and d (2 ≤ n ≤ 2000, 1 ≤ d ≤ 106). The second line contains space separated sequence b0, b1, ..., bn - 1 (1 ≤ bi ≤ 106).

Output format:
Output the minimal number of moves needed to make the sequence increasing.

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

Example input:
4 2
1 3 3 2

Example output:
3

Editorial:
Jumping Jack
Contest: Codeforces Beta Round 11
Difficulty rating: 1600
Tags: math

Jack is working on his jumping skills recently. Currently he's located at point zero of the number line. He would like to get to the point x. In order to train, he has decided that he'll first jump by only one unit, and each subsequent jump will be exactly one longer than the previous one. He can go either left or right with each jump. He wonders how many jumps he needs to reach x.

Input format:
The input data consists of only one integer x ( - 109 ≤ x ≤ 109).

Output format:
Output the minimal number of jumps that Jack requires to reach x.

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

Example input:
2

Example output:
3

Example input:
6

Example output:
3

Editorial:
How Many Squares?
Contest: Codeforces Beta Round 11
Difficulty rating: 2200
Tags: implementation

You are given a 0-1 rectangular matrix. What is the number of squares in it? A square is a solid square frame (border) with linewidth equal to 1. A square should be at least 2 × 2. We are only interested in two types of squares:

1. squares with each side parallel to a side of the matrix;
2. squares with each side parallel to a diagonal of the matrix.

Regardless of type, a square must contain at least one 1 and can't touch (by side or corner) any foreign 1. Of course, the lengths of the sides of each square should be equal.

How many squares are in the given matrix?

Input format:
The first line contains integer t (1 ≤ t ≤ 10000), where t is the number of test cases in the input. Then test cases follow. Each case starts with a line containing integers n and m (2 ≤ n, m ≤ 250), where n is the number of rows and m is the number of columns. The following n lines contain m characters each (0 or 1).

The total number of characters in all test cases doesn't exceed 106 for any input file.

Output format:
You should output exactly t lines, with the answer to the i-th test case on the i-th line.

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

Example input:
2
8 8
00010001
00101000
01000100
10000010
01000100
00101000
11010011
11000011
10 10
1111111000
1000001000
1011001000
1011001010
1000001101
1001001010
1010101000
1001001000
1000001000
1111111000

Example output:
1
2

Example input:
1
12 11
11111111111
10000000001
10111111101
10100000101
10101100101
10101100101
10100000101
10100000101
10111111101
10000000001
11111111111
00000000000

Example output:
3

Editorial:
A Simple Task
Contest: Codeforces Beta Round 11
Difficulty rating: 2200
Tags: bitmasks, dp, graphs

Given a simple graph, output the number of simple cycles in it. A simple cycle is a cycle with no repeated vertices or edges.

Input format:
The first line of input contains two integers n and m (1 ≤ n ≤ 19, 0 ≤ m) – respectively the number of vertices and edges of the graph. Each of the subsequent m lines contains two integers a and b, (1 ≤ a, b ≤ n, a ≠ b) indicating that vertices a and b are connected by an undirected edge. There is no more than one edge connecting any pair of vertices.

Output format:
Output the number of cycles in the given graph.

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

Note:
The example graph is a clique and contains four cycles of length 3 and three cycles of length 4.

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

Example output:
7

Editorial:
Forward, march!
Contest: Codeforces Beta Round 11
Difficulty rating: 2800
Tags: binary search, dp, greedy

Jack has become a soldier now. Unfortunately, he has trouble with the drill. Instead of marching beginning with the left foot and then changing legs with each step, as ordered, he keeps repeating a sequence of steps, in which he sometimes makes the wrong steps or — horror of horrors! — stops for a while. For example, if Jack uses the sequence 'right, left, break', when the sergeant yells: 'Left! Right! Left! Right! Left! Right!', Jack first makes a step with the right foot, then one with the left foot, then he is confused and stops for a moment, then again - this time according to the order - starts with the right foot, then uses the left foot, then - to the sergeant's irritation - he stops to catch his breath, to incorrectly start with the right foot again... Marching this way, Jack will make the step that he is supposed to in the given moment in only one third of cases.

When the officers convinced him he should do something about it, Jack decided to modify the basic sequence of steps that he repeats. However, in order not to get too tired, he has decided that the only thing he'll do is adding any number of breaks in any positions of the original sequence (a break corresponds to stopping for the duration of one step). Of course, Jack can't make a step on the same foot twice in a row, if there is no pause between these steps. It is, however, not impossible that the sequence of steps he used so far is incorrect (it would explain a lot, actually).

Help Private Jack! Given the sequence of steps he keeps repeating, calculate the maximal percentage of time that he can spend marching correctly after adding some breaks to his scheme.

Input format:
The first line of input contains a sequence consisting only of characters 'L', 'R' and 'X', where 'L' corresponds to a step with the left foot, 'R' — with the right foot, and 'X' — to a break. The length of the sequence will not exceed 106.

Output format:
Output the maximum percentage of time that Jack can spend marching correctly, rounded down to exactly six digits after the decimal point.

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

Note:
In the second example, if we add two breaks to receive LXXRXR, Jack will march: LXXRXRLXXRXRL... instead of LRLRLRLRLRLRL... and will make the correct step in half the cases. If we didn't add any breaks, the sequence would be incorrect — Jack can't step on his right foot twice in a row.

Example input:
X

Example output:
0.000000

Example input:
LXRR

Example output:
50.000000

Editorial:
Diverse Permutation
Contest: Codeforces Round 275 (Div. 1)
Difficulty rating: 1200
Tags: constructive algorithms, greedy

Permutation p is an ordered set of integers p1,   p2,   ...,   pn, consisting of n distinct positive integers not larger than n. We'll denote as n the length of permutation p1,   p2,   ...,   pn.

Your task is to find such permutation p of length n, that the group of numbers |p1 - p2|, |p2 - p3|, ..., |pn - 1 - pn| has exactly k distinct elements.

Input format:
The single line of the input contains two space-separated positive integers n, k (1 ≤ k < n ≤ 105).

Output format:
Print n integers forming the permutation. If there are multiple answers, print any of them.

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

Note:
By |x| we denote the absolute value of number x.

Example input:
3 2

Example output:
1 3 2

Example input:
3 1

Example output:
1 2 3

Editorial:
Interesting Array
Contest: Codeforces Round 275 (Div. 1)
Difficulty rating: 1800
Tags: constructive algorithms, data structures, trees

We'll call an array of n non-negative integers a[1], a[2], ..., a[n] interesting, if it meets m constraints. The i-th of the m constraints consists of three integers li, ri, qi (1 ≤ li ≤ ri ≤ n) meaning that value $$a[l_{i}] \& a[l_{i}+1] \& \ldots \& a[r_{i}]$$ should be equal to qi.

Your task is to find any interesting array of n elements or state that such array doesn't exist.

Expression x&y means the bitwise AND of numbers x and y. In programming languages C++, Java and Python this operation is represented as "&", in Pascal — as "and".

Input format:
The first line contains two integers n, m (1 ≤ n ≤ 105, 1 ≤ m ≤ 105) — the number of elements in the array and the number of limits.

Each of the next m lines contains three integers li, ri, qi (1 ≤ li ≤ ri ≤ n, 0 ≤ qi < 230) describing the i-th limit.

Output format:
If the interesting array exists, in the first line print "YES" (without the quotes) and in the second line print n integers a[1], a[2], ..., a[n] (0 ≤ a[i] < 230) decribing the interesting array. If there are multiple answers, print any of them.

If the interesting array doesn't exist, print "NO" (without the quotes) in the single line.

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

Example input:
3 1
1 3 3

Example output:
YES
3 3 3

Example input:
3 2
1 3 3
1 3 2

Example output:
NO

Editorial:
Game with Strings
Contest: Codeforces Round 275 (Div. 1)
Difficulty rating: 2600
Tags: bitmasks, dp, probabilities

You play the game with your friend. The description of this game is listed below.

Your friend creates n distinct strings of the same length m and tells you all the strings. Then he randomly chooses one of them. He chooses strings equiprobably, i.e. the probability of choosing each of the n strings equals $${\frac {1}{n}}$$. You want to guess which string was chosen by your friend.

In order to guess what string your friend has chosen, you are allowed to ask him questions. Each question has the following form: «What character stands on position pos in the string you have chosen?» A string is considered guessed when the answers to the given questions uniquely identify the string. After the string is guessed, you stop asking questions.

You do not have a particular strategy, so as each question you equiprobably ask about a position that hasn't been yet mentioned. Your task is to determine the expected number of questions needed to guess the string chosen by your friend.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 50) — the number of strings your friend came up with.

The next n lines contain the strings that your friend has created. It is guaranteed that all the strings are distinct and only consist of large and small English letters. Besides, the lengths of all strings are the same and are between 1 to 20 inclusive.

Output format:
Print the single number — the expected value. Your answer will be considered correct if its absolute or relative error doesn't exceed 10 - 9.

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

Note:
In the first sample the strings only differ in the character in the third position. So only the following situations are possible:

- you guess the string in one question. The event's probability is $${\frac {1}{3}}$$;
- you guess the string in two questions. The event's probability is $$\frac{2}{3}$$ · $$\frac{1}{2}$$ = $${\frac {1}{3}}$$ (as in this case the first question should ask about the position that is other than the third one);
- you guess the string in three questions. The event's probability is $$\frac{2}{3}$$ · $$\frac{1}{2}$$ · $$\frac{1}{1}$$ = $${\frac {1}{3}}$$;

Thus, the expected value is equal to $$\frac{1+2+3}{3}=2$$

In the second sample we need at most two questions as any pair of questions uniquely identifies the string. So the expected number of questions is $$\frac{1}{3}+2\cdot\frac{2}{3}=\frac{5}{3}$$.

In the third sample whatever position we ask about in the first question, we immediately identify the string.

Example input:
2
aab
aac

Example output:
2.000000000000000

Example input:
3
aaA
aBa
Caa

Example output:
1.666666666666667

Editorial:
Random Function and Tree
Contest: Codeforces Round 275 (Div. 1)
Difficulty rating: 2700
Tags: combinatorics, dp, trees

You have a rooted tree consisting of n vertices. Let's number them with integers from 1 to n inclusive. The root of the tree is the vertex 1. For each i > 1 direct parent of the vertex i is pi. We say that vertex i is child for its direct parent pi.

You have initially painted all the vertices with red color. You like to repaint some vertices of the tree. To perform painting you use the function paint that you call with the root of the tree as an argument. Here is the pseudocode of this function:

As a result of this function, some vertices may change their colors to white or black and some of them may remain red.

Your task is to determine the number of distinct possible colorings of the vertices of the tree. We will assume that the coloring is possible if there is a nonzero probability to get this coloring with a single call of paint(1). We assume that the colorings are different if there is a pair of vertices that are painted with different colors in these colorings. Since the required number may be very large, find its remainder of division by 1000000007 (109 + 7).

Input format:
The first line contains a single integer n (2 ≤ n ≤ 105) — the number of vertexes in the tree.

The second line contains n - 1 integers p2, p3, ..., pn (1 ≤ pi < i). Number pi is the parent of vertex i.

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

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

Note:
All possible coloring patterns of the first sample are given below.

Example input:
4
1 2 1

Example output:
8

Example input:
3
1 1

Example output:
5

Editorial:
ELCA
Contest: Codeforces Round 275 (Div. 1)
Difficulty rating: 3200
Tags: data structures, trees

You have a root tree containing n vertexes. Let's number the tree vertexes with integers from 1 to n. The tree root is in the vertex 1.

Each vertex (except fot the tree root) v has a direct ancestor pv. Also each vertex v has its integer value sv.

Your task is to perform following queries:

- P v u (u ≠ v). If u isn't in subtree of v, you must perform the assignment pv = u. Otherwise you must perform assignment pu = v. Note that after this query the graph continues to be a tree consisting of n vertexes.
- V v t. Perform assignment sv = t.

Your task is following. Before starting performing queries and after each query you have to calculate expected value written on the lowest common ancestor of two equiprobably selected vertices i and j. Here lowest common ancestor of i and j is the deepest vertex that lies on the both of the path from the root to vertex i and the path from the root to vertex j. Please note that the vertices i and j can be the same (in this case their lowest common ancestor coincides with them).

Input format:
The first line of the input contains integer n (2 ≤ n ≤ 5·104) — the number of the tree vertexes.

The second line contains n - 1 integer p2, p3, ..., pn (1 ≤ pi ≤ n) — the description of the tree edges. It is guaranteed that those numbers form a tree.

The third line contains n integers — s1, s2, ... sn (0 ≤ si ≤ 106) — the values written on each vertex of the tree.

The next line contains integer q (1 ≤ q ≤ 5·104) — the number of queries. Each of the following q lines contains the description of the query in the format described in the statement. It is guaranteed that query arguments u and v lie between 1 and n. It is guaranteed that argument t in the queries of type V meets limits 0 ≤ t ≤ 106.

Output format:
Print q + 1 number — the corresponding expected values. Your answer will be considered correct if its absolute or relative error doesn't exceed 10 - 9.

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

Note:
Note that in the query P v u if u lies in subtree of v you must perform assignment pu = v. An example of such case is the last query in the sample.

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

Example output:
1.640000000
1.800000000
2.280000000
2.320000000
2.800000000
1.840000000

Editorial: