kalimm's blog

Can Anyone Help?
By kalimm, history, 8 years ago, In English

Hi, I can't solve it for a long time. There are really short codes, but I can't get the main idea :( Thanks for help.

http://codeforces.com/contest/83/problem/E

  • Vote: I like it
  • +15
  • Vote: I do not like it

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

Ok Let's notice a fact That f(a1, a2, ..., an) = |a1| — f(a1, a2) + |a2| — f(a2, a3) .... + |ai| — f(ai, a[i+1) + ... + |an|
Now just solve it n ^ 2 and after that solve it nk

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

    How?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      dp[i] = lets partition it till i-1
      for (int l = 0; l < n; ++l)
      for (int r = 1; r <= n; ++r)
      dp[r] = min(dp[r], dp[l] — (r != n? lcp(a[l], a[r]): 0) + |a[l]| + |a[l + 1]| + ... + |a[r — 1]| — f(a[l], a[l + 1]) — f(a[l+1], a[l+2]).... f(a[r — 2], a[r — 1) (this can be found with partial sum));

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        I can't understand :(

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

          well if you partition the sequence into two subsequences the sequence will be like this
          c means it belongs to subsequence c
          b means it belongs to subsequence b
          bbbcccbbccbbbb
          in those fors dp[r] = the best way to partition it till r which r and r — 1 are different and dp[n] is a special case where the nth element doesnt exist
          in those 2 fors l means the first place before r where l and l — 1 are different
          the things that will be added are -f(l, l + 1) -f(l + 1, l + 2) ... -f(r — 2, r — 1) and the sizes of the elements by that lcp i mean (l != 0? |f(a[l-1], a[r])|: 0)
          if you didn't understand tell me again ;D it will be appreciated if you tell the place which you can't understand too

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

            Actually I can't understand anything, there is some formulas and something but what can I do with them? :D

            → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

http://codeforces.com/blog/entry/1976

It's a decent explanation even with Google Translate.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I read it but I can't understand with translate.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      First, some notation. We have binary strings s1... sn each of length k. Let si(l) denote the prefix of si of length l.

      Now, let dp[x][suf] be the minimum cost for strings s1... sx given that one subsequence ends in sx and the other ends in suf. Note that suf can have length between 0 and k. Our state transition is:

      Here is the logic behind the transition. In order to make two subsequences, one ending with sx and the other in suf, we can either append sx to the subsequence ending with sx - 1, or we can append sx to a subsequence ending in sx(l) where 0 ≤ l ≤ k. In the later case, we will end up with one subsequence ending with sx and the other subsequence ending with sx - 1, so we need only evaluate this case if sx - 1 ends in suf.

      I'll let you figure out the details of the implementation as an exercise. You'll need to figure out how to handle state transitions in an efficient manner.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        I solved it yesterday, but I really appreciated for your help. Thanks.

        → Reply