Hd7's blog

How to solve this problem by using DP?
By Hd7, history, 5 years ago, In English

The problem VK2012 B — File List.
I solved it by using greedy, but this problem was tagged dp and the editorial instructed dp approach such that:

is [i] — can we cut the prefix of length i .

Initially, is [0] = 1, the remaining zeros.

Now iterate over i in ascending order and if is [i] = 1, try to make the transition to i  + 1 .. i  + 12

I still can't solve it by DP, could you give me a more detailed explanation to solve this problem using DP? Thanks in advance!

Tags #dp
  • Vote: I like it
  • -9
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What wrong with you, all of down-vote lover. You can consider what wrong with my question here.

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

    You need to be atleast candidate master to keep any hopes for getting upvotes and good responses. First become that and ask the same question again. See the difference yourself

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

      Hmm Interesting Theory!, I should try it.

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

        Yeah sure you can. You wont believe, once you become red you will be upvoted even for shitposting

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

      I am so sad to realize the fact. I will try it later when i become purple rating.

      → Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

If we knew the fact that we can divide the prefix ending at $$$i$$$ ($$$is[i]=true$$$), so we have complete partition ending at $$$i$$$, and we can now try to make the next part, which starts at $$$i+1$$$ and ends at either one of the positions $$$i+1$$$, $$$i+2$$$, $$$\dots$$$, $$$i+12$$$, inclusive.

Why $$$+12$$$? Because the longest valid file name possible is $$$8+1+3=12$$$: $$$8$$$ for the first part (of the file name), $$$1$$$ for the period and $$$3$$$ for the second part.

So, at each position $$$i$$$ where $$$is[i]=true$$$, we will try all the substrings $$$A[i+1\dots i+j]$$$ (where $$$1<=j<=12$$$), and at each $$$j$$$, we see if the substring is a valid file name (depending on the conditions in the statement), if yes, we set $$$is[i+j]=true$$$, and here we can keep tracking for an answer by define an array $$$par[]$$$, and when we set $$$is[i+j]=true$$$, we set $$$par[i+j]=i$$$.

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

    Does $$$is[i+1], is[i+2]$$$ is always false, because with one or two characters, we can't construct a valid file name?

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

      Not exactly, but if $$$is[i]=true$$$ you cannot update the values at $$$i+1$$$ and $$$i+2$$$ because of the reason you mentioned, but $$$is[i+1]$$$ and $$$is[i+2]$$$ can be $$$true$$$ because of a valid position before $$$i$$$.

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

        ok, i got it. Thank u a lot

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

My solution for this problem using DP. I implement it quite hard, are there any ways to implement it much better mine?

→ Reply