### Spheniscine's blog

By Spheniscine, history, 20 months ago, Spoiler

Spoiler

Spoiler

Spoiler

Spoiler

Spoiler

Spoiler

### Ex – Hakata

Spoiler dp, Comments (12)
 » 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.
 » 20 months ago, # | ← Rev. 2 →   I have the feeling that F can be solved for higher constraints is it possible?? Using flow or generating function or dp tricks whatever??
•  » » 20 months ago, # ^ | ← Rev. 7 →   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? :)
•  » » 20 months ago, # ^ | ← Rev. 2 →   1627E - Not EscapingAtCoder 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?
•  » » 19 months ago, # ^ | ← Rev. 3 →   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.