1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Hits Different
Contest: Codeforces Round 871 (Div. 4)
Difficulty rating: 1600
Tags: data structures, dp, implementation, math

In a carnival game, there is a huge pyramid of cans with $$$2023$$$ rows, numbered in a regular pattern as shown.

If can $$$9^2$$$ is hit initially, then all cans colored red in the picture above would fall.

You throw a ball at the pyramid, and it hits a single can with number $$$n^2$$$. This causes all cans that are stacked on top of this can to fall (that is, can $$$n^2$$$ falls, then the cans directly above $$$n^2$$$ fall, then the cans directly above those cans, and so on). For example, the picture above shows the cans that would fall if can $$$9^2$$$ is hit.

What is the sum of the numbers on all cans that fall? Recall that $$$n^2 = n \times n$$$.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

The only line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — it means that the can you hit has label $$$n^2$$$.

Output format:
For each test case, output a single integer — the sum of the numbers on all cans that fall.

Please note, that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++). For all valid inputs, the answer will always fit into 64-bit integer type.

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

Note:
The first test case is pictured in the statement. The sum of the numbers that fall is $$$$$$1^2 + 2^2 + 3^2 + 5^2 + 6^2 + 9^2 = 1 + 4 + 9 + 25 + 36 + 81 = 156.$$$$$$

In the second test case, only the can labeled $$$1^2$$$ falls, so the answer is $$$1^2=1$$$.

In the third test case, the cans labeled $$$1^2$$$ and $$$2^2$$$ fall, so the answer is $$$1^2+2^2=1+4=5$$$.

In the fourth test case, the cans labeled $$$1^2$$$ and $$$3^2$$$ fall, so the answer is $$$1^2+3^2=1+9=10$$$.

In the fifth test case, the cans labeled $$$1^2$$$, $$$2^2$$$, and $$$4^2$$$ fall, so the answer is $$$1^2+2^2+4^2=1+4+16=21$$$.

Example input:
10
9
1
2
3
4
5
6
10
1434
1000000

Example output:
156
1
5
10
21
39
46
146
63145186
58116199242129511

Editorial:
There are many solutions which involve going row by row and using some complicated math formulas, but here is a solution that requires no formulas and is much quicker to code.
The cans are hard to deal with, but if we replace them with a different shape, a diamond, we get the following:
To avoid finding the row and column, we can instead iterate through the cells in order $$$1, 2, 3, \dots$$$, that is, we go diagonal-by-diagonal in the grid above. Now, make a separate array $$$\texttt{ans}$$$, and keep track of the answer for each cell from $$$1$$$ to $$$10^6$$$ as we find its prefix sum. This avoids having to do any complicated math or binary search to find the row and column for the prefix sum. See the implementation for more details.
The time complexity is $$$\mathcal{O}(n)$$$ precomputation with $$$\mathcal{O}(1)$$$ per test case.
Don't Blame Me
Contest: Codeforces Round 871 (Div. 4)
Difficulty rating: 1700
Tags: bitmasks, combinatorics, dp, math

Sadly, the problem setter couldn't think of an interesting story, thus he just asks you to solve the following problem.

Given an array $$$a$$$ consisting of $$$n$$$ positive integers, count the number of non-empty subsequences for which the bitwise $$$\mathsf{AND}$$$ of the elements in the subsequence has exactly $$$k$$$ set bits in its binary representation. The answer may be large, so output it modulo $$$10^9+7$$$.

Recall that the subsequence of an array $$$a$$$ is a sequence that can be obtained from $$$a$$$ by removing some (possibly, zero) elements. For example, $$$[1, 2, 3]$$$, $$$[3]$$$, $$$[1, 3]$$$ are subsequences of $$$[1, 2, 3]$$$, but $$$[3, 2]$$$ and $$$[4, 5, 6]$$$ are not.

Note that $$$\mathsf{AND}$$$ represents the bitwise AND operation.

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

The first line of each test case consists of two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$0 \le k \le 6$$$) — the length of the array and the number of set bits that the bitwise $$$\mathsf{AND}$$$ the counted subsequences should have in their binary representation.

The second line of each test case consists of $$$n$$$ integers $$$a_i$$$ ($$$0 \leq a_i \leq 63$$$) — the array $$$a$$$.

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

Output format:
For each test case, output a single integer — the number of subsequences that have exactly $$$k$$$ set bits in their bitwise $$$\mathsf{AND}$$$ value's binary representation. The answer may be large, so output it modulo $$$10^9+7$$$.

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

Example input:
6
5 1
1 1 1 1 1
4 0
0 1 2 3
5 1
5 5 7 4 2
1 2
3
12 0
0 2 0 2 0 2 0 2 0 2 0 2
10 6
63 0 63 5 5 63 63 4 12 13

Example output:
31
10
10
1
4032
15

Editorial:
We can notice that the numbers are pretty small (up to $$$63$$$) and the AND values will be up to $$$63$$$ as well. Thus, we can count the number of subsequences that have AND value equal to $$$x$$$ for all $$$x$$$ from $$$0$$$ to $$$63$$$.
We can do this using dynamic programming. Let's denote $$$dp_{ij}$$$ as the number of subsequences using the first $$$i$$$ elements that have a total AND value of $$$j$$$. The transitions are quite simple. We can iterate over all $$$j$$$ values obtained previously and update the values respectively:
We have three cases:
The first case is when we don't use the $$$i$$$-th value. Here we just update the $$$dp_{ij}$$$ in the following way: $$$dp[i][j] = dp[i][j] + dp[i - 1][j]$$$.
The second case is when we use the $$$i$$$-th value. Here we update the $$$dp[i][a[i] \text{&} j]$$$ in the following way: $$$dp[i][a[i] \text{&} j] = dp[i][a[i] \text{&} j] + dp[i - 1][j]$$$.
The third case is starting a new subsequence with just the $$$i$$$-th element. Thus, we update $$$dp[i][a[i]] = dp[i][a[i]] + 1$$$.
Strange Functions
Contest: Educational Codeforces Round 99 (Rated for Div. 2)
Difficulty rating: 800
Tags: math, number theory

Let's define a function $$$f(x)$$$ ($$$x$$$ is a positive integer) as follows: write all digits of the decimal representation of $$$x$$$ backwards, then get rid of the leading zeroes. For example, $$$f(321) = 123$$$, $$$f(120) = 21$$$, $$$f(1000000) = 1$$$, $$$f(111) = 111$$$.

Let's define another function $$$g(x) = \dfrac{x}{f(f(x))}$$$ ($$$x$$$ is a positive integer as well).

Your task is the following: for the given positive integer $$$n$$$, calculate the number of different values of $$$g(x)$$$ among all numbers $$$x$$$ such that $$$1 \le x \le n$$$.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

Each test case consists of one line containing one integer $$$n$$$ ($$$1 \le n < 10^{100}$$$). This integer is given without leading zeroes.

Output format:
For each test case, print one integer — the number of different values of the function $$$g(x)$$$, if $$$x$$$ can be any integer from $$$[1, n]$$$.

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

Note:
Explanations for the two first test cases of the example:

1. if $$$n = 4$$$, then for every integer $$$x$$$ such that $$$1 \le x \le n$$$, $$$\dfrac{x}{f(f(x))} = 1$$$;
2. if $$$n = 37$$$, then for some integers $$$x$$$ such that $$$1 \le x \le n$$$, $$$\dfrac{x}{f(f(x))} = 1$$$ (for example, if $$$x = 23$$$, $$$f(f(x)) = 23$$$,$$$\dfrac{x}{f(f(x))} = 1$$$); and for other values of $$$x$$$, $$$\dfrac{x}{f(f(x))} = 10$$$ (for example, if $$$x = 30$$$, $$$f(f(x)) = 3$$$, $$$\dfrac{x}{f(f(x))} = 10$$$). So, there are two different values of $$$g(x)$$$.

Example input:
5
4
37
998244353
1000000007
12345678901337426966631415

Example output:
1
2
9
10
26

Editorial:
Let's analyze which values can the function $$$g(x)$$$ have. It can be proven that the value of $$$g(x)$$$ is equal to $$$10^k$$$, where $$$k$$$ is the number of zero-digits at the end of the number $$$x$$$, because $$$f(f(x))$$$ is the same number as $$$x$$$ except for the fact that it doesn't have any trailing zeroes.
Okay, now let's analyze when we reach the new value of $$$g(x)$$$. $$$1$$$ is the first value of $$$x$$$ such that $$$g(x) = 1$$$, $$$10$$$ is the first value of $$$x$$$ such that $$$g(x) = 10$$$, $$$100$$$ is the first value of $$$x$$$ such that $$$g(x) = 100$$$, and so on. We have to calculate the maximum number that has the form $$$10^k$$$ and is not greater than $$$n$$$, and the answer is exactly $$$k + 1$$$.
It can be done with a mathematical solution, but the most simple way to do it is read $$$n$$$ as a string instead, and calculate its length.
Maze
Contest: Codeforces Round 222 (Div. 1)
Difficulty rating: 1600
Tags: dfs and similar

Pavel loves grid mazes. A grid maze is an n × m rectangle maze where each cell is either empty, or is a wall. You can go from one cell to another only if both cells are empty and have a common side.

Pavel drew a grid maze with all empty cells forming a connected area. That is, you can go from any empty cell to any other one. Pavel doesn't like it when his maze has too little walls. He wants to turn exactly k empty cells into walls so that all the remaining cells still formed a connected area. Help him.

Input format:
The first line contains three integers n, m, k (1 ≤ n, m ≤ 500, 0 ≤ k < s), where n and m are the maze's height and width, correspondingly, k is the number of walls Pavel wants to add and letter s represents the number of empty cells in the original maze.

Each of the next n lines contains m characters. They describe the original maze. If a character on a line equals ".", then the corresponding cell is empty and if the character equals "#", then the cell is a wall.

Output format:
Print n lines containing m characters each: the new maze that fits Pavel's requirements. Mark the empty cells that you transformed into walls as "X", the other cells must be left without changes (that is, "." and "#").

It is guaranteed that a solution exists. If there are multiple solutions you can output any of them.

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

Example input:
3 4 2
#..#
..#.
#...

Example output:
#.X#
X.#.
#...

Example input:
5 4 5
#...
#.#.
.#..
...#
.#.#

Example output:
#XXX
#X#.
X#..
...#
.#.#

Editorial:
Captains Mode
Contest: Codeforces Round 222 (Div. 1)
Difficulty rating: 2200
Tags: bitmasks, dp, games

Kostya is a progamer specializing in the discipline of Dota 2. Valve Corporation, the developer of this game, has recently released a new patch which turned the balance of the game upside down. Kostya, as the captain of the team, realizes that the greatest responsibility lies on him, so he wants to resort to the analysis of innovations patch from the mathematical point of view to choose the best heroes for his team in every game.

A Dota 2 match involves two teams, each of them must choose some heroes that the players of the team are going to play for, and it is forbidden to choose the same hero several times, even in different teams. In large electronic sports competitions where Kostya's team is going to participate, the matches are held in the Captains Mode. In this mode the captains select the heroes by making one of two possible actions in a certain, predetermined order: pick or ban.

- To pick a hero for the team. After the captain picks, the picked hero goes to his team (later one of a team members will play it) and can no longer be selected by any of the teams.
- To ban a hero. After the ban the hero is not sent to any of the teams, but it still can no longer be selected by any of the teams.

The team captain may miss a pick or a ban. If he misses a pick, a random hero is added to his team from those that were available at that moment, and if he misses a ban, no hero is banned, as if there was no ban.

Kostya has already identified the strength of all the heroes based on the new patch fixes. Of course, Kostya knows the order of picks and bans. The strength of a team is the sum of the strengths of the team's heroes and both teams that participate in the match seek to maximize the difference in strengths in their favor. Help Kostya determine what team, the first one or the second one, has advantage in the match, and how large the advantage is.

Input format:
The first line contains a single integer n (2 ≤ n ≤ 100) — the number of heroes in Dota 2.

The second line contains n integers s1, s2, ..., sn (1 ≤ si ≤ 106) — the strengths of all the heroes.

The third line contains a single integer m (2 ≤ m ≤ min(n, 20)) — the number of actions the captains of the team must perform.

Next m lines look like "action team", where action is the needed action: a pick (represented as a "p") or a ban (represented as a "b"), and team is the number of the team that needs to perform the action (number 1 or 2).

It is guaranteed that each team makes at least one pick. Besides, each team has the same number of picks and the same number of bans.

Output format:
Print a single integer — the difference between the strength of the first team and the strength of the second team if the captains of both teams will act optimally well.

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

Example input:
2
2 1
2
p 1
p 2

Example output:
1

Example input:
6
6 4 5 4 5 5
4
b 2
p 1
b 1
p 2

Example output:
0

Editorial:
Developing Game
Contest: Codeforces Round 222 (Div. 1)
Difficulty rating: 2400
Tags: data structures

Pavel is going to make a game of his dream. However, he knows that he can't make it on his own so he founded a development company and hired n workers of staff. Now he wants to pick n workers from the staff who will be directly responsible for developing a game.

Each worker has a certain skill level vi. Besides, each worker doesn't want to work with the one whose skill is very different. In other words, the i-th worker won't work with those whose skill is less than li, and with those whose skill is more than ri.

Pavel understands that the game of his dream isn't too hard to develop, so the worker with any skill will be equally useful. That's why he wants to pick a team of the maximum possible size. Help him pick such team.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 105) — the number of workers Pavel hired.

Each of the following n lines contains three space-separated integers li, vi, ri (1 ≤ li ≤ vi ≤ ri ≤ 3·105) — the minimum skill value of the workers that the i-th worker can work with, the i-th worker's skill and the maximum skill value of the workers that the i-th worker can work with.

Output format:
In the first line print a single integer m — the number of workers Pavel must pick for developing the game.

In the next line print m space-separated integers — the numbers of the workers in any order.

If there are multiple optimal solutions, print any of them.

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

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

Example output:
3
1 3 4

Example input:
6
3 5 16
1 6 11
4 8 12
7 9 16
2 10 14
8 13 15

Example output:
4
1 2 3 5

Editorial:
Cookie Clicker
Contest: Codeforces Round 222 (Div. 1)
Difficulty rating: 2800
Tags: dp, geometry

Kostya is playing the computer game Cookie Clicker. The goal of this game is to gather cookies. You can get cookies using different buildings: you can just click a special field on the screen and get the cookies for the clicks, you can buy a cookie factory, an alchemy lab, a time machine and it all will bring lots and lots of cookies.

At the beginning of the game (time 0), Kostya has 0 cookies and no buildings. He has n available buildings to choose from: the i-th building is worth ci cookies and when it's built it brings vi cookies at the end of each second. Also, to make the game more interesting to play, Kostya decided to add a limit: at each moment of time, he can use only one building. Of course, he can change the active building each second at his discretion.

It's important that Kostya is playing a version of the game where he can buy new buildings and change active building only at time moments that are multiples of one second. Kostya can buy new building and use it at the same time. If Kostya starts to use a building at the time moment t, he can get the first profit from it only at the time moment t + 1.

Kostya wants to earn at least s cookies as quickly as possible. Determine the number of seconds he needs to do that.

Input format:
The first line contains two integers n and s (1 ≤ n ≤ 2·105, 1 ≤ s ≤ 1016) — the number of buildings in the game and the number of cookies Kostya wants to earn.

Each of the next n lines contains two integers vi and ci (1 ≤ vi ≤ 108, 0 ≤ ci ≤ 108) — the number of cookies the i-th building brings per second and the building's price.

Output format:
Output the only integer — the minimum number of seconds Kostya needs to earn at least s cookies. It is guaranteed that he can do it.

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

Example input:
3 9
1 0
2 3
5 4

Example output:
6

Example input:
3 6
1 0
2 2
5 4

Example output:
5

Editorial:
Easy As ABC
Contest: 2023-2024 ICPC, Asia Jakarta Regional Contest (Online Mirror, Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 1000
Tags: brute force

You are playing a word puzzle. The puzzle starts with a $$$3$$$ by $$$3$$$ grid, where each cell contains either the letter A, B, or C.

The goal of this puzzle is to find the lexicographically smallest possible word of length $$$3$$$. The word can be formed by choosing three different cells where the cell containing the first letter is adjacent to the cell containing the second letter, and the cell containing the second letter is adjacent to the cell containing the third letter.

Two cells are adjacent to each other if they share a border or a corner, as shown in the following illustration. Formally, if $$$(r, c)$$$ denotes the cell in the $$$r$$$-th row and $$$c$$$-th column, then cell $$$(r, c)$$$ is adjacent to cell $$$(r, c + 1)$$$, $$$(r - 1, c + 1)$$$, $$$(r - 1, c)$$$, $$$(r - 1, c - 1)$$$, $$$(r, c - 1)$$$, $$$(r + 1, c - 1)$$$, $$$(r + 1, c)$$$, and $$$(r + 1, c + 1)$$$.

Determine the lexicographically smallest possible word of length $$$3$$$ that you can find within the grid.

A string $$$s$$$ of length $$$n$$$ is lexicographically smaller than string $$$t$$$ of the same length if there exists an integer $$$1 \leq i \leq n$$$ such that $$$s_j = t_j$$$ for all $$$1 \leq j < i$$$, and $$$s_i < t_i$$$ in alphabetical order. The following illustration shows some examples on some grids and their the lexicographically smallest possible word of length $$$3$$$ that you can find within the grids.

Input format:
Input consists of three lines, each containing three letters, representing the puzzle grid. Each letter in the grid can only be either A, B, or C.

Output format:
Output the lexicographically smallest possible word of length $$$3$$$ that you can find within the grid.

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

Example input:
BCB
CAC
BCB

Example output:
ABC

Example input:
BCB
CCC
CCA

Example output:
ACB

Editorial:
Button Pressing
Contest: 2023-2024 ICPC, Asia Jakarta Regional Contest (Online Mirror, Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2600
Tags: bitmasks, constructive algorithms, hashing

You are given $$$N$$$ buttons (numbered from $$$1$$$ to $$$N$$$) and $$$N$$$ lamps (numbered from $$$1$$$ to $$$N$$$). Each lamp can either be on or off. Initially, lamp $$$i$$$ is on if $$$A_i = 1$$$, and off if $$$A_i = 0$$$.

Button $$$i$$$ is connected to lamp $$$i - 1$$$ (if $$$i > 1$$$) and lamp $$$i + 1$$$ (if $$$i < N$$$). In one move, you can press a button $$$i$$$ only if lamp $$$i$$$ is on. When a button is pressed, the state of the lamps connected to this button is toggled. Formally, the lamps will be on if it was off previously, and the lamps will be off if it was on previously. Note that lamp $$$i$$$ is not connected to button $$$i$$$, thus, the state of lamp $$$i$$$ does not change if button $$$i$$$ is pressed.

After zero or more moves, you want lamp $$$i$$$ to be on if $$$B_i = 1$$$, and off if $$$B_i = 0$$$. Determine if it is possible to achieve this task.

Input format:
This problem has multiple test cases. The first line consists of an integer $$$T$$$ ($$$1 \leq T \leq 1000$$$), which represents the number of test cases. Each test case consists of three lines.

The first line of each test case consists of an integer $$$N$$$ ($$$3 \le N \le 200\,000$$$). The sum of $$$N$$$ over all test cases does not exceed $$$200\,000$$$.

The second line of each test case consists of a string $$$A$$$ of length $$$N$$$. Each character of $$$A$$$ can either be 0 or 1. The $$$i$$$-th character represents the initial state of lamp $$$i$$$.

The third line of each test case consists of a string $$$A$$$ of length $$$N$$$. Each character of $$$B$$$ can either be 0 or 1. The $$$i$$$-th character represents the desired final state of lamp $$$i$$$.

Output format:
For each test case, output YES in a single line if the final state of all lamps can be reached after zero or more moves, or NO otherwise.

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

Note:
Explanation for the sample input/output #1

For the first test case, by pressing the buttons $$$4, 2, 4, 3, 1, 2$$$ in sequence, the condition of the buttons changes as: $$$0101 \rightarrow 0111 \rightarrow 1101 \rightarrow 1111 \rightarrow 1010 \rightarrow 1110 \rightarrow 0100$$$.

For the second test case, you are unable to press any button, hence it is impossible to reach the final state.

Example input:
2
4
0101
0100
3
000
010

Example output:
YES
NO

Example input:
5
7
0101011
1111010
5
11111
00000
4
1101
1101
6
101010
100100
3
000
000

Example output:
NO
NO
YES
YES
YES

Editorial: