We simply use an if statement to determine if the given name is $$$\texttt{kevin}$$$. If it is, print $$$\texttt{Hail, liege lord King Kevin!}$$$ Otherwise, print $$$\texttt{Greetings, }$$$ followed by the name and a period. The specifics of implementation depend on the language being used.

Time complexity: $$$O(1)$$$

We first count the bricks used by each component. Each tower is a hollow rectangular prism of width $$$M$$$ and height $$$H + M$$$ (extending through the wall and above it). Its cross-section uses $$$M^2 - (M-2)^2 = 4M - 4$$$ bricks per layer, so each tower consumes $$$(4M - 4)(H + M)$$$ bricks in total. The remaining $$$N - T(4M-4)(H+M)$$$ bricks form the flat wall of height $$$H$$$ and thickness $$$1$$$, excluding the footprints of the towers. Solving for the wall length $$$L$$$:

Time complexity: $$$O(1)$$$

Simply simulate the process with a for loop. Iterate through each curse: if it is a $$$1$$$, double the current amount of coins; if it is a $$$0$$$, subtract $$$k$$$ from the current amount of coins. Output the final value.

Time complexity: $$$O(m)$$$

For each item, check if its name contains the substring $$$\texttt{sword}$$$. If it does, apply a $$$30\%$$$ discount to its price (i.e. multiply by $$$0.7$$$). Then, check if the resulting price is at most $$$k$$$ and output $$$\texttt{YES}$$$ or $$$\texttt{NO}$$$ accordingly. Otherwise, simply compare the price to $$$k$$$.

Time complexity: $$$O(n)$$$

We claim the answer for a query $$$t$$$ is $$$\max(0,\ b \cdot (t - n + 1))$$$, where $$$b = \min(a_1, a_2, \dots, a_n)$$$.

To see why, observe that the output of the entire pipeline is bottlenecked by the slowest worker, so at most $$$b$$$ swords can be completed per second in a steady state. Furthermore, the first sword cannot be completed until second $$$n$$$, since it must pass through all $$$n$$$ workers. After this initial delay, exactly $$$b$$$ swords are completed each second. Thus the total number of completed swords after $$$t$$$ seconds is $$$\max(0,\ b \cdot (t - n + 1))$$$. We can compute $$$b$$$ with a simple for loop and a running variable.

Time complexity: $$$O(n)$$$

Let $$$a$$$ be the original array of coins before the swaps occurred. Let $$$b_i$$$ represent the $$$i$$$'th swapped array.

Lets say we are trying to determine $$$a[j]$$$, the $$$j$$$'th element of the original array. We claim that $$$a[j]$$$ is the only element which has occurred more than once across all swapped arrays in position $$$j$$$.

Note that for each swapped array, there are two cases. Either the $$$i$$$'th swapped array swapped an element with the $$$j$$$'th element in the original array or it did not. If $$$b_i$$$ swapped position $$$j$$$ with, say, position $$$k$$$, then $$$b_i$$$ must be the only swapped array with $$$a[k]$$$ in position $$$j$$$ since all swapped arrays are distinct. In the case that element $$$j$$$ was not swapped, $$$b_i[j] = a[j]$$$. This can occur across multiple different swapped arrays. Thus, the only element which can appear multiple times in position $$$j$$$ is $$$a[j]$$$, our desired original array element. Thus, when reconstructing the original array, it is sufficient to simply find the element which appears multiple times in each position.

Time complexity: $$$O(n^2)$$$.

Observe that the set of explored rooms always forms a prefix of length $$$i$$$ and a suffix of length $$$j$$$ (unless the entire dungeon can be explored), since we can only explore from the leftmost or rightmost unexplored room. Thus, we iterate over all valid $$$(i, j)$$$ pairs such that the total number of monsters in the first $$$i$$$ rooms and last $$$j$$$ rooms is equal to $$$k$$$, and maximize the total gold collected. Using two pointers, one representing the end of the prefix and one representing the start of the suffix, we can iterate these optimal pairs efficiently.

Time complexity: $$$O(n)$$$

One can simulate the game move by move on a 2D array. After each stone is placed, they should check horizontally, vertically, and diagonally to see if there is a connect five. If all $$$m$$$ moves are exhausted without a five-in-a-row, the player who placed the last stone wins.

This solution works, although it is slow and tedious to implement. A keen eye may notice that the game ends when someone wins. Additionally, in the case of the entire board being filled up, the person who played the last move wins. Thus, we can simply see who was the last person to place a stone by taking $$$m$$$ modulo 2.

Time complexity: $$$O(1)$$$

Note that we only have to pay for an operation if we don't undo it in the future. What we can do is initially decrease the poles as follows:

and then add it back on at the end. Then, all we have to do is make the poles be the same height since, when we add on this spiky sequence at the end, we want the sequence to become spiky. Thus, we have reduced the problem to finding an optimal uniform height $$$h$$$ for all poles instead of an optimal spiky sequence. This optimal height $$$h$$$ is simply the median of all of our subtracted heights. Consequently, after the initial subtraction we can count the number of coins needed to raise and lower each pole to make it at height $$$h$$$.

Time complexity: $$$O(n \log n)$$$.

To solve this problem, we simply use two-dimensional dynamic programming from the top of the hill to the bottom of the hill. Let $$$dp[R][C]$$$ be the maximum steepness sum achievable to reach cell $$$(R, C)$$$. Since Kevin can either move to the bottom left, bottom right, or middle cell, we get that

Note that you have to use an if statement to make sure that $$$C$$$ isn't the left or rightmost column, in which case one shouldn't include $$$dp[R - 1][C - 1]$$$ or $$$dp[R - 1][C + 1]$$$ in the transition.

To deal with trenches, we instead set the steepness of each trench to negative infinity (or a sufficiently large negative number). Because of this, we can effectively ski over a trench which would result in our total steepness hvaing value negative infinity. This forces the DP to favor routes which avoid trenches if possible.

So, to get the final answer, we take the maximum of $$$dp[n]$$$. If the maximum is negative infinity, then we skied over a trench and we should output "-1". Otherwise, we simply output the answer.

Time complexity: $$$O(nm)$$$

Applying the operation on a graph, it is easy to see that it simply "swaps" two of the directed edges. Interestingly, though, the in- and out-degree of each node stays the same. We claim that one can transform $$$G_1$$$ into $$$G_2$$$ if and only if they have the same degrees for each vertex.

To prove this, we can simply begin applying operations. Say you want to "process" a node $$$v$$$ in $$$G_1$$$ to make all of its in- and out-edges match those in $$$G_2$$$. Say $$$v$$$ is supposed to have an edge to $$$x$$$. Since $$$x$$$'s in-degree is correct, you know that $$$x$$$ also has some node $$$y$$$ incorrectly pointing to $$$x$$$. $$$y$$$ cannot be a node which was already processed because, if it were, it would not have an incorrect edge. Thus, we apply an operation to make $$$v$$$ point to $$$x$$$ and remove the edge from $$$y$$$ to $$$x$$$.

After each such operation, we make at least 1 edge point to the correct node while not making any correct edges point to the wrong location. Consequently, if we repeat this operation enough times, we will eventually have every edge pointing to the correct location.

Determining whether each node has the correct in- and out-degree takes $$$O(n + m)$$$ time.

Note that we want soldiers to convert other soldiers which are similar in strength to themselves. So, sorting soldiers by increasing strength, we claim it is optimal for a soldier to convert another soldier if they are adjacent to each other. This holds because it is always true that for sorted $$$s$$$ and three indices $$$i \lt j \lt k$$$, that $$$(s_k - s_i)^2 \geq (s_k - s_j)^2 + (s_j + s_i)^2$$$.

Consequently, for a given $$$c$$$, we can compute the total religion points needed by taking the minimum between $$$c$$$ and the difference in strengths squared:

Note that we still need to add one $$$c$$$ to convert the first soldier.

To answer these queries efficiently, we can first store an array with all the values $$$(s_{i+1} - s_i)^2$$$ and sort said array in increasing order. We can then similarly read in all the queries and sort them in increasing order. Now, we can iterate through the queries array, keeping a pointer variable to simultaneously iterate through the difference array. By iterating through the sorted difference array, we are able to efficiently determine which squared differences to ignore and replace with $$$c$$$. This allows us to compute the answer to every query offline in $$$O(n \log n)$$$ time.

To increase the depth of the tree, we clearly want to make the new parent of any node be the leaf of the diameter of the tree. We claim that the greedy algorithm, simply applying a liege exchange operation on the available subtree with the largest depth, is optimal.

To implement this algorithm, we need to know the longest path from any node $$$v$$$ to its subtree's leafs. Let $$$dist[v]$$$ be the length of the longest path from $$$v$$$ to any of its subtree's leafs and $$$leaf[v]$$$ be the leaf which is the farthest from $$$v$$$ inside of $$$v$$$'s subtree. Additionally, let $$$par[v]$$$ be the parent of any node. We can compute all of these recursively in $$$O(n)$$$ with a depth-first search.

We maintain a boolean array, $$$diam[v]$$$, indicating whether $$$v$$$ is currently inside of the diameter or not. We also maintain a priority queue $$$adj$$$ which stores the nodes which are directly adjacent to the diameter and sorts them in nonincreasing order of $$$dist[v]$$$.

To perform the next liege exchange operation, we pop the node that has the highest $$$dist[v]$$$ from the priority queue and add it to the end of the diameter, updating both the $$$adj$$$ and $$$diam$$$ array as necessary.

This algorithm greedily chooses the availabe subtree with the largest possible diameter and attaches it to the end of the diameter of the whole tree. Additionally, this algorithm runs in $$$O(n \log n)$$$ amortized time since each node can only ever be added or removed from $$$adj$$$ once.

First of all, note that the exact locations of the castles doesn't really matter; we can easily apply a coordinate compression to make the $$$x$$$ and $$$y$$$ coordinates of each castle less than or equal to $$$n$$$ while preserving their relative order.

Consider a naive algorithm which simply iterates across the bounds $$$x_1, x_2, y_1, y_2$$$. After the coordinate compression, this would run in $$$O(n^4)$$$ time with good implementation.

We can speed this solution up by sorting the castles in increasing $$$y$$$ value and keeping track of a one-dimensional array $$$S$$$. We define $$$S$$$ such that $$$S[x]=\sum_{y=y_1}^{y_2} dubloons(x, y)$$$. Now, when we add all the points in $$$y=y_2 + 1$$$, we can simply add their dubloon values to the correct $$$x$$$ locations in $$$S$$$. Then, for every $$$(y_1, y_2)$$$ pair, we can find the maximum subarray sum of $$$S$$$ in $$$O(n)$$$ time. Since $$$y_1, y_2 \leq n$$$ after coordinate compression, this gives us a time complexity of $$$O(n^3)$$$, which is still too slow.

To speed up our algorithm further, we need to optimize the computation of the maximum subarray sum. This can be done by using Kadane's algorithm with a segment tree. For each $$$y_1$$$ value, we iterate across $$$n$$$ castles when increasing $$$y_2$$$, performing one $$$O(\log n)$$$ update operation per castle. Since we iterate $$$y_1$$$ $$$n$$$ times, our final time complexity is $$$O(n^2 \log n)$$$.

Let's first solve $$$f(1, n)$$$. Since we want to construct the minimum possible number of watchtowers, we can think of splitting any distance $$$d$$$ into $$$k$$$ almost-equal-length segments, each either of length $$$\lfloor \frac{d}{k} \rfloor$$$ or of length $$$\lceil \frac{d}{k} \rceil$$$. This would take $$$k - 1$$$ watchtowers. Note that any other way to split the distance into $$$k$$$ segments would cause a larger distance towards the end and a smaller distance towards the start, which would potentially make us need to split previous distances more, worsening our solution. Thus, splitting a distance into these almost-equal-length segments is always optimal.

To compute $$$f(1, n)$$$ using this optimal splitting method, we can iterate from the last distance to the first distance, greedily splitting segments as little as necessary to ensure that the final sequence of distances becomes nondecreasing.

To compute the sum of $$$f(l, r)$$$ across all ranges $$$1 \leq l \lt r \leq n$$$, we can use dynamic programming combined with a running count of how many operations have already been used.

We define $$$dp[i][j]$$$ to be the number of times that the distance $$$d_i$$$ gets split into $$$j$$$ segments across ranges where $$$i \leq l \lt r \leq n$$$. The reason for defining $$$dp[i][j]$$$ as such is that

1. We can compute the total number of watchtowers added from segment $$$i$$$ by summing $$$S = dp[i][j] \cdot (j - 1)$$$, since splitting a segment $$$j$$$ times adds $$$j - 1$$$ watchtowers
2. The total number of times $$$d_i$$$ is split into $$$j$$$ segments stays the same if you add segment $$$d_{i - 1}$$$ in front. Consequently, whenever we add a new segment in front, we add $$$S$$$ to our final answer again. Thus, after computing $$$dp[i]$$$, we add $$$S \cdot i$$$ to the answer, since there are $$$i - 1$$$ segments to add in front of the $$$i$$$'th segment.

To actually compute $$$dp[i][j]$$$, we iterate from $$$i = n$$$ to $$$i = 1$$$. For each new $$$i$$$, we set $$$dp[i][1] = 1$$$, meaning $$$d_i$$$ is left as one segment in the case of $$$f(i, i + 1)$$$. Then, we let

such that $$$\lceil \frac{d_i}{j} \rceil \leq \lfloor \frac{d_{i+1}}{k} \rfloor$$$ and $$$\lceil \frac{d_i}{j - 1} \rceil \gt \lfloor \frac{d_{i+1}}{k} \rfloor$$$. Basically, $$$d_i$$$ is only split into $$$j$$$ segments if splitting $$$d_i$$$ $$$j - 1$$$ times wouldn't result in a nondecreasing sequence.

Naively, this takes $$$O(nd_{max})$$$ time, since we are doing a 2-dimensional dp. Since we are splitting the distances into segments, though, there are only $$$O(\sqrt{d_i})$$$ different possible splits for a segment $$$d_i$$$. This is because we can either split $$$d_i$$$ into $$$1, 2, 3, \dots, \sqrt{d_i}$$$ segments or we can make it so that the segments are approximately each of length $$$1, 2, 3, \dots, \sqrt{d_i}$$$. Consequently, one can implement this dp in $$$O(n\sqrt{d_{max}})$$$, which runs in time.

Note that the coolness of node $$$v$$$ can be described as

where $$$L$$$ is the set of all leafs in the tree. Consequently, the expected $$$coolness$$$ value of a node with $$$k$$$ leafs is the expected gcd of a random size-$$$k$$$ subset of $$${1, 2,\dots, m}$$$. Let the random size-$$$k$$$ subset of $$${1, 2, 3,\dots, m}$$$ be $$$S_k$$$.

Since it is true that $$$n = \sum_{d | n} \phi(d)$$$, it is also true that $$$\gcd(S_k) = \sum_{d | gcd(S_k)} \phi(d)$$$. By taking the expected value, we get that

where $$$\mathrm{P}(d|gcd(S_k))$$$ is the probability of $$$d$$$ being a divisor of $$$\gcd(S_k)$$$. Solving for this probability, we get that $$$\mathrm{P}(d|gcd(S_k)) = \frac{\binom{\lfloor \frac{m}{d} \rfloor}{k}}{\binom{m}{k}}$$$ because there are $$$\lfloor \frac{m}{d} \rfloor$$$ elements which are multiples of $$$d$$$ in the set $$${1, 2, \dots, m}$$$.

Substituting, we ultimately get

One can simply compute the answer by summing $$$E(k_v)$$$ across all nodes where $$$k_v$$$ is the number of leafs in node $$$v$$$'s subtree.

Since $$$\lfloor \frac{m}{d} \rfloor$$$ only takes on $$$O(\sqrt{m})$$$ distinct values, we can iterate across fixed $$$q=\lfloor \frac{m}{d} \rfloor$$$. Note that for any fixed $$$q$$$, $$$d$$$ has a range of $$$[\lfloor \frac{m}{q+1} \rfloor + 1, \lfloor \frac{m}{q} \rfloor]$$$. Thus, we can define $$$F(q) = \sum_d \phi(q)$$$ which can be computed with prefix sums. Consequently, our previous $$$E_k$$$ expression simplifies into

Thus, it takes $$$O(n\sqrt{m})$$$ time to compute the expected value of the sum of the coolness of each node.

We begin by making a series of observations:

1. It is only ever optimal to make the castle consist of one polygon. This is because if it were optimal to make the castle consist of multiple polygons, the area to perimeter ratio of the multiple polygons must be at most the largest area to perimeter ratio of a single polygon.
2. It is always optimal for the castle to be a convex polygon. Consider a concave polygon. We can take the convex hull of the vertices of the convex polygon. This convex hull will enclose more area and, by the triangle inequality, use less perimeter.

Thus, a brute-force way to calculate the answer would be to iterate across all convex hulls and calculate their area to perimeter ratios. This clearly is too slow.

What we can do instead is binary search on the answer. Let the maximum area to perimeter ratio be $$$\lambda_{\max}$$$. If we were to guess a $$$\lambda \lt \lambda_{\max}$$$, then there exists a convex hull for which

If we can efficiently determine whether such a convex hull exists, we can binary search on the answer to sufficient precision. To find this convex hull, we can use dynamic programming across $$$n$$$ graham scans.

Specifically, We will chose a point $$$p$$$ to be an "extreme point" at the corner of our scan. We will then only considering points to the right or directly above this extreme point. Sorting these points by angle to the extreme point and iterate across them, we can perform dynamic programming to maximize the value $$$A - \lambda \cdot P$$$ for each point.

We define $$$dp[v]$$$ to be the largest value of $$$A - \lambda \cdot P$$$ across all polygons using points at a lower angle from the extreme point. We compute $$$dp[v]$$$ as follows:

This iterates across all linear segments from previously processed vertex $$$u$$$ to vertex $$$v$$$. We also need to consider the base case of simply having the triangle consisting of vertices $$$u$$$, $$$v$$$, and $$$p$$$. Thus, we get a final transition of:

Iterating across all extreme points and taking the maximum of all $$$dp$$$ values, we get the largest possible $$$A - \lambda \cdot P$$$ possible across all convex polygons. This allows us to then binary search on the answer value to sufficient absolute or relative precision. Simply using absolute precision will result in a TLE verdict!

iterating across all extreme points and all segments during the graham scan results in a time complexity of $$$O(n^3)$$$.

We initially want to find another way to interpret the solvable condition. Either by messing with small examples, taking the determinant of the adjacency matrix of a tree, or by somehow just "seeing it," we can find the invariant that

Lemma 1: A tree is solvable if and only if the tree has a perfect matching.

Proof: To prove this invariant, we make a series of observations.

1. A solvable tree can never have two leafs which are siblings. If there are two leafs, $$$u$$$ and $$$v$$$, which are siblings, then you cannot uniquely deduce $$$p_u$$$ and $$$p_v$$$. This is because the only information we have about $$$p_u$$$ and $$$p_v$$$ is in $$$t_{par(v)} = p_u + p_v + S$$$ for some constant S, where $$$par(v)$$$ denotes the parent of node $$$v$$$. We thus have one equation to uniquely determine two unknowns, which is impossible.
2. Take any solvable tree. By item 1, there must exist two vertices $$$u, v$$$ such that $$$u=par(v)$$$, $$$v$$$ is a leaf, and $$$v$$$ is the only child of $$$u$$$. We claim that one can delete nodes $$$u$$$ and $$$v$$$ and the remaining tree is still solvable. We look at two cases:
   1. If node $$$u$$$ is the root, then $$$t_u = p_v$$$ and $$$t_v = p_u$$$. Deleting these two nodes gives us the empty graph, which is solvable.
   2. If node $$$u$$$ isn't the root, then $$$t_u = p_v + p_{par(u)}$$$. Since the tree is solvable, we must be able to determine the unique value of $$$p_v$$$. Because the only information we have about $$$p_v$$$ is that $$$p_v = t_u - p_{par(u)}$$$, though, we must be able to determine the value of $$$p_{par(u)}$$$ independently from $$$t_u$$$. Consequently, we can determine $$$p_{par(u)}$$$ independently from nodes $$$u$$$ or $$$v$$$. Thus, if we delete nodes $$$u$$$ and $$$v$$$, then the tree is still solvable.
3. Repeating item 2, we will eventually reach either the empty graph or a single-node graph by induction. Since the single-node graph is not solvable, we can reverse our previous logic to conclude that no solvable tree has an odd number of nodes. Thus, every solvable graph, when reduced, will result in the empty graph, which is solvable. Since we can repeatedly delete pairs of leafs and their parents from the tree, there must be a perfect matching on the tree.

Note that we can prove the reverse direction, that a tree having a perfect matching implies it being solvable, by simply applying this logic except in reverse, building the tree inductively from the empty graph.

Now that we have determined that a tree is only solvable if it has a perfect matching, we can reduce this to a more usable form. Using a similar inductive proof as Lemma 1, one can show that

Lemma 2: A tree has a perfect matching if and only if the amount of nodes with an even number of nodes in their subtree equals the amount of nodes with an odd number of nodes in their subtree.

Proof: Let $$$size(v)$$$ be the number of nodes in node $$$v$$$'s subtree. Furthermore, let the parity of a node be defined as $$$parity(v) = size(v) \mod 2$$$. Our claim is that the number of nodes $$$v$$$ which have parity 1 equals the number that have parity 0.

Assume you have a tree with a perfect matching. Consequently, there must exist two vertices $$$u, v$$$ such that $$$u=par(v)$$$, $$$v$$$ is a leaf, and $$$v$$$ is the only child of $$$u$$$. Since node $$$v$$$ is node $$$u$$$'s only child, $$$parity(u)=0$$$ and $$$parity(v)=1$$$. Note that deleting nodes $$$u$$$ and $$$v$$$ from the tree

1. Doesn't change the parity of any other nodes in the tree
2. Subtracts 1 from the number of odd parity and even parity nodes in the tree.

Since the tree has a perfect matching, we can repeat this deletion operation on the tree until we get the empty graph. Since we deleted a node with parity 1 and a node with parity 0 in each operation, the original graph must have had an equal number of nodes with parity 0 and parity 1.

To prove the reverse direction, we assume that the number of nodes which have parity 1 equals the number which have parity 0. Since $$$size(v) = 1 + \sum size(u)$$$ for all children $$$u$$$ of $$$v$$$, a node with parity 0 must have a child with parity 1. Matching each node of parity 0 to one of their children which has parity 1, we end up with a perfect matching of the tree, since the number of nodes with parity 1 equals the number with parity 0. Thus, having the number of nodes with parity 0 equal the number with parity 1 implies that the tree has a perfect matching.

Combining the two lemmas, the tree is solvable if and only if the number of nodes with parity 0 equals the number of nodes with parity 1. To process each query, we need a data structure which can add a node to the tree and flip the parity of each node on the path from the root to the added node. After each query, we simply check if the number of nodes with each parity is equal. We can use heavy-light decomposition with segment trees to achieve this in $$$O(n\log n + q \log^2 n)$$$.