Spheniscine's blog

By Spheniscine, history, 3 years ago, In English

A – Not Overflow

Spoiler

B – Matrix Transposition

Spoiler

C – kasaka

Spoiler

D – LR insertion

Spoiler

E – Skiing

Spoiler

F – |LIS| = 3

Spoiler

G – Range Sort Query

Spoiler

Ex – Hakata

Spoiler
  • Vote: I like it
  • +115
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Would be very helpful if such blogs / editorial get published for each and every contest.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I have the feeling that F can be solved for higher constraints is it possible?? Using flow or generating function or dp tricks whatever??

  • »
    »
    3 years ago, # ^ |
    Rev. 7   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yup quite a nice trick , very close to time limit tho

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why Prim's algorithm is not working on problem E(skiing)?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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? :)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.