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|)$$$.

//C++ implementation
#include <iostream>
#include <string>
using namespace std;

int main ()
{
    string s;
    cin >> s;
    if (s == "Apple") cout << "Gravity";
    else cout << "Space";
}

Let the number of rounds won by Nutan be $$$n$$$ and that won by Tusla be $$$t$$$. As $$$n + t = L$$$, we are given that $$$n + t$$$ is odd. Thus, we have $$$n \neq t$$$ as otherwise $$$n + t$$$ will be even. So we can see that there is no draw possible, one of Nutan or Tusla must have won more rounds than the other. To find whom, we first initialize $$$n = t = 0$$$. We will then iterate through each character of the string $$$S$$$. If the character is 'N', we increment $$$n$$$ by $$$1$$$, otherwise we increment $$$t$$$ by $$$1$$$. After we have finished iterating the string, if $$$n < t$$$ then Tusla has won, otherwise Tesla has won. You can refer to the following C++ implementation for better understanding.

//C++ implementation
#include <iostream>
#include <string>
using namespace std;

int main ()
{
    int l;
    string s;
    cin >> l >> s;

    int n = 0, t = 0;
    for (int i = 0; i < l; i++)
        if (s[i] == 'N') n++;
        else t++;

    if (n < t) cout << "Tusla";
    else cout << "Nutan";
}

We can think of the problem in a different way. Assume their exists a directed edge between any two adjacent nodes. And assume any cell as a node with some water capacity. So given problem can be thought of in the following way that some water flow starts from the cell $$$(1,1)$$$ and ends at the cell $$$(n,m)$$$. You have to print “YES” if water flow through every node is reaching its maximum capacity; otherwise, print “NO”

Some people may have analyzed the problem in this way and might have directly formed a flow graph and applied some fast max flow algorithm for bipartite graph and have got AC. But that is not required for this question.

This problem can be solved directly through simulation and by analysing whether the end result is valid flow or not?

Observation 1: As we know that, flow from any cell can go either down or right.

We can design the simulation in the following way.

Start from the first column, starting from the bottom-most cell We know that for flow to be valid amount of flow contribution in the cell will come from only the cell above it as there is no cell on the left of it. Hence we got the flow going through edge $$$(n-1,1)$$$ -> $$$(n,1)$$$.

Similarly now pick the cell $$$(n-1,1)$$$ and find the flow going through edge $$$(n-2,1)$$$ -> $$$(n-1,1)$$$. In this way, we can find flow through all vertical edges in the first column.

Now, as we know for any cell in the first column how much flow is going down from it, we can easily find that rest of the flow from any cell is going to the cell right of it. Hence for all $$$(i,1)$$$->$$$(i+1,1)$$$ horizontal edges we got the amount of flow passing through it. Hence by going in this way further, let’s pick the second column and lets analyse this. Again pick the bottom-most cell in the column, and as we know how much flow is coming in it from the cell left of it, so we can find that rest of flow that has to go inside it will come from the cell above it. Similarly, we can analyze the whole distribution in the second column by repeating this procedure.

Now similarly repeating this procedure, we can analyze the distribution for all columns.

Hence we will get flow through all vertical and horizontal edges.

Condition of validity: Flow-through any of the edges should be non-negative because edges are directed. Flow of any cell should be equal to the total flow going out of it through both of its outdirected horizontal and vertical edges.

Flow of any cell should be equal to the total flow going inside of it through both its horizontal and vertical edges.

These conditions are also sufficient conditions because if they followed, then we have got the exact distribution of flow in the grid.

Time complexity: $$$O(n*m)$$$ As we are iterating through the whole grid once and finding flow through every edge in $$$O(1)$$$ hence overall complexity should be $$$O(n*m)$$$.

~~~~~

Consider the vertices in topological order. If there are multiple vertices on which you can do an operation, which one should you choose?

Note that the given graph is a DAG. Thus, any particular chip will move at most $$$n$$$ times as it cannot visit any vertex twice. So we can see that the score can be at most at $$$n$$$ times the total number of chips. As $$$a_i \leq 10^5$$$, in this problem the score will not exceed $$$10^{15}$$$ so the answer can fit in a 64-bit integer datatype.

Consider a topological sorting $$$\{p_i\}$$$ of the given DAG, i.e. an edge from $$$p_i$$$ to $$$p_j$$$ implies $$$i < j$$$. A crucial observation here is that if a vertex $$$i$$$ at any point has more than $$$d_i$$$ chips, where $$$d_i$$$ is its outdegree, then it can never be chosen for a move again as the number of chips at that vertex can only ever increase. Let us call such a vertex saturated. The optimal strategy for this game is to always perform a move on the vertex that comes last in the topological sorting, among all vertices that have chips equal to their outdegree. This is quite intuitive as if we pick an earlier vertex, it is possible that some vertices which came after it and were not already saturated, may become saturated. However, if we always start with the last vertex, a vertex that is not saturated will never become saturated.

We can prove that the strategy is optimal as follows. Let $$$x_i$$$ be the number of moves performed at vertex $$$i$$$ over the entire duration of the game. If vertex $$$i$$$ is saturated at the beginning, then obviously $$$x_i = 0$$$. Otherwise, if the vertices from whom there exists an edge to $$$i$$$ are $$$v_1, v_2, .. v_k$$$ then:

This holds as the total number of chips that ever visit vertex $$$i$$$ is $$$a_i + x_{v_1} + x_{v_2} + ... x_{v_k}$$$, and in each move we may distribute only $$$d_i$$$ of those. Thus, the total number of moves at $$$i$$$ can be at most $$$\lfloor\frac{a_i + x_{v_1} + x_{v_2} + ... + x_{v_k}}{d_i}\rfloor$$$. It is also easy to show that equality is reached when we adopt the above strategy. This is because whenever the total number of chips at vertex $$$i$$$ becomes $$$d_i$$$, no new chip is added until a move is performed on $$$i$$$. Hence, if we proceed in the topological ordering we can show inductively that for any unsaturated vertex $$$i$$$, $$$x_i$$$ takes its maximum value as $$$\lfloor\frac{a_i + x_{v_1} + x_{v_2} + ... + x_{v_k}}{d_i}\rfloor$$$, as by induction hypothesis the values $$$x_{v_1}, x_{v_2}, ... x_{v_k}$$$ are already the greatest possible, and by the inequality above so is $$$x_i$$$. We can compute our final answer as $$$x_1 + x_2 + ... + x_n$$$.

The second part of the question is quite simple. To increase the maximum score, we only need to increase the number of moves performed on any one vertex. Thus, for any vertex $$$i$$$, if we increase $$$a_i$$$ by $$$d_i - ((a_i + x_{v_1} + x_{v_2} + ... x_{v_k}) \mod {d_i})$$$ and if so $$$a_i$$$ does not increase beyond $$$d_i$$$, our score will increase. The answer will be the minimum of all such values.

Consider the prefix xors. What conditions do you need on them?

Think of a DP. If you have one, is there any dimension that you can get rid of?

Let us assume $$$\{a_i\}_{i = 1}^n$$$ to be an array with exactly $$$k$$$ zero-xor subarrays, and $$$\{p_i\}_{i = 0}^n$$$ be the prefix xor, i.e. $$$p_i = a_1 \oplus a_2 ... \oplus a_i$$$. The condition that a subarray $$$[l, r]$$$ has xor zero is equivalent to $$$p_{l - 1} \oplus p_r = 0$$$, or $$$p_{l - 1} = p_r$$$. Thus, the number of zero-xor subarrays of $$$\{a_i\}$$$ is equal to the number of pairs $$$(i, j)$$$ such that $$$0 \leq i < j \leq n$$$ and $$$p_i = p_j$$$. Note that $$$p_0 = 0$$$ here. Now, let $$$b_x$$$ denote the number of elements of $$$p_i$$$ that are equal to $$$x$$$. Thus, the number of zero-xor subarrays will be:

where we know $$$b_0 + b_1 + ... = n + 1$$$.

We also need to ensure that all integers in $$$\{a_i\}$$$ are non-zero. This is equivalent to $$$p_{i - 1} \neq p_i$$$ for each $$$i$$$ satisfying $$$1 \leq i \leq n$$$. So suppose we have the sequence $$$\{b_i\}_{i = 0}^\infty$$$, what conditions it needs to satisfy so that we can find a corresponding sequence $$$\{p_i\}$$$ with no consecutive equal elements? You can easily show that it is $$$b_i \leq \lceil \frac{n}{2} \rceil$$$ for all $$$i \geq 1$$$ and $$$b_0 \leq \lceil \frac{n + 1}{2}\rceil$$$. Thus, our problems reduces to finding whether there exists a non-negative sequence $$$\{b_i\}_{i = 0}^\infty$$$ such that:

We can simplify the last two conditions to $$$b_i \leq \lceil \frac{n + 1}{2} \rceil$$$ for all $$$i$$$. If $$$n$$$ is odd then, $$$\lceil \frac{n}{2} \rceil = \lceil \frac{n + 1}{2} \rceil$$$. If $$$n$$$ is even, then at most one $$$i$$$ can $$$b_i$$$ be equal to $$$\lceil \frac{n + 1}{2} \rceil$$$. If that $$$i > 0$$$, we can always swap $$$b_0$$$ and $$$b_i$$$ and have a valid sequence. Thus, for each query we only need to determine if there exists a sequence $$$\{b_i\}_{i = 0}^\infty$$$ of non-negative integers satisfying:

$$$O(n^4)$$$ solution

This leads us to a DP solution, where we let $$$dp[i][j][sum]$$$ denote whether there exists a sequence $$$\{b_i\}$$$ such that:

with the transition, $$$dp[i][j][sum] = dp[i - 1][j][sum] \text{ OR } dp[i][j - i][sum - \binom{i}{2}]$$$. However, as $$$sum$$$ takes $$$O(n^2)$$$ values, this is an $$$O(n^4)$$$ solution. We can optimize it to $$$O(n^4/64)$$$ using bitsets, however it is still quite large.

$$$O(n^3)$$$ solution

A simple observation here will lead us to a $$$O(n^3)$$$ solution. Note that if we have a sequence $$$\{b_i\}_{i = 0}^\infty$$$ of non-negative integers satisfying:

where $$$s \leq n + 1$$$, then we can generate another sequence satisfying our original constraints, i.e. with $$$s$$$ replaced by $$$n + 1$$$. This can be done by arbitrarily making some $$$b_i$$$'s which were zero to one. Using this observation we can formulate another DP as follows: $$$dp[i][j]$$$ denotes the minimum $$$s$$$ such that there exists $$$\{b_i\}$$$ satisfying:

The transitions now become $$$dp[i][j] = min(dp[i - 1][j], dp[i][j - \binom{i}{2}] + i)$$$. Now each query can be answered in $$$O(1)$$$ time. If $$$dp[\lceil \frac{n + 1}{2} \rceil][k] \leq n + 1$$$, then YES otherwise NO.

However, this solution will MLE as it takes $$$\frac{n^3}{4}$$$ memory. Thus, we can just get rid of the first state in the DP, and compute it as we have been doing. This will require us to handle queries offline, i.e. we will need to store the queries for each $$$i$$$ beforehand, and answer it as we go along computing the DP. This solution will take $$$O(\frac{n^3}{4})$$$ time and $$$O(n^2)$$$ memory, so it is sufficient for our purposes.

If a set has LCM $$$k$$$, what does the LCM of any subset and its complement looks like?

Consider the bitmask corresponding to prime factors of $$$k$$$. Can you formulate some DP on them?

We will find $$$f(i)$$$ for each $$$i$$$, by iterating from $$$1$$$ to $$$10^6$$$. Let the prime factorization of $$$i$$$ be $$$p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$$$ and $$$S$$$ be any subset of $$$\{A_j\}_{j = 1}^{n}$$$ with LCM $$$i$$$. Let $$$x$$$ be a bitmask of size $$$k$$$, which corresponds to a set of integers $$$N(i, x)$$$ with prime factorization $$$p_1^{\beta_1}p_2^{\beta_2}...p_k^{\beta_k}$$$, where if the $$$j$$$-th bit of $$$x$$$ is on then $$$\alpha_j = \beta_j$$$, and if it is off then $$$\alpha_j \leq \beta_j$$$. For instance, if $$$i = 2\times3^5\times7$$$ then the bitmask $$$010$$$ corresponds to $$$N(i, 010) = \{3^5, 2\cdot3^5, 3^5\cdot7, 2\cdot3^5\cdot7\}$$$.

Assume that $$$S$$$ is not singleton for a moment. The crucial idea here is that there exists a bitmask $$$mask$$$ such that $$$S$$$ can be partitioned into two subsets, say $$$T$$$ and $$$S - T$$$ whose LCMs belong to $$$N(i, mask)$$$ and $$$N(i, \tilde msak)$$$ respectively. Indeed, if we partition $$$S$$$ into any two subsets $$$T$$$ and $$$S - T$$$, where the LCM of $$$T$$$ is of the form $$$p_1^{\beta_1}p_2^{\beta_2}...p_k^{\beta_k}$$$, then we can make a mask as follows: the $$$j$$$-th bit is on if $$$\alpha_j = \beta_j$$$, and off if $$$\alpha_j < \beta_j$$$. You can see that this mask will satisfy the above property.

We can use this property to formulate a DP where $$$dp[i][mask]$$$ denotes the minimum sum of a subset of $$$\{B_j\}$$$ such that the corresponding set in $$$\{A_j\}$$$ has LCM strictly smaller than $$$i$$$ and belonging to $$$N(i, mask)$$$. Also, $$$f[i]$$$ as before denotes the minimum sum of a subset of $$$\{B_j\}$$$ such that the corresponding set in $$$\{A_j\}$$$ has LCM exactly equal to $$$i$$$. So what should be the transitions?

Suppose we are currently at some $$$i$$$ and some $$$mask$$$, where $$$i = p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$$$. Let $$$j$$$ be the position of the first zero bit of $$$mask$$$. This divides the elements of $$$N(i, mask)$$$ into two camps, one with $$$\alpha_j = \beta_j$$$ and the other with $$$\alpha_j > \beta_j$$$. Notice that for the elements with $$$\alpha_j > \beta_j$$$, we have already found the minimum sum of subsets with LCMs among them – $$$\min(dp[\frac{i}{p_j}][mask'], f[\frac{i}{p_j}])$$$. Here $$$mask'$$$ will be the same as $$$mask$$$ if $$$p_j$$$ still divides $$$\frac{i}{p_j}$$$, otherwise it will be equal to $$$mask$$$ with the $$$j$$$-th bit dropped out. For the other case, the elements with $$$\alpha_j = \beta_j$$$, if we iterate through the bitmasks in decreasing order we also would have already found the minimum sum subset – $$$dp[i][mask' ']$$$, where $$$mask' '$$$ is $$$mask$$$ with the $$$j$$$-th bit turned on. Thus,

Now, how do we compute $$$f[i]$$$? To cover the case where the minimum subset sum is singleton, we can initially let $$$f[i]$$$ be the minimum $$$B_j$$$ for which $$$A_j = i$$$ ($$$\infty$$$ is $$$A_j$$$ is never $$$i$$$). Then, by our earlier observation $$$f[i] = \min(f[i], dp[i][mask] + dp[i][\tilde mask])$$$, where $$$mask$$$ runs over all bitmasks of size $$$k$$$.

In the implementation, as we iterate through $$$i$$$ from $$$1$$$ to $$$10^6$$$, we will need to generate the list of prime factors of $$$i$$$. This can be done in $$$O(n\log\log n)$$$ time efficiently using a sieve. The other part is to compute $$$f[i]$$$ and $$$dp[i][mask]$$$ for all masks. This is done in $$$O(2^{\text{prime}(i)})$$$ time for each $$$i$$$, where $$$\text{prime}(i)$$$ refers to the number of prime factors of $$$i$$$. Thus, overall complexity is:

Note that for each $$$i$$$, $$$2^{\text{prime}(i)}$$$ is less than the number of divisors of $$$i$$$. As the sum of the number of divisors over all $$$i$$$ upto $$$n$$$ is $$$O(n\log n)$$$, $$$\sum 2^{\text{prime}(i)}$$$ is also $$$O(n\log n)$$$. Thus, the final complexity is $$$O(n\log n)$$$.

Any pattern in the values of the array that maximizes the value?

Since we are filling either $$$W_{i}$$$ or $$$0$$$ in each of the cells, we can frame this problem in another equivalent way.

Problem: Given an array A, permute its elements so that the we get another array B and the value of $$$\sum_{i=1}^{n} \sum_{j=i+1}^{n} {B[i]} {B[j]} (j-i)$$$ is maximized.

Lemma: In the array B, there will we an index $$$i$$$, such that for all $$$j<i$$$, $$$B[j] \geq B[j+1]$$$ and for all $$$j \geq i$$$, $$$B[j] \leq B[j+1]$$$.

Using this lemma, solving this problem becomes much more manageable. First, assume that $$$A$$$ is sorted in non-increasing order and $$$S_{i}$$$ is the sum of the first $$$i$$$ elements of A.

We can define $$$dp[i][j]$$$ as the maximum possible value attainable if we put the first $$$i$$$ elements and the sum of elements that went into the prefix is $$$j$$$. The transitions are as follows:

This gives us a $$$O(N\sum(A[i]))$$$ solution, which is unfortunately too slow to pass the time limit. To optimize this we can see that most of the entries in $$$A$$$ are zero, hence we can compute the $$$dp$$$ for only the non zeros entries of $$$A$$$, since there are $$$M$$$ such entries. This will only take $$$O(M\sum(A[i]))$$$ time. After computing this we can see that the answer is

Compute the number of paths in which $$$i^{th}$$$ time is the time of $$$p^{th}$$$ visit.

Difference between ans for $$$(n,p,k)$$$ and $$$(n, p-1, k)$$$ is independent of p.

Let us start by solving some simpler problems first, which will slowly build up to a complete solution. Let $$$X_{n}$$$ denote the number of walks of length $$$n$$$, that start at the origin and also end at it. To calculate this value, we can use a trick of rotating the coordinates by 45 degrees. More precisely, we will transform points $$$(x, y)$$$ of the plane to $$$(x + y, x - y)$$$. This means that one step in any direction corresponds to $$$(\pm 1, \pm 1)$$$. Thus, each coordinate behaves independently in the rotated plane. For each coordinate, we need the number of ways to return to the origin in $$$n$$$ steps where each step can be $$$\pm 1$$$, which if $$$n$$$ is even will be $$$\binom{n}{\frac{n}{2}}$$$. Thus:

Now, let $$$Q_{n}$$$ denote number of walks of length $$$n$$$ that never visit the origin again. We can see that this satisfies the recurrence:

Let $$$P_{n}$$$ denote the number of walks of length $$$n$$$ that start at origin and end at origin, while not visiting origin at any time in between. We can see that this satisfies the recurrence:

Take $$$X$$$, $$$Q$$$, $$$P$$$ to denote the ordinary generating functions of $$$X_{n}$$$, $$$Q_{n}$$$, $$$P_{n}$$$ respectively.

Let $$$R_{n}$$$ denote the number of walks of length $$$n$$$ that start at origin and end at origin, and visit origin exactly $$$p-1$$$ times, where $$$p \geq 1$$$ and not counting the start but counting the endpoint. It can be easily seen that the generating function of $$$R_{n}$$$ is $$$P^{p - 1}$$$. Similarly, the generating function for walks of length $$$n$$$ that end at the origin and visit it exactly $$$k - p$$$ times is $$$P^{k - p}$$$.

Moving on, let $$$C_{n}$$$ denote the number of walks of length $$$n$$$ that start from the origin and visit the origin exactly $$$p$$$ times but can end at any point. It can be seen that the generation function of $$$C_{n}$$$ is $$$C = QP^{p - 1}$$$. If we interpret $$$C_{n}$$$ in the reverse direction, it is easy to see that $$$C_{n}$$$ is also equal to the number of walks of length $$$n$$$ that visit their endpoint exactly $$$p$$$ times.

We can now see that we are very close to our answer. Let the number of walks of length $$$n$$$ that visit their endpoint exactly $$$k$$$ times, multiplied by the time of the $$$p$$$th visit of the endpoint, be $$$E_n$$$. Indeed, the generating function of $$$E_{n}$$$ can be easily seen to be:

Thus, our final answer becomes:

So we have a way to find the required answer, but it is too slow. To find something faster, first lets put together all the equations in one place:

For convenience, let $$$L$$$ denote:

Now using some simple manipulations, we can see that:

Where $$$Q'$$$ and $$$P'$$$ denote the derivatives of $$$Q$$$ and $$$P$$$ respectively. Now, if $$$F = EL$$$ we can see that the answer for a fixed $$$(n,p,k)$$$ tuple the answer is simply $$$\frac{F[n]}{4^{n}}$$$. We can easily handle queries by splitting $$$F$$$ into two parts $$$x Q'P^{k-1}L$$$ and $$$(p - 1) \times(xQP^{k-2}P'L)$$$, and noting that the computation of each of those parts depends only on $$$k$$$, except for multiplying by $$$p - 1$$$ at the end. We can thus answer each query in $$$O(1)$$$ time.

Also, each operation here, including inverse polynomial and power of polynomial can be done in $$$O(n \log n)$$$ time. Thus, the final complexity is $$$O(n \log n + q)$$$.

To fit this within time limits, we would require some constant optimization. Since the slowest part is computing the powers of P, we will do a few optimizations there. First, we only need to take power once, since after we have computed $$$P^{k-2}$$$, we can get $$$P^{k-1}$$$ by multiplying it with $$$P$$$. The second optimization is that since all $$$P_{2*i+1}$$$ are zero, we can define a new polynomial, $$$Z$$$, such that,

. Then take the power of $$$Z$$$; since the size of $$$Z$$$ is only $$$5*10^4$$$, this can be computed in much less time, and then we can recover $$$P^{k-2}$$$ from $$$Z^{k-2}$$$.

The strength of Thor is $$$z - x$$$, and that of Loki is $$$z - y$$$. Thus, the maximum strength is $$$\text{max}(z-x, z-y)$$$. Equivalently, we can also say the maximum strength is $$$z - \text{min}(x, y)$$$.

Complexity: $$$O(1)$$$

Think of what strategy to take based on the number of monsters of each type.

Think of what to do with types that have a large number of monsters. Then, think of what to do with the other ones.

The optimal strategy is:

1. First, shoot down all monsters of a particular type if there are more than $$$k$$$ of them. Do this until there are no more types with more than $$$k$$$ monsters.

2. The remaining monsters can be shot $$$k$$$ at a time.

It is easy to see that we cannot do any better. Thus, if $$$cnt$$$ represents the number of types with more than $$$k$$$ monsters, and $$$tot$$$ represents the total number of monsters of such types, then the answer is $$$cnt + \lceil \frac{n - tot}{k} \rceil$$$.

Complexity: $$$O(n)$$$

Can you think of a DP solution?

Can we calculate the shortest path to any vertex with a fixed number of edges?

We can solve this problem by a simple DP solution. Let $$$dp[i][j]$$$ denote the minimum distance between vertices $$$1$$$ and $$$i$$$ among all paths containing $$$j$$$ or fewer edges. Our transitions therefore will be:

for j from 1 to n:
   for each edge from x to i:
      dp[i][j] = min(dp[i][j], dp[i][j - 1], dp[x][j - 1] + j*weight_of_edge) 

The transitions can be explained as follows. Whenever we are calculating $$$dp[i][j]$$$, there are 2 possible cases:

1. A path containing less than $$$j$$$ edges gives the shortest distance between $$$1$$$ and $$$i$$$. In this case, $$$dp[i][j] = dp[i][j-1]$$$.

2. A path containing exactly $$$j$$$ edges gives the shortest distance between $$$1$$$ and $$$i$$$. For this case, we can iterate over all the edges ending at $$$i$$$ which will be the $$$j$$$-th edge in our path. Thus, $$$dp[i][j] = \text{min}(dp[i][j], dp[x][j - 1] + j\times\text{weight_of_edge})$$$ as we iterate through the edges from $$$x$$$ to $$$i$$$.

Note that a shortest path may only contain at most $$$n$$$ edges. Thus, the minimum distance from $$$1$$$ to $$$i$$$ will be $$$dp[i][n]$$$.

Complexity: $$$O(nm)$$$

What can you can say about the parity of number of stones for each player?

Does the exact value of available numbers matter?

If there are fewer even numbers than odd numbers available, then how many states are winning?

Since the question contains a lot of constraints, at first we will try to simplify these a bit.

1. In a move, we can add or subtract any odd number of stones. It means that if we have an even number of stones, we can go to any odd number of stones, and if we have an odd number of stones, we can go to any even number of stones. We can thus simplify the problem significantly by observing that only the count of allowed even positions $$$E$$$, and allowed odd positions $$$O$$$ matters. The exact values of positions do not matter.

2. Now let's do a bit of casework.

   • Case 1: $$$E < O$$$. If we try to observe what happens when the starting position is even, we can quickly deduce Natasha wins, no matter what move Natasha or Scott plays after that. This is because, Natasha can only be at odd position and Scott can only be at even positions, and so he will run out of positions before Natasha does. Similarly if she starts from any odd number, she loses, no matter what moves Natasha or Scott plays. So there will be a total of $$$E$$$ winning starting positions in this case.
   • Case 2: $$$O < E$$$. Proceeding as above, we can see that there are $$$O$$$ winning starting positions.
   • Case 3: $$$O = E$$$. In this case, Natasha will win starting from both odd positions and even positions. Thus, there are $$$O + E$$$ winning starting positions.

So now our task is greatly simplified. We loop through all the possibilities of $$$(O, E)$$$, count how many subsets of each case exists and add them to the answer.

The count of even numbers from $$$0$$$ to $$$N$$$ is $$$\lceil \frac{N + 1}{2} \rceil$$$, which we denote by $$$P$$$. The count of odd numbers from $$$0$$$ to $$$N$$$ is $$$\lfloor \frac{N + 1}{2} \rfloor$$$, which we denote by $$$Q$$$.

So now we can compute the answer as:

• Case 1: $$$E < O$$$. Let us iterate over $$$E$$$, then:

Note that we can maintain $$$\sum_{ O={E+1} }^{Q}\binom{Q}{O}$$$ as we compute the sum, so calculating this sum only takes $$$O(N)$$$ time.

• Case 2: $$$O < E$$$. Let us iterate over $$$O$$$, then:

• Case 3: $$$O = E$$$. Let us iterate over $$$O$$$, then:

Thus, we can compute $$$\text{ans}$$$ in $$$O(N)$$$ time.

Complexity: $$$O(N)$$$

Can you solve it in less than quadratic time?

How can the special conditions on queries be used?

Build a tree on the query segments.

DSU on Tree!!

First, we will describe a solution based on Mo's Algorithm, that works in $$$O(N\sqrt{N})$$$.

We maintain the frequency of each number in the current range in an array $$$freq$$$, and the answer for current range $$$ans$$$. We can add a number $$$x$$$ to the range by $$$ans = ans + freq[S-x]$$$ where $$$S$$$ denotes the required sum of pairs. Similarly we can delete a number $$$x$$$ from the range by $$$ans = ans - freq[S-x]$$$. We just need to be slightly careful in the case when $$$x = S - x$$$. Overall, we can add and delete in $$$O(1)$$$ and hence, Mo's algorithm can solve this problem in $$$O(N\sqrt{N})$$$. This will exceed the time limit, unless highly optimised.

However, the query ranges satisfy some special conditions in this problem! How can we use these to our advantage?

Consider each range as one node of a tree. For each range, we find the smallest other range which covers it completely and make it the parent of this node in our tree. We also create a fake node, which will act as parent of all the ranges which are not covered by any other range. We can now use DSU on Trees to solve this problem!!

For each node, we can find its biggest child (Note: Biggest child in terms of length of the range it represents, not in subtree size). To process the answer for a node we do the following:

• Process all its children nodes (if any), not including the biggest child.
• Process the biggest child, and maintain the state of $$$freq$$$ as it is.
• Iterate from left end to right end of current range, and add each element in $$$O(1)$$$ (as in the Mo's solution), while skipping all elements in the range of its biggest child.
• Roll back the changes made to $$$freq$$$ if the current node is not the biggest child of its parent.

Building the tree can be done in $$$O(QlogQ)$$$ by sorting the queries and then using stacks, or in $$$O(Q)$$$ if we use counting sort. DSU on Tree works in $$$O(NlogN)$$$ and hence, the overall complexity of this solution is $$$O(QlogQ + NlogN)$$$, which will comfortably pass in the given time limit.

Complexity: $$$O(QlogQ + NlogN)$$$

Aho-Corasick.

BFS along edges in alphabetical order.

In problems where we are given a list of patterns, which are supposed to appear as substrings and we have to count the number of strings satisfying some constraints, or finding the smallest string satisfying the constraints, Aho-Corasick is almost always a good idea.

The remainder of the editorial assumes familiarity with Aho-Corasick. If you are not comfortable with it, CP-Algorithms has a really nice entry on it.

To start the solution, first build the Aho-Corasick automaton for the given strings. Also, mark all the states at which at least one of the pattern terminates. Once we have done this, we will build the exit links for each node. (Exit link points to the nearest leaf vertex reachable via suffix links — details in the above CP-Algorithms article). Using exit links we can find the exit count for each node, which is the number of leaf nodes, reachable from the current node via suffix links. In other words, these are the number of patterns, which are suffixes of the current state.

Once we have built this, the remainder of the task is pretty straightforward. We create a new graph, where each vertex corresponds to a state (vertex in Aho-Corasick, number of occurrences of patterns). Since total states in Aho-Corasick is smaller than or equal to $$$\sum_{i = 1}^{K} P_{i} + 1$$$, and the number of occurrences is smaller than or equal to $$$ N $$$, there are atmost $$$(N + 1)(\sum_{i = 1}^{K} P_{i} + 1)$$$ states in our new graph.

Now comes the part of adding edges in the graph. It is easy to observe that if we transition from state $$$A$$$ to state $$$B$$$ of Aho-Corasick and let's say exit count of $$$B$$$ is $$$x$$$, then in the graph our edge will be from $$$(A, \text{no. of occurrences})$$$ to $$$(B, \text{no. of occurrences} + x)$$$.

Finding the length of the smallest string is now an easy task. Run a BFS from $$$(0,0)$$$ and record the first time instance when the second parameter crosses $$$N$$$, i.e. we reach a state $$$(A, \text{occurrences})$$$ where $$$N \leq \text{occurrences}$$$. Finding the lexicographically smallest string is a simple addition to it. We simply run the BFS in lexicographical order, i.e. first transition from the edge corresponding to 'A', then 'B', then 'C', ... finally 'Z'. It is easy to show that this will give us the correct answer.

Complexity: $$$O(N * \sum_{i = 1}^{K} P_{i})$$$

Think of a DP solution where we maintain the contributions of $$$a_i$$$'s in the total distance.

What information we need to maintain to find the contribution of $$$a_i$$$ to the total distance?

Do you think a bitmask denoting whether we need to add $$$a_i$$$ at each position in our visit order can help?

We can solve this problem using dynamic programming. The idea here is to maintain the number of sequences of galaxies we visit, as we iterate through galaxies $$$1$$$ to $$$n-1$$$, whose contribution to the total distance by all distances $$$a_k (k \leq i)$$$ is known.

Let $$$dp[i][mask][j]$$$ be the number of sequences ($$$g_1$$$, $$$g_2 ... g_y$$$) of galaxies we visit such that:

• $$$mask$$$ is a bitmask of length $$$y$$$, which is $$$0$$$ at the $$$k$$$-th position if $$$g_k \leq i$$$ and $$$1$$$ otherwise.
• $$$j$$$ is the contribution of all distances $$$a_k$$$ (where $$$k \leq i$$$) to the total distance $$$\mod x$$$.

To write the transitions, we need the contribution of $$$a_i$$$ to the total distance, as the rest of the contribution can already be determined from $$$dp[i-1][...][...]$$$. Note that $$$a_i$$$ will contribute exactly when there is a change from $$$0$$$ to $$$1$$$ (or vice-versa) in $$$mask$$$, as this implies that we will be moving between two galaxies such that $$$a_i$$$ is included in their distance. So, lets define $$$\text{changes}(mask)$$$ as the number of pairs of adjacent bits in $$$mask$$$ with different values.

Now we have two cases:

• The galaxy $$$i$$$ was never visited in the sequence. Thus, $$$dp[i][mask][j] += dp[i - 1][mask][(j - \text{changes}(mask)\times a_i)\mod x]$$$.

• The galaxy $$$i$$$ was visited at the $$$k$$$-position, that is $$$g_k = i$$$. So, when looking up the dp table for $$$i-1$$$, we will need to switch on the $$$k$$$-th bit of $$$mask$$$. Let $$$mask'$$$ be the bitmask with the $$$k$$$-th bit on in $$$mask$$$. Then, $$$dp[i][mask][j] += dp[i - 1][mask'][(j - \text{changes}(mask)\times a_i)\mod x]$$$.

(We can consider $$$a_n = 0$$$ since there is no further contribution to be made). It is now clear that our answer will be $$$dp[n][0][0]$$$, as all visited galaxies will lie before or on $$$n$$$.

Complexity: $$$O(nxy2^y)$$$.

Generating functions.

Try solving the easier problem of counting the number of labelled bipartite graphs on n vertices.

Did you try FFT? Try using FFT at each step to reduce complexity.

Our solution is based on generating functions. For a better understanding, you should read this wonderful book generatingfunctionology up to the third chapter. We will use some terms defined in the book, which you can review below or better yet, check out the book at page 75.

The main theorem we will be using here is that if $$$H(x)$$$ and $$$D(x)$$$ represent the exponential generating functions of {$$$h_i$$$}$$$_{i=0}^\infty$$$ and {$$$d_i$$$}$$$_{i=0}^\infty$$$ respectively, then:

This is actually the main theorem of the 3rd chapter in the book (page 81) and is in fact a very useful combinatorial tool. You can apply it in many different situations, a famous example being that of counting connected graphs of size $$$n$$$.

Before we get to the main problem, let us start by solving the simpler problem of counting labelled bipartite graphs consisting of $$$n$$$ vertices labelled from $$$1$$$ to $$$n$$$. We will call such labelling as standard labelling of size $$$n$$$, and such a graph as a standard graph of size $$$n$$$ from now on.

This problem is covered in the book on page 81. You can read the solution over there, or from the explanation, we have written below. We will see that this solution mostly carries over to our problem with some modifications.

We now come back to our original problem, wherein we need to count the number of standard bipartite graphs of size $$$n$$$ where:

• Each edge of the graph has been coloured with one of $$$p$$$ colours.
• For each component, precisely one vertex has been coloured with one of $$$k$$$ colours.

Let us review the solution of the above simpler problem. We had first calculated the number of bipartite graphs on $$$n$$$ vertices with standard labelling, where each vertex was coloured either red or blue as:

Note that instead of choosing whether an edge exists or not in $$$2$$$ ways, we can choose among $$$1+p$$$ choices for each possible edge — either it is not present or coloured in one of $$$p$$$ colours. Thus, let $$$h_n$$$ — the number of bipartite graphs on $$$n$$$ vertices with standard labelling, where each vertex is red/blue, and the edges have been coloured in one of $$$p$$$ colours is:

Let $$$d_n$$$ now denote the number of connected standard bipartite graphs of size $$$n$$$ with edges coloured in one of $$$p$$$ colours. As before, the egf of {$$$d_i$$$}$$$_{i=0}^\infty$$$ is $$$D(x) = \frac{\log{H(x)}}{2}$$$, where $$$H(x)$$$ is the egf of {$$$h_i$$$}$$$_{i=0}^\infty$$$.

We can now take care of the second type of colouring, given that we are now dealing with only connected bipartite graphs of size $$$n$$$. It is easy to see that $$$nkd_n$$$ represents the number of connected standard bipartite graphs of size $$$n$$$ with edges coloured in one of $$$p$$$ ways, and one vertex coloured in one of $$$k$$$ ways. Also, the egf of {$$$ikd_i$$$}$$$_{i=0}^\infty$$$ will be $$$kxD'(x)$$$. While coding you can just multiply each term of the sequence with $$$ik$$$, but here it is handy to write the egf as the derivative.

We are almost done! We have calculated the size of decks, {$$$ikd_i$$$}$$$_{i=0}^\infty$$$, and whose egf is $$$kxD'(x)$$$. Thus, the number of hands of size $$$n$$$ (the number of labelled standard bipartite graphs of size $$$n$$$, with edges coloured in one of $$$p$$$ colours and one vertex of each component in one of $$$k$$$ colours) can be found by another application of our main theorem. In particular, its egf will be $$$e^{kxD'(x)}$$$.

To summarize, let:

Then, the coefficient of $$$x^n$$$ in $$$G(x)$$$ multiplied by $$$n!$$$ (as $$$G(x)$$$ is egf), will give us the final answer.

Computing the polynomials

We have seen what our answer actually will be, in terms of polynomials. Here, we take a quick look at how to compute those polynomials with code. To solve our problem for $$$n$$$, it is sufficient to calculate all polynomials only up to degree $$$n$$$, as at no step above can a coefficient with degree greater than $$$n$$$ can affect the $$$n$$$-th coefficient of $$$G(x)$$$.

We will thus need to compute $$$h_i$$$ for all values from $$$1$$$ to $$$n$$$. This can be done natively in $$$O(n^2)$$$ time. The only other operation that may take more than linear time is taking the $$$\exp$$$ and $$$\log$$$ of the $$$n$$$-th degree polynomials. This has a detailed explanation on the CP-Algorithms page, but we can actually consider it as a black-box and know the implementation takes only $$$O(n\log n)$$$ time. Thus, overall $$$G(x)$$$ can be computed in $$$O(n^2)$$$ time.

We can reduce this to $$$O(n\log n)$$$ time, using the idea in this blog. As,

Thus,

Now if you consider the product:

It is clear that if we multiply the coefficient of $$$x^i$$$ in this polynomial with $$$(1+p)^{\frac{i(i-1)}{2}}$$$, we will have our egf $$$H(x)$$$. Thus, we have calculated $$$H(x)$$$ in $$$O(n\log n)$$$ time as we just needed to multiply two polynomials. The final complexity of our solution is thus $$$O(n\log n)$$$.

Complexity: $$$O(n\log n)$$$