1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
GCD of an Array
Contest: Codeforces Round 705 (Div. 2)
Difficulty rating: 2100
Tags: brute force, data structures, hashing, implementation, math, number theory, sortings, two pointers

You are given an array $$$a$$$ of length $$$n$$$. You are asked to process $$$q$$$ queries of the following format: given integers $$$i$$$ and $$$x$$$, multiply $$$a_i$$$ by $$$x$$$.

After processing each query you need to output the greatest common divisor (GCD) of all elements of the array $$$a$$$.

Since the answer can be too large, you are asked to output it modulo $$$10^9+7$$$.

Input format:
The first line contains two integers — $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — the elements of the array $$$a$$$ before the changes.

The next $$$q$$$ lines contain queries in the following format: each line contains two integers $$$i$$$ and $$$x$$$ ($$$1 \le i \le n$$$, $$$1 \le x \le 2 \cdot 10^5$$$).

Output format:
Print $$$q$$$ lines: after processing each query output the GCD of all elements modulo $$$10^9+7$$$ on a separate line.

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

Note:
After the first query the array is $$$[12, 6, 8, 12]$$$, $$$\operatorname{gcd}(12, 6, 8, 12) = 2$$$.

After the second query — $$$[12, 18, 8, 12]$$$, $$$\operatorname{gcd}(12, 18, 8, 12) = 2$$$.

After the third query — $$$[12, 18, 24, 12]$$$, $$$\operatorname{gcd}(12, 18, 24, 12) = 6$$$.

Here the $$$\operatorname{gcd}$$$ function denotes the greatest common divisor.

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

Example output:
2
2
6

Editorial:
Notice that after each query the answer doesn't become smaller and we can solve the problem for each prime divisor independently.
For each number let's maintain an amount of occurences for all its prime divisors (you can implement it using $$$map$$$). For each prime divisor let's write to its corresponding $$$multiset$$$ the amount of times it is met in every of the numbers of the array, at the same time we won't add null values.
Initially, $$$ans=1$$$. Let's understand the way a prime divisor $$$p$$$ is included in the answer. If the size of its $$$multiset$$$ is not equal to $$$n$$$, then $$$ans$$$ won't change, otherwise $$$ans=(ans \cdot p^x)$$$ $$$\%$$$ $$$mod$$$, where $$$x$$$ is a minimal number of $$$multiset$$$.
Since $$$ans$$$ is not decreasing, then we can avoid calculating it all over again every time and instead recalculate it only for divisors that are being changed (with that, because the minimal number of $$$multiset$$$ is not decreasing as well, we can just increase the answer using multiplication).
To process the query, we need to find the prime factorization of $$$x$$$ (for example, using the Sieve of Eratosthenes) and add the prime divisors to the $$$map$$$ for $$$i$$$-th element (and correspondingly change the $$$multiset$$$ for that divisor).
Each query is processed in the complexity of the amount of prime divisors multiplied by the time of $$$map$$$ and $$$multiset$$$ operation, i.e. $$$log$$$.
Place Your Ad Here
Contest: VK Cup 2015 - Раунд 3
Difficulty rating: 2400

Ivan Anatolyevich's agency is starting to become famous in the town.

They have already ordered and made n TV commercial videos. Each video is made in a special way: the colors and the soundtrack are adjusted to the time of the day and the viewers' mood. That's why the i-th video can only be shown within the time range of [li, ri] (it is not necessary to use the whole segment but the broadcast time should be within this segment).

Now it's time to choose a TV channel to broadcast the commercial. Overall, there are m TV channels broadcasting in the city, the j-th one has cj viewers, and is ready to sell time [aj, bj] to broadcast the commercial.

Ivan Anatolyevich is facing a hard choice: he has to choose exactly one video i and exactly one TV channel j to broadcast this video and also a time range to broadcast [x, y]. At that the time range should be chosen so that it is both within range [li, ri] and within range [aj, bj].

Let's define the efficiency of the broadcast as value (y - x)·cj — the total sum of time that all the viewers of the TV channel are going to spend watching the commercial. Help Ivan Anatolyevich choose the broadcast with the maximum efficiency!

Input format:
The first line contains two integers n and m (1 ≤ n, m ≤ 2·105) — the number of commercial videos and channels, respectively.

Each of the following n lines contains two integers li, ri (0 ≤ li ≤ ri ≤ 109) — the segment of time when it is possible to show the corresponding video.

Each of the following m lines contains three integers aj, bj, cj (0 ≤ aj ≤ bj ≤ 109, 1 ≤ cj ≤ 109), characterizing the TV channel.

Output format:
In the first line print an integer — the maximum possible efficiency of the broadcast. If there is no correct way to get a strictly positive efficiency, print a zero.

If the maximum efficiency is strictly positive, in the second line also print the number of the video i (1 ≤ i ≤ n) and the number of the TV channel j (1 ≤ j ≤ m) in the most effective broadcast.

If there are multiple optimal answers, you can print any of them.

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

Note:
In the first sample test the most optimal solution is to show the second commercial using the first TV channel at time [2, 4]. The efficiency of such solution is equal to (4 - 2)·2 = 4.

In the second sample test Ivan Anatolievich's wish does not meet the options of the TV channel, the segments do not intersect, so the answer is zero.

Example input:
2 3
7 9
1 4
2 8 2
0 4 1
8 9 3

Example output:
4
2 1

Example input:
1 1
0 0
1 1 10

Example output:
0

Editorial:
Duck Hunt
Contest: VK Cup 2015 - Раунд 3
Difficulty rating: 3100
Tags: data structures

A duck hunter is doing his favorite thing, hunting. He lives in a two dimensional world and is located at point (0, 0). As he doesn't like walking for his prey, he prefers to shoot only vertically up (because in this case, the ducks fall straight into his hands). The hunter doesn't reload the gun immediately — r or more seconds must pass between the shots. When the hunter shoots up, the bullet immediately hits all the ducks who are directly above the hunter.

In a two dimensional world each duck is a horizontal segment that moves horizontally in the negative direction of the Ox axis at the speed 1 length unit per second. For each duck we know the values hi and ti — the x-coordinates of its head (the left end of the segment) and its tail (the right end of the segment) at time 0. The height where the duck is flying isn't important as the gun shoots vertically up to the infinite height and hits all the ducks on its way.

The figure to the first sample.

What maximum number of ducks can the hunter shoot? The duck is considered shot by the hunter if at the moment of the shot at least one of its point intersects the Oy axis. After the hunter shoots the duck, it falls and it can't be shot anymore. The hunter cannot make shots before the moment of time 0.

Input format:
The first line of the input contains integers n, r (1 ≤ n ≤ 200 000, 1 ≤ r ≤ 109) — the number of ducks and the minimum time in seconds between the shots.

Then n lines follow, each of them contains two integers hi, ti ( - 109 ≤ hi < ti ≤ 109) — the x-coordinate of the head and tail of the i-th duck at the moment 0.

Output format:
Print a single integer — the maximum number of ducks that can be shot by the hunter.

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

Note:
In the first sample the hunter must shoot at time 0, this shot kills ducks 1 and 3. Then the hunter needs to reload the gun and shoot again at time 3. His second shot hits the tail of duck 2.

In the second sample the hunter can make shots at times 0 and 6 to hit three ducks.

Example input:
3 3
-3 0
1 3
-1 2

Example output:
3

Example input:
4 5
-1 1
2 4
5 9
6 8

Example output:
3

Editorial:
Idempotent functions
Contest: VK Cup 2015 - Раунд 3
Difficulty rating: 2000

Some time ago Leonid have known about idempotent functions. Idempotent function defined on a set {1, 2, ..., n} is such function $$g:\{1,2,\ldots,n\}\to\{1,2,\ldots,n\}$$, that for any $$x \in \{1, 2, \ldots, n\}$$ the formula g(g(x)) = g(x) holds.

Let's denote as f(k)(x) the function f applied k times to the value x. More formally, f(1)(x) = f(x), f(k)(x) = f(f(k - 1)(x)) for each k > 1.

You are given some function $$f: \{1, 2, \ldots, n\} \to \{1, 2, \ldots, n\}$$. Your task is to find minimum positive integer k such that function f(k)(x) is idempotent.

Input format:
In the first line of the input there is a single integer n (1 ≤ n ≤ 200) — the size of function f domain.

In the second line follow f(1), f(2), ..., f(n) (1 ≤ f(i) ≤ n for each 1 ≤ i ≤ n), the values of a function.

Output format:
Output minimum k such that function f(k)(x) is idempotent.

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

Note:
In the first sample test function f(x) = f(1)(x) is already idempotent since f(f(1)) = f(1) = 1, f(f(2)) = f(2) = 2, f(f(3)) = f(3) = 2, f(f(4)) = f(4) = 4.

In the second sample test:

- function f(x) = f(1)(x) isn't idempotent because f(f(1)) = 3 but f(1) = 2;
- function f(x) = f(2)(x) is idempotent since for any x it is true that f(2)(x) = 3, so it is also true that f(2)(f(2)(x)) = 3.

In the third sample test:

- function f(x) = f(1)(x) isn't idempotent because f(f(1)) = 3 but f(1) = 2;
- function f(f(x)) = f(2)(x) isn't idempotent because f(2)(f(2)(1)) = 2 but f(2)(1) = 3;
- function f(f(f(x))) = f(3)(x) is idempotent since it is identity function: f(3)(x) = x for any $$x \in \{1, 2, 3\}$$ meaning that the formula f(3)(f(3)(x)) = f(3)(x) also holds.

Example input:
4
1 2 2 4

Example output:
1

Example input:
3
2 3 3

Example output:
2

Editorial:
Superhero's Job
Contest: VK Cup 2015 - Раунд 3
Difficulty rating: 2600

It's tough to be a superhero. And it's twice as tough to resist the supervillain who is cool at math. Suppose that you're an ordinary Batman in an ordinary city of Gotham. Your enemy Joker mined the building of the city administration and you only have several minutes to neutralize the charge. To do that you should enter the cancel code on the bomb control panel.

However, that mad man decided to give you a hint. This morning the mayor found a playing card under his pillow. There was a line written on the card:

$$J(x) = \sum_{\substack{1 \leq k \leq x \\ k | x \\ \gcd(k, x/k) = 1}} k$$

The bomb has a note saying "J(x) = A", where A is some positive integer. You suspect that the cancel code is some integer x that meets the equation J(x) = A. Now in order to decide whether you should neutralize the bomb or run for your life, you've got to count how many distinct positive integers x meet this equation.

Input format:
The single line of the input contains a single integer A (1 ≤ A ≤ 1012).

Output format:
Print the number of solutions of the equation J(x) = A.

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

Note:
Record x|n means that number n divides number x.

$$\gcd(a,b)$$ is defined as the largest positive integer that divides both a and b.

In the first sample test the only suitable value of x is 2. Then J(2) = 1 + 2.

In the second sample test the following values of x match:

- x = 14, J(14) = 1 + 2 + 7 + 14 = 24
- x = 15, J(15) = 1 + 3 + 5 + 15 = 24
- x = 23, J(23) = 1 + 23 = 24

Example input:
3

Example output:
1

Example input:
24

Example output:
3

Editorial:
Playing on Graph
Contest: VK Cup 2015 - Раунд 3
Difficulty rating: 2600

Vova and Marina love offering puzzles to each other. Today Marina offered Vova to cope with the following task.

Vova has a non-directed graph consisting of n vertices and m edges without loops and multiple edges. Let's define the operation of contraction two vertices a and b that are not connected by an edge. As a result of this operation vertices a and b are deleted and instead of them a new vertex x is added into the graph, and also edges are drawn from it to all vertices that were connected with a or with b (specifically, if the vertex was connected with both a and b, then also exactly one edge is added from x to it). Thus, as a result of contraction again a non-directed graph is formed, it contains no loops nor multiple edges, and it contains (n - 1) vertices.

Vova must perform the contraction an arbitrary number of times to transform the given graph into a chain of the maximum length. A chain of length k (k ≥ 0) is a connected graph whose vertices can be numbered with integers from 1 to k + 1 so that the edges of the graph connect all pairs of vertices (i, i + 1) (1 ≤ i ≤ k) and only them. Specifically, the graph that consists of one vertex is a chain of length 0. The vertices that are formed as a result of the contraction are allowed to be used in the following operations of contraction.

The picture illustrates the contraction of two vertices marked by red.

Help Vova cope with his girlfriend's task. Find the maximum length of the chain that can be obtained from the resulting graph or else determine that it is impossible to obtain the chain.

Input format:
The first line contains two integers n, m (1 ≤ n ≤ 1000, 0 ≤ m ≤ 100 000) — the number of vertices and the number of edges in the original graph.

Next m lines contain the descriptions of edges in the format ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi), which means that there is an edge between vertices ai and bi. It is guaranteed that there is at most one edge between each pair of vertexes.

Output format:
If it is impossible to obtain a chain from the given graph, print  - 1. Otherwise, print the maximum possible number of edges in the resulting chain.

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

Note:
In the first sample test you can contract vertices 4 and 5 and obtain a chain of length 3.

In the second sample test it is initially impossible to contract any pair of vertexes, so it is impossible to achieve the desired result.

In the third sample test you can contract vertices 1 and 2 and obtain a chain of length 2.

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

Example output:
3

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

Example output:
-1

Editorial:
Quest
Contest: VK Cup 2015 - Раунд 3
Difficulty rating: 2100

Polycarp is making a quest for his friends. He has already made n tasks, for each task the boy evaluated how interesting it is as an integer qi, and the time ti in minutes needed to complete the task.

An interesting feature of his quest is: each participant should get the task that is best suited for him, depending on his preferences. The task is chosen based on an interactive quiz that consists of some questions. The player should answer these questions with "yes" or "no". Depending on the answer to the question, the participant either moves to another question or goes to one of the tasks that are in the quest. In other words, the quest is a binary tree, its nodes contain questions and its leaves contain tasks.

We know that answering any of the questions that are asked before getting a task takes exactly one minute from the quest player. Polycarp knows that his friends are busy people and they can't participate in the quest for more than T minutes. Polycarp wants to choose some of the n tasks he made, invent the corresponding set of questions for them and use them to form an interactive quiz as a binary tree so that no matter how the player answers quiz questions, he spends at most T minutes on completing the whole quest (that is, answering all the questions and completing the task). Specifically, the quest can contain zero questions and go straight to the task. Each task can only be used once (i.e., the people who give different answers to questions should get different tasks).

Polycarp wants the total "interest" value of the tasks involved in the quest to be as large as possible. Help him determine the maximum possible total interest value of the task considering that the quest should be completed in T minutes at any variant of answering questions.

Input format:
The first line contains two integers n and T (1 ≤ n ≤ 1000, 1 ≤ T ≤ 100) — the number of tasks made by Polycarp and the maximum time a quest player should fit into.

Next n lines contain two integers ti, qi (1 ≤ ti ≤ T, 1 ≤ qi ≤ 1000) each — the time in minutes needed to complete the i-th task and its interest value.

Output format:
Print a single integer — the maximum possible total interest value of all the tasks in the quest.

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

Note:
In the first sample test all the five tasks can be complemented with four questions and joined into one quest.

In the second sample test it is impossible to use all the five tasks, but you can take two of them, the most interesting ones.

In the third sample test the optimal strategy is to include only the second task into the quest.

Here is the picture that illustrates the answers to the sample tests. The blue circles represent the questions, the two arrows that go from every circle represent where a person goes depending on his answer to that question. The tasks are the red ovals.

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

Example output:
11

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

Example output:
9

Editorial:
PIN Codes
Contest: Codeforces Round 603 (Div. 2)
Difficulty rating: 1400
Tags: greedy, implementation

A PIN code is a string that consists of exactly $$$4$$$ digits. Examples of possible PIN codes: 7013, 0000 and 0990. Please note that the PIN code can begin with any digit, even with 0.

Polycarp has $$$n$$$ ($$$2 \le n \le 10$$$) bank cards, the PIN code of the $$$i$$$-th card is $$$p_i$$$.

Polycarp has recently read a recommendation that it is better to set different PIN codes on different cards. Thus he wants to change the minimal number of digits in the PIN codes of his cards so that all $$$n$$$ codes would become different.

Formally, in one step, Polycarp picks $$$i$$$-th card ($$$1 \le i \le n$$$), then in its PIN code $$$p_i$$$ selects one position (from $$$1$$$ to $$$4$$$), and changes the digit in this position to any other. He needs to change the minimum number of digits so that all PIN codes become different.

Polycarp quickly solved this problem. Can you solve it?

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

The first line of each of $$$t$$$ test sets contains a single integer $$$n$$$ ($$$2 \le n \le 10$$$) — the number of Polycarp's bank cards. The next $$$n$$$ lines contain the PIN codes $$$p_1, p_2, \dots, p_n$$$ — one per line. The length of each of them is $$$4$$$. All PIN codes consist of digits only.

Output format:
Print the answers to $$$t$$$ test sets. The answer to each set should consist of a $$$n + 1$$$ lines

In the first line print $$$k$$$ — the least number of changes to make all PIN codes different. In the next $$$n$$$ lines output the changed PIN codes in the order corresponding to their appearance in the input. If there are several optimal answers, print any of them.

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

Example input:
3
2
1234
0600
2
1337
1337
4
3139
3139
3139
3139

Example output:
0
1234
0600
1
1337
1237
3
3139
3138
3939
6139

Editorial:
Group all the numbers into groups of equals PIN-Codes. Note that the size of each such group does not exceed $$$10$$$. Therefore, in each PIN-Code we need to change no more than $$$1$$$ digits. If the group consists of $$$1$$$ element, then we do nothing, otherwise, we take all the PIN-codes except one from this group and change exactly one digit in them so that the new PIN-code becomes unique.
Secret Passwords
Contest: Codeforces Round 603 (Div. 2)
Difficulty rating: 1500
Tags: dfs and similar, dsu, graphs

One unknown hacker wants to get the admin's password of AtForces testing system, to get problems from the next contest. To achieve that, he sneaked into the administrator's office and stole a piece of paper with a list of $$$n$$$ passwords — strings, consists of small Latin letters.

Hacker went home and started preparing to hack AtForces. He found that the system contains only passwords from the stolen list and that the system determines the equivalence of the passwords $$$a$$$ and $$$b$$$ as follows:

- two passwords $$$a$$$ and $$$b$$$ are equivalent if there is a letter, that exists in both $$$a$$$ and $$$b$$$;
- two passwords $$$a$$$ and $$$b$$$ are equivalent if there is a password $$$c$$$ from the list, which is equivalent to both $$$a$$$ and $$$b$$$.

If a password is set in the system and an equivalent one is applied to access the system, then the user is accessed into the system.

For example, if the list contain passwords "a", "b", "ab", "d", then passwords "a", "b", "ab" are equivalent to each other, but the password "d" is not equivalent to any other password from list. In other words, if:

- admin's password is "b", then you can access to system by using any of this passwords: "a", "b", "ab";
- admin's password is "d", then you can access to system by using only "d".

Only one password from the list is the admin's password from the testing system. Help hacker to calculate the minimal number of passwords, required to guaranteed access to the system. Keep in mind that the hacker does not know which password is set in the system.

Input format:
The first line contain integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — number of passwords in the list. Next $$$n$$$ lines contains passwords from the list – non-empty strings $$$s_i$$$, with length at most $$$50$$$ letters. Some of the passwords may be equal.

It is guaranteed that the total length of all passwords does not exceed $$$10^6$$$ letters. All of them consist only of lowercase Latin letters.

Output format:
In a single line print the minimal number of passwords, the use of which will allow guaranteed to access the system.

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

Note:
In the second example hacker need to use any of the passwords to access the system.

Example input:
4
a
b
ab
d

Example output:
2

Example input:
3
ab
bc
abc

Example output:
1

Editorial:
This problem can be solved in many ways (DSU, bipartite graph, std::set and so on). A solution using a bipartite graph will be described here.
Consider a bipartite graph with $$$26$$$ vertices corresponding to each letter of the Latin alphabet in the first set and $$$n$$$ vertices corresponding to each password in the second set. Connect each password and the letters that are part of this password with an edge. From the definition of equivalence of passwords, it is easy to understand that the answer to the problem is the number of connected components in this bipartite graph.
Total complexity: $$$\mathcal{O}(n)$$$.