Codeforces and Polygon may be unavailable from May 23, 4:00 (UTC) to May 23, 8:00 (UTC) due to technical maintenance. ×

rishabh1889's blog

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.

Full text and comments »

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