You can solve each row independently of each other. Using window sums, you can count the number of A or B in any contiguous section of $$$K$$$ cells, and thus detect whether any player has an opposing player in front of them.

Time complexity: $$$O(NM)$$$

The key observation is that you can think of the students as a queue standing from $$$1$$$ to $$$M$$$. The students that answer the $$$i$$$-th question are always the first $$$B_i$$$ students in front of the queue, then they move to the back of the queue in the same order that they were in before. We could prove this by induction; first assume each student $$$j$$$ starts with a score of $$$j \cdot \varepsilon$$$ for some small real number $$$\varepsilon$$$, to preserve tiebreaking order. If we assume that the difference between the scores of the first and last student in the queue is $$$< A_i$$$ (trivially true for $$$i = 1$$$), answering the question and moving the students to the back of the queue ensures the students are still correctly ordered for question $$$i+1$$$, and then the score of the new-first student is $$$S_{B_i + 1}$$$ and the new-last student is $$$S_{B_i} + A_i$$$. Since $$$S_{B_i} < S_{B_i + 1}$$$, $$$S_{B_i} + A_i - S_{B_i + 1} < A_i \leq A_{i+1}$$$, therefore the property is preserved for the next question.

This gives an $$$O(NM)$$$ solution, but we could optimize it by realizing that since scores are always added to up to two contiguous segments of students, we could use a finite difference array (to add $$$x$$$ to a contiguous segment $$$[l, r]$$$ of the original array, we add $$$x$$$ to $$$D_l$$$ and subtract $$$x$$$ from $$$D_{r+1}$$$) and restore the answer by its prefix sum.

Time complexity: $$$O(N + M)$$$

The tournament is modelable as a perfect binary tree, where the first round are the leaves of the tree, the next round are their parents, and so on. Let each node of the tree contain both the maximum number student and the sum of the "underwhelmingness" of the matches in its subtree. To shift the missing student means updating two leaves of the tree and their ancestors, which takes $$$O(\log N)$$$ each time.

The perfect binary tree can be modeled as an array indexed from $$$1$$$ to $$$2N - 1$$$; the leaves are nodes $$$N$$$ to $$$2N-1$$$, and each parent node $$$i$$$ has children $$$2i$$$ and $$$2i + 1$$$. If you are familiar with a data structure called a segment tree, it should form this perfect binary tree when $$$N$$$ is a power of $$$2$$$, and the answer can then be obtained from its root.

Time complexity: $$$O(N \log N)$$$

First, reorder the candidates by the given ranking, indeed, you may want to do this even before trying to solve this problem, as it makes things easier to visualize. For example, the sample input becomes

3 4 4
3 4 4
1 4 4
4 4 2
2 4 2
1 4 1
4 3 4
2 3 3
4 1 4
2 1 2
1 1 2

We'll refer to this reordered matrix by $$$R_{i,j}$$$.

It can be seen that any possible first factor must have non-increasing scores when looking at the ordered candidates. Once the first factor $$$j$$$ is chosen, it essentially splits the list of candidates into several contiguous sublists where $$$R_{i,j}$$$ are all equal. A factor becomes a possibility for being the next one if they are non-increasing in each sublist.

To update the possible next factors efficiently, consider a "bad row" $$$i$$$ for each factor $$$j$$$ to be where $$$R_{i, j} < R_{i+1, j}$$$. The candidates for first factors are those with no bad rows, and picking a factor $$$j$$$ will nullify bad rows $$$i$$$ for other factors where $$$R_{i, j} > R_{i+1, j}$$$. Note that each row should only be considered for nullification at most once. This can be efficiently done by storing a count of bad rows for each factor, and a priority queue or ordered set for the factors with no bad rows (to ensure we always pick the minimum possible factor each time).

Time complexity: $$$O(K (N + \log K))$$$

Consider a function $$$f(l, k)$$$ to return the minimum position of a student blamed at least $$$k$$$ times, given that the leftmost interview is at index $$$l$$$, or $$$\infty$$$ if there is no such student. Note that this can answer queries simply by comparing the returned value with the given $$$r$$$.

We solve the queries offline by considering how to transition from being able to answer $$$f(l+1, *)$$$ to $$$f(l, *)$$$. Let's have an array $$$F_k$$$ that stores the answers for $$$f(*, k)$$$ where $$$k \leq X$$$, where $$$X$$$ is some threshold value we decide later. To transition from $$$f(l+1, *)$$$ to $$$f(l, *)$$$, we use an array of growable arrays, where growable array $$$i$$$ is the list of blames for student $$$i$$$, in decreasing order. We can easily add the blame for student $$$A_l$$$, then look at up to last $$$X$$$ items of that list to update $$$F_k$$$.

This allows us to answer $$$f(l, k)$$$ for $$$k \leq X$$$. To answer for $$$k > X$$$, we store any student that first exceeds $$$X$$$ blames into another growable array and call them heavy students. We can then answer those queries by searching through the heavy students, as they are the only students that might have at least $$$k$$$ blames. There can only be up to $$$N / X$$$ heavy students.

Therefore, we can answer all queries in time $$$O(NX + QN / X)$$$. By picking $$$X \sim \sqrt Q$$$, we could achieve a time complexity of $$$O(N\sqrt Q)$$$.

First, for each node we want to find $$$src[i]$$$ : the nearest tree to each node, and $$$ds[i]$$$, the distance to that tree. These can be found via multi-source breadth-first search. To ensure that ties are broken correctly, ensure that $$$T$$$ is sorted in increasing order before entering them in the queue.

Now consider the park to be a tree graph rooted at node $$$1$$$. Let $$$c(u, v)$$$ be the cost of starting from node $$$u$$$ and going to node $$$v$$$ (without considering what the dog does after reaching node $$$v$$$). It is easy to answer $$$c(u, v)$$$ if $$$u$$$ and $$$v$$$ are neighbors in the graph; $$$c(u, v) = 1$$$ if $$$src[u] = src[v]$$$ and $$$ds[u] > ds[v]$$$ (because the dog is already chasing in that direction), otherwise $$$c(u, v) = 2 \cdot ds[u] + 1$$$, as the dog has to chase the squirrel before you could bring him back to node $$$u$$$ to step to node $$$v$$$.

It can be seen that for nodes that aren't neighbors $$$u$$$ and $$$v$$$, if the simple path between them is $$$u, p_1, p_2, \ldots, p_m, v$$$, $$$c(u, v) = c(u, p_1) + c(p_1, p_2) + \ldots + c(p_m, v)$$$.

To find arbitrary $$$c(u, v)$$$ quickly, precalculate $$$w_{up}[i]$$$ and $$$w_{dn}[i]$$$, these are cumulative costs for paths going up toward or down from the root of the tree graph. $$$w_{up}[i] = w_{up}[P_i] + c(i, P_i)$$$, and $$$w_{dn}[i] = w_{dn}[P_i] + c(P_i, i)$$$.

To answer a query for $$$x, y$$$, first find $$$l$$$, the lowest common ancestor (LCA) of nodes $$$x$$$ and $$$y$$$, using your favorite method (link, link). Then then answer is given by $$$c(x, y) + (2 \cdot ds[y]) = (w_{up}[x] - w_{up}[l]) + (w_{dn}[y] - w_{dn}[l]) + (2 \cdot ds[y])$$$: the cost of the path from $$$x$$$ upward to $$$l$$$, the path from $$$l$$$ downward to $$$y$$$, and we must not forget to include the last chase at node $$$y$$$.

Note that it is possible to "cheese" subtask 1 if you can spot the method:

Time complexity: $$$O((N+Q) \log N)$$$

Note that $$$N$$$ has to be read as a signed 64-bit integer type. You could check it by either doing to comparison manually, or casting back and forth between the signed 32-bit integer type.

Time complexity: $$$O(1)$$$

Simply construct a $$$W$$$-by-$$$H$$$ matrix, assign $$$B_{i, j} = A_{j, i}$$$ for all relevant $$$i, j$$$, then output it.

Alternatively, if you use Python, the numpy library installed in AtCoder gives a really short implementation, as noted in this user editorial: https://atcoder.jp/contests/abc237/editorial/3344

Time complexity: $$$O(HW)$$$

Note that for a string to be a palindrome, it must start with the same number of contiguous as as it ends with.

If there are less contiguous as at the end of $$$S$$$ than at is start, the answer is No. Otherwise, add the difference in number of as to its start, then test if it is a palindrome.

Time complexity: $$$O(|S|)$$$

There are at least two methods that could be used, a straightforward method with linked list, or a reversed method with deque.

Straightforward method with linked list:

One could make a simple linked list using two arrays, $$$pr$$$ "previous" and $$$nx$$$ "next", where $$$pr[i]$$$ is the index of the node before $$$i$$$ in the list, while $$$nx[i]$$$ is the index of the node after $$$i$$$ in the list. One node ($$$N+1$$$ is convenient for this problem, thus making $$$N+2$$$ total nodes) is reserved as the "sentinel" node, whose $$$nx[s]$$$ points to the first element, and $$$pr[s]$$$ points to the last element of the list.

Then implement as in the problem statement. For the L case you should insert the new node between $$$pr[i]$$$ and $$$i$$$ by updating the $$$pr$$$ and $$$nx$$$ arrays, for the R case, insert the new node between $$$i$$$ and $$$nx[i]$$$.

Reversed method with deque:

Consider the operations in reversed order.

L is equivalent to appending $$$i-1$$$ to the right of $$$A$$$, as $$$i$$$ is already in $$$A$$$, and everything in between was supposed to be added after $$$i$$$ in the normal order. Similarly, R is equivalent to appending $$$i-1$$$ to the left of $$$A$$$.

To efficiently perform these operations, we use a deque, that allow amortized $$$O(1)$$$ appending to either end of the logical array.

Time complexity: $$$O(N)$$$

One may think of using Dijkstra's algorithm, however the happiness increases are a problem as they are effectively a negative cost. However, Dijkstra's algorithm can still be used, provided that there is a potential function $$$\phi(i)$$$ for all vertices $$$i \in [1, N]$$$, such that:

• Let $$$C_e$$$ be the current cost of a directed edge (that may be negative) going from vertex $$$u$$$ to vertex $$$v$$$. Define the new cost $$$C'_e = C_e + \phi(u) - \phi(v)$$$. These new costs must all be non-negative for the potential function to be admissible.

• After Dijkstra's is run on the graph with these new costs, let $$$R'_v$$$ be the final cost from source vertex $$$u$$$ to the destination vertex $$$v$$$. To transform this value back to the true cost, we apply $$$R_v = R'_v - \phi(u) + \phi(v)$$$.

How do we find this potential function? Turns out the problem already gives us one; you could verify that $$$\phi(i) := H_i$$$ is an admissible potential function, leaving all new edge costs non-negative:

• If $$$H_X \geq H_Y$$$, the old cost is $$$H_Y - H_X$$$, and the new cost is $$$(H_Y - H_X) + H_X - H_Y = 0$$$.
• If $$$H_X < H_Y$$$, the old cost is $$$2(H_Y - H_X)$$$, and the new cost is $$$2(H_Y - H_X) + H_X - H_Y = H_Y - H_X$$$, which is positive.

Note that the true cost should be negated before output.

Time complexity: $$$O((N+M) \log (N+M))$$$

Recall the algorithm to find the length of the LIS (longest increasing subsequence) of an array:

• Maintain a dynamic array or ordered set $$$L$$$, that is initially empty.
• For each element $$$A_i$$$, find the index of the smallest element $$$L_j \geq A_i$$$. If it exists, replace $$$L_j$$$ with $$$A_i$$$, otherwise append $$$A_i$$$ to $$$L$$$. Note that in the dynamic array variant, this is often implemented with binary search (as $$$L$$$ would always be strictly increasing), but this is not necessary for this problem.
• The final length of $$$L$$$ is the length of the LIS.

Since we are only interested in LISes up to length $$$3$$$ and because $$$M$$$ is small, we can note that there aren't that many states $$$L$$$ could be. Thus we can use dynamic programming, where $$$dp_{i, L}$$$ is the number of sequences of length $$$i$$$ that results in a particular state of $$$L$$$. Since $$$L$$$ is an array of length up to three, one could either implement it as three dimensions (zero padding if necessary), or use hashmaps and/or bitmasks.

Note that you should only sum the final $$$dp_{N, L}$$$ where $$$|L|$$$ is exactly $$$3$$$.

Time complexity: There are $$$O(N)$$$ iterations of DP, each with up to $$$O(M^3)$$$ states for $$$L$$$, each with up to $$$O(M)$$$ transitions, so the total time is $$$O(NM^4)$$$, which should fit in the time limit.

Note that we are only interested in the position of a fixed value $$$X$$$. We can thus transform all values $$$P_i$$$ to "$$$<$$$", "$$$=$$$", or "$$$>$$$" based on their relation to $$$X$$$.

One could use a lazy segment tree where each node contains the number of "$$$<$$$", "$$$=$$$", and "$$$>$$$" in that segment. To sort a subarray, we simply query for the total number of each. We can then sort that segment by range-assigning on up to $$$3$$$ subranges.

(Alternatively, you could also use three range-sum/range-assign lazy segment trees.)

Time complexity: $$$O((N + Q) \log N)$$$

Let $$$sub_1, ..., sub_{|sub|}$$$ be all distinct palindromic substrings of $$$S$$$, this can be constructed using hashmap in $$$O(|S|^3)$$$. This problem thus amounts to finding the maximum antichain among $$$sub$$$, where the partial order relation $$$s < t$$$ holds if $$$s$$$ is a proper substring of $$$t$$$.

To do so, we can use Dilworth's theorem to transform this problem to a bipartite matching problem. We could create a flow graph with the following vertices:

• $$$U_i$$$, $$$V_i$$$ for $$$i \in [1, |sub|]$$$
• $$$src$$$ (the source node), $$$snk$$$ (the sink node).

And the following edges, all with a capacity of $$$1$$$:

• $$$src \rightarrow U_i$$$, $$$V_i \rightarrow snk$$$ for $$$i \in [1, |sub|]$$$
• $$$U_i \rightarrow V_j$$$ for all $$$i, j$$$ where $$$sub_i > sub_j$$$ (in other words, $$$sub_j$$$ is a proper substring of $$$sub_i$$$)...

And here we run into a problem. $$$|sub|$$$ is $$$O(|S|^2)$$$, so there could be up to $$$O(|S|^4)$$$ edges in this graph. If this doesn't exhaust the memory limit, finding the max-flow with Dinic/Hopcroft-Karp almost certainly would exceed the time limit with $$$O(E\sqrt V) = O(|S|^5)$$$. [Update: Actually this is fine, as there can only be $$$O(|S|)$$$ distinct palindromes, so the flow would run at $$$O(|S|^{2.5})$$$. Proof: Define a substring $$$S[l...r]$$$ as "earlier" than another substring if its $$$r$$$ is lower. For each $$$r$$$ there is at most one $$$l$$$ that $$$S[l...r]$$$ is the earliest occurrence of a palindromic substring. This can be proven by contradiction: suppose that $$$S[i...r]$$$ and $$$S[j...r]$$$ ($$$i < j$$$ WLOG) are both palindromic, and are both earliest occurrences of themselves. However, since $$$S[i...r]$$$ is a palindrome, $$$S[i...r-(j-i)] = \text{rev}(S[j...r]) = S[j...r]$$$, hence $$$S[j...r]$$$ can't be the earliest occurrence of itself.]

To reduce the number of edges in the flow graph, we could, instead of only including palindromic substrings in $$$sub$$$, include all distinct substrings of $$$S$$$. (Let's call the original set of palindromic substrings $$$pal$$$).

Our new flow graph would also have two vertices for every $$$sub_i$$$, as well as $$$src$$$ and $$$snk$$$. It would have the following edges:

• $$$1$$$-capacity: $$$src \rightarrow U_i$$$, $$$V_i \rightarrow snk$$$ only if $$$sub_i \in pal$$$
• We still want to allow flow from $$$U_i \rightarrow V_j$$$ for all $$$sub_i > sub_j$$$...
  • Let $$$sub_i$$$ be a substring of length $$$\geq 2$$$. Let $$$sub_j$$$ be $$$sub_i$$$ without its last character, similarly $$$sub_k$$$ is $$$sub_i$$$ without its first character. Note that all proper substrings of $$$sub_i$$$ is a substring of at least one of $$$sub_j$$$ and $$$sub_k$$$.
  • Thus we can add these edges, all infinite-capacity:
    • $$$U_i \rightarrow V_j$$$, $$$U_i \rightarrow V_k$$$ for all $$$sub_i$$$ of length $$$\geq 2$$$
    • $$$V_x \rightarrow U_x$$$ for all $$$x \in [1, |sub|]$$$. This allows flow to "continue on" to lesser substrings.

This keeps the number of edges down to $$$O(|S|^2)$$$. The final answer is $$$|pal| - maxFlow$$$.

Time complexity: $$$O(|S|^3)$$$

Note: Codeforces also quite recently had another problem involving maximum antichain and Dinic's max flow: 1630F - Making It Bipartite

The ball is invisible when it's between $$$V \cdot T$$$ and $$$V \cdot S$$$ meters away, inclusive. Thus the answer is Yes if $$$D < V \cdot T$$$ or $$$D > V \cdot S$$$, and No otherwise.

Time complexity: $$$O(1)$$$

Either use a dynamic array (vector in C++ / ArrayList in Java/Kotlin) to store the values $$$A_i \neq X$$$, or construct the output string directly. If using the latter method in Java/Kotlin, one should use the StringBuilder class to avoid wasting time copying the string in $$$O(N^2)$$$; this is not a problem in C++ as strings are mutable there.

Time complexity: $$$O(N)$$$

Simulate a "wall-following" algorithm. Specifically, let . represent empty space, and # represent walls. Find the first # character in reading order. Stand to its north, facing east, with your right hand on the "wall". Then walk forwards. If your hand runs out of wall, turn right, if you run into a wall, turn left, incrementing the answer each time you change direction. Stop when you return to your starting position.

Time complexity: $$$O(HW)$$$

Working with double floating points in this problem may cause precision issues. It's best to multiply the input by $$$10^4$$$ and convert to signed 64-bit integers right away (note that if you're reading the input as a floating point, you need to round before converting). Now the problem becomes the number of points in the circle where $$$X$$$ and $$$Y$$$ are both divisible by $$$10^4$$$.

Iterate through the multiples of $$$10^4$$$ between $$$Y - R$$$ and $$$Y + R$$$ inclusive; let the current value be $$$y$$$.

Now you want to find the minimum and maximum $$$x$$$ that remains in the circle. Either binary search for them, or use sqrt to solve $$$(x - X)^2 + (y - Y)^2 \leq R^2$$$; however since sqrt uses floating points, brute force its neighborhood to avoid precision issues. Then add $$$\displaystyle\left\lfloor\frac {max} {10^4} \right\rfloor - \left\lceil\frac {min} {10^4} \right\rceil + 1$$$ to the answer.

One must also be careful with the divisions, as the behavior of the / operator may differ depending on the sign of the dividend. (In C++ and Java/Kotlin, it truncates, i.e., rounds toward zero, instead of finding the floor consistently.)

Time complexity: $$$O(\lceil R \rceil)$$$ or $$$O(\lceil R \rceil \log \lceil R \rceil)$$$

Construct the weighted directed graph and run Dijkstra's algorithm from each node. However we have to deal with the fact that the goal node is the same as the source node. There are several ways:

• Set the cost of the source node to $$$\infty$$$ and prepopulate the priority queue with the nodes directly reachable from the source
• Create a new fictional node $$$n+1$$$ to use as the goal node. Redirect all back-to-source edges there.
• First precalculate the cheapest edge from each node to the source node (or $$$\infty$$$ if there are none). Run Dijkstra as normal, then add the costs and find the minimum.

Time complexity: $$$O(N (N+M) \log (N+M))$$$

Observe that a value $$$x$$$ could be the final value iff $$$x \leq \min A$$$ AND $$$x$$$ is the gcd of some non-empty subset of $$$A$$$.

For the latter condition to hold, $$$x$$$ must be a divisor of at least one value $$$A_i$$$. Also, if $$$[A_a, A_b, ..., A_c]$$$ are all the values of $$$A$$$ divisible by $$$x$$$, their collective gcd must be equal to $$$x$$$.

Thus we can iterate through the divisors of each $$$A_i$$$ and maintain a hashmap, mapping a divisor to the collective gcd of its multiples in $$$A$$$, then count the number of divisors that satisfy.

Time complexity: $$$O(N (\sqrt M + D \log M))$$$, where $$$M = \max A$$$ and $$$D$$$ is the maximum number of divisors for a value $$$A_i$$$, which can be considered roughly $$$O(M^{1/3})$$$.

Basically, just do what it says in the problem statement. The function to turn a character uppercase is std::toupper(t) in C++, Character.toUpperCase(t) in Java, t.toUpperCase() in Kotlin, or t.upper() in Python.

Iterate through every row and column. If the current square is ., look at the neighbor to the right, if it's also ., increment the answer. Likewise the neighbor downward. There is no need to look leftward or upward as those positions would already have been counted.

Initiate an array of booleans indexed over $$$[0, 1 + \max p]$$$. Maintain a pointer $$$j$$$ starting at index $$$0$$$.

Iterate through $$$p$$$. In each iteration, mark the corresponding index as "true", then use $$$j$$$ to find the first index that remains "false" and output it.

This operation is more commonly known as the mex, over the sets/multisets represented by the prefixes of the sequence.

Special case: If $$$A + B > N$$$, the answer is always $$$0$$$.

Let $$$\alpha := N - A + 1$$$ and $$$\beta := N - B + 1$$$. It can be noted that, disregarding overlaps, there are $$$\alpha^2$$$ choices for the position of the blue square, likewise $$$\beta^2$$$ for the red square. Let's try to count the number of overlapping configurations and subtract them from $$$\alpha^2\beta^2$$$.

It can be noted that if the two squares overlap, the segments they occupy considering the $$$x$$$ axis must overlap, and likewise the $$$y$$$ axis as well. Thus we can reduce the problem to counting $$$v$$$, the number of ways an $$$A$$$-length segment can overlap with a $$$B$$$-length segment within an $$$N$$$-length interval, then squaring it to get the number of overlapping configurations.

To count that, we can reverse the problem yet again by subtracting the number of ways the intervals can not overlap from $$$\alpha \beta$$$. Assuming the $$$A$$$-length segment goes to the left of the $$$B$$$-length segment, let $$$k$$$ be the left end of the $$$B$$$-length segment. Then it can be noted that:

If $$$k = A$$$, there is only one position the $$$A$$$-length segment can go in;
If $$$k = A+1$$$, there are two positions the $$$A$$$-length segment can go in;
If $$$k = A+2$$$, there are three positions the $$$A$$$-length segment can go in, etc.

Thus the total number of configurations (assuming $$$A$$$ goes before $$$B$$$) is the $$$\gamma$$$-th triangular number, i.e. $$$\dfrac {\gamma (\gamma + 1)} 2$$$, where $$$\gamma := N-A-B+1$$$, the number of possible positions of $$$k$$$. This number also applies to the case where $$$B$$$ goes before $$$A$$$ (by reflection), so we can get rid of the $$$2$$$ divisor and get $$$v := \alpha \beta - \gamma (\gamma + 1)$$$

Then obtain the final answer by $$$\alpha^2\beta^2 - v^2$$$. Note that the intermediate products may overflow even a 64-bit integer, thus it's important to calculate them under modulo as well.

Reframe the problem as: for each tidy square, how many configurations will light it? This sum is equal to the sum the problem asks for.

Let $$$p_{i, j}$$$ denote the number of positions a lamp can be placed to light square $$$(i, j)$$$. This can be precalculated in $$$O(HW)$$$ by two-pointer technique (whenever you encounter a wall or the end of a line, add the run-length to the tidy squares. This can be done both horizontally and vertically, but remember to subtract $$$1$$$ from the end as the square $$$(i, j)$$$ itself will be counted twice)

The number of configurations that light a tidy square $$$(i, j)$$$ is equal to the total number of configurations minus the configurations that don't light the square (i.e. all the places that could light this square are left empty), thus the sum for that square is $$$2^K - 2^{K - p_{i, j}}$$$.

Thanks to Everule for help with this problem.

Let's denote the random variates with $$$X_i$$$ (capital X) to avoid confusion with the parametric variable $$$x$$$ in the following notations.

Let $$$F(x) := \Pr[\max X \leq x]$$$, the cumulative distribution function (CDF) of the maximum variate. There is a formula for deriving the expected value from the CDF of a random variate:

The latter integral can be ignored as $$$F(x) = 0$$$ for all $$$x \leq 0$$$. We can also adjust the upper bound of the left integral to $$$\max R$$$ as $$$F(x) = 1$$$ when $$$x \geq \max R$$$. Thus we may simplify:

Now let's figure out the behavior of $$$F(x)$$$. We may note that it's the product of the CDFs of all the individual random variates:

Let $$$f_i(x) := \Pr[X_i \leq x]$$$. Let's decompose $$$f_i(x)$$$, the CDF for a single variate:

Note that the middle expression is a degree-$$$1$$$ polynomial. To analyze the behavior of $$$F(x)$$$ we can imagine a sweep line on decreasing $$$x$$$. When $$$x$$$ touches the $$$R_i$$$ of one of the given intervals, its corresponding $$$f_i(x)$$$ "switches on" and contributes its middle expression to the product. Then as soon as $$$x$$$ touches $$$\max L$$$ one of the CDFs goes to $$$0$$$, which sets the product to $$$0$$$ for good. (This matches intuition, as the maximum variate could never be less than $$$\max L$$$). From this we can conclude that $$$F(x)$$$ is a piecewise function, with each piece being describable by a polynomial. We can integrate each piece individually, and their sum would be the integral of $$$F(x)$$$.

What does this mean in terms of implementation? We could at first set variable $$$E := \max R$$$, and sort all intervals in non-increasing (descending) order of $$$R_i$$$ (henceforth we assume $$$R_i \geq R_{i+1}$$$ for all $$$1 \leq i \leq N-1$$$). Let $$$m$$$ denote the number of intervals where $$$R_i > \max L$$$. Let $$$S_{1..m} := R_{1..m}$$$, and $$$S_{m+1} := \max L$$$, which together denote the change-points of $$$F(x)$$$.

Now let $$$p_0(x)$$$ be the polynomial $$$1$$$ (storing all polynomials as arrays of coefficients). As you iterate $$$i$$$ over $$$[1, m]$$$, construct the new polynomial:

Then integrate this polynomial over $$$[S_{i+1}, S_{i}]$$$ (the formula being derivable from the power rule for integrating polynomials):

Subtract each integral from $$$E$$$ and we have our desired expected value. Don't forget to multiply by the required scaling factor $$$(N+1)! \cdot \prod_{i=1}^N (R_i - L_i)$$$ before outputting.

This works in $$$\tilde O(N^2)$$$ as the polynomial increases in length by $$$1$$$ each iteration, taking about $$$\tilde O(n)$$$ to multiply and to integrate. The tildes (~) over the O's indicate hidden $$$\log$$$ factors from modular inverses and exponentiation. It can also be optimized to strict $$$O(N^2)$$$ using the multiple inverse trick and by accumulating the powers instead of exponentiating each time.

Easy programming-language-knowledge check typical of the first task of AtCoder beginner contests. The following is a passing Kotlin submission:

fun main() {
    val k = readLine()!!.toInt()
    val ans = "ACL".repeat(k)
    println(ans)
}

Assume there is an integer in both ranges and call it $$$x$$$. Note that both $$$x \ge \max(A, C)$$$ and $$$x \le \min(B, D)$$$ must therefore be true.

Thus $$$x$$$ exists if and only if $$$\max(A, C) \le \min(B, D)$$$ is true. This is the standard formula for finding the overlap of two ranges.

Note that the initial network of cities can be divided into one or more components, where any city of a component can reach any other city in that component following roads, but there are no roads connecting components together.

If there are $$$c$$$ components, Snuke can connect two of them by choosing one city from each component and building a road between them, which combines them to a single component; so the answer would be $$$c - 1$$$.

Components can be found using breadth-first/depth-first searches, however there's an easier way if you already have a special data structure known as DSU (disjoint-set union). And there is an implementation available right in the dsu module of the AtCoder library. So start with $$$c := N$$$, for each road given in the input, you can use same to check if the vertices are already connected; if they aren't, merge them and decrement $$$c$$$.

Note that though the input is $$$1$$$-indexed, the AtCoder DSU implementation is $$$0$$$-indexed.

Imagine an array $$$B$$$, initially filled with zeros. The answer then can be theoretically obtained with the following algorithm:

For each $$$a$$$ in $$$A$$$:

• Find $$$\displaystyle\max _{j = a-k} ^{a+k} B_j$$$. Let it be $$$r$$$
• Set $$$B_a := r+1$$$. This works because you are finding the longest subsequence that can include $$$a$$$, and then extending it.

Then the final answer is $$$\max B_i$$$.

Unfortunately this is too slow as searching for the maximum in a range naively is $$$O(K)$$$, thus making the final complexity $$$O(NK)$$$. However, there is a special data structure that solves this problem, called a segment tree.

Segment trees work by storing the array data in the leaves of a fixed binary tree, then storing a "sum" in the ancestor nodes of those leaves. Updating a single entry is slower than a normal array as $$$O(\log n)$$$ ancestors need to be updated, but querying the "sum" of a range becomes much faster, as only $$$O(\log n)$$$ nodes need to be accessed, and the data "summed".

The scare quotes around "sum" imply that it's a more general term — segment trees can indeed implement sums, but more generally, it can implement any monoid. Basically, it's a closed binary operation $$$(S \oplus S) \rightarrow S$$$ that is both associative and has an identity element.

As you are only storing non-negative integers, the $$$\max$$$ operator indeed has an identity element, $$$0$$$. Even if you needed to store negative integers, you can typically set the identity to any number lower than anything else you'd use (just like how you might use a large number as "infinity" in DP/greedy problems)

The segtree module in the AtCoder library is an implementation of a segment tree. Be sure to read the documentation carefully; you need to set the operator and identity element. Ranges should be entered in half-open form, and be careful of accidentally exceeding the index limits in queries.

There is also a way to solve this using only an ordered map.

Precalculate $$$10^x$$$ (under modulo, of course) for $$$0 \le x \le N$$$. Also precalculate $$$\displaystyle ones(x) = \sum _{j=0} ^{x-1} 10^j$$$ for $$$0 \le x \le N$$$, representing the value of a string of all ones of length $$$x$$$.

This problem should remind you a lot of the previous one, however you now have to also update on a range. This can be done using a lazy-propagating segment tree. It's "lazy" because range updates are not all done straight away, but could be "queued" up in an ancestor node, only being "pushed" toward the leaves when needed for queries.

There is a lazysegtree in the AtCoder library as well. Configuring it for this problem is a little more involved than the previous one:

• The monoid operator isn't a simple sum, but requires that the size of the segment to be known as well. Thus $$$S$$$ should be a tuple $$$(sum, size)$$$, with the operator $$$(sum_a, size_a) \oplus (sum_b, size_b) = (sum_a \cdot 10^{size_b} + sum_b, size_a + size_b)$$$. Its identity, $$$e = (0, 0)$$$. The $$$sum$$$ terms should be under modulo.

• $$$F$$$, the mapping, can be a simple integer indicating the digit to update with, however a "null / identity map" needs to be assigned as well, this could be $$$id = -1$$$. $$$composition(g, f)$$$ should be $$$g$$$ (the newer update is on the left as in the traditional notation $$$(g \circ f)(x) = g(f(x))$$$). $$$mapping(f, s)$$$ should be $$$s$$$ if $$$f = id$$$, and otherwise $$$(f \cdot ones(size_s), size_s)$$$

The rest is then just implementing the task. Note that when initializing the segment tree, the value $$$(1, 1)$$$ needs to be set individually to all indices; you can't just queue a $$$1$$$ range-update as they start out as the empty segment $$$(0, 0)$$$.

You can also still solve this with an ordered map.

Define a bad pair as a pair where the two persons' heights are equal.

Let's define a useful function $$$\displaystyle pairs(n) := \frac{(2n)!}{n!\cdot 2^n}$$$, the number of ways to make $$$n$$$ pairs (good or bad) out of $$$2n$$$ people. Explanation: Start with any of $$$(2n)!$$$ permutations. When you pair them up, you don't care about the order within the pair, so you divide by $$$2$$$ a total of $$$n$$$ times. Then you also don't care about the order between the pairs, so you divide by $$$n!$$$.

The main idea involves the Inclusion–exclusion principle.

In general, principle of inclusion-exclusion (PIE) can be summarized with the following steps:

1. Identify a set of "violations", i.e. a set of rules you want to obey and specific requirements for each rule to be broken.
2. Identify a way to calculate $$$F(S)$$$: for every subset $$$S$$$ of possible violations, the number of ways to violate at least that subset (note that we don't need to know how to calculate the number of ways to violate exactly that subset).
3. The number of ways to obey all rules (i.e. not commit any violations) will then equal $$$(\sum _ {|S| \text{ is even}}F(S)) - (\sum _ {|S| \text{ is odd}}F(S)) = \sum _ S (-1) ^ {|S|} \cdot F(S)$$$ (note that zero is also even)

In this problem there are up to $$$N$$$ possible violations, i.e. the $$$i$$$-th pair of people being of equal height, i.e. a bad pair. Note that we don't actually care about the order of the pairs, so we can just push all the "bad pairs" to the beginning, so we actually only have to worry about $$$O(N)$$$ possible subsets of violations. Let's define $$$G(k) = \sum _ {|S|=k}F(S)$$$, and calculate the final answer as $$$(\sum _ {k \text{ is even}}G(k)) - (\sum _ {k \text{ is odd}}G(k)) = \sum _{k=0} ^N (-1) ^ {k} \cdot G(k)$$$

Let $$$f(k)$$$ be the number of ways to match up $$$k$$$ bad pairs from the $$$2N$$$ given people. We can thus see that $$$G(k) = f(k) \cdot pairs(N-k)$$$; note we don't care about accidentally making more bad pairs, as it's accounted for in the definitions of $$$F(S)$$$ and $$$G(k)$$$.

Now let's figure out how to find $$$f(k)$$$. First note that the exact heights don't matter, only their equality. We can divide the people into components with the same height as each other. Collect all component sizes into array $$$a$$$. For example, if $$$h = [1, 1, 1, 2, 2, 4]$$$, then $$$a = [3, 2, 1]$$$. This can be easily done using sorting and run-length compression.

Then from each component $$$a_i$$$, construct array $$$b_i$$$, indexed over $$$[0, \lfloor a_i/2 \rfloor]$$$, where $$$b_i[j]$$$ denotes how many ways are there to fix $$$j$$$ bad pairs from this component. $$$\displaystyle b_i[j] = \binom {a_i}{2j} \cdot pairs(j)$$$, since we take $$$2j$$$ people from the component and make $$$j$$$ pairs out of them.

In the case of a single component, $$$f(j) = b_1[j]$$$, but how do we combine the results of several components? Let's assume we have only two components. Then we may take $$$0$$$ bad pairs from one component and $$$j$$$ from the other, or $$$1$$$ from one and $$$j-1$$$ from the other, etc., therefore:

$$$\displaystyle f(j) = b_1[0] \cdot b_2[j] + b_1[1]\cdot b_2[j-1] + b_1[2]\cdot b_2[j-2] + ... + b_1[j]\cdot b_2[0] = \sum_{i=0}^j b_1[i] \cdot b_2[j-i] $$$.

This is called a convolution, and is the same formula for when we multiply two polynomials of the form $$$p(x) = B_0x^0 + B_1x^1 + B_2x^2 + ... + B_nx^n$$$ and wishing to find the $$$j$$$-th coefficient. The case with more components is similar, except we must convolve all the $$$b_i$$$ arrays, i.e. find the product of several polynomials of different lengths.

[One can visualize this by treating $$$x^k$$$ as a formal symbol meaning "ways to make $$$k$$$ bad pairs", which naturally add together when their coefficients are multiplied]

However, computing convolutions for two polynomials of size $$$n$$$ and $$$m$$$ naively is $$$O(nm)$$$, which is too slow. There is just the right tool in the AtCoder library for that; the function convolution. This function uses the Fast Fourier Transform method to convolve two polynomials in $$$O((n+m) \log (n+m))$$$. However note that it only accepts two arguments, and convolving multiple polynomials could be inefficient if called in the wrong order; imagine if you had about $$$N/2$$$ polynomials, and all of them are short except for one. Then imagine if you convolved a short one to the longest one over and over; suddenly your submission takes $$$O(N^2 \log N)$$$ and times out.

Fortunately there is a simple fix: just put all the polynomials into a queue. While there is more than one polynomial in that queue, withdraw two from the front, convolve them, then put the result back in the end of the queue.

This works in $$$O(N \log ^2 N)$$$, the worst case being $$$N$$$ polynomials of degree $$$1$$$ (length $$$2$$$), which would take $$$O(\log N)$$$ "cycles" to fully combine, with the convolutions taking a time of $$$O(N \log N)$$$ each cycle.

And thus finally, you are able to obtain $$$f(k)$$$ by reading the coefficients of the final polynomial, and can apply the inclusion-exclusion formula above to obtain the answer.

Should be easy as long as you know the basics of your chosen programming language. Can be computed with an if/else statement, the ternary operator (ans = x == 1 ? 0 : 1), or the xor operator (ans = x ^ 1)

Answer is one of: $$$a \cdot c, a \cdot d, b \cdot c, b \cdot d$$$; find the maximum of these and print it.

Proof by exchange argument: No matter what you pick $$$x$$$ to be, you can improve the product by either maximizing or minimizing $$$y$$$, based on the sign of $$$x$$$. Same argument applies when $$$x$$$ and $$$y$$$ are swapped.

There are $$$10$$$ possible digits among $$$n$$$ positions, thus the total number of sequences that satisfy the first constraint is $$$10^n$$$.

Now we want to subtract sequences that violate the second or third constraints. We can construct $$$9^n$$$ sequences without any 0s (violating the second constraint), same with sequences without any 9s (violating the third constraint).

However if we subtract $$$2 \cdot 9^n$$$, note that we have subtracted the sequences that violate both the second and third constraints twice. There are $$$8^n$$$ such sequences (as they lack both 0s and 9s), so we add them back to get the correct count. This pattern of overcounting, adding, overcounting, subtracting, repeat until a final accurate count is known as the inclusion-exclusion principle.

Final answer is thus $$$10^n - 2 \cdot 9^n + 8^n$$$. This can be calculated in $$$O(n)$$$ via repeated multiplication, or $$$O(\log n)$$$ via fast exponentiation. If you don't know how to work with large numbers under a modulus, see my tutorial on that subject.

Can be done with basic dynamic programming. Let $$$dp_i$$$ represent the number of sequences whose sum is $$$i$$$. $$$dp_0 = 1$$$, the empty sequence. Then $$$\displaystyle dp_i = \sum_{j=0}^{i-3} dp_j$$$, i.e. the sum of $$$dp_j$$$ for all integers $$$j$$$ between $$$0$$$ and $$$i-3$$$ inclusive, representing the addition of a number $$$\ge 3$$$ to each of the previous sequences. The final answer, naturally, is $$$dp_s$$$.

This can be easily calculated in $$$O(s^2)$$$, which is good enough to pass, however it can be improved to $$$O(s)$$$ by accumulating the prefix sum.

An $$$O(\log s)$$$ solution is possible via matrix exponentiation.

We can take the following approach — for each $$$i$$$ from $$$2$$$ to $$$n$$$, try to match $$$(x_i, y_i)$$$ with the "best" previous point $$$(x_j, y_j), 1 \le j < i$$$, then update the answer.

Testing all previous points is too slow ($$$O(n^2)$$$). However, it is sufficient only to keep up to $$$4$$$ previous points to test against. $$$2$$$ of those points are the maximal and minimal of the "score" $$$x_i + y_i$$$, while the other $$$2$$$ maximize and minimize $$$x_i - y_i$$$

Why? Note that taking any point as the center, the set of points with Manhattan distance some arbitrary constant $$$d$$$, forms a "diamond" shape, i.e. a square rotated 45 degrees. Thus the furthest point must lie on at least one of the four sides of this square when $$$d$$$ is maximized. As the sides are on lines with equations of $$$x+y = C$$$ or $$$x-y = C$$$, the maximums and minimums of these values are sufficient to find the furthest point in each of the 4 possible directions.

Thus we have a solution in $$$O(n)$$$.

Let $$$C$$$ be the array that holds the answer sequence. At first, we can greedily put any value of $$$B$$$ that doesn't match $$$A_i$$$ for each position from left to right.

If this strategy fails, it means that we are in a position where $$$A_i = z$$$ and all remaining members of $$$B$$$ are $$$z$$$. If we put all the remaining $$$z$$$ values into $$$C$$$, the situation looks like this:

A = [   < z   ][           z           ][    > z    ]
C = [ maybe z ][  not z  ][            z            ]
                          {TROUBLE ZONE}

So to fix the "trouble zone", we need to swap the $$$z$$$ values in it with some other values. It can be seen that the only values we can swap with lie in the "maybe $$$z$$$" zone; we can't swap with "not $$$z$$$" as that will cause another collision.

Thus we can iterate through the "maybe $$$z$$$" zone to try to find enough non-$$$z$$$ values to swap with. If we run out of values to swap with without eliminating all collisions, the answer is No, as there are no more values to swap with.

public static long multiplyHighUnsigned(long x, long y) {
    long x_high = x >>> 32;
    long y_high = y >>> 32;
    long x_low = x & 0xFFFFFFFFL;
    long y_low = y & 0xFFFFFFFFL;
        
    long z2 = x_low * y_low;
    long t = x_high * y_low + (z2 >>> 32);
    long z1 = t & 0xFFFFFFFFL;
    long z0 = t >>> 32;
    z1 += x_low * y_high;
    return x_high * y_high + z0 + (z1 >>> 32);
}

function mulMod(a: Long, b: Long): Long {
    xh = multiplyHighUnsigned(a, b) // high word of product
    xl = a * b // low word of product

    xrh = multiplyHighUnsigned(xh, BARR_R) // high word of xr
    xrm = multiplyHighUnsigned(xl, BARR_R) // middle word of xr, first part
    add = xh * BARR_R // second part of middle word
    xrm += add // add them
    if(add ^ (1L << 63) > xrm ^ (1L << 63)) xrh++ // carry, see note 1

    t = xl - ((xrh << 2) | (xrm >>> 62)) * MOD - MOD // see note 2
    t += (t >> 63) & MOD
    return t
}

Note 1: The carry step does a little trick for unsigned comparison (flip high bits and compare as signed). If the addend is greater than the result, an overflow must have occurred, so we perform the carry.

Note 2: $$$t$$$ fits in 64 bits, so we only need the low word of $$$x$$$. We reconstruct $$$\left\lfloor \frac{xr}{4^{63}} \right\rfloor$$$ with the bits from xrh and xrm. Note we don't need the low word of $$$xr$$$ as it's discarded by the floor operation. When we multiply this factor with $$$m$$$, we ignore the overflow as the final result is guaranteed to fit in 64 bits.

You are basically asked to do the same thing as in part 1, but with $$$119315717514047$$$ cards, and repeating the steps in your input $$$101741582076661$$$ times. Also you're asked for the card in position $$$2020$$$.

If you are familiar with matrices, you may note that the LCF $$$f(x) = ax + b\ \text{ mod } m$$$ can be represented by the matrix $$$\begin{bmatrix} a & b \\ 0 & 1 \end{bmatrix}$$$.

Composing two LCFs correspond to left-multiplying their matrices (i.e. multiplying in reverse order, so $$$f\ ; g \rightarrow M_g \cdot M_f$$$); exponentiation and inversion correspond to their namesake matrix operations. Finally, invoking an LCF with argument $$$x$$$ corresponds to multiplying its matrix to the column vector $$$\begin{bmatrix} x \\ 1 \end{bmatrix}$$$ and obtaining the first (top) value of the resulting vector.

@JvmField val INPUT = System.`in`
@JvmField val OUTPUT = System.out

@JvmField val _reader = INPUT.bufferedReader()
fun readLine(): String? = _reader.readLine()
fun readLn() = _reader.readLine()!!
@JvmField var _tokenizer: StringTokenizer = StringTokenizer("")
fun read(): String {
    while (_tokenizer.hasMoreTokens().not()) _tokenizer = StringTokenizer(_reader.readLine() ?: return "", " ")
    return _tokenizer.nextToken()
}
fun readInt() = read().toInt()
fun readDouble() = read().toDouble()
fun readLong() = read().toLong()
fun readStrings(n: Int) = List(n) { read() }
fun readLines(n: Int) = List(n) { readLn() }
fun readInts(n: Int) = List(n) { read().toInt() }
fun readIntArray(n: Int) = IntArray(n) { read().toInt() }
fun readDoubles(n: Int) = List(n) { read().toDouble() }
fun readDoubleArray(n: Int) = DoubleArray(n) { read().toDouble() }
fun readLongs(n: Int) = List(n) { read().toLong() }
fun readLongArray(n: Int) = LongArray(n) { read().toLong() }

@JvmField val _writer = PrintWriter(OUTPUT, false)
inline fun output(block: PrintWriter.() -> Unit) { _writer.apply(block).flush() }

The output function allows me to wrap all code within the main function in an output { ... } block, and call println etc. within it. It's automatically flushed when the block is finished.