Dynamic programming, Combinatorial game theory, Graph theory
Best explained in the problem statement itself.
If vertices 1 and 2 belong to one connected component, the first magician wins in the first turn.
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
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)
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.
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
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.
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.
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.
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.
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.
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.
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
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.
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.
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.
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.
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.
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.
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.
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
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.
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.
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.
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.
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!
Can be found here.
Can be found here.