The problem asks to place $$$n$$$ fishies into a $$$15\times25$$$ tank (including the borders). One way that we can accomplish this is by placing a single fishy at the beginning of rows $$$2$$$ to $$$n+1$$$, and no fishies in rows $$$n+2$$$ to $$$14$$$. This works since at most $$$10$$$ rows will have fishies (one for each fishy) and we have $$$13$$$ rows to work with. Make sure to print the border of the tank properly.

Fun fact, the judge solution places the fishies uniformly at random into the tank. You can view this solution here. (It is definitely not the simplest solution, but the output looks really nice)

We can use a range query data structure to solve this problem. We are interested in two values: the sum of all previous numbers that are less than $$$c_i$$$, and the count of all previous numbers that are less than $$$c_i$$$. With these two values, we may add $$$c_i \cdot cnt$$$ and $$$sum$$$ to get the sum of all previous values lesser than $$$c_i$$$, plus $$$c_i$$$. To get $$$cnt$$$ and $$$sum$$$, we can use two Segment Trees or Fenwick Trees that lets us query the count and sum of cards less than $$$c_i$$$. For the count tree, query the sum from index 1 to $$$i$$$, then update index $$$c_i$$$ to value 1 after processing the card. For the sum tree, query the sum from index 1 to $$$i$$$, then update index $$$c_i$$$ to value $$$c_i$$$ after processing the card. In total, we will make $$$n$$$ queries with each being $$$\log n$$$ complexity, letting us solve this problem in $$$O(N \log N)$$$.

Given a substring $$$p$$$ of $$$s$$$, we want to find the size of the union of the indices contained in substrings of $$$s$$$ that equal $$$p$$$. Intuitively we can picture the matching substrings as intervals of equal length, and we want to know how many indices are covered by the intervals.

To categorizes the substrings of $$$s$$$ by their matches, I used a suffix automaton, but a suffix array can be used with the exact same result (they both serve the same purpose here), so I will refer to the suffix automaton version. The suffix automaton has $$$O(n)$$$ nodes, and each node represents both a set of ending indices, combined with a range of lengths for which substrings ending at all such ending positions are matching. Suppose we want to only look at one node, and suppose we can afford to iterate over all of the endpoints that the node contains. Also suppose that the query string lies inside this node of the automaton. Then, if the length of the query string is $$$x$$$, we can divide the answer to the query into a sum of contributions from each endpoint in this node. Moreover, for an endpoint $$$i$$$, let $$$j$$$ be the largest endpoint in the node that is less than $$$i$$$ (or $$$-1$$$ if $$$i$$$ is the smallest endpoint). Then, the contribution of endpoint $$$i$$$ will be $$$\min(x, i - j)$$$. This is a piecewise linear function, and if we add up the individual functions for each endpoint, we obtain a function for the answer (for queries that refer to substring in this node).

We now want to find an efficient way to store this function, if we want any hope of being able to extend the idea to all nodes in the automaton. My first approach (which passes but is quite slow) uses a sparse segment tree equipped with the operations defined in this problem. The range sum is overkill since we only need a point sum to answer a query, so I implemented the segment tree such that it isn't lazy in order to reduce the overhead. This gives us the ability to add and subtract individual functions to the entire function in $$$O(\log n)$$$ time, as well as to answer queries in $$$O(\log n)$$$ time.

Now we need to find a way to extend this idea to all nodes in the automaton. The suffix link tree is the tree formed by suffix links in the suffix automaton, where the suffix link of a node is a pointer to its parent node. We also know that each endpoint appears exactly in the nodes on some path from the root to the node created upon processing the endpoint during the suffix automaton creation. So, we can build the function for lower nodes in the tree, and then obtain the function for higher nodes with small-to-large merging. When merging one function into the other, we need to consider how the individual functions change as a result of inserting new endpoints. Specifically, if we add an endpoint $$$i$$$, then we want to look for the largest endpoint in the set that is less than $$$i$$$ and the smallest endpoint in the set that is greater than $$$i$$$. Let these be $$$l$$$ and $$$r$$$ respectively, either of which may not exist. If both $$$l$$$ and $$$r$$$ exist, then we want to subtract the function $$$\min(x, r - l)$$$. Then, if $$$r$$$ exists we will add the function $$$\min(x, r - i)$$$. Likewise, if $$$l$$$ exists we will add the function $$$\min(x, i - l)$$$. This gives us a way to merge the segment trees efficiently, and since merging adds an additional $$$O(\log n)$$$ factor to the entire tree traversal, we obtain a complexity of $$$O(n \log^2n)$$$ for maintaining the functions across all nodes in the automaton.

That was the hardest part. All we have left is to determine which queries belong to which node. Since the solution already has a complexity of $$$O(n \log^2n)$$$, I just maintained priority queues in each node and did independent small-to-large merging on them. This also has complexity $$$O(n \log^2 n)$$$, but other methods such as binary lifting can be used to achieve $$$O(n \log n)$$$ complexity for this part. In total the solution has complexity $$$O(n \log^2 n)$$$.

You can see my solution using this approach here.

Merging sparse segment tree is quite overkill still for what we need to accomplish, since we can recognize that the queries will be strictly decreasing (due to the strictly decreasing size property of the suffix automaton nodes as we traverse upwards). Thus, we can sort of use slope trick, where we maintain the slope-changing points of the piecewise linear function in an ordered set, and to process a query we remove the largest slope-changing points until we reach the query size.

You can see my improved solution using this idea here.

The problem involves selecting a subset of building expansion proposals along Austin's East–West highway such that no two approved proposals are closer than a given distance $$$d$$$. Each proposal is located at a distinct integer coordinate $$$x_i$$$ and has an associated profit $$$p_i$$$. The objective is to maximize the total profit while adhering to the spacing constraint, ensuring that if a proposal at $$$x_i$$$ is chosen, no other proposal within a distance $$$d$$$ from $$$x_i$$$ can be selected.

It is natural here to think about this as a dynamic programming problem with the help of a pointer to keep track of the distance requirements. Sorting is crucial because it allows the use of a two-pointer method to quickly find the last proposal that does not conflict with the current one based on the minimum distance $$$D$$$.

$$$\texttt{dp}[i]$$$ is maintained, where $$$\texttt{dp}[i]$$$ represents the maximum profit achievable considering proposals up to the $$$i$$$-th proposal (in sorted order). As the main loop iterates through each proposal $$$i$$$, a secondary pointer $$$j$$$ is used to advance through proposals that are far enough from $$$i$$$ (i.e., where the distance condition $$$\text{points}[i].\text{first} - \text{points}[j].\text{first} \ge D$$$ holds). The variable $$$\texttt{mx}$$$ keeps track of the maximum profit among these valid proposals. Consequently, the state transition is simply:

with $$$p_i$$$ being the profit of the $$$i$$$-th proposal. The overall answer is the maximum value found in the DP array.

Notice that the furthest point from a given line must lie on the convex hull of the points. Furthermore, there are at most two disjoint points where the angle of the hull is closest to being parallel to the line. Thus, we can sort both the queries and the lines between points on the hull by slope, and use rotating calipers or two pointers to find the two candidates for the furthest point. We can check the distance of both candidates to obtain the answer to a query.

Consider a normal DP implementation of this problem. We can define a DP state $$$dp[i][j][k]$$$ to be the probability that Michael is headed towards position $$$i$$$, arriving there in $$$j$$$ more minutes, and the current time is $$$k$$$ minutes. This means that when $$$j$$$ is 0, Michael is at position $$$i$$$ and ready to move to another location. This way, we model each edge as 1. an instant move from one location to another and 2. a wait for a certain amount of time. The transition states would be defined in one of 2 cases:

• If Michael is at state $$$dp[i][0][k]$$$, then he will choose to go along any of the edges adjacent to $$$i$$$ with probability $$$\frac{1}{\text{deg}(i)}$$$. If he chooses to go along an edge to $$$j$$$ with length $$$l$$$, then $$$dp[j][l-1][k+1]$$$ will be incremented by $$$dp[i][0][k]\cdot\frac{1}{\text{deg}(i)}$$$.
• If Michael is at state $$$dp[i][j][k]$$$ with $$$j\neq 0$$$, then he must continue to wait at position $$$i$$$, so $$$dp[i][j-1][k+1]$$$ will be incremented by $$$dp[i][j][k]$$$.

Note that each time, we must clear out $$$dp[n][0][k]$$$ and save that to the answer because Michael stops at position $$$n$$$.

However, this DP runs in $$$O(n^2\cdot \text{max}(t_i)\cdot k) = O(5n^2k)$$$, which is around $$$1.25\cdot 10^{10}$$$, so this is too slow.

We can instead use a matrix exponentiation approach. We will define a matrix $$$M$$$ of size $$$5n\times5n$$$. Here, we will compress the original $$$i$$$ and $$$j$$$ into a single state by doing $$$5i+j$$$, and then transform the DP transitions into transitions in this new matrix. $$$M[u][v]$$$ will be the probability that Michael will be at state $$$v$$$ starting from state $$$u$$$ after 1 minute. However, we must also consider the fact that Michael will stop moving after reaching position $$$n$$$. So, we will set $$$M[u][5(n-1)]$$$ to be 0 for all states $$$u$$$. We can imagine this is Michael leaving the matrix. Then after exponentiating the matrix $$$M$$$ to the $$$k$$$th power, we can find the answer by taking $$$1-\sum_{u=0}^{5n-1} M[0][u]$$$. This is because the sum of all probabilities must equal 1, so the complement of the sum of all probabilities that Michael is at any state $$$u$$$ is the probability that Michael is at state $$$n$$$.

This approach runs in $$$O((5n)^3\log k)$$$, which is around $$$3.11\cdot 10^8$$$, so this is fast enough.