//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}$$$.