A – Not Overflow
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)$$$
B – Matrix Transposition
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)$$$
C – kasaka
Note that for a string to be a palindrome, it must start with the same number of contiguous a
s as it ends with.
If there are less contiguous a
s at the end of $$$S$$$ than at is start, the answer is No
. Otherwise, add the difference in number of a
s to its start, then test if it is a palindrome.
Time complexity: $$$O(|S|)$$$
D – LR insertion
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)$$$
E – Skiing
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))$$$
F – |LIS| = 3
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.
G – Range Sort Query
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)$$$
Ex – Hakata
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
Actually, in problem Ex. it's well known that $$$|sub| = \mathcal{O}(|S|)$$$, so naive solution works in $$$O(|S|^2\sqrt{|S|})$$$. For every $$$r$$$ there is at most one $$$l$$$, such that $$$s[l \dots r]$$$ is a first occurrence of a palindrome.
Would be very helpful if such blogs / editorial get published for each and every contest.
I have the feeling that F can be solved for higher constraints is it possible?? Using flow or generating function or dp tricks whatever??
I know that if $$$N$$$ is large it can be solved with matrix exponentiation in $$$O(M^{9} \log N)$$$. The $$$M^9$$$ part seems scary but if you actually count the number of possible states, the matrix dimension is $$$\binom M 0 + \binom M 1 + \binom M 2 + \binom M 3 \leq 176$$$, making the time $$$\approx O(176^3 \log N)$$$, which should be passable.
Yup quite a nice trick , very close to time limit tho
Why Prim's algorithm is not working on problem E(skiing)?
Initially, I solved E with just some observations on making 1 edge as 0 and the other as positive to find answer, but seeing editorial it turns out that this trick can be applied at various places with correct potential function... Thanks for the editorial.:) If you have some problems based on this theme, can you please post some? :)
1627E - Not Escaping
AtCoder Beginner Contest 214H — Collecting – kinda advanced, requires strongly-connected component find, and min-cost-max-flow. The AtCoder library has implementations for those.
For Problem E, can someone mention how can we prove this potential function works i.e. how to prove the second requirement of a valid potential function is satisfied?
Let the shortest path between $$$u$$$ and $$$v$$$ be $$$u, p_1, p_2, ... p_m, v$$$, and $$$w(u, v)$$$ be the unadjusted weight of the edge between $$$u$$$ and $$$v$$$.
$$$dist'(u, v) = (w(u, p_1) + \phi(u) - \phi(p_1)) + (w(p_1, p_2) + \phi(p_1) - \phi(p_2)) + \dots + (w(p_m, v) + \phi(p_m) - \phi(v))$$$
Every $$$ +\phi(p_i)$$$ is cancelled by $$$-\phi(p_i)$$$ in the previous bracketed expression, so we are left with
$$$dist'(u, v) = (w(u, p_1) + w(p_1, p_2) + \dots + w(p_m, v)) + \phi(u) - \phi(v)$$$
Can anyone explain approach to solve F with code or the dp transitions in detail? I am not able to understand this editorial since I am a beginner in dp.
I'm beginner in dp too so bear with me. Just in case, are you familiar with LIS dp algo? (I were not). If not read about it.
Let's think for some case. Where can we get next L = {1, 2, 3} from? Maybe sum counts from current L = {1, 2, 3}, L = {1, 2, 4}, L = {1, 2, 5}, ... right?
So, for current L = {1, 2, 5}, we're going to add current counts to next L = {1, 2, 5}, L = {1, 2, 4}, and L = {1, 2, 3}. Notice that those three Ls were the loop 5, 4, and 3. (think what does the loop number mean)
What about loop 2 and 1? both add to next L = {1, 2, 5}. (think why + think about loop 2 for when L = {1, 3, 4})
What about loop 6, 7, ... ? do nothing, because it will make our LIS > 3.
This may not be the best approach but it makes sense for me, hope it helps.