By performing the operation, try to break a block into $$$2$$$ blocks.

The only way to increase the count of blocks is to break a block into $$$2$$$ blocks by performing an operation such that some characters of a block are present at the start of the string and some characters at the end of the string. For us to be able to achieve this, there must exist at least one block with a size greater than or equal to $$$2$$$. But, if in the original string, the first and the last character are already equal, this means a block is already broken into $$$2$$$ block (in some other rotation, it will be one block). Hence in this case the answer will be the score of the original string.

Inshort, if first and the last character of the string are equal, or no $$$2$$$ adjacent characters are equal, then the answer will be score of the original string. Else the answer will be score of the original string $$$+ 1$$$.

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

What is the condition for -1?

If the length of the string is odd and the count of 1 is odd, then and only then the answer will be -1.

First of all, flipping a bit an even number of times is equivalent to not flipping the bit at all, and flipping a bit an odd number of times is equivalent to flipping the bit just one time. So, to make all the bits equal to $$$0$$$, we have to make sure we flip all the $$$0$$$ bits an even number of times and all the $$$1$$$ bits an odd number of times.

One of the ways to achieve this is, if the count of $$$0$$$ bits in the string is odd, then apply the operation on all the $$$0$$$ bits. If the count of $$$0$$$ bits in the string is even and the count of $$$1$$$ bits in the string is also even, then apply the operation on all the $$$1$$$ bits. If the count of $$$0$$$ bits in the string is even and the count of $$$1$$$ bits in the string is odd, then after applying any operation, the count of $$$0$$$ bits will always stay even. But the length of the string in this case is odd which means we cannot make all the bits equal to $$$0$$$. Hence in this case the answer will be $$$-1$$$.

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

If an entire magazine is used, then the operation does not change the total damage dealt or the time used by that magazine. Hence, the operation mainly impacts only the last magazine.

For us to be able to kill the enemy using only $$$i$$$ bullets from the last magazine, what is the necessary condition? Also, what would be the most optimal operation for this?

First, calculate the total damage an entire magazine deals, which is sum of the array $$$a$$$. We will have to use at least $$$h/sum$$$ magazines. Now, the remaining health of the enemy would be $$$h$$$ modulo $$$sum$$$. If the remaining health is $$$0$$$, then we don't need to worry about the operation.

If the remaining health is greater than $$$0$$$, then we will try to perform an operation that can minimise the number of bullets required in the last magazine. For every $$$i$$$ from $$$1$$$ to $$$n$$$, we will check if we can kill the enemy using only $$$i$$$ bullets from the last magazine. When checking for the index $$$i$$$, the most optimal operation will always be to swap $$$min(a_0, a_1,\ldots a_i)$$$ and $$$max(a_{i+1}, a_{i+2},\ldots a_n)$$$. If $$$min(a_0, a_1,\ldots a_i) \gt max(a_{i+1}, a_{i+2},\ldots a_n)$$$, then it is optimal to not perform the operation for this $$$i$$$. After performing the operation (or not performing), if $$$sum(a_0, a_1,\ldots a_i)$$$ becomes less than or equal to the remaining health, then it is possible to kill the enemy using only $$$i$$$ bullets from the last magazine. The smallest $$$i$$$ satisfying this condition gives us the most optimal answer.

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

How to solve the problem for all subtrees without considering the operation?

Answer of hint $$$1$$$: If $$$cost(i)$$$ represents the cost of subtree with root $$$i$$$, and $$$sum(i)$$$ represents the sum of value of all nodes present in the subtree with root $$$i$$$, then $$$cost(i)$$$ is the summation of $$$cost(j) + sum(j)$$$ for all nodes $$$j$$$ that are children of node $$$i$$$.

Now for the operation, for a chosen node $$$u$$$, once the edge between node $$$u$$$ and the parent of node $$$u$$$ is removed, always choose node $$$v$$$ as the node present in the subtree with root as parent of node $$$u$$$, and having maximum $$$d($$$parent of node $$$u$$$, $$$v)$$$ (distance from partent of node $$$u$$$). Do this for all possible node $$$u$$$.

This problem can be solved in a single DFS on the tree. In the DFS, each node will calculate $$$2$$$ things for it's subtree, cost without performing operation and the maximum cost with operation already performed in the subtree.

For calculating cost without performing operation, as compared to the child, the value of $$$d(r, i)$$$ (distance of $$$i$$$ from $$$r$$$) increases by $$$1$$$ for the parent, where $$$i$$$ are all the nodes present in the subtree of child. $$$d(r, i)$$$ increasing by $$$1$$$ means adding $$$a_i$$$ once, as per the equation of the cost of the tree. And adding $$$a_i$$$ once for all nodes present in the subtree means adding sum of values of all nodes present in the subtree once. So, cost of parent $$$=$$$ summation of cost of $$$j$$$ + $$$sum(j)$$$ for all nodes $$$j$$$ that are children of the parent, where $$$sum(j)$$$ represents the sum of value of all nodes present in the subtree of $$$j$$$.

For calculating the maximum cost with operation already performed in the subtree, what the operation does is, it changes the value of $$$d(r, i)$$$ for all nodes $$$i$$$ present in the subtree of node $$$u$$$ (nodes $$$u$$$ and $$$v$$$ are described in the operation). To maximize the cost, we have to increase $$$d(r, i)$$$ by the maximum possible value. And if the value of $$$d(r, i)$$$ is increased by $$$x$$$, for all nodes $$$i$$$ present in the subtree of node $$$u$$$, it means the cost of tree increases by $$$sum(u) * x$$$. Hence, for a chosen node $$$u$$$, node $$$v$$$ should be the node with the maximum depth in the remaining tree. At this point, if node $$$v$$$ does not lie in the subtree of parent of node $$$u$$$, then it will always be optimal to choose parent of $$$u$$$ as node $$$u$$$ (because this increases $$$sum(u)$$$). We can keep doing this, until node $$$v$$$ lies in the subtree of parent of node $$$u$$$. Hence, if we try performing operation for each node $$$u$$$, and node $$$v$$$ is always chosen as the node with the maximum depth present in the remaining subtree of parent of node $$$u$$$, and we take the maximum cost across all these operations, we will always get the maximum cost of the tree we can achieve. In the DFS, for subtree of $$$r$$$, we only need to calculate cost by performing operations for node $$$u$$$, where node $$$u$$$ are children of node $$$r$$$. For all other nodes present in subtree that can be the node $$$u$$$, the maximum cost with operation already performed in the subtree of children of node $$$r$$$ would have already taken care of this.

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

Graph problem?

Eulerian cycle?

Make $$$a$$$ a rearrangement of $$$b$$$ means the frequency of all numbers present in array $$$a$$$ should be equal to the frequency of all numbers present in array $$$b$$$. For this to be possible, the combined frequency of all numbers present in array $$$a$$$ and array $$$b$$$ should be even. If at least one number has combined frequency as odd, the answer will be $$$-1$$$.

Now, if the answer is not $$$-1$$$, let's see how to perform the operations. Create a graph with $$$n$$$ nodes and $$$n$$$ directed edges from node $$$a_i$$$ to $$$b_i$$$. The operation swap $$$a_i$$$ and $$$b_i$$$ means the direction of the $$$i$$$-th edge is reversed in the graph. This means, for each edge any direction is possible. Hence, we can consider the graph as an undirected graph, which we need to convert to a directed graph. In other words, we need to decide the direction of all the edges.

In the directed graph, the indegrees and outdegrees of a node $$$i$$$ actually mean the frequency of $$$i$$$ in array $$$a$$$ and array $$$b$$$ respectively. Our problem is to make the frequency of each number in array $$$a$$$ equal to array $$$b$$$, which means to make the indegrees of each node equal to its outdegree.

Since, the combined frequency of all numbers is even, it means the degree of each node in the undirected graph is even. This means the graph contains Eulerian cycles. Each connected component can be treated like a separate graph (because it is possible that our graph is not a single connected component), and find Eulerian cycle in all these graphs. Keep assigning direction to the edges in the direction used in the Eulerian cycle and hence accordingly perform the operations.

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

DP?

Try solving the problem in $$$2$$$ phases. Phase $$$1$$$, when Alice's fish and Bob's fish are not adjacent to each other, and phase $$$2$$$, when they are adjacent to each other.

First, let's solve the problem for phase $$$1$$$ (fish $$$A$$$ (Alice's fish) and fish $$$B$$$ (Bob's fish) are not adjacent to each other):

We will maintain $$$2$$$ separate $$$dp$$$, one for each player. Both the $$$dp$$$ work independently of each other. Each $$$dp$$$ will have $$$2$$$ states $$$l$$$ and $$$r$$$, denoting the fish has eaten all other fishes present in the range $$$[l, r]$$$, and $$$dp[l][r]$$$ stores the probability of this happening (without considering the turns played by the other player's fish). This means, the size of the fish has increased by the sum of $$$b_i$$$ for all $$$i$$$ present in the range $$$[l, r]$$$ and $$$i$$$ not equal to the original position of the fish ($$$x$$$ for fish $$$A$$$ and $$$y$$$ for fish $$$B$$$).

From $$$dp[l][r]$$$ we can go to $$$dp[l - 1][r]$$$ and $$$dp[l][r + 1]$$$. But if both the adjacent fishes (fish $$$(l - 1)$$$ and fish $$$(r + 1)$$$) have a larger size and can't be eaten, then in this case the player's fish gets eaten and loses. Hence this directly contributes to the answer without going to the phase $$$2$$$ (only if due to this the fish $$$A$$$ wins). But in this case, we can't directly add $$$dp[l][r]$$$ to the answer as we need to ensure that the other fish is still alive.

Let's say, $$$dpA$$$ and $$$dpB$$$ represents $$$dp$$$ of fish $$$A$$$ and fish $$$B$$$ respectively, and $$$la$$$ and $$$lb$$$ represent $$$l$$$ of fish $$$A$$$ and $$$B$$$ respectively, and $$$ra$$$ and $$$rb$$$ represent $$$r$$$ of fish $$$A$$$ and $$$B$$$ respectively.

If from $$$dpB[lb][rb]$$$ the fish $$$B$$$ can't eat any of the adjacent fish and hence fish $$$B$$$ is going to get eaten, then

$$$probabiliityB = dpB[lb][rb]$$$

At this point, fish $$$B$$$ occupies subarray of length $$$rb - lb + 1$$$, which means fish $$$B$$$ has played a total of $$$rb - lb$$$ turns. Corresponding to this, the fish $$$A$$$ would have played $$$rb - lb + 1$$$ turns (since they play alternate turns starting from fish $$$A$$$). So, we need to find the probability that the fish $$$A$$$ is not a neighbor of fish $$$B$$$ and fish $$$A$$$ is still alive (fish $$$A$$$ occupies subarray of length $$$rb - lb + 2$$$). Considering fish $$$A$$$ is present to the right of fish $$$B$$$, for fish $$$A$$$ to not be a neighbour of fish $$$B$$$, $$$la$$$ should be at least $$$rb + 2$$$. And for fish $$$A$$$ to occupy subarray of length $$$rb - lb + 2$$$, $$$ra$$$ should be equal to $$$la + (rb - lb + 1)$$$. Hence,

$$$probabiliityA =$$$ summation of $$$dpA[la][ra]$$$ (for all $$$la \ge rb + 2$$$ and corresponding $$$ra \le n$$$)

We can similarly calculate when fish $$$A$$$ is towards the left of fish $$$B$$$. We can maintain prefix sum and suffix sum to get these summations in $$$O(1)$$$ time.

We will add $$$probabiliityA * probabiliityB$$$ directly to the final answer without going to the second phase.

No need to do these things when fish $$$A$$$ can't eat any of the adjacent fish and hence fish $$$A$$$ is going to get eaten, because this increases the answer by $$$0$$$ as we need to calculate the probability of fish $$$A$$$ winning and not the probability of $$$A$$$ losing.

Now, let's solve the problem for phase $$$2$$$ (fish $$$A$$$ and fish $$$B$$$ are adjacent to each other):

For this, we will maintain a single $$$dp$$$. The states of the $$$dp$$$ will be $$$la$$$ and the total number of turns played (combined of both fish $$$A$$$ and $$$B$$$). Since both the fishes are adjacent to each other, from only these $$$2$$$ states we can calculate all $$$4$$$ states ($$$la, ra, lb, rb$$$). In phase $$$1$$$, when fishs $$$A$$$ and $$$B$$$ get adjacent to each other, the corresponding probability $$$(probabilityA * probabilityB)$$$ can be added to this $$$dp$$$ of phase $$$2$$$. If the total number of turns played is $$$c$$$, then in this $$$dp$$$, either we can move to $$$dp$$$ with state $$$c + 1$$$ (and correspondingly the other state $$$la$$$ can also change), or the fish eats the other player's fish, or it gets eaten by it's adjacent fishes. In the latter $$$2$$$ cases, if the fish $$$A$$$ wins, then we can add the probability of this happening in the final answer.

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

Space complexity: $$$O(n^2)$$$