1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Maximum Increase
Contest: Educational Codeforces Round 15
Difficulty rating: 800
Tags: dp, greedy, implementation

You are given array consisting of n integers. Your task is to find the maximum length of an increasing subarray of the given array.

A subarray is the sequence of consecutive elements of the array. Subarray is called increasing if each element of this subarray strictly greater than previous.

Input format:
The first line contains single positive integer n (1 ≤ n ≤ 105) — the number of integers.

The second line contains n positive integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Output format:
Print the maximum length of an increasing subarray of the given array.

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

Example input:
5
1 7 2 11 15

Example output:
3

Example input:
6
100 100 100 100 100 100

Example output:
1

Editorial:
Let's iterate through the given array from the left to the right and store in the variable cur the length of the current increasing subarray. If the current element is more than the previous we need to increase cur on one. In the other case we need to update the answer with the value of cur and put in cur 1, because new increasing subarray began.
Powers of Two
Contest: Educational Codeforces Round 15
Difficulty rating: 1500
Tags: brute force, data structures, implementation, math

You are given n integers a1, a2, ..., an. Find the number of pairs of indexes i, j (i < j) that ai + aj is a power of 2 (i. e. some integer x exists so that ai + aj = 2x).

Input format:
The first line contains the single positive integer n (1 ≤ n ≤ 105) — the number of integers.

The second line contains n positive integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Output format:
Print the number of pairs of indexes i, j (i < j) that ai + aj is a power of 2.

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

Note:
In the first example the following pairs of indexes include in answer: (1, 4) and (2, 4).

In the second example all pairs of indexes (i, j) (where i < j) include in answer.

Example input:
4
7 3 2 1

Example output:
2

Example input:
3
1 1 1

Example output:
3

Editorial:
To solve this problem we need to use map cnt and store in this map how many times every integer appears in the given array.
Then we need to iterate through all given numbers with variable i. Let the current number is equal to ai. For this number we need to iterate on all possible powers of 2 (the number of these powers is no more than 31). Let the current power is equal to cur. Then we need to make cnt[ai] –  and add the value cnt[ai - cur] to the asnwer.
Cellular Network
Contest: Educational Codeforces Round 15
Difficulty rating: 1500
Tags: binary search, implementation, two pointers

You are given n points on the straight line — the positions (x-coordinates) of the cities and m points on the same line — the positions (x-coordinates) of the cellular towers. All towers work in the same way — they provide cellular network for all cities, which are located at the distance which is no more than r from this tower.

Your task is to find minimal r that each city has been provided by cellular network, i.e. for each city there is at least one cellular tower at the distance which is no more than r.

If r = 0 then a tower provides cellular network only for the point where it is located. One tower can provide cellular network for any number of cities, but all these cities must be at the distance which is no more than r from this tower.

Input format:
The first line contains two positive integers n and m (1 ≤ n, m ≤ 105) — the number of cities and the number of cellular towers.

The second line contains a sequence of n integers a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — the coordinates of cities. It is allowed that there are any number of cities in the same point. All coordinates ai are given in non-decreasing order.

The third line contains a sequence of m integers b1, b2, ..., bm ( - 109 ≤ bj ≤ 109) — the coordinates of cellular towers. It is allowed that there are any number of towers in the same point. All coordinates bj are given in non-decreasing order.

Output format:
Print minimal r so that each city will be covered by cellular network.

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

Example input:
3 2
-2 2 4
-3 0

Example output:
4

Example input:
5 3
1 5 10 14 17
4 11 15

Example output:
3

Editorial:
At first store coordinates of all towers in set towers.
Then let's look through all cities. Let the current city be located in the point cur. Let it = towers.lowerbound(cur). Then if it is not equal to the end of the set we put in the variable dist the value ( * it - cur) — the distance to the nearest tower on the right for the current city. If it is not equal to the beginning of the set we need to make it –  and update dist = min(dist, cur -  * it) — the distance to the nearest tower on the left to the current city. After that we only need to update the answer: ans = max(ans, dist).
Also this problem can be solved with help of two pointers in linear time.
Road to Post Office
Contest: Educational Codeforces Round 15
Difficulty rating: 1900
Tags: math

Vasiliy has a car and he wants to get from home to the post office. The distance which he needs to pass equals to d kilometers.

Vasiliy's car is not new — it breaks after driven every k kilometers and Vasiliy needs t seconds to repair it. After repairing his car Vasiliy can drive again (but after k kilometers it will break again, and so on). In the beginning of the trip the car is just from repair station.

To drive one kilometer on car Vasiliy spends a seconds, to walk one kilometer on foot he needs b seconds (a < b).

Your task is to find minimal time after which Vasiliy will be able to reach the post office. Consider that in every moment of time Vasiliy can left his car and start to go on foot.

Input format:
The first line contains 5 positive integers d, k, a, b, t (1 ≤ d ≤ 1012; 1 ≤ k, a, b, t ≤ 106; a < b), where:

- d — the distance from home to the post office;
- k — the distance, which car is able to drive before breaking;
- a — the time, which Vasiliy spends to drive 1 kilometer on his car;
- b — the time, which Vasiliy spends to walk 1 kilometer on foot;
- t — the time, which Vasiliy spends to repair his car.

Output format:
Print the minimal time after which Vasiliy will be able to reach the post office.

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

Note:
In the first example Vasiliy needs to drive the first 2 kilometers on the car (in 2 seconds) and then to walk on foot 3 kilometers (in 12 seconds). So the answer equals to 14 seconds.

In the second example Vasiliy needs to drive the first 2 kilometers on the car (in 2 seconds), then repair his car (in 5 seconds) and drive 2 kilometers more on the car (in 2 seconds). After that he needs to walk on foot 1 kilometer (in 4 seconds). So the answer equals to 13 seconds.

Example input:
5 2 1 4 10

Example output:
14

Example input:
5 2 1 4 5

Example output:
13

Editorial:
To solve this problem we need to analyze some cases.
If d ≤ k then Vasiliy can ride car all road without breaking, so the answer is d * a.
If t + k * a > k * b (i. e. it is better to do not repair the car), Vasiliy must ride car the first k kilometers and then walks on foot, so the answer is k * a + (d - k) * b.
The only case left when it is better to ride car through all road until d % k kilometers left. Now we need to understand what better — repair the car and ride or do not repair the car and walk on foot. Let cnt = d / k, so Vasiliy necessarily must repair the car cnt - 1 times. Then the answer equals to k * cnt * a + (cnt - 1) * t + min(t + (d % k) * a, (d % k) * b).
Analysis of Pathes in Functional Graph
Contest: Educational Codeforces Round 15
Difficulty rating: 2100
Tags: data structures, graphs

You are given a functional graph. It is a directed graph, in which from each vertex goes exactly one arc. The vertices are numerated from 0 to n - 1.

Graph is given as the array f0, f1, ..., fn - 1, where fi — the number of vertex to which goes the only arc from the vertex i. Besides you are given array with weights of the arcs w0, w1, ..., wn - 1, where wi — the arc weight from i to fi.

The graph from the first sample test.

Also you are given the integer k (the length of the path) and you need to find for each vertex two numbers si and mi, where:

- si — the sum of the weights of all arcs of the path with length equals to k which starts from the vertex i;
- mi — the minimal weight from all arcs on the path with length k which starts from the vertex i.

The length of the path is the number of arcs on this path.

Input format:
The first line contains two integers n, k (1 ≤ n ≤ 105, 1 ≤ k ≤ 1010). The second line contains the sequence f0, f1, ..., fn - 1 (0 ≤ fi < n) and the third — the sequence w0, w1, ..., wn - 1 (0 ≤ wi ≤ 108).

Output format:
Print n lines, the pair of integers si, mi in each line.

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

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

Example output:
10 1
8 1
7 1
10 2
8 2
7 1
9 3

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

Example output:
0 0
4 1
8 2
12 3

Editorial:
This problem can be solved with help of the binary exponentiation.
Let the fr[u] is a structure, which for the vertex u store the information about the path from this vertex with length equals to r. The information which we need:
• fr[u].to — the number of vertex, in which ends the path with length r from the vertex u,
• fr[u].len — the sum of the arcs weights on the path with length r from the vertex u,
• fr[u].min — the minimal weight of the arc on the path with length r from the vertex u.
So if we have this values for all vertices and two fixed values r: r = r1 and r = r2 it is easy to find the values fr1 + r2[u] for all u:
• fr1 + r2[u].to = fr2[fr1[u].to].to, i. e. at first we went to the vertex fr1[u].to, and then with help of the array fr2 we can undrstand where we will stand in the end of the path;
• fr1 + r2[u].len = fr1[u].len + fr2[fr1[u].to].len;
• fr1 + r2[u].min = min(fr1[u].min, fr2[fr1[u].to].min).
The structures for the values r = r1 and r = r2 are and arrays of the structures, indexed with numbers of the graph vertices. So we showed that if we have two arrays for r = r1 and r = r2 we can get the array for r = r1 + r2. The operation which we described above we can call the multiply of the arrays, then the needed values fk can be found with help of raised values f1 to the power k. For make it we can use the binary exponentiation.
Also this problem can be solved with help of "binary shifts", but in fact it is the same thing that we described above.
T-Shirts
Contest: Educational Codeforces Round 15
Difficulty rating: 2800
Tags: data structures

The big consignment of t-shirts goes on sale in the shop before the beginning of the spring. In all n types of t-shirts go on sale. The t-shirt of the i-th type has two integer parameters — ci and qi, where ci — is the price of the i-th type t-shirt, qi — is the quality of the i-th type t-shirt. It should be assumed that the unlimited number of t-shirts of each type goes on sale in the shop, but in general the quality is not concerned with the price.

As predicted, k customers will come to the shop within the next month, the j-th customer will get ready to spend up to bj on buying t-shirts.

All customers have the same strategy. First of all, the customer wants to buy the maximum possible number of the highest quality t-shirts, then to buy the maximum possible number of the highest quality t-shirts from residuary t-shirts and so on. At the same time among several same quality t-shirts the customer will buy one that is cheaper. The customers don't like the same t-shirts, so each customer will not buy more than one t-shirt of one type.

Determine the number of t-shirts which each customer will buy, if they use the described strategy. All customers act independently from each other, and the purchase of one does not affect the purchase of another.

Input format:
The first line contains the positive integer n (1 ≤ n ≤ 2·105) — the number of t-shirt types.

Each of the following n lines contains two integers ci and qi (1 ≤ ci, qi ≤ 109) — the price and the quality of the i-th type t-shirt.

The next line contains the positive integer k (1 ≤ k ≤ 2·105) — the number of the customers.

The next line contains k positive integers b1, b2, ..., bk (1 ≤ bj ≤ 109), where the j-th number is equal to the sum, which the j-th customer gets ready to spend on t-shirts.

Output format:
The first line of the input data should contain the sequence of k integers, where the i-th number should be equal to the number of t-shirts, which the i-th customer will buy.

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

Note:
In the first example the first customer will buy the t-shirt of the second type, then the t-shirt of the first type. He will spend 10 and will not be able to buy the t-shirt of the third type because it costs 4, and the customer will owe only 3. The second customer will buy all three t-shirts (at first, the t-shirt of the second type, then the t-shirt of the first type, and then the t-shirt of the third type). He will spend all money on it.

Example input:
3
7 5
3 5
4 3
2
13 14

Example output:
2 3

Example input:
2
100 500
50 499
4
50 200 150 100

Example output:
1 2 2 1

Editorial:
Rotate, Flip and Zoom
Contest: VK Cup 2015 - Qualification Round 2
Difficulty rating: 1200
Tags: *special, implementation

Polycarp is writing the prototype of a graphic editor. He has already made up his mind that the basic image transformations in his editor will be: rotate the image 90 degrees clockwise, flip the image horizontally (symmetry relative to the vertical line, that is, the right part of the image moves to the left, and vice versa) and zooming on the image. He is sure that that there is a large number of transformations that can be expressed through these three.

He has recently stopped implementing all three transformations for monochrome images. To test this feature, he asked you to write a code that will consecutively perform three actions with a monochrome image: first it will rotate the image 90 degrees clockwise, then it will flip the image horizontally and finally, it will zoom in twice on the image (that is, it will double all the linear sizes).

Implement this feature to help Polycarp test his editor.

Input format:
The first line contains two integers, w and h (1 ≤ w, h ≤ 100) — the width and height of an image in pixels. The picture is given in h lines, each line contains w characters — each character encodes the color of the corresponding pixel of the image. The line consists only of characters "." and "*", as the image is monochrome.

Output format:
Print 2w lines, each containing 2h characters — the result of consecutive implementing of the three transformations, described above.

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

Example input:
3 2
.*.
.*.

Example output:
....
....
****
****
....
....

Example input:
9 20
**.......
****.....
******...
*******..
..******.
....****.
......***
*.....***
*********
*********
*********
*********
....**...
...****..
..******.
.********
****..***
***...***
**.....**
*.......*

Example output:
********......**********........********
********......**********........********
********........********......********..
********........********......********..
..********......********....********....
..********......********....********....
..********......********..********......
..********......********..********......
....********....****************........
....********....****************........
....********....****************........
....********....****************........
......******************..**********....
......******************..**********....
........****************....**********..
........****************....**********..
............************......**********
............************......**********

Editorial:
Name Quest
Contest: VK Cup 2015 - Qualification Round 2
Difficulty rating: 1400
Tags: *special, greedy

A Martian boy is named s — he has got this name quite recently from his parents for his coming of age birthday. Now he enjoys looking for his name everywhere. If he sees that he can obtain his name from some string by removing zero or more letters (at that, the remaining letters remain in the same order), he gets happy. For example, if s=«aba», then strings «baobab», «aabbaa», «helloabahello» make him very happy and strings «aab», «baaa» and «helloabhello» do not.

However rather than being happy once, he loves twice as much being happy twice! So, when he got string t as a present, he wanted to cut it in two parts (the left part and the right part) so that each part made him happy.

Help s determine the number of distinct ways to cut the given string t into two parts in the required manner.

Input format:
The first line contains string s, consisting of lowercase English letters. The length of string s is from 1 to 1000 letters.

The second line contains string t, that also consists of lowercase English letters. The length of string t is from 1 to 106 letters.

Output format:
Print the sought number of ways to cut string t in two so that each part made s happy.

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

Example input:
aba
baobababbah

Example output:
2

Example input:
mars
sunvenusearthmarsjupitersaturnuranusneptune

Example output:
0

Editorial:
Statistics of Recompressing Videos
Contest: VK Cup 2015 - Qualification Round 2
Difficulty rating: 1600
Tags: *special, data structures, implementation

A social network for dogs called DH (DogHouse) has k special servers to recompress uploaded videos of cute cats. After each video is uploaded, it should be recompressed on one (any) of the servers, and only after that it can be saved in the social network.

We know that each server takes one second to recompress a one minute fragment. Thus, any server takes m seconds to recompress a m minute video.

We know the time when each of the n videos were uploaded to the network (in seconds starting from the moment all servers started working). All videos appear at different moments of time and they are recompressed in the order they appear. If some video appeared at time s, then its recompressing can start at that very moment, immediately. Some videos can await recompressing when all the servers are busy. In this case, as soon as a server is available, it immediately starts recompressing another video. The videos that await recompressing go in a queue. If by the moment the videos started being recompressed some servers are available, then any of them starts recompressing the video.

For each video find the moment it stops being recompressed.

Input format:
The first line of the input contains integers n and k (1 ≤ n, k ≤ 5·105) — the number of videos and servers, respectively.

Next n lines contain the descriptions of the videos as pairs of integers si, mi (1 ≤ si, mi ≤ 109), where si is the time in seconds when the i-th video appeared and mi is its duration in minutes. It is guaranteed that all the si's are distinct and the videos are given in the chronological order of upload, that is in the order of increasing si.

Output format:
Print n numbers e1, e2, ..., en, where ei is the time in seconds after the servers start working, when the i-th video will be recompressed.

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

Example input:
3 2
1 5
2 5
3 5

Example output:
6
7
11

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

Example output:
1000000001
2000000001
3000000001
4000000001
5000000001
5000000004

Editorial:
Important Exam
Contest: Codeforces Round 577 (Div. 2)
Difficulty rating: 900
Tags: implementation, strings

A class of students wrote a multiple-choice test.

There are $$$n$$$ students in the class. The test had $$$m$$$ questions, each of them had $$$5$$$ possible answers (A, B, C, D or E). There is exactly one correct answer for each question. The correct answer for question $$$i$$$ worth $$$a_i$$$ points. Incorrect answers are graded with zero points.

The students remember what answers they gave on the exam, but they don't know what are the correct answers. They are very optimistic, so they want to know what is the maximum possible total score of all students in the class.

Input format:
The first line contains integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 1000$$$) — the number of students in the class and the number of questions in the test.

Each of the next $$$n$$$ lines contains string $$$s_i$$$ ($$$|s_i| = m$$$), describing an answer of the $$$i$$$-th student. The $$$j$$$-th character represents the student answer (A, B, C, D or E) on the $$$j$$$-th question.

The last line contains $$$m$$$ integers $$$a_1, a_2, \ldots, a_m$$$ ($$$1 \le a_i \le 1000$$$) — the number of points for the correct answer for every question.

Output format:
Print a single integer — the maximum possible total score of the class.

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

Note:
In the first example, one of the most optimal test answers is "ABCD", this way the total number of points will be $$$16$$$.

In the second example, one of the most optimal test answers is "CCC", this way each question will be answered by exactly one student and the total number of points is $$$5 + 4 + 12 = 21$$$.

Example input:
2 4
ABCD
ABCE
1 2 3 4

Example output:
16

Example input:
3 3
ABC
BCD
CDE
5 4 12

Example output:
21

Editorial:
For each of the question let's count the number of answers of different type. Let $$$cnt[i][A]=$$$The number of A answers to the i-th question. The maximum score for that answer is $$$a[i]\cdot max(cnt[i][A], cnt[i][B], cnt[i][C], cnt[i][D], cnt[i][E])$$$. The answer is the sum of the maximum answer for the $$$m$$$ questions.
Zero Array
Contest: Codeforces Round 577 (Div. 2)
Difficulty rating: 1500
Tags: greedy, math

You are given an array $$$a_1, a_2, \ldots, a_n$$$.

In one operation you can choose two elements $$$a_i$$$ and $$$a_j$$$ ($$$i \ne j$$$) and decrease each of them by one.

You need to check whether it is possible to make all the elements equal to zero or not.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the size of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array.

Output format:
Print "YES" if it is possible to make all elements zero, otherwise print "NO".

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

Note:
In the first example, you can make all elements equal to zero in $$$3$$$ operations:

- Decrease $$$a_1$$$ and $$$a_2$$$,
- Decrease $$$a_3$$$ and $$$a_4$$$,
- Decrease $$$a_3$$$ and $$$a_4$$$

In the second example, one can show that it is impossible to make all elements equal to zero.

Example input:
4
1 1 2 2

Example output:
YES

Example input:
6
1 2 3 4 5 6

Example output:
NO

Editorial:
There are 2 things needed to be possible to make all elements zero:
1: The sum of the elements must be even.
2: The biggest element have to be less or equal than the sum of all the other elements.
If both are true, the answer is "YES", otherwise "NO".