rishabh1889's blog

Alternative solution to 1418C
By rishabh1889, 4 years ago, In English

Here's another approach to the problem C of Education round 95. This is a greedy one.

From the beginning, we keep on looking for continuous segments of $$$1$$$'s. We list their lengths as $$$x_1, x_2, \cdots , x_k$$$.

Let the first segment begin in the first position. The optimal strategy, then, will be that my friend kills one boss, and I kill two. If, however, only one is left for me at the end of the segment, I'll kill only that one leaving my friend to deal with the easy boss (if any) following. The number of skip points used in this case is $$$\left\lceil\dfrac{x_1}{3}\right\rceil$$$. We claim that we can't bring it down further. This is true, as my friend is making a minimal number of moves.

For any segments that do not begin with the first position, we have the optimal strategy as follows. Notice that we always have a sequence of moves such that I can open the segment. If unsure, try proving it.

Proof
Now, I'll kill two bosses, my friend kills one and repeat. In this way, we're using $$$\left\lfloor\dfrac{x_i}{3}\right\rfloor$$$ skip points, where $$$1\le i \le k$$$. As above, we can observe that it is minimal. We just sum all of them up.

Hope you liked it.

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

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I came up with this solution too when I couldn't come up with the dp solution.. but the proof is mostly a bunch of checks (with us trying to be at the beginning of every sequence of 1s) so.. I didn't like this solution much.

The dp solution is a lot better in my opinion.

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

    Right. Even the simplest proof requires us to go through many scenarios. But during a contest, we do not generally try to prove rigorously. Sometimes, we just convince ourselves looking at few cases.

    → Reply