1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Board Moves
Contest: Codeforces Round 642 (Div. 3)
Difficulty rating: 1000
Tags: math

You are given a board of size $$$n \times n$$$, where $$$n$$$ is odd (not divisible by $$$2$$$). Initially, each cell of the board contains one figure.

In one move, you can select exactly one figure presented in some cell and move it to one of the cells sharing a side or a corner with the current cell, i.e. from the cell $$$(i, j)$$$ you can move the figure to cells:

- $$$(i - 1, j - 1)$$$;
- $$$(i - 1, j)$$$;
- $$$(i - 1, j + 1)$$$;
- $$$(i, j - 1)$$$;
- $$$(i, j + 1)$$$;
- $$$(i + 1, j - 1)$$$;
- $$$(i + 1, j)$$$;
- $$$(i + 1, j + 1)$$$;

Of course, you can not move figures to cells out of the board. It is allowed that after a move there will be several figures in one cell.

Your task is to find the minimum number of moves needed to get all the figures into one cell (i.e. $$$n^2-1$$$ cells should contain $$$0$$$ figures and one cell should contain $$$n^2$$$ figures).

You have to answer $$$t$$$ independent test cases.

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

The only line of the test case contains one integer $$$n$$$ ($$$1 \le n < 5 \cdot 10^5$$$) — the size of the board. It is guaranteed that $$$n$$$ is odd (not divisible by $$$2$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$ ($$$\sum n \le 5 \cdot 10^5$$$).

Output format:
For each test case print the answer — the minimum number of moves needed to get all the figures into one cell.

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

Example input:
3
1
5
499993

Example output:
0
40
41664916690999888

Editorial:
It is intuitive (and provable) that the best strategy is to move each figure to the center cell $$$(\frac{n+1}{2}, \frac{n+1}{2})$$$. Now, with some paperwork or easy observations, we can notice that we have exactly $$$8$$$ cells with the shortest distance $$$1$$$, $$$16$$$ cells with the shortest distance $$$2$$$, $$$24$$$ cells with the shortest distance $$$3$$$ and so on. So we have $$$8i$$$ cells with the shortest distance $$$i$$$. So the answer is $$$1 \cdot 8 + 2 \cdot 16 + 3 \cdot 24 + \dots + (\frac{n-1}{2})^2 \cdot 8$$$. It can be rewritten as $$$8 (1 + 4 + 9 + \dots + (\frac{n-1}{2})^2)$$$ so we can just calculate the sum of squares of all integers from $$$1$$$ to $$$\frac{n-1}{2}$$$ using loop (or formula $$$\frac{n(n+1)(2n+1)}{6}$$$) and multiply the answer by $$$8$$$.
Time complexity: $$$O(n)$$$ or $$$O(1)$$$.
MUH and Sticks
Contest: Codeforces Round 269 (Div. 2)
Difficulty rating: 1100
Tags: implementation

Two polar bears Menshykov and Uslada from the St.Petersburg zoo and elephant Horace from the Kiev zoo got six sticks to play with and assess the animals' creativity. Menshykov, Uslada and Horace decided to make either an elephant or a bear from those sticks. They can make an animal from sticks in the following way:

- Four sticks represent the animal's legs, these sticks should have the same length.
- Two remaining sticks represent the animal's head and body. The bear's head stick must be shorter than the body stick. The elephant, however, has a long trunk, so his head stick must be as long as the body stick. Note that there are no limits on the relations between the leg sticks and the head and body sticks.

Your task is to find out which animal can be made from the given stick set. The zoo keeper wants the sticks back after the game, so they must never be broken, even bears understand it.

Input format:
The single line contains six space-separated integers li (1 ≤ li ≤ 9) — the lengths of the six sticks. It is guaranteed that the input is such that you cannot make both animals from the sticks.

Output format:
If you can make a bear from the given set, print string "Bear" (without the quotes). If you can make an elephant, print string "Elephant" (wıthout the quotes). If you can make neither a bear nor an elephant, print string "Alien" (without the quotes).

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

Note:
If you're out of creative ideas, see instructions below which show how to make a bear and an elephant in the first two samples. The stick of length 2 is in red, the sticks of length 4 are in green, the sticks of length 5 are in blue.

Example input:
4 2 5 4 4 4

Example output:
Bear

Example input:
4 4 5 4 4 5

Example output:
Elephant

Editorial:
MUH and Important Things
Contest: Codeforces Round 269 (Div. 2)
Difficulty rating: 1300
Tags: implementation, sortings

It's time polar bears Menshykov and Uslada from the zoo of St. Petersburg and elephant Horace from the zoo of Kiev got down to business. In total, there are n tasks for the day and each animal should do each of these tasks. For each task, they have evaluated its difficulty. Also animals decided to do the tasks in order of their difficulty. Unfortunately, some tasks can have the same difficulty, so the order in which one can perform the tasks may vary.

Menshykov, Uslada and Horace ask you to deal with this nuisance and come up with individual plans for each of them. The plan is a sequence describing the order in which an animal should do all the n tasks. Besides, each of them wants to have its own unique plan. Therefore three plans must form three different sequences. You are to find the required plans, or otherwise deliver the sad news to them by stating that it is impossible to come up with three distinct plans for the given tasks.

Input format:
The first line contains integer n (1 ≤ n ≤ 2000) — the number of tasks. The second line contains n integers h1, h2, ..., hn (1 ≤ hi ≤ 2000), where hi is the difficulty of the i-th task. The larger number hi is, the more difficult the i-th task is.

Output format:
In the first line print "YES" (without the quotes), if it is possible to come up with three distinct plans of doing the tasks. Otherwise print in the first line "NO" (without the quotes). If three desired plans do exist, print in the second line n distinct integers that represent the numbers of the tasks in the order they are done according to the first plan. In the third and fourth line print two remaining plans in the same form.

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

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

Note:
In the first sample the difficulty of the tasks sets one limit: tasks 1 and 4 must be done before tasks 2 and 3. That gives the total of four possible sequences of doing tasks : [1, 4, 2, 3], [4, 1, 2, 3], [1, 4, 3, 2], [4, 1, 3, 2]. You can print any three of them in the answer.

In the second sample there are only two sequences of tasks that meet the conditions — [3, 1, 2, 4, 5] and [3, 1, 4, 2, 5]. Consequently, it is impossible to make three distinct sequences of tasks.

Example input:
4
1 3 3 1

Example output:
YES
1 4 2 3
4 1 2 3
4 1 3 2

Example input:
5
2 4 1 4 8

Example output:
NO

Editorial:
MUH and House of Cards
Contest: Codeforces Round 269 (Div. 2)
Difficulty rating: 1700
Tags: binary search, brute force, greedy, math

Polar bears Menshykov and Uslada from the zoo of St. Petersburg and elephant Horace from the zoo of Kiev decided to build a house of cards. For that they've already found a hefty deck of n playing cards. Let's describe the house they want to make:

1. The house consists of some non-zero number of floors.
2. Each floor consists of a non-zero number of rooms and the ceiling. A room is two cards that are leaned towards each other. The rooms are made in a row, each two adjoining rooms share a ceiling made by another card.
3. Each floor besides for the lowest one should contain less rooms than the floor below.

Please note that the house may end by the floor with more than one room, and in this case they also must be covered by the ceiling. Also, the number of rooms on the adjoining floors doesn't have to differ by one, the difference may be more.

While bears are practicing to put cards, Horace tries to figure out how many floors their house should consist of. The height of the house is the number of floors in it. It is possible that you can make a lot of different houses of different heights out of n cards. It seems that the elephant cannot solve this problem and he asks you to count the number of the distinct heights of the houses that they can make using exactly n cards.

Input format:
The single line contains integer n (1 ≤ n ≤ 1012) — the number of cards.

Output format:
Print the number of distinct heights that the houses made of exactly n cards can have.

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

Note:
In the first sample you can build only these two houses (remember, you must use all the cards):

Thus, 13 cards are enough only for two floor houses, so the answer is 1.

The six cards in the second sample are not enough to build any house.

Example input:
13

Example output:
1

Example input:
6

Example output:
0

Editorial:
MUH and Cube Walls
Contest: Codeforces Round 269 (Div. 2)
Difficulty rating: 1800
Tags: string suffix structures, strings

Polar bears Menshykov and Uslada from the zoo of St. Petersburg and elephant Horace from the zoo of Kiev got hold of lots of wooden cubes somewhere. They started making cube towers by placing the cubes one on top of the other. They defined multiple towers standing in a line as a wall. A wall can consist of towers of different heights.

Horace was the first to finish making his wall. He called his wall an elephant. The wall consists of w towers. The bears also finished making their wall but they didn't give it a name. Their wall consists of n towers. Horace looked at the bears' tower and wondered: in how many parts of the wall can he "see an elephant"? He can "see an elephant" on a segment of w contiguous towers if the heights of the towers on the segment match as a sequence the heights of the towers in Horace's wall. In order to see as many elephants as possible, Horace can raise and lower his wall. He even can lower the wall below the ground level (see the pictures to the samples for clarification).

Your task is to count the number of segments where Horace can "see an elephant".

Input format:
The first line contains two integers n and w (1 ≤ n, w ≤ 2·105) — the number of towers in the bears' and the elephant's walls correspondingly. The second line contains n integers ai (1 ≤ ai ≤ 109) — the heights of the towers in the bears' wall. The third line contains w integers bi (1 ≤ bi ≤ 109) — the heights of the towers in the elephant's wall.

Output format:
Print the number of segments in the bears' wall where Horace can "see an elephant".

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

Note:
The picture to the left shows Horace's wall from the sample, the picture to the right shows the bears' wall. The segments where Horace can "see an elephant" are in gray.

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

Example output:
2

Editorial:
MUH and Lots and Lots of Segments
Contest: Codeforces Round 269 (Div. 2)
Difficulty rating: 2700
Tags: data structures, dsu

Polar bears Menshykov and Uslada from the zoo of St. Petersburg and elephant Horace from the zoo of Kiev decided to do some painting. As they were trying to create their first masterpiece, they made a draft on a piece of paper. The draft consists of n segments. Each segment was either horizontal or vertical. Now the friends want to simplify the draft by deleting some segments or parts of segments so that the final masterpiece meets three conditions:

1. Horace wants to be able to paint the whole picture in one stroke: by putting the brush on the paper and never taking it off until the picture is ready. The brush can paint the same place multiple times. That's why all the remaining segments must form a single connected shape.
2. Menshykov wants the resulting shape to be simple. He defines a simple shape as a shape that doesn't contain any cycles.
3. Initially all the segment on the draft have integer startpoint and endpoint coordinates. Uslada doesn't like real coordinates and she wants this condition to be fulfilled after all the changes.

As in other parts the draft is already beautiful, the friends decided to delete such parts of the draft that the sum of lengths of the remaining segments is as large as possible. Your task is to count this maximum sum of the lengths that remain after all the extra segments are removed.

Input format:
The first line of the input contains integer n (1 ≤ n ≤ 2·105) — the number of segments on the draft. The next n lines contain four integers each: x1, y1, x2, y2 ( - 109 ≤ x1 ≤ x2 ≤ 109;  - 109 ≤ y1 ≤ y2 ≤ 109) — the two startpoint and the two endpoint coordinates of a segment. All segments are non-degenerative and either are strictly horizontal or strictly vertical.

No two horizontal segments share common points. No two vertical segments share common points.

Output format:
Print a single integer — the maximum sum of lengths for the remaining segments.

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

Note:
The shapes that you can get in the two given samples are:

In the first sample you need to delete any segment as the two segments together do not form a single connected shape.

In the second sample the initial segments form a cycle, there are four ways to break the cycle: delete the first, second or fourth segment altogether or delete the middle of the third segment. The last way is shown on the picture.

Example input:
2
0 0 0 1
1 0 1 1

Example output:
1

Example input:
4
0 0 1 0
0 0 0 1
1 -1 1 2
0 1 1 1

Example output:
5

Editorial:
Drazil and Date
Contest: Codeforces Round 292 (Div. 2)
Difficulty rating: 1000
Tags: math

Someday, Drazil wanted to go on date with Varda. Drazil and Varda live on Cartesian plane. Drazil's home is located in point (0, 0) and Varda's home is located in point (a, b). In each step, he can move in a unit distance in horizontal or vertical direction. In other words, from position (x, y) he can go to positions (x + 1, y), (x - 1, y), (x, y + 1) or (x, y - 1).

Unfortunately, Drazil doesn't have sense of direction. So he randomly chooses the direction he will go to in each step. He may accidentally return back to his house during his travel. Drazil may even not notice that he has arrived to (a, b) and continue travelling.

Luckily, Drazil arrived to the position (a, b) successfully. Drazil said to Varda: "It took me exactly s steps to travel from my house to yours". But Varda is confused about his words, she is not sure that it is possible to get from (0, 0) to (a, b) in exactly s steps. Can you find out if it is possible for Varda?

Input format:
You are given three integers a, b, and s ( - 109 ≤ a, b ≤ 109, 1 ≤ s ≤ 2·109) in a single line.

Output format:
If you think Drazil made a mistake and it is impossible to take exactly s steps and get from his home to Varda's home, print "No" (without quotes).

Otherwise, print "Yes".

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

Note:
In fourth sample case one possible route is: $$(0,0)\longrightarrow(0,1)\longrightarrow(0,0)$$.

Example input:
5 5 11

Example output:
No

Example input:
10 15 25

Example output:
Yes

Editorial:
Drazil and His Happy Friends
Contest: Codeforces Round 292 (Div. 2)
Difficulty rating: 1300
Tags: brute force, dsu, meet-in-the-middle, number theory

Drazil has many friends. Some of them are happy and some of them are unhappy. Drazil wants to make all his friends become happy. So he invented the following plan.

There are n boys and m girls among his friends. Let's number them from 0 to n - 1 and 0 to m - 1 separately. In i-th day, Drazil invites $$(i \bmod n)$$-th boy and $$(i \bmod m)$$-th girl to have dinner together (as Drazil is programmer, i starts from 0). If one of those two people is happy, the other one will also become happy. Otherwise, those two people remain in their states. Once a person becomes happy (or if he/she was happy originally), he stays happy forever.

Drazil wants to know whether he can use this plan to make all his friends become happy at some moment.

Input format:
The first line contains two integer n and m (1 ≤ n, m ≤ 100).

The second line contains integer b (0 ≤ b ≤ n), denoting the number of happy boys among friends of Drazil, and then follow b distinct integers x1, x2, ..., xb (0 ≤ xi < n), denoting the list of indices of happy boys.

The third line conatins integer g (0 ≤ g ≤ m), denoting the number of happy girls among friends of Drazil, and then follow g distinct integers y1, y2, ... , yg (0 ≤ yj < m), denoting the list of indices of happy girls.

It is guaranteed that there is at least one person that is unhappy among his friends.

Output format:
If Drazil can make all his friends become happy by this plan, print "Yes". Otherwise, print "No".

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

Note:
By $$i \bmod k$$ we define the remainder of integer division of i by k.

In first sample case:

- On the 0-th day, Drazil invites 0-th boy and 0-th girl. Because 0-th girl is happy at the beginning, 0-th boy become happy at this day.
- On the 1-st day, Drazil invites 1-st boy and 1-st girl. They are both unhappy, so nothing changes at this day.
- On the 2-nd day, Drazil invites 0-th boy and 2-nd girl. Because 0-th boy is already happy he makes 2-nd girl become happy at this day.
- On the 3-rd day, Drazil invites 1-st boy and 0-th girl. 0-th girl is happy, so she makes 1-st boy happy.
- On the 4-th day, Drazil invites 0-th boy and 1-st girl. 0-th boy is happy, so he makes the 1-st girl happy. So, all friends become happy at this moment.

Example input:
2 3
0
1 0

Example output:
Yes

Example input:
2 4
1 0
1 2

Example output:
No

Editorial:
Drazil and Factorial
Contest: Codeforces Round 292 (Div. 2)
Difficulty rating: 1400
Tags: greedy, math, sortings

Drazil is playing a math game with Varda.

Let's define $$\mathbf{F}(x)$$ for positive integer x as a product of factorials of its digits. For example, $$F(135) = 1! * 3! * 5! = 720$$.

First, they choose a decimal number a consisting of n digits that contains at least one digit larger than 1. This number may possibly start with leading zeroes. Then they should find maximum positive number x satisfying following two conditions:

1. x doesn't contain neither digit 0 nor digit 1.

2. $$\mathbf{F}(x)$$ = $$\mathbf{F}(a)$$.

Help friends find such number.

Input format:
The first line contains an integer n (1 ≤ n ≤ 15) — the number of digits in a.

The second line contains n digits of a. There is at least one digit in a that is larger than 1. Number a may possibly contain leading zeroes.

Output format:
Output a maximum possible integer satisfying the conditions above. There should be no zeroes and ones in this number decimal representation.

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

Note:
In the first case, $$F(1234) = 1! * 2! * 3! * 4! = 288 = F(3322)$$

Example input:
4
1234

Example output:
33222

Example input:
3
555

Example output:
555

Editorial:
Drazil and Tiles
Contest: Codeforces Round 292 (Div. 2)
Difficulty rating: 2000
Tags: constructive algorithms, greedy

Drazil created a following problem about putting 1 × 2 tiles into an n × m grid:

"There is a grid with some cells that are empty and some cells that are occupied. You should use 1 × 2 tiles to cover all empty cells and no two tiles should cover each other. And you should print a solution about how to do it."

But Drazil doesn't like to write special checking program for this task. His friend, Varda advised him: "how about asking contestant only to print the solution when it exists and it is unique? Otherwise contestant may print 'Not unique' ".

Drazil found that the constraints for this task may be much larger than for the original task!

Can you solve this new problem?

Note that you should print 'Not unique' either when there exists no solution or when there exists several different solutions for the original task.

Input format:
The first line contains two integers n and m (1 ≤ n, m ≤ 2000).

The following n lines describe the grid rows. Character '.' denotes an empty cell, and the character '*' denotes a cell that is occupied.

Output format:
If there is no solution or the solution is not unique, you should print the string "Not unique".

Otherwise you should print how to cover all empty cells with 1 × 2 tiles. Use characters "<>" to denote horizontal tiles and characters "^v" to denote vertical tiles. Refer to the sample test for the output format example.

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

Note:
In the first case, there are indeed two solutions:

and

so the answer is "Not unique".

Example input:
3 3
...
.*.
...

Example output:
Not unique

Example input:
4 4
..**
*...
*.**
....

Example output:
<>**
*^<>
*v**
<><>

Editorial:
Drazil and Park
Contest: Codeforces Round 292 (Div. 2)
Difficulty rating: 2300
Tags: data structures

Drazil is a monkey. He lives in a circular park. There are n trees around the park. The distance between the i-th tree and (i + 1)-st trees is di, the distance between the n-th tree and the first tree is dn. The height of the i-th tree is hi.

Drazil starts each day with the morning run. The morning run consists of the following steps:

- Drazil chooses two different trees
- He starts with climbing up the first tree
- Then he climbs down the first tree, runs around the park (in one of two possible directions) to the second tree, and climbs on it
- Then he finally climbs down the second tree.

But there are always children playing around some consecutive trees. Drazil can't stand children, so he can't choose the trees close to children. He even can't stay close to those trees.

If the two trees Drazil chooses are x-th and y-th, we can estimate the energy the morning run takes to him as 2(hx + hy) + dist(x, y). Since there are children on exactly one of two arcs connecting x and y, the distance dist(x, y) between trees x and y is uniquely defined.

Now, you know that on the i-th day children play between ai-th tree and bi-th tree. More formally, if ai ≤ bi, children play around the trees with indices from range [ai, bi], otherwise they play around the trees with indices from $${ \left[ a _ { i }, n \right] } \cup { \left[ 1, b _ { i } \right] }$$.

Please help Drazil to determine which two trees he should choose in order to consume the most energy (since he wants to become fit and cool-looking monkey) and report the resulting amount of energy for each day.

Input format:
The first line contains two integer n and m (3 ≤ n ≤ 105, 1 ≤ m ≤ 105), denoting number of trees and number of days, respectively.

The second line contains n integers d1, d2, ..., dn (1 ≤ di ≤ 109), the distances between consecutive trees.

The third line contains n integers h1, h2, ..., hn (1 ≤ hi ≤ 109), the heights of trees.

Each of following m lines contains two integers ai and bi (1 ≤ ai, bi ≤ n) describing each new day. There are always at least two different trees Drazil can choose that are not affected by children.

Output format:
For each day print the answer in a separate line.

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

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

Example output:
12
16
18

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

Example output:
17
22
11

Editorial: