1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Milutin's Plums
Contest: Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 1]
Difficulty rating: 2800
Tags: interactive

As you all know, the plum harvesting season is on! Little Milutin had his plums planted in an orchard that can be represented as an $$$n$$$ by $$$m$$$ matrix. While he was harvesting, he wrote the heights of all trees in a matrix of dimensions $$$n$$$ by $$$m$$$.

At night, when he has spare time, he likes to perform various statistics on his trees. This time, he is curious to find out the height of his lowest tree. So far, he has discovered some interesting properties of his orchard. There is one particular property that he thinks is useful for finding the tree with the smallest heigh.

Formally, let $$$L(i)$$$ be the leftmost tree with the smallest height in the $$$i$$$-th row of his orchard. He knows that $$$L(i) \le L(i+1)$$$ for all $$$1 \le i \le n - 1$$$. Moreover, if he takes a submatrix induced by any subset of rows and any subset of columns, $$$L(i) \le L(i+1)$$$ will hold for all $$$1 \le i \le n'-1$$$, where $$$n'$$$ is the number of rows in that submatrix.

Since the season is at its peak and he is short on time, he asks you to help him find the plum tree with minimal height.

Input format:
This problem is interactive.

The first line of input will contain two integers $$$n$$$ and $$$m$$$, representing the number of rows and the number of columns in Milutin's orchard. It is guaranteed that $$$1 \le n, m \le 10^6$$$.

The following lines will contain the answers to your queries.

Output format:
Once you know have found the minimum value $$$r$$$, you should print ! $$$r$$$ to the standard output.

Interaction format:
Your code is allowed to query for an entry $$$(i, j)$$$ of a matrix (i.e. get the height of the tree which is in the $$$i$$$-th row and $$$j$$$-th column). The query should be formatted as ? $$$i$$$ $$$j$$$, so that $$$1 \le i \le n$$$ and $$$1 \le j \le m$$$.

You may assume that the entries of the matrix will be integers between $$$1$$$ and $$$10^9$$$.

Your solution should use not more than $$$\mathbf{4 \cdot (n + m)}$$$ queries.

This is an interactive problem. You have to use a flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout), in Java — System.out.flush(), in Pascal — flush(output) and in Python — sys.stdout.flush().

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

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

BubbleSquare social network is celebrating $$$13^{th}$$$ anniversary and it is rewarding its members with special edition BubbleSquare tokens. Every member receives one personal token. Also, two additional tokens are awarded to each member for every friend they have on the network. Yet, there is a twist – everyone should end up with different number of tokens from all their friends. Each member may return one received token. Also, each two friends may agree to each return one or two tokens they have obtained on behalf of their friendship.

Input format:
First line of input contains two integer numbers $$$n$$$ and $$$k$$$ ($$$2$$$ $$$\leq$$$ $$$n$$$ $$$\leq$$$ $$$12500$$$, $$$1$$$ $$$\leq$$$ $$$k$$$ $$$\leq$$$ $$$1000000$$$) - number of members in network and number of friendships.

Next $$$k$$$ lines contain two integer numbers $$$a_i$$$ and $$$b_i$$$ ($$$1$$$ $$$\leq$$$ $$$a_i$$$, $$$b_i$$$ $$$\leq$$$ $$$n$$$, $$$a_i$$$ $$$\neq$$$ $$$b_i$$$) - meaning members $$$a_i$$$ and $$$b_i$$$ are friends.

Output format:
First line of output should specify the number of members who are keeping their personal token.

The second line should contain space separated list of members who are keeping their personal token.

Each of the following $$$k$$$ lines should contain three space separated numbers, representing friend pairs and number of tokens each of them gets on behalf of their friendship.

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

Note:
In the first test case, only the first member will keep its personal token and no tokens will be awarded for friendship between the first and the second member.

In the second test case, none of the members will keep their personal token. The first member will receive two tokens (for friendship with the third member), the second member will receive one token (for friendship with the third member) and the third member will receive three tokens (for friendships with the first and the second member).

Example input:
2 1
1 2

Example output:
1
1 
1 2 0

Example input:
3 3
1 2
1 3
2 3

Example output:
0
1 2 0
2 3 1
1 3 2

Editorial:
Battlefield
Contest: Codeforces Round 117 (Div. 2)
Difficulty rating: 2200
Tags: geometry, graphs, implementation, shortest paths

Vasya lagged behind at the University and got to the battlefield. Just joking! He's simply playing some computer game. The field is a flat platform with n trenches dug on it. The trenches are segments on a plane parallel to the coordinate axes. No two trenches intersect.

There is a huge enemy laser far away from Vasya. The laser charges for a seconds, and then shoots continuously for b seconds. Then, it charges for a seconds again. Then it shoots continuously for b seconds again and so on. Vasya knows numbers a and b. He also knows that while the laser is shooting, Vasya must be in the trench, but while the laser is charging, Vasya can safely move around the field. The main thing is to have time to hide in the trench before the shot. If Vasya reaches the trench exactly at the moment when the laser starts shooting, we believe that Vasya managed to hide. Coincidentally, the length of any trench in meters numerically does not exceed b.

Initially, Vasya is at point A. He needs to get to point B. Vasya moves at speed 1 meter per second in either direction. You can get in or out of the trench at any its point. Getting in or out of the trench takes no time. It is also possible to move in the trench, without leaving it.

What is the minimum time Vasya needs to get from point A to point B, if at the initial time the laser has just started charging? If Vasya cannot get from point A to point B, print -1. If Vasya reaches point B at the moment when the laser begins to shoot, it is believed that Vasya managed to reach point B.

Input format:
The first line contains two space-separated integers: a and b (1 ≤ a, b ≤ 1000), — the duration of charging and the duration of shooting, in seconds.

The second line contains four space-separated integers: Ax, Ay, Bx, By ( - 104 ≤ Ax, Ay, Bx, By ≤ 104) — the coordinates of points А and B. It is guaranteed that points A and B do not belong to any trench.

The third line contains a single integer: n (1 ≤ n ≤ 1000), — the number of trenches.

Each of the following n lines contains four space-separated integers: x1, y1, x2, y2 ( - 104 ≤ xi, yi ≤ 104) — the coordinates of ends of the corresponding trench.

All coordinates are given in meters. It is guaranteed that for any trench either x1 = x2, or y1 = y2. No two trenches intersect. The length of any trench in meters doesn't exceed b numerically.

Output format:
If Vasya can get from point A to point B, print the minimum time he will need for it. Otherwise, print number -1.

The answer will be considered correct if the absolute or relative error does not exceed 10 - 4

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

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

Example output:
19.0000000000

Example input:
5 10
0 0 10 10
1
5 0 5 9

Example output:
-1

Editorial:
Vasya's Calendar
Contest: Codeforces Round 117 (Div. 2)
Difficulty rating: 1000
Tags: implementation

Vasya lives in a strange world. The year has n months and the i-th month has ai days. Vasya got a New Year present — the clock that shows not only the time, but also the date.

The clock's face can display any number from 1 to d. It is guaranteed that ai ≤ d for all i from 1 to n. The clock does not keep information about the current month, so when a new day comes, it simply increases the current day number by one. The clock cannot display number d + 1, so after day number d it shows day 1 (the current day counter resets). The mechanism of the clock allows you to increase the day number by one manually. When you execute this operation, day d is also followed by day 1.

Vasya begins each day checking the day number on the clock. If the day number on the clock does not match the actual day number in the current month, then Vasya manually increases it by one. Vasya is persistent and repeats this operation until the day number on the clock matches the actual number of the current day in the current month.

A year passed and Vasya wonders how many times he manually increased the day number by one, from the first day of the first month to the last day of the n-th month inclusive, considering that on the first day of the first month the clock display showed day 1.

Input format:
The first line contains the single number d — the maximum number of the day that Vasya's clock can show (1 ≤ d ≤ 106).

The second line contains a single integer n — the number of months in the year (1 ≤ n ≤ 2000).

The third line contains n space-separated integers: ai (1 ≤ ai ≤ d) — the number of days in each month in the order in which they follow, starting from the first one.

Output format:
Print a single number — the number of times Vasya manually increased the day number by one throughout the last year.

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

Note:
In the first sample the situation is like this:

- Day 1. Month 1. The clock shows 1. Vasya changes nothing.
- Day 2. Month 1. The clock shows 2. Vasya changes nothing.
- Day 1. Month 2. The clock shows 3. Vasya manually increases the day number by 1. After that the clock shows 4. Vasya increases the day number by 1 manually. After that the clock shows 1.
- Day 2. Month 2. The clock shows 2. Vasya changes nothing.

Example input:
4
2
2 2

Example output:
2

Example input:
5
3
3 4 3

Example output:
3

Editorial:
Optimal Sum
Contest: Codeforces Round 117 (Div. 2)
Difficulty rating: 2000
Tags: data structures, greedy

And here goes another problem on arrays. You are given positive integer len and array a which consists of n integers a1, a2, ..., an. Let's introduce two characteristics for the given array.

- Let's consider an arbitrary interval of the array with length len, starting in position i. Value $$\text{modSum}(i, \text{len}) = \left| \sum_{j=i}^{i+\text{len}-1} a_j \right|$$, is the modular sum on the chosen interval. In other words, the modular sum is the sum of integers on the chosen interval with length len, taken in its absolute value.
- Value $$\max_{1 \leq i \leq n - len + 1} modSum(i, len)$$ is the optimal sum of the array. In other words, the optimal sum of an array is the maximum of all modular sums on various intervals of array with length len.

Your task is to calculate the optimal sum of the given array a. However, before you do the calculations, you are allowed to produce no more than k consecutive operations of the following form with this array: one operation means taking an arbitrary number from array ai and multiply it by -1. In other words, no more than k times you are allowed to take an arbitrary number ai from the array and replace it with  - ai. Each number of the array is allowed to choose an arbitrary number of times.

Your task is to calculate the maximum possible optimal sum of the array after at most k operations described above are completed.

Input format:
The first line contains two integers n, len (1 ≤ len ≤ n ≤ 105) — the number of elements in the array and the length of the chosen subinterval of the array, correspondingly.

The second line contains a sequence consisting of n integers a1, a2, ..., an (|ai| ≤ 109) — the original array.

The third line contains a single integer k (0 ≤ k ≤ n) — the maximum allowed number of operations.

All numbers in lines are separated by a single space.

Output format:
In a single line print the maximum possible optimal sum after no more than k acceptable operations are fulfilled.

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

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

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

Example output:
10

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

Example output:
14

Editorial:
Common Divisors
Contest: Codeforces Round 117 (Div. 2)
Difficulty rating: 1400
Tags: brute force, hashing, implementation, math, strings

Vasya has recently learned at school what a number's divisor is and decided to determine a string's divisor. Here is what he came up with.

String a is the divisor of string b if and only if there exists a positive integer x such that if we write out string a consecutively x times, we get string b. For example, string "abab" has two divisors — "ab" and "abab".

Now Vasya wants to write a program that calculates the number of common divisors of two strings. Please help him.

Input format:
The first input line contains a non-empty string s1.

The second input line contains a non-empty string s2.

Lengths of strings s1 and s2 are positive and do not exceed 105. The strings only consist of lowercase Latin letters.

Output format:
Print the number of common divisors of strings s1 and s2.

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

Note:
In first sample the common divisors are strings "abcd" and "abcdabcd".

In the second sample the common divisor is a single string "a". String "aa" isn't included in the answer as it isn't a divisor of string "aaa".

Example input:
abcdabcd
abcdabcdabcdabcd

Example output:
2

Example input:
aaa
aa

Example output:
1

Editorial:
Wooden Fence
Contest: Codeforces Round 117 (Div. 2)
Difficulty rating: 1800
Tags: dp

Vasya has recently bought some land and decided to surround it with a wooden fence.

He went to a company called "Wooden board" that produces wooden boards for fences. Vasya read in the catalog of products that the company has at its disposal n different types of wood. The company uses the i-th type of wood to produce a board of this type that is a rectangular ai by bi block.

Vasya decided to order boards in this company and build a fence from them. It turned out that the storehouse of the company is so large that Vasya can order arbitrary number of boards of every type. Note that Vasya is allowed to turn the boards as he builds the fence. However, Vasya cannot turn square boards.

Vasya is required to construct a fence of length l, however, an arbitrary fence won't do. Vasya wants his fence to look beautiful. We'll say that a fence is beautiful if and only if the following two conditions are fulfilled:

- there are no two successive boards of the same type
- the first board of the fence has an arbitrary length, and the length of each subsequent board equals the width of the previous one

In other words, the fence is considered beautiful, if the type of the i-th board in the fence is different from the i - 1-th board's type; besides, the i-th board's length is equal to the i - 1-th board's width (for all i, starting from 2).

Now Vasya wonders, how many variants of arranging a fence for his land exist. Your task is to count the number of different beautiful fences of length l.

Two fences will be considered the same if the corresponding sequences of fence boards types and rotations are the same, otherwise the fences are different. Since the sought number can be large enough, you need to calculate the answer modulo 1000000007 (109 + 7).

Input format:
The first line contains two integers n and l (1 ≤ n ≤ 100, 1 ≤ l ≤ 3000) — the number of different board types and the fence length, correspondingly. Next n lines contain descriptions of board types: the i-th line contains two integers ai and bi (1 ≤ ai, bi ≤ 100) — the sizes of the board of the i-th type. All numbers on the lines are separated by spaces.

Output format:
Print a single integer — the sought number of variants modulo 1000000007 (109 + 7).

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

Note:
In the first sample there are exactly two variants of arranging a beautiful fence of length 3:

- As the first fence board use the board of the first type of length 1 and width 2. As the second board use board of the second type of length 2 and width 3.
- Use one board of the second type after you turn it. That makes its length equal 3, and width — 2.

Example input:
2 3
1 2
2 3

Example output:
2

Example input:
1 2
2 2

Example output:
1

Editorial:
Balanced Shuffle (Easy)
Contest: Helvetic Coding Contest 2024 online mirror (teams allowed, unrated)
Difficulty rating: 1000
Tags: implementation, sortings

A parentheses sequence is a string consisting of characters "(" and ")", for example "(()((".

A balanced parentheses sequence is a parentheses sequence which can become a valid mathematical expression after inserting numbers and operations into it, for example "(()(()))".

The balance of a parentheses sequence is defined as the number of opening parentheses "(" minus the number of closing parentheses ")". For example, the balance of the sequence "(()((" is 3.

A balanced parentheses sequence can also be defined as a parentheses sequence with balance 0 such that each of its prefixes has a non-negative balance.

We define the balanced shuffle operation that takes a parentheses sequence and returns a parentheses sequence as follows: first, for every character of the input sequence, we compute the balance of the prefix of the sequence before that character and write those down in a table together with the positions of the characters in the input sequence, for example:

Prefix balance01212321Position12345678Character(()(()))

Then, we sort the columns of this table in increasing order of prefix balance, breaking ties in decreasing order of position. In the above example, we get:

Prefix balance01112223Position18427536Character()(()())

The last row of this table forms another parentheses sequence, in this case "()(()())". This sequence is called the result of applying the balanced shuffle operation to the input sequence, or in short just the balanced shuffle of the input sequence.

You are given a balanced parentheses sequence. Print its balanced shuffle.

Input format:
The only line of input contains a string $$$s$$$ consisting only of characters "(" and ")". This string is guaranteed to be a non-empty balanced parentheses sequence with its length not exceeding $$$500\,000$$$.

Output format:
Print the parentheses sequence $$$t$$$ — the balanced shuffle of $$$s$$$.

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

Example input:
(()(()))

Example output:
()(()())

Editorial:
The problem statement describes exactly what needs to be done, so we just need to implement it carefully, using a $$$O(n\log n)$$$ sorting algorithm from the standard library.
If you're using Python for this problem, the time limit can be a bit tight so you might need to optimize a bit. For example, tuples are much faster than custom classes in Python, so the following passes in 0.5s:
Game on Tree (Easy)
Contest: Helvetic Coding Contest 2024 online mirror (teams allowed, unrated)
Difficulty rating: 1400
Tags: games

This is the easy version of the problem. The difference in this version is that $$$t=1$$$ and we work on an array-like tree.

Ron and Hermione are playing a game on a tree of $$$n$$$ nodes that are initially inactive. This tree is special because it has exactly two leaves. It can thus be seen as an array. The game consists of $$$t$$$ rounds, each of which starts with a stone on exactly one node, which is considered as activated. A move consists of picking an inactive neighbor of the node with a stone on it and moving the stone there (thus activating this neighbor). Ron makes the first move, after which he alternates with Hermione until no valid move is available. The player that cannot make a move loses the round. If both players play optimally, who wins each round of this game?

Note that all the rounds are played with the same tree; only the starting node changes. Moreover, after each round, all active nodes are considered inactive again.

Input format:
The first line contains integers $$$n$$$ ($$$2 \leq n \leq 2\times 10^5$$$), $$$t$$$ ($$$t=1$$$), the number of nodes in the tree and the number of rounds, respectively.

The next $$$n-1$$$ lines contain two integers $$$1 \leq u, v \leq n$$$ each, corresponding to an edge of the tree. It is guaranteed that the tree has exactly two leaves.

The next line contains $$$t$$$ integers $$$1 \leq u_1 , \dots, u_t \leq n$$$, corresponding to the node where the stone is initially put.

Output format:
The output consists of $$$t=1$$$ line which is either "Ron" or "Hermione".

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

Example input:
3 1
2 3
3 1
3

Example output:
Ron

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

Example output:
Hermione

Editorial:
We are given a linked list with an initial coin at index $$$1 \leq i \leq n$$$. There are $$$i-1$$$ nodes to its left and $$$n-i$$$ nodes to its right. Note that after the first move, all the remaining moves are fixed since there will be exactly one inactive neighbor.  If one of $$$i-1, n-i$$$ is odd, Ron should move to the corresponding node as there will be an even number left thus guaranteeing a victory for Ron. Otherwise, Hermione is guaranteed to win.
Game on Tree (Medium)
Contest: Helvetic Coding Contest 2024 online mirror (teams allowed, unrated)
Difficulty rating: 1700
Tags: dfs and similar, dp, games, trees

This is the medium version of the problem. The difference in this version is that $$$t=1$$$ and we work on trees.

Ron and Hermione are playing a game on a tree of $$$n$$$ nodes that are initially inactive. The game consists of $$$t$$$ rounds, each of which starts with a stone on exactly one node, which is considered as activated. A move consists of picking an inactive neighbor of the node with a stone on it and moving the stone there (thus activating this neighbor). Ron makes the first move, after which he alternates with Hermione until no valid move is available. The player that cannot make a move loses the round. If both players play optimally, who wins each round of this game?

Note that all the rounds are played with the same tree; only the starting node changes. Moreover, after each round, all active nodes are considered inactive again.

Input format:
The first line contains integers $$$n$$$ ($$$2 \leq n \leq 2\times 10^5$$$), $$$t$$$ ($$$t=1$$$), the number of nodes in the tree and the number of rounds, respectively.

The next $$$n-1$$$ lines contain two integers $$$1 \leq u, v \leq n$$$ each, corresponding to an edge of the tree.

The next line contains $$$t$$$ integers $$$1 \leq u_1 , \dots, u_t \leq n$$$, corresponding to the node where the stone is initially put.

Output format:
The output consists of $$$t=1$$$ line which is either "Ron" or "Hermione".

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

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

Example output:
Ron

Editorial:
Let's root the tree at node $$$u_1$$$ (the start node). By doing so, we guarantee that if the coin is at node $$$v$$$, the parent of $$$v$$$ is already active and thus we can only go down in the tree. This means that each subtree can be seen as its own independent game. So, each node is either a winning or losing position (w.r.t. to the player whose turn is next). We will find recursively whether $$$u_1$$$ corresponds to a winning game for Ron.  If some child of a node $$$v$$$ is a losing position, then the current player should move the coin to that child to guarantee a win. If all children are winning positions, the current player will surely lose. So, $$$v$$$ is a winning position iff it has a child that is a losing position. Note that the leaves are losing positions.  This is solved in $$$O(n)$$$ time.