MAGIC - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

Hard

PREREQUISITES:

Dynamic programming, Combinatorial game theory, Graph theory

PROBLEM:

Best explained in the problem statement itself.

DETAILED EXPLANATION:

  1. If vertices 1 and 2 belong to one connected component, the first magician wins in the first turn.

  2. We don’t care about individual vertices, all we care about is connected
    components. This is so because in phase 1, magician can freely travel within a
    connected component.

  3. Further, even about connected components, the only information we need is
    their vertex size and their edge count. Their internal structure doesn’t matter
    (as a follow up of point 2)

  4. If there is a missing edge in a connected component, we’ll always be able to
    create such an edge until it’s actually created. What this means for us is for
    each connected component, we only need to care about vertex sizes and can ignore
    their edge counts. Reason is edges which are already present in them can’t be
    reused and edges which are missing have nothing special regarding that
    component. So if we also store the total number of edges that could be added without
    changing the component count, we don’t need to care about edges of individual
    components. From now on, any edge which can be added without changing component
    count will be called a potential edge.

  5. Usually games are solved via a DP. We need to be able to fully represent game
    in our DP state. So from previous observation, following state is sufficient :
    a) the size of the component in which the current magician is located
    b) the size of the component in which the other magician is located
    c) a sorted list of sizes of other existing components (note that we don’t care about their order)
    d) the number of potential edges
    e) the number of telepoints of the current magician
    f) the number of telepoints of the other magician

  6. What would be transitions in this DP? We could either create a potential
    edge. Or we could connect any two components (creating some new potential edges
    as well). It’s also possible to teleport somewhere afterwards.

  7. Each state is either winning or losing. As usual, if from state X we can move to
    winning states only, then state X is losing. If we can move from state X to at least
    one losing state, then state X is winning. In particular, if no safe moves are possible
    in state X, then state X is losing.

  8. Adding a potential edge doesn’t change the state of the game at all except
    for reducing the number of potential edges. So it is more like a ‘pass’ turn
    with fixed number of ‘pass’ turns allowed. As with any other game, parity of
    ‘pass’ turns matter as if my opponent passes, I could pass as well. And we both
    would continue doing so until 1 or 0 ‘pass’ turns remain. So we don’t really
    care about exact number of potential edges, but only their parity.

  9. Suppose in our turn we connect components with sizes X and Y. We
    create XY-1 potential edges in this case. The components’ sizes are used only here.
    From previous point it can be seen that we are only interested in the parity of each component’s size too.

  10. That’s a breakthrough! Now our DP state contains the parities of a), b) and d),
    two integers denoting the number of even-sized and odd-sized components - instead of a sorted list
    and two more integers denoting the number of teleporting points of both the
    magicians. Thus there are only O(N2 * P2) DP states now.

  11. When would a magician ever need a teleportation? There is only one possibility – if he connected his component and his opponent’s component in this turn.

  12. There are three fundamentally different connecting moves – connecting two
    even components, an even and an odd component, or two odd components. All
    even-even moves are alike. Similarly all odd-even moves are alike and so are all
    odd-odd moves.

  13. If there are only two components left, there is no place for teleportation
    after connecting these two components. Hence assume that there are atleast 3
    components if a magician is forced to use teleportation point.

  14. Connecting two even components creates an even number of potential edges and
    decreases the number of even components by 1. If the only two even components are
    the components where the magicians are located, it seems that the current magician
    may really need this move to win (if there are more than two even components, he can connect his component and some other even component, for example). But note that he can also connect his component and any other odd component instead – in this case an even number of potential edges is created and the number of even components is decreased by 1, which is the same effect as if he connected two even components. That being said, there is no real need for teleportation in this case.

  15. Connecting an even and an odd component— As there are at least 3
    components, there is always a way to choose these components so that at least one of them doesn’t contain a magician. So there is no real need for teleportation here either.

  16. Connecting two odd components may require a teleportation in case the only two odd components both contain magicians. But note that after such a move all the components will be even-sized! That means that this case is possible at most once during the whole game.

  17. We see that no magician will ever need more than one teleportation during
    the game. The answer for P > 1 is thus the same as for P = 1. We can
    change P into min(P, 1). Now we have only O(N2) DP states
    (actually about 2 * 2 * N * (N/2) * 2 * 2 * 2 ~ 16N2). This is still a bit too much.

  18. If you print some values of DP into a file, you’ll see that for evenComp = 5
    and for evenComp > 5 the answers are the same. That means if in our DP state the
    number of even components is more than 5, we can shrink it to exactly 5 without
    changing the answer. This makes the number of states be O(N), which must be enough to get AC.

  19. A similar thing can be applied to the number of odd components. The
    difference is that the values of DP are periodic with period 4 according to the
    number of odd components (starting from 5 or even less). So we can do the
    following: while (oddComp > 8) oddComp -= 4;. The number of DP states is
    O(1) now, so it easily passes the time limit.

  20. Previous two points together can be proved using induction. Let’s build our DP by diagonals (that is, filling the states with smaller oddComp+evenComp sum first). Every diagonal is filled using the information from the previous diagonal only. As the properties above apply starting from some diagonal (it can be verified using computer :)), it can be proved that they apply for each of the next diagonals as well.

DP is not the only way to solve this problem. There are closed form solutions as
well!

  1. Note that when the magicians play optimally the game ends with two components which are full of edges.
    Now for N = 1 (mod 4) any separation into two components results in an even total number of edges.
    This way the winner can be determined from the number of edges already present in the graph
    (if it’s odd, the first wins, otherwise the second). You should check this
    property by hand for small cases, it is not that obvious.

  2. For N = 3 (mod 4), it’s the opposite – any separation results in an odd total number of edges.
    From previous two points, we can solve the game easily by simple checks of
    parity of N and parity of edge count if N is odd. Again, check this
    property by hand as well.

  3. For N = 2 (mod 4) the first magician wins if ((the initial number of edges
    is even) XOR (the resulting components are both odd-sized)) is true.
    For N = 0 (mod 4) it’s exactly the opposite. Overall, one of the players wins if he
    manages to make both final components even-sized, and the other wins if he manages
    to make both final components odd-sized. You’re encouraged to check this
    property by hand as well. If you’ve not already guessed, previous three
    properties hold because the parity of the quantity K * (K - 1) / 2 is periodic with period of four.

  4. That calls for a greedy. It seems the “odd” player should always try to connect even-odd
    components or even-even components (so that the number of even components decreases),
    and the “even” player should always try to connect odd-odd components.
    Yet it isn’t so easy to code this solution correctly (especially from the first attempt).
    One good testcase is N = 6, M = 0, P = 1. The first player needs two even components,
    and the second player needs two odd components. The first player may connect vertices
    3 and 4, the second may connect vertices 3 and 5. Now there are four components with
    sizes 3, 1, 1, 1. It seems reasonable for the first player to connect two odd components
    to make it, for example, 4, 1, 1. Yet the second player would connect the
    components with sizes 4 and 1 and win.
    Actually the first player should connect vertices 4 and 5 in his turn.
    Then the second player will be forced to connect two odd components (a bad move for him!),
    and the first player will connect the other two odd components and win.

  5. Another thing – some contestants coded a DP solution with O(N2) and then tried to
    code all possible cases (some of them definitely succeeded). Yet that’s useless.
    This DP is periodic, so applying points 18 and 19 is easier.

My suggestion to everyone is to go through all the Ac solutions, there aren’t too many of them anyway. Different contestants have slightly different solutions and there is plenty to be learnt.

On a side note, initially constraints of this problem were set to allow
O(N2) solutions to pass and each magician had infinite
telepoints. The problem was considered to fit in Medium category. Later it was
decided to increase these constraints to the current value. But then setter came
up with a greedy solution (as outlined above). To manage that, concept of
telepoints was introduced. Though a greedy solution exists for this case as
well, it is much less obvious. Through out the process we guessed the problem would be an easy Hard / tougher medium problem but in the end it turned out to be much more difficult that we thought it to be!

SETTER’S SOLUTION:

Can be found here.

TESTER’S SOLUTION:

Can be found here.

2 Likes
2

Very nice editorial! Thank you.

3 Likes
3

Awesome problem and great editorial!!

Here is a nice writeup to solve two person problem in general

3 Likes
4

The 4th step (greedy) in the second approach can be analyzed further.

  1. If P>0 and there is at least 1 even
    component on the “even” player’s
    turn, the “even” player wins.
    (He
    can keep connecting odd-odd
    components, and optionally teleport
    when connecting last 2 odd
    components)
  2. If P>0 and there are only 2 odd components (no even
    components) on the “even” player’s
    turn, then the “odd” player wins.
  3. If P>0 and there are more than 2 odd components (no even
    components) on the “even” player’s
    turn, then the “even” player
    wins.
    (On each odd-odd connection,
    the parity of (number of edges +
    number of potential edges) changed.
    Thus one can verify that when there
    are only 4 odd components, the
    “even” player can keep adding edge
    inside component, and force the “odd” player to connect odd-odd components.)
  4. If P==0, the “even” player tries to keep 2 players on even components, and the “odd” player tries to keep 2 players on odd components. So the “even” player looses if and only if both players are on odd components on his turn. Likewise, the “odd” player looses if and only if both players are on even components on his turn.

From above, the result can be deduced directly from the initial state.

3 Likes
5

Actually I notice a fallacy in the reduction for the dp solution. This occurs in the statement of “When would a magician ever need a teleportation.” Note that you deduce that you will never need a teleportation except if you are connecting your component with your opponents component. The fallacy actually occurs because you never consider how the state of the game changes when you teleport from an even sized component to an odd sized component or vice versa. The parity of the game does not change that turn but now consider what happens when you connect an even component to a component your opponent is occupying in the future. Notice now that the parity of the change in number of free edges we have left to remove changes depending on the parity of our own component in this case. (I define free edges as edges we can add but do not connect two components) So teleporting also serves another purpose of changing the parity of our occupied component which in future turns changes how the free edge parity is effected with connecting components to our opponent’s component.

So does this really matter? I decided to test this with a little experiment. Lets roll back our dp state to O(P^2*N^2) that step 10 describes. Now lets add transitions after each edge adding in each step. After each edge adding where we connect two components enable us to teleport ourselves from an odd component to an even component or an even component to an odd component. We also allow for the link with our current component to our opponent then the teleport transition that currently exists in the writer solution. Next we brute for the value of P and the number of odd and even components respectively. Now we compare the result gained from the dp of the writer solution to the one with our extra and still valid transitions. After performing this experiment I noticed that the answers are different! If is was only necessary to teleport when connecting your component to your opponents then these answers should be correct. So this should prove as a satisfactory counter example to the claim that the only time you would need to teleport would be when you link your own component to your opponents. I humbly ask that the contest organizers repeat my experiment and try to confirm my findings. Now It is possible I made a mistake somewhere but I think this finding is at least worth a look if only to quell my current doubts about the correctness of this problem.

1 Like
6

Thank you for your work!

I’ve repeated your experiment, and the results are the same for P = 1 and P > 1. I might have made a mistake somewhere as well, though.

Here is my reasoning. I claim that the answer for P = infinity is the same as for P = 1.

First, let’s see what happens for P = infinity. In this case we don’t care about the locations of the magicians at all – they can connect any two components of their wish in each turn (and then teleport to any free component).

7

Second, let’s see what happens for P = 1. I claim that both magicians can still connect any two components of their wish in each turn (we consider all even components to be the same, and all odd components to be the same). This claim might be false in exactly two cases: when both magicians are placed in the only two even components, and when both magicians are placed in the only two odd components.

8

In the first case, the current magician can connect his component with any odd component instead – this will have the same effect. In the second case, the current magician can connect the only two odd components and teleport – he won’t need any teleportations in future, as all components are even now.

Could you please try to spot a mistake in this reasoning?

9

Thank you for running my experiment. It seems that I misunderstood how you were handling potential edges in you solution and had another mistake in my experiment. Now that I understand your solution better I see no fallacy in your claim. I corrected my mistakes and reran the experiment. The solution matches even if you add these extra decisions to the DP state transitions. (Just as when you ran my experiment) It seems that in my original experiment, the solution was making illegal moves because of this misunderstanding. I double checked the rest of you claims and everything makes sense.

I had lots of fun working on this problem, both during and after the contest, and look forward to your future problems. =)

1 Like