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!
What wrong with you, all of down-vote lover. You can consider what wrong with my question here.
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
Hmm Interesting Theory!, I should try it.
Yeah sure you can. You wont believe, once you become red you will be upvoted even for shitposting
I am so sad to realize the fact. I will try it later when i become purple rating.
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 \lt =j \lt =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$$$.
Does $$$is[i+1], is[i+2]$$$ is always false, because with one or two characters, we can't construct a valid file name?
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$$$.
ok, i got it. Thank u a lot
My solution for this problem using DP. I implement it quite hard, are there any ways to implement it much better mine?