1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
PolandBall and Forest
Contest: 8VC Venture Cup 2017 - Elimination Round
Difficulty rating: 1300
Tags: dfs and similar, dsu, graphs, interactive, trees

PolandBall lives in a forest with his family. There are some trees in the forest. Trees are undirected acyclic graphs with k vertices and k - 1 edges, where k is some integer. Note that one vertex is a valid tree.

There is exactly one relative living in each vertex of each tree, they have unique ids from 1 to n. For each Ball i we know the id of its most distant relative living on the same tree. If there are several such vertices, we only know the value of the one with smallest id among those.

How many trees are there in the forest?

Input format:
The first line contains single integer n (1 ≤ n ≤ 104) — the number of Balls living in the forest.

The second line contains a sequence p1, p2, ..., pn of length n, where (1 ≤ pi ≤ n) holds and pi denotes the most distant from Ball i relative living on the same tree. If there are several most distant relatives living on the same tree, pi is the id of one with the smallest id.

It's guaranteed that the sequence p corresponds to some valid forest.

Hacking: To hack someone, you should provide a correct forest as a test. The sequence p will be calculated according to the forest and given to the solution you try to hack as input. Use the following format:

In the first line, output the integer n (1 ≤ n ≤ 104) — the number of Balls and the integer m (0 ≤ m < n) — the total number of edges in the forest. Then m lines should follow. The i-th of them should contain two integers ai and bi and represent an edge between vertices in which relatives ai and bi live. For example, the first sample is written as follows:

Output format:
You should output the number of trees in the forest where PolandBall lives.

Interaction format:
From the technical side, this problem is interactive. However, it should not affect you (except hacking) since there is no interaction.

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

Note:
In the first sample testcase, possible forest is: 1-2 3-4-5.

There are 2 trees overall.

In the second sample testcase, the only possible graph is one vertex and no edges. Therefore, there is only one tree.

Example input:
5
2 1 5 3 3

Example output:
2

Example input:
1
1

Example output:
1

Editorial:
Property: Look at one tree and take its diameter. Name its endpoints A and B. For each vertex u from this component, p[u] = A or p[u] = B. It's easy to prove that.
We can just count number of different elements in P and divide it by two.
Special case : Isolated vertices (those with p[i] = i).
Poland has a diverse landscape. We have forests (PolandBall had to live somewhere =) ), mountains, sea and even deserts. We have all 4 weather seasons. And various beautiful animals live here. Like żubr, King of The Wilderness. Say hi!
PolandBall and Polygon
Contest: 8VC Venture Cup 2017 - Elimination Round
Difficulty rating: 2000
Tags: data structures

PolandBall has such a convex polygon with n veritces that no three of its diagonals intersect at the same point. PolandBall decided to improve it and draw some red segments.

He chose a number k such that gcd(n, k) = 1. Vertices of the polygon are numbered from 1 to n in a clockwise way. PolandBall repeats the following process n times, starting from the vertex 1:

Assume you've ended last operation in vertex x (consider x = 1 if it is the first operation). Draw a new segment from vertex x to k-th next vertex in clockwise direction. This is a vertex x + k or x + k - n depending on which of these is a valid index of polygon's vertex.

Your task is to calculate number of polygon's sections after each drawing. A section is a clear area inside the polygon bounded with drawn diagonals or the polygon's sides.

Input format:
There are only two numbers in the input: n and k (5 ≤ n ≤ 106, 2 ≤ k ≤ n - 2, gcd(n, k) = 1).

Output format:
You should print n values separated by spaces. The i-th value should represent number of polygon's sections after drawing first i lines.

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

Note:
The greatest common divisor (gcd) of two integers a and b is the largest positive integer that divides both a and b without a remainder.

For the first sample testcase, you should output "2 3 5 8 11". Pictures below correspond to situations after drawing lines.

Example input:
5 2

Example output:
2 3 5 8 11

Example input:
10 3

Example output:
2 3 4 6 9 12 16 21 26 31

Editorial:
First, we can set k = min(k, n - k). This changes nothing right now, but we'll use it later.
Our diagonals correspond to intervals [Li, Ri], each intersection of two diagonals:
A) adds one to result
B) is equivalent to intersection of their intervals
We will use segment or fenwick tree to store beginnings and ends of intervals. Because of the fact that all the segments have equal length (length = K) we know exactly what their intersection looks like.
Also, in order to maintain edges like (7, 3) we'll insert some intervals twice. Because of changes we did to k in the very beginning, we'll never count anything more than once.
Complexity : O(NlogN)
PolandBall and Gifts
Contest: 8VC Venture Cup 2017 - Elimination Round
Difficulty rating: 2600
Tags: bitmasks, dp, greedy

It's Christmas time! PolandBall and his friends will be giving themselves gifts. There are n Balls overall. Each Ball has someone for whom he should bring a present according to some permutation p, pi ≠ i for all i.

Unfortunately, Balls are quite clumsy. We know earlier that exactly k of them will forget to bring their gift. A Ball number i will get his present if the following two constraints will hold:

1. Ball number i will bring the present he should give.
2. Ball x such that px = i will bring his present.

What is minimum and maximum possible number of kids who will not get their present if exactly k Balls will forget theirs?

Input format:
The first line of input contains two integers n and k (2 ≤ n ≤ 106, 0 ≤ k ≤ n), representing the number of Balls and the number of Balls who will forget to bring their presents.

The second line contains the permutation p of integers from 1 to n, where pi is the index of Ball who should get a gift from the i-th Ball. For all i, pi ≠ i holds.

Output format:
You should output two values — minimum and maximum possible number of Balls who will not get their presents, in that order.

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

Note:
In the first sample, if the third and the first balls will forget to bring their presents, they will be th only balls not getting a present. Thus the minimum answer is 2. However, if the first ans the second balls will forget to bring their presents, then only the fifth ball will get a present. So, the maximum answer is 4.

Example input:
5 2
3 4 1 5 2

Example output:
2 4

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

Example output:
2 2

Editorial:
Every permutation can be represented as a set of cycles.
Maximum:
This is the easier case. Greedy works, some careful implementation and it's ok. Answer is usually 2k in this case, but not always.
Minimum:
If there are such cycles c1, c2, ... cm of length a1, a2, ..., an that a1 + a2 + ... + an = K, then K it's enough. Otherwise the result can be K + 1.
We would like to use knapsack to check it. However, the constraints are too big in this case for a normal knapsack.
We will choose some parameter T and process all numbers bigger than T normally. If there are w such elements, then complexity of this step is $${\mathcal{O}}\left({\frac{{w\cdot k}}{{32}}}\right)$$. There can be at most $$\frac{N}{T}$$ numbers bigger than T, so it's $${\mathcal{O}}\left({\frac{{n\cdot k}}{{32*T}}}\right)$$.
What should we do with numbers smaller than T? We'll process all numbers of the same type at once. When processing number of type x, we will maintain array c[] which denotes "how many numbers of type x are neccessary to have a certain number knapsack-possible. This step works in O(k·T).
Complexity : O(k·T + $$\frac{n \cdot k}{32 \cdot T}$$). We should choose such T that this value is minimum possible. T = 100 seems reasonable.
The situation described in a problem is a possible one. There is a tradition in Poland that we give our friends or schoolmates gifts during Christmas.
Frog Jumping
Contest: Codeforces Round 521 (Div. 3)
Difficulty rating: 800
Tags: math

A frog is currently at the point $$$0$$$ on a coordinate axis $$$Ox$$$. It jumps by the following algorithm: the first jump is $$$a$$$ units to the right, the second jump is $$$b$$$ units to the left, the third jump is $$$a$$$ units to the right, the fourth jump is $$$b$$$ units to the left, and so on.

Formally:

- if the frog has jumped an even number of times (before the current jump), it jumps from its current position $$$x$$$ to position $$$x+a$$$;
- otherwise it jumps from its current position $$$x$$$ to position $$$x-b$$$.

Your task is to calculate the position of the frog after $$$k$$$ jumps.

But... One more thing. You are watching $$$t$$$ different frogs so you have to answer $$$t$$$ independent queries.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of queries.

Each of the next $$$t$$$ lines contain queries (one query per line).

The query is described as three space-separated integers $$$a, b, k$$$ ($$$1 \le a, b, k \le 10^9$$$) — the lengths of two types of jumps and the number of jumps, respectively.

Output format:
Print $$$t$$$ integers. The $$$i$$$-th integer should be the answer for the $$$i$$$-th query.

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

Note:
In the first query frog jumps $$$5$$$ to the right, $$$2$$$ to the left and $$$5$$$ to the right so the answer is $$$5 - 2 + 5 = 8$$$.

In the second query frog jumps $$$100$$$ to the right, $$$1$$$ to the left, $$$100$$$ to the right and $$$1$$$ to the left so the answer is $$$100 - 1 + 100 - 1 = 198$$$.

In the third query the answer is $$$1 - 10 + 1 - 10 + 1 = -17$$$.

In the fourth query the answer is $$$10^9 - 1 + 10^9 - 1 + 10^9 - 1 = 2999999997$$$.

In the fifth query all frog's jumps are neutralized by each other so the answer is $$$0$$$.

The sixth query is the same as the fifth but without the last jump so the answer is $$$1$$$.

Example input:
6
5 2 3
100 1 4
1 10 5
1000000000 1 6
1 1 1000000000
1 1 999999999

Example output:
8
198
-17
2999999997
0
1

Editorial:
With each pair of jumps of kind "to the right — to the left" the frog jumps $$$a - b$$$. So the answer is almost $$$(a - b) \cdot \lfloor\frac{k}{2}\rfloor$$$. Almost because there can be one more jump to the right. So if $$$k$$$ is odd then we have to add $$$a$$$ to the answer.
Disturbed People
Contest: Codeforces Round 521 (Div. 3)
Difficulty rating: 1000
Tags: greedy

There is a house with $$$n$$$ flats situated on the main street of Berlatov. Vova is watching this house every night. The house can be represented as an array of $$$n$$$ integer numbers $$$a_1, a_2, \dots, a_n$$$, where $$$a_i = 1$$$ if in the $$$i$$$-th flat the light is on and $$$a_i = 0$$$ otherwise.

Vova thinks that people in the $$$i$$$-th flats are disturbed and cannot sleep if and only if $$$1 < i < n$$$ and $$$a_{i - 1} = a_{i + 1} = 1$$$ and $$$a_i = 0$$$.

Vova is concerned by the following question: what is the minimum number $$$k$$$ such that if people from exactly $$$k$$$ pairwise distinct flats will turn off the lights then nobody will be disturbed? Your task is to find this number $$$k$$$.

Input format:
The first line of the input contains one integer $$$n$$$ ($$$3 \le n \le 100$$$) — the number of flats in the house.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$a_i \in \{0, 1\}$$$), where $$$a_i$$$ is the state of light in the $$$i$$$-th flat.

Output format:
Print only one integer — the minimum number $$$k$$$ such that if people from exactly $$$k$$$ pairwise distinct flats will turn off the light then nobody will be disturbed.

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

Note:
In the first example people from flats $$$2$$$ and $$$7$$$ or $$$4$$$ and $$$7$$$ can turn off the light and nobody will be disturbed. It can be shown that there is no better answer in this example.

There are no disturbed people in second and third examples.

Example input:
10
1 1 0 1 1 0 1 0 1 0

Example output:
2

Example input:
5
1 1 0 0 0

Example output:
0

Editorial:
The first observation is that we are interested only in patterns of kind "101". All other patterns don't make sense at all.
So, let's build a greedy approach. Let's iterate over the given array from the left to the right and maintain that the prefix of the given answer is already correct. If now we are at some position $$$i$$$, $$$a_{i - 1} = a_{i + 1} = 1$$$ and $$$a_i = 0$$$ (and the prefix from $$$1$$$ to $$$i-2$$$ is already correct) then which one $$$1$$$ we have to replace? When we replace the left one then we cannot do better in the future, but when we replace the right one then we can fix some on the suffix of the array.
The easiest example is "1101011". If now we are at the position $$$3$$$ then we will do better if we will set $$$a_4 := 0$$$.
Pictures with Kittens (easy version)
Contest: Codeforces Round 521 (Div. 3)
Difficulty rating: 1900
Tags: dp

The only difference between easy and hard versions is the constraints.

Vova likes pictures with kittens. The news feed in the social network he uses can be represented as an array of $$$n$$$ consecutive pictures (with kittens, of course). Vova likes all these pictures, but some are more beautiful than the others: the $$$i$$$-th picture has beauty $$$a_i$$$.

Vova wants to repost exactly $$$x$$$ pictures in such a way that:

- each segment of the news feed of at least $$$k$$$ consecutive pictures has at least one picture reposted by Vova;
- the sum of beauty values of reposted pictures is maximum possible.

For example, if $$$k=1$$$ then Vova has to repost all the pictures in the news feed. If $$$k=2$$$ then Vova can skip some pictures, but between every pair of consecutive pictures Vova has to repost at least one of them.

Your task is to calculate the maximum possible sum of values of reposted pictures if Vova follows conditions described above, or say that there is no way to satisfy all conditions.

Input format:
The first line of the input contains three integers $$$n, k$$$ and $$$x$$$ ($$$1 \le k, x \le n \le 200$$$) — the number of pictures in the news feed, the minimum length of segment with at least one repost in it and the number of pictures Vova is ready to repost.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the beauty of the $$$i$$$-th picture.

Output format:
Print -1 if there is no way to repost some pictures to satisfy all the conditions in the problem statement.

Otherwise print one integer — the maximum sum of values of reposted pictures if Vova follows conditions described in the problem statement.

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

Example input:
5 2 3
5 1 3 10 1

Example output:
18

Example input:
6 1 5
10 30 30 70 10 10

Example output:
-1

Editorial:
Let's solve the problem using dynamic programming. Let $$$dp_{i, j}$$$ be the maximum total beauty of pictures if Vova is at the $$$i$$$-th picture now, the number of remaining reposts is $$$j$$$ and Vova reposted the $$$i$$$-th picture. Initially, $$$dp_{0, x} = 0$$$ and all other values of $$$dp$$$ are $$$-\infty$$$.
Let's learn to do some transitions to calculate this dynamic programming. What is the way to do it? Let's iterate over the position of the previously reposted picture and try to update $$$dp_{i, j}$$$ using previously calculated values. Obviously, this position can be from $$$i-1$$$ to $$$i-k$$$. So let's iterate over the position (let it be $$$p$$$) and if $$$dp_{p, j + 1}$$$ (we need one more repost to repost the $$$i$$$-th picture) is not $$$-\infty$$$ then try to update $$$dp_{i, j} = max(dp_{i, j}, dp_{p, j + 1} + a_i$$$) (pictures are $$$1$$$-indexed).
So, where can we find the answer? The answer is $$$\max\limits_{i = n - k + 1}^{n} dp_{i}$$$. If this value is $$$-\infty$$$ then the answer is -1.
Overall complexity is $$$O(nkx)$$$.
Sasha and His Trip
Contest: Codeforces Round 539 (Div. 2)
Difficulty rating: 900
Tags: dp, greedy, math

Sasha is a very happy guy, that's why he is always on the move. There are $$$n$$$ cities in the country where Sasha lives. They are all located on one straight line, and for convenience, they are numbered from $$$1$$$ to $$$n$$$ in increasing order. The distance between any two adjacent cities is equal to $$$1$$$ kilometer. Since all roads in the country are directed, it's possible to reach the city $$$y$$$ from the city $$$x$$$ only if $$$x < y$$$.

Once Sasha decided to go on a trip around the country and to visit all $$$n$$$ cities. He will move with the help of his car, Cheetah-2677. The tank capacity of this model is $$$v$$$ liters, and it spends exactly $$$1$$$ liter of fuel for $$$1$$$ kilometer of the way. At the beginning of the journey, the tank is empty. Sasha is located in the city with the number $$$1$$$ and wants to get to the city with the number $$$n$$$. There is a gas station in each city. In the $$$i$$$-th city, the price of $$$1$$$ liter of fuel is $$$i$$$ dollars. It is obvious that at any moment of time, the tank can contain at most $$$v$$$ liters of fuel.

Sasha doesn't like to waste money, that's why he wants to know what is the minimum amount of money is needed to finish the trip if he can buy fuel in any city he wants. Help him to figure it out!

Input format:
The first line contains two integers $$$n$$$ and $$$v$$$ ($$$2 \le n \le 100$$$, $$$1 \le v \le 100$$$)  — the number of cities in the country and the capacity of the tank.

Output format:
Print one integer — the minimum amount of money that is needed to finish the trip.

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

Note:
In the first example, Sasha can buy $$$2$$$ liters for $$$2$$$ dollars ($$$1$$$ dollar per liter) in the first city, drive to the second city, spend $$$1$$$ liter of fuel on it, then buy $$$1$$$ liter for $$$2$$$ dollars in the second city and then drive to the $$$4$$$-th city. Therefore, the answer is $$$1+1+2=4$$$.

In the second example, the capacity of the tank allows to fill the tank completely in the first city, and drive to the last city without stops in other cities.

Example input:
4 2

Example output:
4

Example input:
7 6

Example output:
6

Editorial:
When $$$n - 1 < v$$$ the answer is $$$n - 1$$$. Else you must notice, that it is optimal to fill the tank as soon as possible, because if you don't do that, you will have to spend more money in future. So to drive first $$$v - 1$$$ kilometers just buy $$$v - 1$$$ liters in the first city, then to drive between cities with numbers $$$i$$$ and $$$i + 1$$$, buy liter in the city with number $$$i - v + 1$$$.
Sasha and Magnetic Machines
Contest: Codeforces Round 539 (Div. 2)
Difficulty rating: 1300
Tags: greedy, number theory

One day Sasha visited the farmer 2D and his famous magnetic farm. On this farm, the crop grows due to the influence of a special magnetic field. Maintaining of the magnetic field is provided by $$$n$$$ machines, and the power of the $$$i$$$-th machine is $$$a_i$$$.

This year 2D decided to cultivate a new culture, but what exactly he didn't say. For the successful growth of the new culture, it is necessary to slightly change the powers of the machines. 2D can at most once choose an arbitrary integer $$$x$$$, then choose one machine and reduce the power of its machine by $$$x$$$ times, and at the same time increase the power of one another machine by $$$x$$$ times (powers of all the machines must stay positive integers). Note that he may not do that if he wants. More formally, 2D can choose two such indices $$$i$$$ and $$$j$$$, and one integer $$$x$$$ such that $$$x$$$ is a divisor of $$$a_i$$$, and change powers as following: $$$a_i = \frac{a_i}{x}$$$, $$$a_j = a_j \cdot x$$$

Sasha is very curious, that's why he wants to calculate the minimum total power the farmer can reach. There are too many machines, and Sasha can't cope with computations, help him!

Input format:
The first line contains one integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^4$$$) — the number of machines.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$) — the powers of the machines.

Output format:
Print one integer — minimum total power.

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

Note:
In the first example, the farmer can reduce the power of the $$$4$$$-th machine by $$$2$$$ times, and increase the power of the $$$1$$$-st machine by $$$2$$$ times, then the powers will be: $$$[2, 2, 3, 2, 5]$$$.

In the second example, the farmer can reduce the power of the $$$3$$$-rd machine by $$$2$$$ times, and increase the power of the $$$2$$$-nd machine by $$$2$$$ times. At the same time, the farmer can leave is be as it is and the total power won't change.

In the third example, it is optimal to leave it be as it is.

Example input:
5
1 2 3 4 5

Example output:
14

Example input:
4
4 2 4 4

Example output:
14

Editorial:
First notice that if we divide some number by $$$x$$$, then to get the minimal sum, it is optimal to multiply by $$$x$$$ the smallest number in the array. So now precalculate the sum of the initial array and the minimal $$$a_i$$$, then you can check all possible $$$x$$$ for every $$$a_i$$$, and choose the best variant. So the complexity is $$$O(n \cdot a_i)$$$.
Interview
Contest: Codeforces Round 344 (Div. 2)
Difficulty rating: 900
Tags: brute force, implementation

Blake is a CEO of a large company called "Blake Technologies". He loves his company very much and he thinks that his company should be the best. That is why every candidate needs to pass through the interview that consists of the following problem.

We define function f(x, l, r) as a bitwise OR of integers xl, xl + 1, ..., xr, where xi is the i-th element of the array x. You are given two arrays a and b of length n. You need to determine the maximum value of sum f(a, l, r) + f(b, l, r) among all possible 1 ≤ l ≤ r ≤ n.

Input format:
The first line of the input contains a single integer n (1 ≤ n ≤ 1000) — the length of the arrays.

The second line contains n integers ai (0 ≤ ai ≤ 109).

The third line contains n integers bi (0 ≤ bi ≤ 109).

Output format:
Print a single integer — the maximum value of sum f(a, l, r) + f(b, l, r) among all possible 1 ≤ l ≤ r ≤ n.

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

Note:
Bitwise OR of two non-negative integers a and b is the number c = a OR b, such that each of its digits in binary notation is 1 if and only if at least one of a or b have 1 in the corresponding position in binary notation.

In the first sample, one of the optimal answers is l = 2 and r = 4, because f(a, 2, 4) + f(b, 2, 4) = (2 OR 4 OR 3) + (3 OR 3 OR 12) = 7 + 15 = 22. Other ways to get maximum value is to choose l = 1 and r = 4, l = 1 and r = 5, l = 2 and r = 4, l = 2 and r = 5, l = 3 and r = 4, or l = 3 and r = 5.

In the second sample, the maximum value is obtained for l = 1 and r = 9.

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

Example output:
22

Example input:
10
13 2 7 11 8 4 9 8 5 1
5 7 18 9 2 3 0 11 8 6

Example output:
46

Editorial: