2100

标签：number will each such array 2100 he

Max Median

You are a given an array \(a\) of length \(n\). Find a subarray \(a[l..r]\) with length at least \(k\) with the largest median.

A median in an array of length \(n\) is an element which occupies position number \(\lfloor \frac{n + 1}{2} \rfloor\) after we sort the elements in non-decreasing order. For example: \(median([1, 2, 3, 4]) = 2\), \(median([3, 2, 1]) = 2\), \(median([2, 1, 2, 1]) = 1\).

Subarray \(a[l..r]\) is a contiguous part of the array \(a\), i. e. the array \(a_l,a_{l+1},\ldots,a_r\) for some \(1 \leq l \leq r \leq n\), its length is \(r - l + 1\).

Zero Remainder Sum

You are given a matrix \(a\) of size \(n \times m\) consisting of integers.

You can choose no more than \(\left\lfloor\frac{m}{2}\right\rfloor\) elements in each row. Your task is to choose these elements in such a way that their sum is divisible by \(k\) and this sum is the maximum.

In other words, you can choose no more than a half (rounded down) of elements in each row, you have to find the maximum sum of these elements divisible by \(k\).

Note that you can choose zero elements (and the sum of such set is \(0\)).

Array Shrinking

You are given an array \(a_1, a_2, \dots, a_n\). You can perform the following operation any number of times:

• Choose a pair of two neighboring equal elements \(a_i = a_{i + 1}\) (if there is at least one such pair).
• Replace them by one element with value \(a_i + 1\).

After each such operation, the length of the array will decrease by one (and elements are renumerated accordingly). What is the minimum possible length of the array \(a\) you can get?

The Number of Pairs

You are given three positive (greater than zero) integers \(c\), \(d\) and \(x\).

You have to find the number of pairs of positive integers \((a, b)\) such that equality \(c \cdot lcm(a, b) - d \cdot gcd(a, b) = x\) holds. Where \(lcm(a, b)\) is the least common multiple of \(a\) and \(b\) and \(gcd(a, b)\) is the greatest common divisor of \(a\) and \(b\).

Ancient Berland Circus

Nowadays all circuses in Berland have a round arena with diameter 13 meters, but in the past things were different.

In Ancient Berland arenas in circuses were shaped as a regular (equiangular) polygon, the size and the number of angles could vary from one circus to another. In each corner of the arena there was a special pillar, and the rope strung between the pillars marked the arena edges.

Recently the scientists from Berland have discovered the remains of the ancient circus arena. They found only three pillars, the others were destroyed by the time.

You are given the coordinates of these three pillars. Find out what is the smallest area that the arena could have.

Omkar and Circle

Danny, the local Math Maniac, is fascinated by circles, Omkar's most recent creation. Help him solve this circle problem!

You are given \(n\) nonnegative integers \(a_1, a_2, \dots, a_n\) arranged in a circle, where \(n\) must be odd (ie. \(n-1\) is divisible by \(2\)). Formally, for all \(i\) such that \(2 \leq i \leq n\), the elements \(a_{i - 1}\) and \(a_i\) are considered to be adjacent, and \(a_n\) and \(a_1\) are also considered to be adjacent. In one operation, you pick a number on the circle, replace it with the sum of the two elements adjacent to it, and then delete the two adjacent elements from the circle. This is repeated until only one number remains in the circle, which we call the circular value.

Help Danny find the maximum possible circular value after some sequences of operations.

Coloring Edges

You are given a directed graph with \(n\) vertices and \(m\) directed edges without self-loops or multiple edges.

Let's denote the \(k\)-coloring of a digraph as following: you color each edge in one of \(k\) colors. The \(k\)-coloring is good if and only if there no cycle formed by edges of same color.

Find a good \(k\)-coloring of given digraph with minimum possible \(k\).

Xor-Paths

There is a rectangular grid of size \(n \times m\). Each cell has a number written on it; the number on the cell (\(i, j\)) is \(a_{i, j}\). Your task is to calculate the number of paths from the upper-left cell (\(1, 1\)) to the bottom-right cell (\(n, m\)) meeting the following constraints:

• You can move to the right or to the bottom only. Formally, from the cell (\(i, j\)) you may move to the cell (\(i, j + 1\)) or to the cell (\(i + 1, j\)). The target cell can't be outside of the grid.
• The xor of all the numbers on the path from the cell (\(1, 1\)) to the cell (\(n, m\)) must be equal to \(k\) (xor operation is the bitwise exclusive OR, it is represented as '^' in Java or C++ and "xor" in Pascal).

Find the number of such paths in the given grid.

Weights Distributing

You are given an undirected unweighted graph consisting of \(n\) vertices and \(m\) edges (which represents the map of Bertown) and the array of prices \(p\) of length \(m\). It is guaranteed that there is a path between each pair of vertices (districts).

Mike has planned a trip from the vertex (district) \(a\) to the vertex (district) \(b\) and then from the vertex (district) \(b\) to the vertex (district) \(c\). He can visit the same district twice or more. But there is one issue: authorities of the city want to set a price for using the road so if someone goes along the road then he should pay the price corresponding to this road (he pays each time he goes along the road). The list of prices that will be used \(p\) is ready and they just want to distribute it between all roads in the town in such a way that each price from the array corresponds to exactly one road.

You are a good friend of Mike (and suddenly a mayor of Bertown) and want to help him to make his trip as cheap as possible. So, your task is to distribute prices between roads in such a way that if Mike chooses the optimal path then the price of the trip is the minimum possible. Note that you cannot rearrange prices after the start of the trip.

You have to answer \(t\) independent test cases.

Remainder Problem

You are given an array \(a\) consisting of \(500000\) integers (numbered from \(1\) to \(500000\)). Initially all elements of \(a\) are zero.

You have to process two types of queries to this array:

• \(1\) \(x\) \(y\) — increase \(a_x\) by \(y\);
• \(2\) \(x\) \(y\) — compute \(\sum\limits_{i \in R(x, y)} a_i\), where \(R(x, y)\) is the set of all integers from \(1\) to \(500000\) which have remainder \(y\) modulo \(x\).

Can you process all the queries?

Restorer Distance

You have to restore the wall. The wall consists of \(N\) pillars of bricks, the height of the \(i\)-th pillar is initially equal to \(h_{i}\), the height is measured in number of bricks. After the restoration all the \(N\) pillars should have equal heights.

You are allowed the following operations:

• put a brick on top of one pillar, the cost of this operation is \(A\);
• remove a brick from the top of one non-empty pillar, the cost of this operation is \(R\);
• move a brick from the top of one non-empty pillar to the top of another pillar, the cost of this operation is \(M\).

You cannot create additional pillars or ignore some of pre-existing pillars even if their height becomes \(0\).

What is the minimal total cost of restoration, in other words, what is the minimal total cost to make all the pillars of equal height?

GCD of an Array

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

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

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

Binary Subsequence Rotation

Naman has two binary strings \(s\) and \(t\) of length \(n\) (a binary string is a string which only consists of the characters "0" and "1"). He wants to convert \(s\) into \(t\) using the following operation as few times as possible.

In one operation, he can choose any subsequence of \(s\) and rotate it clockwise once.

For example, if \(s = 1\textbf{1}101\textbf{00}\), he can choose a subsequence corresponding to indices (\(1\)-based) \(\{2, 6, 7 \}\) and rotate them clockwise. The resulting string would then be \(s = 1\textbf{0}101\textbf{10}\).

A string \(a\) is said to be a subsequence of string \(b\) if \(a\) can be obtained from \(b\) by deleting some characters without changing the ordering of the remaining characters.

To perform a clockwise rotation on a sequence \(c\) of size \(k\) is to perform an operation which sets \(c_1:=c_k, c_2:=c_1, c_3:=c_2, \ldots, c_k:=c_{k-1}\) simultaneously.

Determine the minimum number of operations Naman has to perform to convert \(s\) into \(t\) or say that it is impossible.

Binary Median

Consider all binary strings of length \(m\) (\(1 \le m \le 60\)). A binary string is a string that consists of the characters 0 and 1 only. For example, 0110 is a binary string, and 012aba is not. Obviously, there are exactly \(2^m\) such strings in total.

The string \(s\) is lexicographically smaller than the string \(t\) (both have the same length \(m\)) if in the first position \(i\) from the left in which they differ, we have \(s[i] < t[i]\). This is exactly the way strings are compared in dictionaries and in most modern programming languages when comparing them in a standard way. For example, the string 01011 is lexicographically smaller than the string 01100, because the first two characters are the same, and the third character in the first string is less than that in the second.

We remove from this set \(n\) (\(1 \le n \le \min(2^m-1, 100)\)) distinct binary strings \(a_1, a_2, \ldots, a_n\), each of length \(m\). Thus, the set will have \(k=2^m-n\) strings. Sort all strings of the resulting set in lexicographical ascending order (as in the dictionary).

We number all the strings after sorting from \(0\) to \(k-1\). Print the string whose index is \(\lfloor \frac{k-1}{2} \rfloor\) (such an element is called median), where \(\lfloor x \rfloor\) is the rounding of the number down to the nearest integer.

For example, if \(n=3\), \(m=3\) and $a=[\(010, 111, 001\)]$, then after removing the strings \(a_i\) and sorting, the result will take the form: $[\(000, 011, 100, 101, 110\)]$. Thus, the desired median is 100.

Gift Set

Polycarp has \(x\) of red and \(y\) of blue candies. Using them, he wants to make gift sets. Each gift set contains either \(a\) red candies and \(b\) blue candies, or \(a\) blue candies and \(b\) red candies. Any candy can belong to at most one gift set.

Help Polycarp to find the largest number of gift sets he can create.

For example, if \(x = 10\), \(y = 12\), \(a = 5\), and \(b = 2\), then Polycarp can make three gift sets:

• In the first set there will be \(5\) red candies and \(2\) blue candies;
• In the second set there will be \(5\) blue candies and \(2\) red candies;
• In the third set will be \(5\) blue candies and \(2\) red candies.

Note that in this example there is one red candy that Polycarp does not use in any gift set.

We Need More Bosses

Your friend is developing a computer game. He has already decided how the game world should look like — it should consist of \(n\) locations connected by \(m\) two-way passages. The passages are designed in such a way that it should be possible to get from any location to any other location.

Of course, some passages should be guarded by the monsters (if you just can go everywhere without any difficulties, then it's not fun, right?). Some crucial passages will be guarded by really fearsome monsters, requiring the hero to prepare for battle and designing his own tactics of defeating them (commonly these kinds of monsters are called bosses). And your friend wants you to help him place these bosses.

The game will start in location \(s\) and end in location \(t\), but these locations are not chosen yet. After choosing these locations, your friend will place a boss in each passage such that it is impossible to get from \(s\) to \(t\) without using this passage. Your friend wants to place as much bosses as possible (because more challenges means more fun, right?), so he asks you to help him determine the maximum possible number of bosses, considering that any location can be chosen as \(s\) or as \(t\).

Swaps Again

Ayush, Ashish and Vivek are busy preparing a new problem for the next Codeforces round and need help checking if their test cases are valid.

Each test case consists of an integer \(n\) and two arrays \(a\) and \(b\), of size \(n\). If after some (possibly zero) operations described below, array \(a\) can be transformed into array \(b\), the input is said to be valid. Otherwise, it is invalid.

An operation on array \(a\) is:

• select an integer \(k\) \((1 \le k \le \lfloor\frac{n}{2}\rfloor)\)
• swap the prefix of length \(k\) with the suffix of length \(k\)

For example, if array \(a\) initially is \(\{1, 2, 3, 4, 5, 6\}\), after performing an operation with \(k = 2\), it is transformed into \(\{5, 6, 3, 4, 1, 2\}\).

Given the set of test cases, help them determine if each one is valid or invalid.

Subsequences of Length Two

You are given two strings \(s\) and \(t\) consisting of lowercase Latin letters. The length of \(t\) is \(2\) (i.e. this string consists only of two characters).

In one move, you can choose any character of \(s\) and replace it with any lowercase Latin letter. More formally, you choose some \(i\) and replace \(s_i\) (the character at the position \(i\)) with some character from 'a' to 'z'.

You want to do no more than \(k\) replacements in such a way that maximizes the number of occurrences of \(t\) in \(s\) as a subsequence.

Recall that a subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

Trash Problem

Vova decided to clean his room. The room can be represented as the coordinate axis \(OX\). There are \(n\) piles of trash in the room, coordinate of the \(i\)-th pile is the integer \(p_i\). All piles have different coordinates.

Let's define a total cleanup as the following process. The goal of this process is to collect all the piles in no more than two different \(x\) coordinates. To achieve this goal, Vova can do several (possibly, zero) moves. During one move, he can choose some \(x\) and move all piles from \(x\) to \(x+1\) or \(x-1\) using his broom. Note that he can't choose how many piles he will move.

Also, there are two types of queries:

• \(0\) \(x\) — remove a pile of trash from the coordinate \(x\). It is guaranteed that there is a pile in the coordinate \(x\) at this moment.
• \(1\) \(x\) — add a pile of trash to the coordinate \(x\). It is guaranteed that there is no pile in the coordinate \(x\) at this moment.

Note that it is possible that there are zero piles of trash in the room at some moment.

Vova wants to know the minimum number of moves he can spend if he wants to do a total cleanup before any queries. He also wants to know this number of moves after applying each query. Queries are applied in the given order. Note that the total cleanup doesn't actually happen and doesn't change the state of piles. It is only used to calculate the number of moves.

For better understanding, please read the Notes section below to see an explanation for the first example.

Reducing Delivery Cost

You are a mayor of Berlyatov. There are \(n\) districts and \(m\) two-way roads between them. The \(i\)-th road connects districts \(x_i\) and \(y_i\). The cost of travelling along this road is \(w_i\). There is some path between each pair of districts, so the city is connected.

There are \(k\) delivery routes in Berlyatov. The \(i\)-th route is going from the district \(a_i\) to the district \(b_i\). There is one courier on each route and the courier will always choose the cheapest (minimum by total cost) path from the district \(a_i\) to the district \(b_i\) to deliver products.

The route can go from the district to itself, some couriers routes can coincide (and you have to count them independently).

You can make at most one road to have cost zero (i.e. you choose at most one road and change its cost with \(0\)).

Let \(d(x, y)\) be the cheapest cost of travel between districts \(x\) and \(y\).

Your task is to find the minimum total courier routes cost you can achieve, if you optimally select the some road and change its cost with \(0\). In other words, you have to find the minimum possible value of \(\sum\limits_{i = 1}^{k} d(a_i, b_i)\) after applying the operation described above optimally.

Cut

This time Baby Ehab will only cut and not stick. He starts with a piece of paper with an array \(a\) of length \(n\) written on it, and then he does the following:

• he picks a range \((l, r)\) and cuts the subsegment \(a_l, a_{l + 1}, \ldots, a_r\) out, removing the rest of the array.
• he then cuts this range into multiple subranges.
• to add a number theory spice to it, he requires that the elements of every subrange must have their product equal to their least common multiple (LCM).

Formally, he partitions the elements of \(a_l, a_{l + 1}, \ldots, a_r\) into contiguous subarrays such that the product of every subarray is equal to its LCM. Now, for \(q\) independent ranges \((l, r)\), tell Baby Ehab the minimum number of subarrays he needs.

Ehab's Last Corollary

Given a connected undirected graph with \(n\) vertices and an integer \(k\), you have to either:

• either find an independent set that has exactly \(\lceil\frac{k}{2}\rceil\) vertices.
• or find a simple cycle of length at most \(k\).

An independent set is a set of vertices such that no two of them are connected by an edge. A simple cycle is a cycle that doesn't contain any vertex twice.

I have a proof that for any input you can always solve at least one of these problems, but it's left as an exercise for the reader.

Present

Catherine received an array of integers as a gift for March 8. Eventually she grew bored with it, and she started calculated various useless characteristics for it. She succeeded to do it for each one she came up with. But when she came up with another one — xor of all pairwise sums of elements in the array, she realized that she couldn't compute it for a very large array, thus she asked for your help. Can you do it? Formally, you need to compute

\[(a_1 + a_2) \oplus (a_1 + a_3) \oplus \ldots \oplus (a_1 + a_n) \\ \oplus (a_2 + a_3) \oplus \ldots \oplus (a_2 + a_n) \\ \ldots \\ \oplus (a_{n-1} + a_n) \\ \]

Here \(x \oplus y\) is a bitwise XOR operation (i.e. \(x\) ^ \(y\) in many modern programming languages). You can read about it in Wikipedia: https://en.wikipedia.org/wiki/Exclusive_or#Bitwise_operation.

Segment Intersections

You are given two lists of segments \([al_1, ar_1], [al_2, ar_2], \dots, [al_n, ar_n]\) and \([bl_1, br_1], [bl_2, br_2], \dots, [bl_n, br_n]\).

Initially, all segments \([al_i, ar_i]\) are equal to \([l_1, r_1]\) and all segments \([bl_i, br_i]\) are equal to \([l_2, r_2]\).

In one step, you can choose one segment (either from the first or from the second list) and extend it by \(1\). In other words, suppose you've chosen segment \([x, y]\) then you can transform it either into \([x - 1, y]\) or into \([x, y + 1]\).

Let's define a total intersection \(I\) as the sum of lengths of intersections of the corresponding pairs of segments, i.e. \(\sum\limits_{i=1}^{n}{\text{intersection_length}([al_i, ar_i], [bl_i, br_i])}\). Empty intersection has length \(0\) and length of a segment \([x, y]\) is equal to \(y - x\).

What is the minimum number of steps you need to make \(I\) greater or equal to \(k\)?

Two Arrays

You are given two arrays \(a_1, a_2, \dots , a_n\) and \(b_1, b_2, \dots , b_m\). Array \(b\) is sorted in ascending order (\(b_i < b_{i + 1}\) for each \(i\) from \(1\) to \(m - 1\)).

You have to divide the array \(a\) into \(m\) consecutive subarrays so that, for each \(i\) from \(1\) to \(m\), the minimum on the \(i\)-th subarray is equal to \(b_i\). Note that each element belongs to exactly one subarray, and they are formed in such a way: the first several elements of \(a\) compose the first subarray, the next several elements of \(a\) compose the second subarray, and so on.

For example, if \(a = [12, 10, 20, 20, 25, 30]\) and \(b = [10, 20, 30]\) then there are two good partitions of array \(a\):

1. \([12, 10, 20], [20, 25], [30]\);
2. \([12, 10], [20, 20, 25], [30]\).

You have to calculate the number of ways to divide the array \(a\). Since the number can be pretty large print it modulo 998244353.

Magic Gems

Reziba has many magic gems. Each magic gem can be split into \(M\) normal gems. The amount of space each magic (and normal) gem takes is \(1\) unit. A normal gem cannot be split.

Reziba wants to choose a set of magic gems and split some of them, so the total space occupied by the resulting set of gems is \(N\) units. If a magic gem is chosen and split, it takes \(M\) units of space (since it is split into \(M\) gems); if a magic gem is not split, it takes \(1\) unit.

How many different configurations of the resulting set of gems can Reziba have, such that the total amount of space taken is \(N\) units? Print the answer modulo \(1000000007\) (\(10^9+7\)). Two configurations are considered different if the number of magic gems Reziba takes to form them differs, or the indices of gems Reziba has to split differ.

Guess The Maximums

This is an interactive problem.

Ayush devised a new scheme to set the password of his lock. The lock has \(k\) slots where each slot can hold integers from \(1\) to \(n\). The password \(P\) is a sequence of \(k\) integers each in the range \([1, n]\), \(i\)-th element of which goes into the \(i\)-th slot of the lock.

To set the password of his lock, Ayush comes up with an array \(A\) of \(n\) integers each in the range \([1, n]\) (not necessarily distinct). He then picks \(k\) non-empty mutually disjoint subsets of indices \(S_1, S_2, ..., S_k\) \((S_i \underset{i \neq j} \cap S_j = \emptyset)\) and sets his password as \(P_i = \max\limits_{j \notin S_i} A[j]\). In other words, the \(i\)-th integer in the password is equal to the maximum over all elements of \(A\) whose indices do not belong to \(S_i\).

You are given the subsets of indices chosen by Ayush. You need to guess the password. To make a query, you can choose a non-empty subset of indices of the array and ask the maximum of all elements of the array with index in this subset. You can ask no more than 12 queries.

Boring Segments

You are given \(n\) segments on a number line, numbered from \(1\) to \(n\). The \(i\)-th segments covers all integer points from \(l_i\) to \(r_i\) and has a value \(w_i\).

You are asked to select a subset of these segments (possibly, all of them). Once the subset is selected, it's possible to travel between two integer points if there exists a selected segment that covers both of them. A subset is good if it's possible to reach point \(m\) starting from point \(1\) in arbitrary number of moves.

The cost of the subset is the difference between the maximum and the minimum values of segments in it. Find the minimum cost of a good subset.

In every test there exists at least one good subset.

Segment Tree

As the name of the task implies, you are asked to do some work with segments and trees.

Recall that a tree is a connected undirected graph such that there is exactly one simple path between every pair of its vertices.

You are given \(n\) segments \([l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]\), \(l_i < r_i\) for every \(i\). It is guaranteed that all segments' endpoints are integers, and all endpoints are unique — there is no pair of segments such that they start in the same point, end in the same point or one starts in the same point the other one ends.

Let's generate a graph with \(n\) vertices from these segments. Vertices \(v\) and \(u\) are connected by an edge if and only if segments \([l_v, r_v]\) and \([l_u, r_u]\) intersect and neither of it lies fully inside the other one.

For example, pairs \(([1, 3], [2, 4])\) and \(([5, 10], [3, 7])\) will induce the edges but pairs \(([1, 2], [3, 4])\) and \(([5, 7], [3, 10])\) will not.

Determine if the resulting graph is a tree or not.

Array Partition

You are given an array \(a\) consisting of \(n\) integers.

Let \(min(l, r)\) be the minimum value among \(a_l, a_{l + 1}, \ldots, a_r\) and \(max(l, r)\) be the maximum value among \(a_l, a_{l + 1}, \ldots, a_r\).

Your task is to choose three positive (greater than \(0\)) integers \(x\), \(y\) and \(z\) such that:

• \(x + y + z = n\);
• \(max(1, x) = min(x + 1, x + y) = max(x + y + 1, n)\).

In other words, you have to split the array \(a\) into three consecutive non-empty parts that cover the whole array and the maximum in the first part equals the minimum in the second part and equals the maximum in the third part (or determine it is impossible to find such a partition).

Among all such triples (partitions), you can choose any.

You have to answer \(t\) independent test cases.

Divisibility by 25

You are given an integer \(n\) from \(1\) to \(10^{18}\) without leading zeroes.

In one move you can swap any two adjacent digits in the given number in such a way that the resulting number will not contain leading zeroes. In other words, after each move the number you have cannot contain any leading zeroes.

What is the minimum number of moves you have to make to obtain a number that is divisible by \(25\)? Print -1 if it is impossible to obtain a number that is divisible by \(25\).

Water Balance

There are \(n\) water tanks in a row, \(i\)-th of them contains \(a_i\) liters of water. The tanks are numbered from \(1\) to \(n\) from left to right.

You can perform the following operation: choose some subsegment \([l, r]\) (\(1\le l \le r \le n\)), and redistribute water in tanks \(l, l+1, \dots, r\) evenly. In other words, replace each of \(a_l, a_{l+1}, \dots, a_r\) by \(\frac{a_l + a_{l+1} + \dots + a_r}{r-l+1}\). For example, if for volumes \([1, 3, 6, 7]\) you choose \(l = 2, r = 3\), new volumes of water will be \([1, 4.5, 4.5, 7]\). You can perform this operation any number of times.

What is the lexicographically smallest sequence of volumes of water that you can achieve?

As a reminder:

A sequence \(a\) is lexicographically smaller than a sequence \(b\) of the same length if and only if the following holds: in the first (leftmost) position where \(a\) and \(b\) differ, the sequence \(a\) has a smaller element than the corresponding element in \(b\).

Martial Arts Tournament

Monocarp is planning to host a martial arts tournament. There will be three divisions based on weight: lightweight, middleweight and heavyweight. The winner of each division will be determined by a single elimination system.

In particular, that implies that the number of participants in each division should be a power of two. Additionally, each division should have a non-zero amount of participants.

\(n\) participants have registered for the tournament so far, the \(i\)-th of them weighs \(a_i\). To split participants into divisions, Monocarp is going to establish two integer weight boundaries \(x\) and \(y\) (\(x < y\)).

All participants who weigh strictly less than \(x\) will be considered lightweight. All participants who weigh greater or equal to \(y\) will be considered heavyweight. The remaining participants will be considered middleweight.

It's possible that the distribution doesn't make the number of participants in each division a power of two. It can also lead to empty divisions. To fix the issues, Monocarp can invite an arbitrary number of participants to each division.

Note that Monocarp can't kick out any of the \(n\) participants who have already registered for the tournament.

However, he wants to invite as little extra participants as possible. Help Monocarp to choose \(x\) and \(y\) in such a way that the total amount of extra participants required is as small as possible. Output that amount.

01 Tree

There is an edge-weighted complete binary tree with \(n\) leaves. A complete binary tree is defined as a tree where every non-leaf vertex has exactly 2 children. For each non-leaf vertex, we label one of its children as the left child and the other as the right child.

The binary tree has a very strange property. For every non-leaf vertex, one of the edges to its children has weight \(0\) while the other edge has weight \(1\). Note that the edge with weight \(0\) can be connected to either its left or right child.

You forgot what the tree looks like, but luckily, you still remember some information about the leaves in the form of an array \(a\) of size \(n\). For each \(i\) from \(1\) to \(n\), \(a_i\) represents the distance\(^\dagger\) from the root to the \(i\)-th leaf in dfs order\(^\ddagger\). Determine whether there exists a complete binary tree which satisfies array \(a\). Note that you do not need to reconstruct the tree.

\(^\dagger\) The distance from vertex \(u\) to vertex \(v\) is defined as the sum of weights of the edges on the path from vertex \(u\) to vertex \(v\).

\(^\ddagger\) The dfs order of the leaves is found by calling the following \(\texttt{dfs}\) function on the root of the binary tree.

  
dfs\_order = \[\]  
  
function dfs(v):  
    if v is leaf:  
        append v to the back of dfs\_order  
    else:  
        dfs(left child of v)  
        dfs(right child of v)  
  
dfs(root)  

Optimal Partition

You are given an array \(a\) consisting of \(n\) integers. You should divide \(a\) into continuous non-empty subarrays (there are \(2^{n-1}\) ways to do that).

Let \(s=a_l+a_{l+1}+\ldots+a_r\). The value of a subarray \(a_l, a_{l+1}, \ldots, a_r\) is:

• \((r-l+1)\) if \(s>0\),
• \(0\) if \(s=0\),
• \(-(r-l+1)\) if \(s<0\).

What is the maximum sum of values you can get with a partition?

Recovering BST

Dima the hamster enjoys nibbling different things: cages, sticks, bad problemsetters and even trees!

Recently he found a binary search tree and instinctively nibbled all of its edges, hence messing up the vertices. Dima knows that if Andrew, who has been thoroughly assembling the tree for a long time, comes home and sees his creation demolished, he'll get extremely upset.

To not let that happen, Dima has to recover the binary search tree. Luckily, he noticed that any two vertices connected by a direct edge had their greatest common divisor value exceed \(1\).

Help Dima construct such a binary search tree or determine that it's impossible. The definition and properties of a binary search tree can be found here.

Beautiful Mirrors

Creatnx has \(n\) mirrors, numbered from \(1\) to \(n\). Every day, Creatnx asks exactly one mirror "Am I beautiful?". The \(i\)-th mirror will tell Creatnx that he is beautiful with probability \(\frac{p_i}{100}\) for all \(1 \le i \le n\).

Creatnx asks the mirrors one by one, starting from the \(1\)-st mirror. Every day, if he asks \(i\)-th mirror, there are two possibilities:

• The \(i\)-th mirror tells Creatnx that he is beautiful. In this case, if \(i = n\) Creatnx will stop and become happy, otherwise he will continue asking the \(i+1\)-th mirror next day;
• In the other case, Creatnx will feel upset. The next day, Creatnx will start asking from the \(1\)-st mirror again.

You need to calculate the expected number of days until Creatnx becomes happy.

This number should be found by modulo \(998244353\). Formally, let \(M = 998244353\). It can be shown that the answer can be expressed as an irreducible fraction \(\frac{p}{q}\), where \(p\) and \(q\) are integers and \(q \not \equiv 0 \pmod{M}\). Output the integer equal to \(p \cdot q^{-1} \bmod M\). In other words, output such an integer \(x\) that \(0 \le x < M\) and \(x \cdot q \equiv p \pmod{M}\).

Monocarp and the Set

Monocarp has \(n\) numbers \(1, 2, \dots, n\) and a set (initially empty). He adds his numbers to this set \(n\) times in some order. During each step, he adds a new number (which has not been present in the set before). In other words, the sequence of added numbers is a permutation of length \(n\).

Every time Monocarp adds an element into the set except for the first time, he writes out a character:

• if the element Monocarp is trying to insert becomes the maximum element in the set, Monocarp writes out the character >;
• if the element Monocarp is trying to insert becomes the minimum element in the set, Monocarp writes out the character <;
• if none of the above, Monocarp writes out the character ?.

You are given a string \(s\) of \(n-1\) characters, which represents the characters written out by Monocarp (in the order he wrote them out). You have to process \(m\) queries to the string. Each query has the following format:

• \(i\) \(c\) — replace \(s_i\) with the character \(c\).

Both before processing the queries and after each query, you have to calculate the number of different ways to order the integers \(1, 2, 3, \dots, n\) such that, if Monocarp inserts the integers into the set in that order, he gets the string \(s\). Since the answers might be large, print them modulo \(998244353\).

Arena

There are \(n\) heroes fighting in the arena. Initially, the \(i\)-th hero has \(a_i\) health points.

The fight in the arena takes place in several rounds. At the beginning of each round, each alive hero deals \(1\) damage to all other heroes. Hits of all heroes occur simultaneously. Heroes whose health is less than \(1\) at the end of the round are considered killed.

If exactly \(1\) hero remains alive after a certain round, then he is declared the winner. Otherwise, there is no winner.

Your task is to calculate the number of ways to choose the initial health points for each hero \(a_i\), where \(1 \le a_i \le x\), so that there is no winner of the fight. The number of ways can be very large, so print it modulo \(998244353\). Two ways are considered different if at least one hero has a different amount of health. For example, \([1, 2, 1]\) and \([2, 1, 1]\) are different.

GCD Queries

This is an interactive problem.

There is a secret permutation \(p\) of \([0,1,2,\ldots,n-1]\). Your task is to find \(2\) indices \(x\) and \(y\) (\(1 \leq x, y \leq n\), possibly \(x=y\)) such that \(p_x=0\) or \(p_y=0\). In order to find it, you are allowed to ask at most \(2n\) queries.

In one query, you give two integers \(i\) and \(j\) (\(1 \leq i, j \leq n\), \(i \neq j\)) and receive the value of \(\gcd(p_i,p_j)^\dagger\).

Note that the permutation \(p\) is fixed before any queries are made and does not depend on the queries.

\(^\dagger\) \(\gcd(x, y)\) denotes the greatest common divisor (GCD) of integers \(x\) and \(y\). Note that \(\gcd(x,0)=\gcd(0,x)=x\) for all positive integers \(x\).

Omkar and Duck

This is an interactive problem.

Omkar has just come across a duck! The duck is walking on a grid with \(n\) rows and \(n\) columns (\(2 \leq n \leq 25\)) so that the grid contains a total of \(n^2\) cells. Let's denote by \((x, y)\) the cell in the \(x\)-th row from the top and the \(y\)-th column from the left. Right now, the duck is at the cell \((1, 1)\) (the cell in the top left corner) and would like to reach the cell \((n, n)\) (the cell in the bottom right corner) by moving either down \(1\) cell or to the right \(1\) cell each second.

Since Omkar thinks ducks are fun, he wants to play a game with you based on the movement of the duck. First, for each cell \((x, y)\) in the grid, you will tell Omkar a nonnegative integer \(a_{x,y}\) not exceeding \(10^{16}\), and Omkar will then put \(a_{x,y}\) uninteresting problems in the cell \((x, y)\). After that, the duck will start their journey from \((1, 1)\) to \((n, n)\). For each cell \((x, y)\) that the duck crosses during their journey (including the cells \((1, 1)\) and \((n, n)\)), the duck will eat the \(a_{x,y}\) uninteresting problems in that cell. Once the duck has completed their journey, Omkar will measure their mass to determine the total number \(k\) of uninteresting problems that the duck ate on their journey, and then tell you \(k\).

Your challenge, given \(k\), is to exactly reproduce the duck's path, i. e. to tell Omkar precisely which cells the duck crossed on their journey. To be sure of your mastery of this game, Omkar will have the duck complete \(q\) different journeys (\(1 \leq q \leq 10^3\)). Note that all journeys are independent: at the beginning of each journey, the cell \((x, y)\) will still contain \(a_{x,y}\) uninteresting tasks.

Common Number

At first, let's define function \(f(x)\) as follows:

\[\begin{matrix} f(x) & = & \left\{ \begin{matrix} \frac{x}{2} & \mbox{if } x \text{ is even} \\ x - 1 & \mbox{otherwise } \end{matrix} \right. \end{matrix} \]

We can see that if we choose some value \(v\) and will apply function \(f\) to it, then apply \(f\) to \(f(v)\), and so on, we'll eventually get \(1\). Let's write down all values we get in this process in a list and denote this list as \(path(v)\). For example, \(path(1) = [1]\), \(path(15) = [15, 14, 7, 6, 3, 2, 1]\), \(path(32) = [32, 16, 8, 4, 2, 1]\).

Let's write all lists \(path(x)\) for every \(x\) from \(1\) to \(n\). The question is next: what is the maximum value \(y\) such that \(y\) is contained in at least \(k\) different lists \(path(x)\)?

Formally speaking, you need to find maximum \(y\) such that \(\left| \{ x ~|~ 1 \le x \le n, y \in path(x) \} \right| \ge k\).

Graph Coloring

You are given an undirected graph without self-loops or multiple edges which consists of \(n\) vertices and \(m\) edges. Also you are given three integers \(n_1\), \(n_2\) and \(n_3\).

Can you label each vertex with one of three numbers 1, 2 or 3 in such way, that:

1. Each vertex should be labeled by exactly one number 1, 2 or 3;
2. The total number of vertices with label 1 should be equal to \(n_1\);
3. The total number of vertices with label 2 should be equal to \(n_2\);
4. The total number of vertices with label 3 should be equal to \(n_3\);
5. \(|col_u - col_v| = 1\) for each edge \((u, v)\), where \(col_x\) is the label of vertex \(x\).

If there are multiple valid labelings, print any of them.

Permutation Shift

An identity permutation of length \(n\) is an array \([1, 2, 3, \dots, n]\).

We performed the following operations to an identity permutation of length \(n\):

• firstly, we cyclically shifted it to the right by \(k\) positions, where \(k\) is unknown to you (the only thing you know is that \(0 \le k \le n - 1\)). When an array is cyclically shifted to the right by \(k\) positions, the resulting array is formed by taking \(k\) last elements of the original array (without changing their relative order), and then appending \(n - k\) first elements to the right of them (without changing relative order of the first \(n - k\) elements as well). For example, if we cyclically shift the identity permutation of length \(6\) by \(2\) positions, we get the array \([5, 6, 1, 2, 3, 4]\);
• secondly, we performed the following operation at most \(m\) times: pick any two elements of the array and swap them.

You are given the values of \(n\) and \(m\), and the resulting array. Your task is to find all possible values of \(k\) in the cyclic shift operation.

Number of Components

The Kingdom of Kremland is a tree (a connected undirected graph without cycles) consisting of \(n\) vertices. Each vertex \(i\) has its own value \(a_i\). All vertices are connected in series by edges. Formally, for every \(1 \leq i &lt; n\) there is an edge between the vertices of \(i\) and \(i+1\).

Denote the function \(f(l, r)\), which takes two integers \(l\) and \(r\) (\(l \leq r\)):

- We leave in the tree only vertices whose values ​​range from \(l\) to \(r\).

• The value of the function will be the number of connected components in the new graph.

Your task is to calculate the following sum:

\[\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) \]

Best Pair

You are given an array \(a\) of length \(n\). Let \(cnt_x\) be the number of elements from the array which are equal to \(x\). Let's also define \(f(x, y)\) as \((cnt_x + cnt_y) \cdot (x + y)\).

Also you are given \(m\) bad pairs \((x_i, y_i)\). Note that if \((x, y)\) is a bad pair, then \((y, x)\) is also bad.

Your task is to find the maximum value of \(f(u, v)\) over all pairs \((u, v)\), such that \(u \neq v\), that this pair is not bad, and also that \(u\) and \(v\) each occur in the array \(a\). It is guaranteed that such a pair exists.

Decryption

An agent called Cypher is decrypting a message, that contains a composite number \(n\). All divisors of \(n\), which are greater than \(1\), are placed in a circle. Cypher can choose the initial order of numbers in the circle.

In one move Cypher can choose two adjacent numbers in a circle and insert their least common multiple between them. He can do that move as many times as needed.

A message is decrypted, if every two adjacent numbers are not coprime. Note that for such constraints it's always possible to decrypt the message.

Find the minimal number of moves that Cypher should do to decrypt the message, and show the initial order of numbers in the circle for that.

Timofey and Black-White Tree

Timofey came to a famous summer school and found a tree on \(n\) vertices. A tree is a connected undirected graph without cycles.

Every vertex of this tree, except \(c_0\), is colored white. The vertex \(c_0\) is colored black.

Timofey wants to color all the vertices of this tree in black. To do this, he performs \(n - 1\) operations. During the \(i\)-th operation, he selects the vertex \(c_i\), which is currently white, and paints it black.

Let's call the positivity of tree the minimum distance between all pairs of different black vertices in it. The distance between the vertices \(v\) and \(u\) is the number of edges on the path from \(v\) to \(u\).

After each operation, Timofey wants to know the positivity of the current tree.

More Wrong

This is an interactive problem.

The jury has hidden a permutation\(^\dagger\) \(p\) of length \(n\).

In one query, you can pick two integers \(l\) and \(r\) (\(1 \le l &lt; r \le n\)) by paying \((r - l)^2\) coins. In return, you will be given the number of inversions\(^\ddagger\) in the subarray \([p_l, p_{l + 1}, \ldots p_r]\).

Find the index of the maximum element in \(p\) by spending at most \(5 \cdot n^2\) coins.

Note: the grader is not adaptive: the permutation is fixed before any queries are made.

\(^\dagger\) A permutation of length \(n\) is an array consisting of \(n\) distinct integers from \(1\) to \(n\) in arbitrary order. For example, \([2,3,1,5,4]\) is a permutation, but \([1,2,2]\) is not a permutation (\(2\) appears twice in the array), and \([1,3,4]\) is also not a permutation (\(n=3\) but there is \(4\) in the array).

\(^\ddagger\) The number of inversions in an array is the number of pairs of indices \((i,j)\) such that \(i &lt; j\) and \(a_i &gt; a_j\). For example, the array \([10,2,6,3]\) contains \(4\) inversions. The inversions are \((1,2),(1,3),(1,4)\), and \((3,4)\).

New Year and Conference

Filled with optimism, Hyunuk will host a conference about how great this new year will be!

The conference will have \(n\) lectures. Hyunuk has two candidate venues \(a\) and \(b\). For each of the \(n\) lectures, the speaker specified two time intervals \([sa_i, ea_i]\) (\(sa_i \le ea_i\)) and \([sb_i, eb_i]\) (\(sb_i \le eb_i\)). If the conference is situated in venue \(a\), the lecture will be held from \(sa_i\) to \(ea_i\), and if the conference is situated in venue \(b\), the lecture will be held from \(sb_i\) to \(eb_i\). Hyunuk will choose one of these venues and all lectures will be held at that venue.

Two lectures are said to overlap if they share any point in time in common. Formally, a lecture held in interval \([x, y]\) overlaps with a lecture held in interval \([u, v]\) if and only if \(\max(x, u) \le \min(y, v)\).

We say that a participant can attend a subset \(s\) of the lectures if the lectures in \(s\) do not pairwise overlap (i.e. no two lectures overlap). Note that the possibility of attending may depend on whether Hyunuk selected venue \(a\) or venue \(b\) to hold the conference.

A subset of lectures \(s\) is said to be venue-sensitive if, for one of the venues, the participant can attend \(s\), but for the other venue, the participant cannot attend \(s\).

A venue-sensitive set is problematic for a participant who is interested in attending the lectures in \(s\) because the participant cannot be sure whether the lecture times will overlap. Hyunuk will be happy if and only if there are no venue-sensitive sets. Determine whether Hyunuk will be happy.

MEX vs DIFF

You are given an array \(a\) of \(n\) non-negative integers. In one operation you can change any number in the array to any other non-negative integer.

Let's define the cost of the array as \(\operatorname{DIFF}(a) - \operatorname{MEX}(a)\), where \(\operatorname{MEX}\) of a set of non-negative integers is the smallest non-negative integer not present in the set, and \(\operatorname{DIFF}\) is the number of different numbers in the array.

For example, \(\operatorname{MEX}(\{1, 2, 3\}) = 0\), \(\operatorname{MEX}(\{0, 1, 2, 4, 5\}) = 3\).

You should find the minimal cost of the array \(a\) if you are allowed to make at most \(k\) operations.

Monsters

There is an undirected graph with \(n\) vertices and \(m\) edges. Initially, for each vertex \(i\), there is a monster with danger \(a_{i}\) on that vertex. For a monster with danger \(a_{i}\), you can defeat it if and only if you have defeated at least \(a_{i}\) other monsters before.

Now you want to defeat all the monsters. First, you choose some vertex \(s\) and defeat the monster on that vertex (since you haven't defeated any monsters before, \(a_{s}\) has to be \(0\)). Then, you can move through the edges. If you want to move from vertex \(u\) to vertex \(v\), then the following must hold: either the monster on vertex \(v\) has been defeated before, or you can defeat it now. For the second case, you defeat the monster on vertex \(v\) and reach vertex \(v\).

You can pass the vertices and the edges any number of times. Determine whether you can defeat all the monsters or not.

标签：number,will,each,such,array,2100,he
From： https://www.cnblogs.com/alric/p/18310565