1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Yaroslav and Algorithm
Contest: Codeforces Round 182 (Div. 1)
Difficulty rating: 2500
Tags: constructive algorithms

Yaroslav likes algorithms. We'll describe one of his favorite algorithms.

1. The algorithm receives a string as the input. We denote this input string as a.
2. The algorithm consists of some number of command. Сommand number i looks either as si >> wi, or as si <> wi, where si and wi are some possibly empty strings of length at most 7, consisting of digits and characters "?".
3. At each iteration, the algorithm looks for a command with the minimum index i, such that si occurs in a as a substring. If this command is not found the algorithm terminates.
4. Let's denote the number of the found command as k. In string a the first occurrence of the string sk is replaced by string wk. If the found command at that had form sk >> wk, then the algorithm continues its execution and proceeds to the next iteration. Otherwise, the algorithm terminates.
5. The value of string a after algorithm termination is considered to be the output of the algorithm.

Yaroslav has a set of n positive integers, he needs to come up with his favorite algorithm that will increase each of the given numbers by one. More formally, if we consider each number as a string representing the decimal representation of the number, then being run on each of these strings separately, the algorithm should receive the output string that is a recording of the corresponding number increased by one.

Help Yaroslav.

Input format:
The first line contains integer n (1 ≤ n ≤ 100) — the number of elements in the set. The next n lines contains one positive integer each. All the given numbers are less than 1025.

Output format:
Print the algorithm which can individually increase each number of the set. In the i-th line print the command number i without spaces.

Your algorithm will be launched for each of these numbers. The answer will be considered correct if:

- Each line will a correct algorithm command (see the description in the problem statement).
- The number of commands should not exceed 50.
- The algorithm will increase each of the given numbers by one.
- To get a respond, the algorithm will perform no more than 200 iterations for each number.

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

Example input:
2
10
79

Example output:
10<>11
79<>80

Editorial:
Yaroslav and Divisors
Contest: Codeforces Round 182 (Div. 1)
Difficulty rating: 2200
Tags: data structures

Yaroslav has an array p = p1, p2, ..., pn (1 ≤ pi ≤ n), consisting of n distinct integers. Also, he has m queries:

- Query number i is represented as a pair of integers li, ri (1 ≤ li ≤ ri ≤ n).
- The answer to the query li, ri is the number of pairs of integers q, w (li ≤ q, w ≤ ri) such that pq is the divisor of pw.

Help Yaroslav, answer all his queries.

Input format:
The first line contains the integers n and m (1 ≤ n, m ≤ 2·105). The second line contains n distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n). The following m lines contain Yaroslav's queries. The i-th line contains integers li, ri (1 ≤ li ≤ ri ≤ n).

Output format:
Print m integers — the answers to Yaroslav's queries in the order they appear in the input.

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

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

Example input:
1 1
1
1 1

Example output:
1

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

Example output:
27
14
8
4
2
1
2
7
9

Editorial:
Yaroslav and Arrangements
Contest: Codeforces Round 182 (Div. 1)
Difficulty rating: 2800
Tags: dp

Yaroslav calls an array of r integers a1, a2, ..., ar good, if it meets the following conditions: |a1 - a2| = 1, |a2 - a3| = 1, ..., |ar - 1 - ar| = 1, |ar - a1| = 1, at that $$a_{1} = \min_{i=1}^{r} a_{i}$$.

An array of integers b1, b2, ..., br is called great, if it meets the following conditions:

1. The elements in it do not decrease (bi ≤ bi + 1).
2. If the inequalities 1 ≤ r ≤ n and 1 ≤ bi ≤ m hold.
3. If we can rearrange its elements and get at least one and at most k distinct good arrays.

Yaroslav has three integers n, m, k. He needs to count the number of distinct great arrays. Help Yaroslav! As the answer may be rather large, print the remainder after dividing it by 1000000007 (109 + 7).

Two arrays are considered distinct if there is a position in which they have distinct numbers.

Input format:
The single line contains three integers n, m, k (1 ≤ n, m, k ≤ 100).

Output format:
In a single line print the remainder after dividing the answer to the problem by number 1000000007 (109 + 7).

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

Example input:
1 1 1

Example output:
0

Example input:
3 3 3

Example output:
2

Editorial:
Wakanda Forever
Contest: Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 1]
Difficulty rating: 3500

In the Kingdom of Wakanda, the 2020 economic crisis has made a great impact on each city and its surrounding area. Cities have made a plan to build a fast train rail between them to boost the economy, but because of the insufficient funds, each city can only build a rail with one other city, and they want to do it together.

Cities which are paired up in the plan will share the cost of building the rail between them, and one city might need to pay more than the other. Each city knows the estimated cost of building their part of the rail to every other city. One city can not have the same cost of building the rail with two different cities.

If in a plan, there are two cities that are not connected, but the cost to create a rail between them is lower for each of them than the cost to build the rail with their current pairs, then that plan is not acceptable and the collaboration won't go on. Your task is to create a suitable plan for the cities (pairing of the cities) or say that such plan doesn't exist.

Input format:
First line contains one integer $$$N \;(2 \leq N \leq 10^3)\, $$$ — the number of cities.

Each of the next $$$N$$$ lines contains $$$N-1$$$ integers $$$A_{i,1}, A_{i,2}, ..., A_{i,i-1}, A_{i,i+1}, ..., A_{i,N-1}\; (1 \leq A_{i,j} \leq 10^9)\, $$$ — where $$$A_{i,j}$$$ represents the cost for city $$$i$$$ to build the rail to city $$$j$$$. Note that in each line $$$A_{i,i}$$$ is skipped.

Output format:
Output should contain $$$N$$$ integers $$$O_{1}, O_{2}, ..., O_N$$$, where $$$O_i$$$ represents the city with which city $$$i$$$ should build the rail with, or $$$-1$$$ if it is not possible to find the stable pairing.

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

Example input:
4
35 19 20
76 14 75
23 43 78
14 76 98

Example output:
3
4
1
2

Example input:
4
2 5 8
7 1 12
4 6 7
8 4 5

Example output:
-1

Editorial:
Valuable Paper
Contest: Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 1]
Difficulty rating: 1900
Tags: binary search, flows, graph matchings, graphs

The pandemic is upon us, and the world is in shortage of the most important resource: toilet paper. As one of the best prepared nations for this crisis, BubbleLand promised to help all other world nations with this valuable resource. To do that, the country will send airplanes to other countries carrying toilet paper.

In BubbleLand, there are $$$N$$$ toilet paper factories, and $$$N$$$ airports. Because of how much it takes to build a road, and of course legal issues, every factory must send paper to only one airport, and every airport can only take toilet paper from one factory.

Also, a road can't be built between all airport-factory pairs, again because of legal issues. Every possible road has number $$$d$$$ given, number of days it takes to build that road.

Your job is to choose $$$N$$$ factory-airport pairs, such that if the country starts building all roads at the same time, it takes the least amount of days to complete them.

Input format:
The first line contains two integers $$$N$$$ $$$(1 \leq N \leq 10^4)$$$ - number of airports/factories, and $$$M$$$ $$$(1 \leq M \leq 10^5)$$$ - number of available pairs to build a road between.

On next $$$M$$$ lines, there are three integers $$$u$$$, $$$v$$$ $$$(1 \leq u,v \leq N)$$$, $$$d$$$ $$$(1 \leq d \leq 10^9)$$$ - meaning that you can build a road between airport $$$u$$$ and factory $$$v$$$ for $$$d$$$ days.

Output format:
If there are no solutions, output -1. If there exists a solution, output the minimal number of days to complete all roads, equal to maximal $$$d$$$ among all chosen roads.

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

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

Example output:
4

Editorial:
Dušan's Railway
Contest: Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 1]
Difficulty rating: 3500
Tags: divide and conquer, graphs, trees

As you may already know, Dušan is keen on playing with railway models. He has a big map with cities that are connected with railways. His map can be seen as a graph where vertices are cities and the railways connecting them are the edges. So far, the graph corresponding to his map is a tree. As you already know, a tree is a connected acyclic undirected graph.

He is curious to find out whether his railway can be optimized somehow. He wants to add so-called shortcuts, which are also railways connecting pairs of cities. This shortcut will represent the railways in the unique path in the tree between the pair of cities it connects. Since Dušan doesn't like repeating the railways, he has also defined good paths in his newly obtained network (notice that after adding the shortcuts, his graph is no more a tree). He calls a path good, if no edge appears more than once, either as a regular railway edge or as an edge represented by some shortcut (Every shortcut in a good path has length 1, but uses up all the edges it represents - they can't appear again in that path). Having defined good paths, he defines good distance between two cities to be the length of the shortest good path between them. Finally, the shortcutting diameter of his network is the largest good distance between any two cities.

Now he is curious to find out whether it is possible to achieve shortcutting diameter less or equal than $$$k$$$, while adding as few shortcuts as possible.

Your solution should add no more than $$$\mathbf{10 \cdot n}$$$ shortcuts.

Input format:
The first line in the standard input contains an integer $$$n$$$ ($$$1 \le n \le 10^4$$$), representing the number of the cities in Dušan's railway map, and an integer k ($$$3 \le k \le n$$$) representing the shortcutting diameter that he wants to achieve.

Each of the following $$$n - 1$$$ lines will contain two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n, u_i \neq v_i$$$), meaning that there is a railway between cities $$$u_i$$$ and $$$v_i$$$.

Output format:
The first line of the output should contain a number $$$t$$$ representing the number of the shortcuts that were added.

Each of the following $$$t$$$ lines should contain two integers $$$u_i$$$ and $$$v_i$$$, signifying that a shortcut is added between cities $$$u_i$$$ and $$$v_i$$$.

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

Note:
Notice that adding a shortcut between all cities and city 1 will make a graph theoretic diameter become 2. On the other hand, the paths obtained that way might not be good, since some of the edges might get duplicated. In the example, adding a shortcut between all cities and city 1 doesn't create a valid solution, because for cities 5 and 10 the path that uses shortcuts 5-1 and 1-10 is not valid because it uses edges 1-2, 2-3, 3-4, 4-5 twice.

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

Example output:
8
3 7
3 5
3 6
3 1
7 9
7 10
7 4
7 5

Editorial:
Coins
Contest: Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 1]
Difficulty rating: 2700
Tags: math

A famous gang of pirates, Sea Dogs, has come back to their hideout from one of their extravagant plunders. They want to split their treasure fairly amongst themselves, that is why You, their trusted financial advisor, devised a game to help them:

All of them take a sit at their round table, some of them with the golden coins they have just stolen. At each iteration of the game if one of them has equal or more than 2 coins, he is eligible to the splitting and he gives one coin to each pirate sitting next to him. If there are more candidates (pirates with equal or more than 2 coins) then You are the one that chooses which one of them will do the splitting in that iteration. The game ends when there are no more candidates eligible to do the splitting.

Pirates can call it a day, only when the game ends. Since they are beings with a finite amount of time at their disposal, they would prefer if the game that they are playing can end after finite iterations, and if so, they call it a good game. On the other hand, if no matter how You do the splitting, the game cannot end in finite iterations, they call it a bad game. Can You help them figure out before they start playing if the game will be good or bad?

Input format:
The first line of input contains two integer numbers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^{9}$$$, $$$0 \le k \le 2\cdot10^5$$$), where $$$n$$$ denotes total number of pirates and $$$k$$$ is the number of pirates that have any coins.

The next $$$k$$$ lines of input contain integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i \le n$$$, $$$1 \le b_i \le 10^{9}$$$), where $$$a_i$$$ denotes the index of the pirate sitting at the round table ($$$n$$$ and $$$1$$$ are neighbours) and $$$b_i$$$ the total number of coins that pirate $$$a_i$$$ has at the start of the game.

Output format:
Print $$$1$$$ if the game is a good game: There is a way to do the splitting so the game ends after finite number of iterations.

Print $$$-1$$$ if the game is a bad game: No matter how You do the splitting the game does not end in finite number of iterations.

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

Note:
In the third example the game has no end, because You always only have only one candidate, after whose splitting you end up in the same position as the starting one.

Example input:
4 2
1 2
2 2

Example output:
1

Example input:
6 2
2 3
4 1

Example output:
1

Editorial:
Virus
Contest: Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 1]
Difficulty rating: 2500
Tags: data structures, divide and conquer, dsu, graphs

In Bubbleland a group of special programming forces gets a top secret job to calculate the number of potentially infected people by a new unknown virus. The state has a population of $$$n$$$ people and every day there is new information about new contacts between people. The job of special programming forces is to calculate how many contacts in the last $$$k$$$ days a given person had.

The new virus has an incubation period of $$$k$$$ days, and after that time people consider as non-infectious. Because the new virus is an extremely dangerous, government mark as suspicious everybody who had direct or indirect contact in the last $$$k$$$ days, independently of the order of contacts.

This virus is very strange, and people can't get durable immunity.

You need to help special programming forces to calculate the number of suspicious people for a given person (number of people who had contact with a given person).

There are 3 given inputs on beginning $$$n$$$ where $$$n$$$ is population, $$$q$$$ number of queries, $$$k$$$ virus incubation time in days. Each query is one of three types:

1. ($$$x$$$, $$$y$$$) person $$$x$$$ and person $$$y$$$ met that day ($$$x \neq y$$$).
2. ($$$z$$$) return the number of people in contact with $$$z$$$, counting himself.
3. The end of the current day moves on to the next day.

Input format:
The first line of input contains three integers $$$n$$$ ($$$1 \le n\le 10^5$$$) the number of people in the state, $$$q$$$ ($$$1 \le q\le 5×10^5$$$) number of queries and $$$k$$$ ($$$1 \le k\le 10^5$$$) virus incubation time in days.

Each of the next $$$q$$$ lines starts with an integer $$$t$$$ ($$$1 \le t\le 3$$$) the type of the query.

A pair of integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n$$$) follows in the query of the first type ($$$x \neq y$$$).

An integer $$$i$$$ ($$$1 \le i\le n$$$) follows in the query of the second type.

Query of third type does not have the following number.

Output format:
For the queries of the second type print on a separate line the current number of people in contact with a given person.

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

Note:
Pay attention if persons $$$1$$$ and $$$2$$$ had contact first day and next day persons $$$1$$$ and $$$3$$$ had contact, for $$$k$$$>$$$1$$$ number of contacts of person $$$3$$$ is $$$3$$$(persons:1,2,3).

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

Example output:
4
1
1
3
1

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

Example output:
4
1
4
4
3

Editorial:
Bubble Cup hypothesis
Contest: Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 1]
Difficulty rating: 2400
Tags: bitmasks, constructive algorithms, dp, math

The Bubble Cup hypothesis stood unsolved for $$$130$$$ years. Who ever proves the hypothesis will be regarded as one of the greatest mathematicians of our time! A famous mathematician Jerry Mao managed to reduce the hypothesis to this problem:

Given a number $$$m$$$, how many polynomials $$$P$$$ with coefficients in set $$${\{0,1,2,3,4,5,6,7\}}$$$ have: $$$P(2)=m$$$?

Help Jerry Mao solve the long standing problem!

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

On next line there are $$$t$$$ numbers, $$$m_i$$$ $$$(1 \leq m_i \leq 10^{18})$$$ - meaning that in case $$$i$$$ you should solve for number $$$m_i$$$.

Output format:
For each test case $$$i$$$, print the answer on separate lines: number of polynomials $$$P$$$ as described in statement such that $$$P(2)=m_i$$$, modulo $$$10^9 + 7$$$.

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

Note:
In first case, for $$$m=2$$$, polynomials that satisfy the constraint are $$$x$$$ and $$$2$$$.

In second case, for $$$m=4$$$, polynomials that satisfy the constraint are $$$x^2$$$, $$$x + 2$$$, $$$2x$$$ and $$$4$$$.

Example input:
2
2 4

Example output:
2
4

Editorial:
Lonely Numbers
Contest: Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 1]
Difficulty rating: 1600
Tags: binary search, math, number theory, two pointers

In number world, two different numbers are friends if they have a lot in common, but also each one has unique perks.

More precisely, two different numbers $$$a$$$ and $$$b$$$ are friends if $$$gcd(a,b)$$$, $$$\frac{a}{gcd(a,b)}$$$, $$$\frac{b}{gcd(a,b)}$$$ can form sides of a triangle.

Three numbers $$$a$$$, $$$b$$$ and $$$c$$$ can form sides of a triangle if $$$a + b > c$$$, $$$b + c > a$$$ and $$$c + a > b$$$.

In a group of numbers, a number is lonely if it doesn't have any friends in that group.

Given a group of numbers containing all numbers from $$$1, 2, 3, ..., n$$$, how many numbers in that group are lonely?

Input format:
The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^6)$$$ - number of test cases.

On next line there are $$$t$$$ numbers, $$$n_i$$$ $$$(1 \leq n_i \leq 10^6)$$$ - meaning that in case $$$i$$$ you should solve for numbers $$$1, 2, 3, ..., n_i$$$.

Output format:
For each test case, print the answer on separate lines: number of lonely numbers in group $$$1, 2, 3, ..., n_i$$$.

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

Note:
For first test case, $$$1$$$ is the only number and therefore lonely.

For second test case where $$$n=5$$$, numbers $$$1$$$, $$$3$$$ and $$$5$$$ are lonely.

For third test case where $$$n=10$$$, numbers $$$1$$$, $$$5$$$ and $$$7$$$ are lonely.

Example input:
3
1 5 10

Example output:
1
3
3

Editorial:
Light switches
Contest: Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 1]
Difficulty rating: 2600
Tags: meet-in-the-middle

Nikola owns a large warehouse which is illuminated by $$$N$$$ light bulbs, numbered $$$1$$$ to $$$N$$$. At the exit of the warehouse, there are $$$S$$$ light switches, numbered $$$1$$$ to $$$S$$$. Each switch swaps the on/off state for some light bulbs, so if a light bulb is off, flipping the switch turns it on, and if the light bulb is on, flipping the switch turns it off.

At the end of the day, Nikola wants to turn all the lights off. To achieve this, he will flip some of the light switches at the exit of the warehouse, but since Nikola is lazy, he wants to flip the _minimum_ number of switches required to turn all the lights off. Since Nikola was not able to calculate the minimum number of switches, he asked you to help him. During a period of $$$D$$$ days, Nikola noted which light bulbs were off and which were on at the end of each day. He wants you to tell him the minimum number of switches he needed to flip to turn all the lights off for each of the $$$D$$$ days or tell him that it's impossible.

Input format:
First line contains three integers, $$$N$$$, $$$S$$$ and $$$D$$$ ($$$1 \leq N \leq 10^3$$$, $$$1 \leq S \leq 30$$$, $$$1 \leq D \leq 10^3$$$) – representing number of light bulbs, the number of light switches, and the number of days respectively.

The next $$$S$$$ lines contain the description of each light switch as follows: The first number in the line, $$$C_i$$$ ($$$1 \leq C_i \leq N$$$), represents the number of light bulbs for which the on/off state is swapped by light switch $$$i$$$, the next $$$C_i$$$ numbers (sorted in increasing order) represent the indices of those light bulbs.

The next $$$D$$$ lines contain the description of light bulbs for each day as follows: The first number in the line, $$$T_i$$$ ($$$1 \leq T_i \leq N$$$), represents the number of light bulbs which are on at the end of day $$$i$$$, the next $$$T_i$$$ numbers (sorted in increasing order) represent the indices of those light bulbs.

Output format:
Print $$$D$$$ lines, one for each day. In the $$$i^{th}$$$ line, print the minimum number of switches that need to be flipped on day $$$i$$$, or $$$-1$$$ if it's impossible to turn all the lights off.

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

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

Example output:
2
2
3
-1

Editorial: