1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Numbers
Contest: Codeforces Beta Round 72 (Div. 1 Only)
Difficulty rating: 2400
Tags: dp, math, number theory

One quite ordinary day Valera went to school (there's nowhere else he should go on a week day). In a maths lesson his favorite teacher Ms. Evans told students about divisors. Despite the fact that Valera loved math, he didn't find this particular topic interesting. Even more, it seemed so boring that he fell asleep in the middle of a lesson. And only a loud ringing of a school bell could interrupt his sweet dream.

Of course, the valuable material and the teacher's explanations were lost. However, Valera will one way or another have to do the homework. As he does not know the new material absolutely, he cannot do the job himself. That's why he asked you to help. You're his best friend after all, you just cannot refuse to help.

Valera's home task has only one problem, which, though formulated in a very simple way, has not a trivial solution. Its statement looks as follows: if we consider all positive integers in the interval [a;b] then it is required to count the amount of such numbers in this interval that their smallest divisor will be a certain integer k (you do not have to consider divisor equal to one). In other words, you should count the amount of such numbers from the interval [a;b], that are not divisible by any number between 2 and k - 1 and yet are divisible by k.

Input format:
The first and only line contains three positive integers a, b, k (1 ≤ a ≤ b ≤ 2·109, 2 ≤ k ≤ 2·109).

Output format:
Print on a single line the answer to the given problem.

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

Note:
Comments to the samples from the statement:

In the first sample the answer is numbers 2, 4, 6, 8, 10.

In the second one — 15, 21

In the third one there are no such numbers.

Example input:
1 10 2

Example output:
5

Example input:
12 23 3

Example output:
2

Editorial:
Two Subsequences
Contest: Codeforces Beta Round 72 (Div. 1 Only)
Difficulty rating: 2800
Tags: bitmasks, dp

On an IT lesson Valera studied data compression. The teacher told about a new method, which we shall now describe to you.

Let {a1, a2, ..., an} be the given sequence of lines needed to be compressed. Here and below we shall assume that all lines are of the same length and consist only of the digits 0 and 1. Let's define the compression function:

- f(empty sequence) = empty string
- f(s) = s.
- f(s1, s2) =  the smallest in length string, which has one of the prefixes equal to s1 and one of the suffixes equal to s2. For example, f(001, 011) = 0011, f(111, 011) = 111011.
- f(a1, a2, ..., an) = f(f(a1, a2, an - 1), an). For example, f(000, 000, 111) = f(f(000, 000), 111) = f(000, 111) = 000111.

Valera faces a real challenge: he should divide the given sequence {a1, a2, ..., an} into two subsequences {b1, b2, ..., bk} and {c1, c2, ..., cm}, m + k = n, so that the value of S = |f(b1, b2, ..., bk)| + |f(c1, c2, ..., cm)| took the minimum possible value. Here |p| denotes the length of the string p.

Note that it is not allowed to change the relative order of lines in the subsequences. It is allowed to make one of the subsequences empty. Each string from the initial sequence should belong to exactly one subsequence. Elements of subsequences b and c don't have to be consecutive in the original sequence a, i. e. elements of b and c can alternate in a (see samples 2 and 3).

Help Valera to find the minimum possible value of S.

Input format:
The first line of input data contains an integer n — the number of strings (1 ≤ n ≤ 2·105). Then on n lines follow elements of the sequence — strings whose lengths are from 1 to 20 characters, consisting only of digits 0 and 1. The i + 1-th input line contains the i-th element of the sequence. Elements of the sequence are separated only by a newline. It is guaranteed that all lines have the same length.

Output format:
Print a single number — the minimum possible value of S.

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

Note:
Detailed answers to the tests:

- The best option is to make one of the subsequences empty, and the second one equal to the whole given sequence. |f(01, 10, 01)| = |f(f(01, 10), 01)| = |f(010, 01)| = |0101| = 4.
- The best option is: b = {000, 001}, c = {111, 110}. S = |f(000, 001)| + |f(111, 110)| = |0001| + |1110| = 8.
- The best option is: b = {10101, 01010, 01000}, c = {11111, 10010}. S = |10101000| + |111110010| = 17.

Example input:
3
01
10
01

Example output:
4

Example input:
4
000
111
110
001

Example output:
8

Editorial:
K-Complete Word
Contest: Codeforces Round 630 (Div. 2)
Difficulty rating: 1500
Tags: dfs and similar, dsu, greedy, implementation, strings

Word $$$s$$$ of length $$$n$$$ is called $$$k$$$-complete if

- $$$s$$$ is a palindrome, i.e. $$$s_i=s_{n+1-i}$$$ for all $$$1 \le i \le n$$$;
- $$$s$$$ has a period of $$$k$$$, i.e. $$$s_i=s_{k+i}$$$ for all $$$1 \le i \le n-k$$$.

For example, "abaaba" is a $$$3$$$-complete word, while "abccba" is not.

Bob is given a word $$$s$$$ of length $$$n$$$ consisting of only lowercase Latin letters and an integer $$$k$$$, such that $$$n$$$ is divisible by $$$k$$$. He wants to convert $$$s$$$ to any $$$k$$$-complete word.

To do this Bob can choose some $$$i$$$ ($$$1 \le i \le n$$$) and replace the letter at position $$$i$$$ with some other lowercase Latin letter.

So now Bob wants to know the minimum number of letters he has to replace to convert $$$s$$$ to any $$$k$$$-complete word.

Note that Bob can do zero changes if the word $$$s$$$ is already $$$k$$$-complete.

You are required to answer $$$t$$$ test cases independently.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k < n \le 2 \cdot 10^5$$$, $$$n$$$ is divisible by $$$k$$$).

The second line of each test case contains a word $$$s$$$ of length $$$n$$$.

It is guaranteed that word $$$s$$$ only contains lowercase Latin letters. And it is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output one integer, representing the minimum number of characters he has to replace to convert $$$s$$$ to any $$$k$$$-complete word.

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

Note:
In the first test case, one optimal solution is aaaaaa.

In the second test case, the given word itself is $$$k$$$-complete.

Example input:
4
6 2
abaaba
6 3
abaaba
36 9
hippopotomonstrosesquippedaliophobia
21 7
wudixiaoxingxingheclp

Example output:
2
0
23
16

Editorial:
One should notice that word $$$s$$$ of length $$$n$$$ is $$$k$$$-complete if and only if there exists a palindrome $$$t$$$ of length $$$k$$$ such that $$$s$$$ can be generated by several concatenations of $$$t$$$.
So in the final string all characters at positions $$$i$$$, $$$k - i + 1$$$, $$$k + i$$$, $$$2k - i + 1$$$, $$$2k + i$$$, $$$3k - i + 1$$$, $$$\dots$$$ for all $$$1 \le i \le k$$$ should all be equal. This helps us to solve the problem independently for each $$$i$$$. To minimize the required number of changes, you should make all the letters equal to the one which appears at these positions the most initially. Calculate that maximum number of appearances and sum up over all $$$i$$$. Be careful with an odd $$$k$$$ because the letter in the center of each block has a different formula.
Walk on Matrix
Contest: Codeforces Round 630 (Div. 2)
Difficulty rating: 1700
Tags: bitmasks, constructive algorithms, math

Bob is playing a game named "Walk on Matrix".

In this game, player is given an $$$n \times m$$$ matrix $$$A=(a_{i,j})$$$, i.e. the element in the $$$i$$$-th row in the $$$j$$$-th column is $$$a_{i,j}$$$. Initially, player is located at position $$$(1,1)$$$ with score $$$a_{1,1}$$$.

To reach the goal, position $$$(n,m)$$$, player can move right or down, i.e. move from $$$(x,y)$$$ to $$$(x,y+1)$$$ or $$$(x+1,y)$$$, as long as player is still on the matrix.

However, each move changes player's score to the bitwise AND of the current score and the value at the position he moves to.

Bob can't wait to find out the maximum score he can get using the tool he recently learnt  — dynamic programming. Here is his algorithm for this problem.

However, he suddenly realize that the algorithm above fails to output the maximum score for some matrix $$$A$$$. Thus, for any given non-negative integer $$$k$$$, he wants to find out an $$$n \times m$$$ matrix $$$A=(a_{i,j})$$$ such that

- $$$1 \le n,m \le 500$$$ (as Bob hates large matrix);
- $$$0 \le a_{i,j} \le 3 \cdot 10^5$$$ for all $$$1 \le i\le n,1 \le j\le m$$$ (as Bob hates large numbers);
- the difference between the maximum score he can get and the output of his algorithm is exactly $$$k$$$.

It can be shown that for any given integer $$$k$$$ such that $$$0 \le k \le 10^5$$$, there exists a matrix satisfying the above constraints.

Please help him with it!

Input format:
The only line of the input contains one single integer $$$k$$$ ($$$0 \le k \le 10^5$$$).

Output format:
Output two integers $$$n$$$, $$$m$$$ ($$$1 \le n,m \le 500$$$) in the first line, representing the size of the matrix.

Then output $$$n$$$ lines with $$$m$$$ integers in each line, $$$a_{i,j}$$$ in the $$$(i+1)$$$-th row, $$$j$$$-th column.

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

Note:
In the first example, the maximum score Bob can achieve is $$$300000$$$, while the output of his algorithm is $$$300000$$$.

In the second example, the maximum score Bob can achieve is $$$7\&3\&3\&3\&7\&3=3$$$, while the output of his algorithm is $$$2$$$.

Example input:
0

Example output:
1 1
300000

Example input:
1

Example output:
3 4
7 3 3 1
4 8 3 6
7 7 7 3

Editorial:
In fact, the following matrix will work: $$$$$$\left( \begin{array}{ccc} 2^{17}+k & 2^{17} & 0\\ k & 2^{17}+k & k\\ \end{array} \right)$$$$$$
To find such a matrix, one should find out why the dp solution fails.
One should notice that $$$dp_{2,2}=\max(a_{1,1}\&a_{1,2}\&a_{2,2},a_{1,1}\&a_{2,1}\&a_{2,2})$$$ and dp solution will choose the optimal path from $$$(1,1)$$$ to $$$(2,2)$$$ for later decision. However, we should notice that we can only discard the suboptimal result if and only if $$$ans_{suboptimal} \& ans_{optimal}=ans_{suboptimal}$$$ rather than $$$ans_{suboptimal} < ans_{optimal}$$$. Based on above analysis, we can construct the matrix easily.
In fact, even if $$$n,m$$$ is fixed satisfying that $$$n \ge 2,m \ge 2$$$ and $$$n\cdot m>4$$$, we could easily construct a matrix for a given $$$k$$$ based on our $$$2 \times 3$$$ matrix.
New Year and Counting Cards
Contest: Good Bye 2017
Difficulty rating: 800
Tags: brute force, implementation

Your friend has n cards.

You know that each card has a lowercase English letter on one side and a digit on the other.

Currently, your friend has laid out the cards on a table so only one side of each card is visible.

You would like to know if the following statement is true for cards that your friend owns: "If a card has a vowel on one side, then it has an even digit on the other side." More specifically, a vowel is one of 'a', 'e', 'i', 'o' or 'u', and even digit is one of '0', '2', '4', '6' or '8'.

For example, if a card has 'a' on one side, and '6' on the other side, then this statement is true for it. Also, the statement is true, for example, for a card with 'b' and '4', and for a card with 'b' and '3' (since the letter is not a vowel). The statement is false, for example, for card with 'e' and '5'. You are interested if the statement is true for all cards. In particular, if no card has a vowel, the statement is true.

To determine this, you can flip over some cards to reveal the other side. You would like to know what is the minimum number of cards you need to flip in the worst case in order to verify that the statement is true.

Input format:
The first and only line of input will contain a string s (1 ≤ |s| ≤ 50), denoting the sides of the cards that you can see on the table currently. Each character of s is either a lowercase English letter or a digit.

Output format:
Print a single integer, the minimum number of cards you must turn over to verify your claim.

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

Note:
In the first sample, we must turn over both cards. Note that even though both cards have the same letter, they could possibly have different numbers on the other side.

In the second sample, we don't need to turn over any cards. The statement is vacuously true, since you know your friend has no cards with a vowel on them.

In the third sample, we need to flip the second and fourth cards.

Example input:
ee

Example output:
2

Example input:
z

Example output:
0

Editorial:
Let's start off a bit more abstractly. We would like to know if the statement "if P then Q" is true, where P and Q are some statements (in this case, P is "card has vowel", and Q is "card has even number"). To do determine this, we need to flip over any cards which could be counter-examples (i.e. could make the statement false).
Let's look at the truth table for if P then Q (see here: http://www.math.hawaii.edu/ ramsey/Logic/IfThen.html). The statement is only false when Q is false and P is true. Thus, it suffices to flip cards when P is true or Q is false.
To solve this problem, we need to print the count of vowels and odd digits in the string.
New Year and Buggy Bot
Contest: Good Bye 2017
Difficulty rating: 1200
Tags: brute force, implementation

Bob programmed a robot to navigate through a 2d maze.

The maze has some obstacles. Empty cells are denoted by the character '.', where obstacles are denoted by '#'.

There is a single robot in the maze. Its start position is denoted with the character 'S'. This position has no obstacle in it. There is also a single exit in the maze. Its position is denoted with the character 'E'. This position has no obstacle in it.

The robot can only move up, left, right, or down.

When Bob programmed the robot, he wrote down a string of digits consisting of the digits 0 to 3, inclusive. He intended for each digit to correspond to a distinct direction, and the robot would follow the directions in order to reach the exit. Unfortunately, he forgot to actually assign the directions to digits.

The robot will choose some random mapping of digits to distinct directions. The robot will map distinct digits to distinct directions. The robot will then follow the instructions according to the given string in order and chosen mapping. If an instruction would lead the robot to go off the edge of the maze or hit an obstacle, the robot will crash and break down. If the robot reaches the exit at any point, then the robot will stop following any further instructions.

Bob is having trouble debugging his robot, so he would like to determine the number of mappings of digits to directions that would lead the robot to the exit.

Input format:
The first line of input will contain two integers n and m (2 ≤ n, m ≤ 50), denoting the dimensions of the maze.

The next n lines will contain exactly m characters each, denoting the maze.

Each character of the maze will be '.', '#', 'S', or 'E'.

There will be exactly one 'S' and exactly one 'E' in the maze.

The last line will contain a single string s (1 ≤ |s| ≤ 100) — the instructions given to the robot. Each character of s is a digit from 0 to 3.

Output format:
Print a single integer, the number of mappings of digits to directions that will lead the robot to the exit.

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

Note:
For the first sample, the only valid mapping is $$0 \rightarrow D, 1 \rightarrow L, 2 \rightarrow U, 3 \rightarrow R$$, where D is down, L is left, U is up, R is right.

Example input:
5 6
.....#
S....#
.#....
.#....
...E..
333300012

Example output:
1

Example input:
6 6
......
......
..SE..
......
......
......
01232123212302123021

Example output:
14

Editorial:
This problem is intended as an implementation problem. The bounds are small enough that a brute force works. We can iterate through all mapping of numbers to directions (i.e. using next permutation in C++ or doing some recursive DFS if there is no built in next permutation in your language), and simulate the robot's movements. We have to be careful that if the robot ever gets in an invalid state, we break out early and say the mapping is invalid.
New Year and Curling
Contest: Good Bye 2017
Difficulty rating: 1500
Tags: brute force, geometry, implementation, math

Carol is currently curling.

She has n disks each with radius r on the 2D plane.

Initially she has all these disks above the line y = 10100.

She then will slide the disks towards the line y = 0 one by one in order from 1 to n.

When she slides the i-th disk, she will place its center at the point (xi, 10100). She will then push it so the disk’s y coordinate continuously decreases, and x coordinate stays constant. The disk stops once it touches the line y = 0 or it touches any previous disk. Note that once a disk stops moving, it will not move again, even if hit by another disk.

Compute the y-coordinates of centers of all the disks after all disks have been pushed.

Input format:
The first line will contain two integers n and r (1 ≤ n, r ≤ 1 000), the number of disks, and the radius of the disks, respectively.

The next line will contain n integers x1, x2, ..., xn (1 ≤ xi ≤ 1 000) — the x-coordinates of the disks.

Output format:
Print a single line with n numbers. The i-th number denotes the y-coordinate of the center of the i-th disk. The output will be accepted if it has absolute or relative error at most 10 - 6.

Namely, let's assume that your answer for a particular value of a coordinate is a and the answer of the jury is b. The checker program will consider your answer correct if $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$ for all coordinates.

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

Note:
The final positions of the disks will look as follows:

In particular, note the position of the last disk.

Example input:
6 2
5 5 6 8 3 12

Example output:
2 6.0 9.87298334621 13.3370849613 12.5187346573 13.3370849613

Editorial:
This is another simulation problem with some geometry. As we push a disk, we can iterate through all previous disks and see if their x-coordinates are  ≤ 2r. If so, then that means these two circles can possibly touch.
If they do, we can compute the difference of heights between these two circles using pythagorean theorem. In particular, we want to know the change in y coordinate between the two touching circles. We know the hypotenuse (it is 2r since the circles are touching), and the change in x-coordinate is given, so the change in y coordinate is equal to $$\sqrt{4r^2 - dx^2}$$, where dx is the change in x-coordinate.
We can then take the maximum over all of these cases to get our final y-coordinate, since this is where this disk will first stop. Overall, this takes O(n2) time.
New Year and Rainbow Roads
Contest: Good Bye 2017
Difficulty rating: 2400
Tags: graphs, greedy, implementation

Roy and Biv have a set of n points on the infinite number line.

Each point has one of 3 colors: red, green, or blue.

Roy and Biv would like to connect all the points with some edges. Edges can be drawn between any of the two of the given points. The cost of an edge is equal to the distance between the two points it connects.

They want to do this in such a way that they will both see that all the points are connected (either directly or indirectly).

However, there is a catch: Roy cannot see the color red and Biv cannot see the color blue.

Therefore, they have to choose the edges in such a way that if all the red points are removed, the remaining blue and green points are connected (and similarly, if all the blue points are removed, the remaining red and green points are connected).

Help them compute the minimum cost way to choose edges to satisfy the above constraints.

Input format:
The first line will contain an integer n (1 ≤ n ≤ 300 000), the number of points.

The next n lines will contain two tokens pi and ci (pi is an integer, 1 ≤ pi ≤ 109, ci is a uppercase English letter 'R', 'G' or 'B'), denoting the position of the i-th point and the color of the i-th point. 'R' means red, 'G' denotes green, and 'B' means blue. The positions will be in strictly increasing order.

Output format:
Print a single integer, the minimum cost way to solve the problem.

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

Note:
In the first sample, it is optimal to draw edges between the points (1,2), (1,4), (3,4). These have costs 4, 14, 5, respectively.

Example input:
4
1 G
5 R
10 B
15 G

Example output:
23

Example input:
4
1 G
2 R
3 B
10 G

Example output:
12

Editorial:
Let's make a few simplifying observations
• It is not optimal to connect a red and blue point directly: Neither Roy or Biv will see this edge.
• If we have a sequence like red green red (or similarly blue green blue), it is not optimal to connect the outer two red nodes. We can replace the outer edge with two edges that have the same weight. This replacement will form some cycle in the red-green points, so we can remove one of these edges for a cheaper cost.
With these two observations, we can construct a solution as follows. First, split the points by the green points. Each section is now independent. There are then two cases, the outer green points are not directly connected, in which case, we must connect all the red/blue points in the line (for 2 * length of segment weight), or the outer green points are directly connected, in which case, we can omit the heaviest red and blue segment (for 3 * length of segment - heaviest red - heaviest blue). Thus, this problem can be solved in linear time.
Be careful about the case with no green points.
New Year and Original Order
Contest: Good Bye 2017
Difficulty rating: 2800
Tags: dp, math

Let S(n) denote the number that represents the digits of n in sorted order. For example, S(1) = 1, S(5) = 5, S(50394) = 3459, S(353535) = 333555.

Given a number X, compute $$\sum_{1 \leq k \leq X} S(k)$$ modulo 109 + 7.

Input format:
The first line of input will contain the integer X (1 ≤ X ≤ 10700).

Output format:
Print a single integer, the answer to the question.

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

Note:
The first few values of S are 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 12. The sum of these values is 195.

Example input:
21

Example output:
195

Example input:
345342

Example output:
390548434

Editorial:
This is a digit dp problem. Let's try to solve the subproblem "How many ways can the i-th digit be at least j?". Let's fix j, and solve this with dp. We have a dp state dp[a][b][c] = number of ways given we've considered the first a digits of X, we need b more occurrences of digits at least j, and c is a boolean saying whether or not we are strictly less than X or not yet.
For a fixed digit, we can compute this dp table in O(n2) time, and then compute the answers to our subproblem for each i (i.e. by varying b in our table).