lucius_fox's blog

Need help with Codeforces Round #885 (Div.2). A — Vika and Her Friends
By lucius_fox, history, 12 months ago, In English

This problem has left me baffled, I couldn't come with a proof for the solution so I looked at the editorial. In its editorial I don't understand what this term "area to Vika" means, its definition is written with a really confusing language and I can't understand it(none of the three cases). If you could please help me understand what it means(perhaps through a picture or by just rewording it) I would be grateful. Thank you

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by lucius_fox (previous revision, new revision, compare).

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by lucius_fox (previous revision, new revision, compare).

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Don't feel too bad if you can't solve it because the problem is much harder than usual div2 A.

First, as the editorial says, if none of her friends is on a cell of the same color as Vika, Vika can always escape, because in one move, you will surely change your color. This is not hard to understand.

What we want to do now is to prove that Vika can't escape if there is at least one of her friends is on a cell of the same color as Vika. Since multiple people is allowed to stand on the same cell, we can consider the catchers independently. Hence, let's choose any of the friends who is in a cell of the same color as Vika. We will show how the friend will act to catch Vika in a finite time.

How can you prove some kind of process is finite? Well, a good idea is to do it by induction. As you may know, induction basically works on some nature numbers like this:

  • Step 1 (Corner Case): You prove that for unary predicate $$$p$$$, $$$p(0)$$$ is true.
  • Step 2 (Inducting): You prove that if $$$p(k)$$$ is true, than $$$p(k+1)$$$ is true.
  • Step 3 (Conclusion): You conclude that for every $$$k$$$, $$$p(k)$$$ is true.

I prefer to call the the parameter of $$$p$$$ a potential-value, because this number indicates the number of steps left to transform the current case to the corner case. In most problems, the potential-value can be very obvious, but not in our problem. The key of applying induction to out problem is to define our own potential-value, and that is the so called "area to Vika" in the editorial.

In other words, the editorial proves the value of "area to Vika" (or the potential-value in the induction prove), is always strictly decreasing move by move and when it decreases to $$$0$$$, Vika was caught (please refer to the original editorial about the detailed proof, the main topic here is that I want to illustrate the motivation of defining "area to Vika").

You will meet this idea again in the so called "potential analysis" in time complexity analysis. In potential analysis, we give each state of the algorithm a value called "potential energy", and we prove that in each step of the algorithm, the potential energy will be deceased by at least 1, so we can conclude the algorithm's overall time complexity is no bigger than the potential energy of the initial state.

→ Reply