Pythagoras' theorem.

We know a triangle is right-angled if and only if it satisfies Pythagoras' theorem. In other words, the given triangle is right-angled when $$$x^2 + y^2 = z^2$$$, where $$$z$$$ is the largest side-length and $$$x, y$$$ are the smaller side-lengths.

Iterate through the array and cut subarrays when suitable.

Let $$$total$$$ be the sum of all elements of the array, and let $$$target = \frac{total}{k}$$$. Of course, if $$$target$$$ is not an integer then a partition is not possible. Otherwise, we can iterate through the array maintaining a $$$sum$$$ variable which will contain the sum of all elements of our current subarray. As we iterate through the array, whenever $$$sum$$$ equals $$$target$$$ we can split off into a new subarray and reassign $$$sum = 0$$$. On the other hand, if $$$sum$$$ exceeds $$$target$$$ without equalling it, it is easy to see that a partition is not possible.

If we reach the end of the array without $$$sum$$$ ever exceeding $$$target$$$, then and only then do we have a valid partition of the array.

Think of maintaining pointers for each of the 26 letters.

We can solve this problem by simply maintaining the positions of the last and the second-last index for each of the 26 letters. Let us store the last and second-last indices where the character $$$ch$$$ appears in $$$l[ch]$$$ and $$$sl[ch]$$$ respectively, and let $$$x[i]$$$ be the number of amicable substrings at index $$$i$$$.

We will iterate through the string, and when we reach index $$$i$$$ we will need to calculate $$$x[i]$$$. Note that $$$x[i]$$$ is basically the count of all indices which do not belong to the union of $$$[sl[j], l[j]]$$$, for all letters $$$j$$$. This is because the union is precisely the set of indices where at least one of the characters appears exactly once.

Now initially, we can set $$$x[i] = x[i - 1]$$$ and let $$$ch$$$ be the character at index $$$i$$$. Then, as we iterate through $$$sl[ch] + 1$$$ to $$$l[ch]$$$ (note that both these values have not yet been updated for index $$$i$$$), we can increment $$$x[i]$$$ if that index does not belong to any other interval $$$[sl[j], l[j]]$$$ for some letter $$$j$$$. We can do this by maintaining an array $$$cnt[k]$$$, which counts the number of such intervals index $$$k$$$ belongs to, and keep updating it as we iterate through $$$[sl[ch] + 1, l[ch]]$$$.

Similarly, we can iterate through $$$l[ch] + 1$$$ to $$$i$$$, and decrement $$$x[i]$$$ if that index does not belong to any other interval $$$[sl[j], l[j]]$$$. Again, we should also update $$$cnt$$$ as we iterate through $$$[l[ch] + 1, i]$$$. Finally, we can update $$$sl[ch]$$$ and $$$l[ch]$$$ to their new values, and keep repeating this process. The final answer will thus be the sum of all $$$x[i]$$$. Note that for each letter, we only iterate through the array twice. Thus, the time complexity is $$$O(26n)$$$.

Think of a DP solution, through which we can exclude blocked paths.

We can solve this problem through dynamic programming. Let $$$dp[i]$$$ denote the number of paths from $$$(0, 0)$$$ to $$$(x_i, y_i)$$$ which does not pass through blocked points. We can consider our destination point $$$(x, y)$$$ as $$$(x_{n+1}, y_{n+1})$$$, thus $$$dp[n + 1]$$$ will be our final solution. Note that we can move only in the forward direction for both $$$x$$$ and $$$y$$$ axes. Thus, to calculate $$$dp[i]$$$, we can take all paths to $$$(x_i, y_i)$$$ and one-by-one subtract the paths that pass through a blocked point.

To do this, we need to calculate the number of paths we can take from some point $$$(a, b)$$$ to another point $$$(c, d)$$$, where each step follows either of the two operations. To remind you, the operations consist of choosing one of the $$$x$$$ or $$$y$$$ coordinates, and switching on some off bits in that coordinate. Thus, if we wish to go from $$$(a, b)$$$ to $$$(c, d)$$$ then $$$a | c = c$$$ and $$$b | d = d$$$ must hold. Further, it is easy to see that the answer only depends on the number of extra bits switched on in $$$c$$$ and $$$d$$$. Thus, let us say we calculate a matrix $$$ways[i][j]$$$ which contains the number of possible paths that we can take to go to the points with $$$i$$$ (and $$$j$$$) extra bits switched on in the $$$x$$$ (and $$$y$$$) coordinate. Then,

where $$$\text{bits}(x)$$$ denotes the number of on bits in $$$x$$$.

We are now left to calculate $$$ways[i][j]$$$. Assume that $$$a$$$ and $$$b$$$ are the total numbers of moves made towards the $$$x$$$ and $$$y$$$ axes, respectively. We can then compute $$$ways[i][j]$$$ by iterating over all possible values of $$$a$$$ and $$$b$$$.

We need to define another matrix $$$cnt[i][j]$$$ to complete our computations. Let $$$cnt[i][j]$$$ denote the number of ways in which we can turn on $$$i$$$ bits in exactly $$$j$$$ moves. It is easy to calculate this by inclusion-exclusion principle, we start by assigning any of the $$$j$$$ moves to each bit for a total of $$$j^i$$$ ways. We can then successively add and subtract $$$\binom{j}{r}(j-r)^i$$$, the number of ways for which $$$r$$$ of the moves were not assigned any of the $$$i$$$ bits. In particular:

This implies,

Thus all the computations are handled. What is the time complexity of this solution? Well, we needed $$$O(\log(x_i)^3)$$$ to compute $$$cnt$$$, $$$O(\log(x_i)^4)$$$ to compute $$$ways$$$ (here $$$\log(x_i)$$$ is the number of bits in $$$x_i$$$ and $$$y_i$$$), and also $$$O(n^2)$$$ to compute $$$dp$$$. Thus, the final complexity is $$$O(n^2 + \log(x_i)^4)$$$. As the number of bits in $$$x_i$$$ and $$$y_i$$$ can only be upto $$$64$$$, it is sufficient.

Binary Search

Let us summarize the statement in short first. Given a set of $$$N$$$ robots on the number line with some position and velocity, we need to remove at most $$$M$$$ of them to delay the first collision for as long as possible. In other words, we need to find the largest time $$$T$$$ for which any $$$N-M$$$ robots can survive without crashing into each other for $$$T$$$ seconds.

Consider the maximum number of robots that may survive till a time instant. It is easy to see that this number either stays constant or decreases with increasing time. This hints towards a binary search solution. If we can efficiently calculate for a given time instant $$$T$$$, the maximum number of robots that may survive without crashing, we can solve the problem.

Consider two initial robots which started at positions $$$x_1$$$ and $$$y_1$$$ at time $$$t = 0$$$, and ended at positions $$$x_2$$$ and $$$y_2$$$ at time $$$t = T$$$. WLOG, let $$$x_1 < y_1$$$. We can observe that if a collision occurred between these two robots then it must be the case that $$$x_2 > y_2$$$. This observation enables us to solve the problem efficiently enough.

We can simply sort the initial positions of the robots. At a time instant $$$T$$$, let us create a vector of their new positions. The maximum number of robots that can survive till time $$$T$$$ is simply the longest increasing subsequence of this sequence of positions!!

Regarding the accuracy of the answer, we can multiply the initial positions by $$$10^5$$$ and binary search only over integer time instants. The maximum time delay for a collision will be $$$10^8$$$ seconds, or $$$10^{13}$$$ seconds using the modified initial positions.

Time Complexity: $$$O(NlogNlogA)$$$ where $$$A = 10^{13}$$$.

KMP Automaton

First, if we ignore the lexicographically minimum condition, then we only need to count unique strings. A string is a unique string if and only if there is $$$t$$$ and $$$n$$$ where $$$n>1$$$ such that $$$t^n=s$$$.

Let us use $$$\Sigma$$$ to denote the set of all characters. If we just need to count the number of unique strings, then we can simply do this by a Mobius transform between $$$|\Sigma|^n$$$ and $$$\mu$$$, where $$$\mu$$$ is the Mobius function.

To handle the condition of beauty let's first solve another problem where given a string $$$p$$$, you need to count the number of beautiful and unique strings with prefix $$$p$$$ and length less than or equal to $$$n$$$.

To do this, we can build the KMP automaton over the string $$$p$$$. For any node, if multiple edges are going outside of it, then we should delete all the edges except the one with the largest character, whereby dynamic programming would give us the required answer.

To solve the original problem, we will iterate one by one through all the possible prefixes, starting with the string given in the input. We will count the number of the beautiful and unique strings starting with this prefix; if this is less than the count, then increase the last character of the string, and decrease k by this count. and repeat. Otherwise, add 'a' to the end of the string, and repeat the procedure.

The whole procedure can be done in $$$O(n^4 |\Sigma|)$$$.