PROBLEM LINK:
Author: Roman Furko
Tester: Sergey Kulik
Editorialist: Mugurel Ionut Andreica
DIFFICULTY:
HARD
PREREQUISITES:
Graphs,Treaps,Segment trees
PROBLEM:
Two players are playing a game on an undirected graph with weights on its edges. The players move in turns. At his turn, a player chooses an unmarked vertex and marks it with the player’s color. The game ends when all the nodes have been marked. At the end of the game the score of each player is equal to the sum of the weights of those edges having both endpoints marked in the player’s color. Let’s denote by Score(i) the score of player i. During the game each of the two players tries to maximize the difference between their score and the score of the opponent (i.e. player i tries to maximize Score(i)-Score(3-i)).
You need to decide what is the maximum difference between the score of player 1 (i.e. the player making the first move) and that of player 2, assuming that both players play optimally.
In addition, the edges are added to the graph one by one and you need to find the maximum difference for each game played from scratch on the graph obtained after adding every edge.
QUICK EXPLANATION:
Let’s define a weight for each node: w(i)=the sum of weights of all the edges incident with the node i. At their turn, the optimal move for each player is to mark the unmarked vertex i with the maximum value w(i).
Let’s consider these node weights sorted in descending order: w(p(1)) >= w(p(2)) >= … >= w(p(N)). Player 1 will mark all the nodes p(i) with odd i, while player 2 will mark all the vertices p(j) with even j.
Let’s compute the value DIF=\sum_{i=1}^{2*i-1≤N}{w(p(2*i-1))}-\sum_{i=1}^{2*i≤N}{w(p(2*i))}. DIF is equal to twice the maximum difference between the scores of player 1 and player 2. Why? It’s easy to see that if an edge (i,j) has both endpoints marked with the same color, then its weight will be considered both in wp(i) and in wp(j). However, if its endpoints have different colors, its weight will appear once with the sign + (for player 1) and once with the sign -, effectively contributing zero to DIF.
After the addition of every edge we need to update the weights of the nodes incident to it and then update DIF. In order to do this efficiently we need to use data structures which support logarithmic updates (e.g. treaps, segment trees).
EXPLANATION:
Let’s see why the optimal strategy in a game is to always pick the unmarked vertex with the largest weight. As we saw, the difference between the score of the first player and that of the second player is twice the difference between the weights of the vertices selected by the first player and those selected by the second player. Thus, in order to maximize his score, a player will want to select vertices with larger weights. Moreover, if a player A doesn’t select the unmarked vertex with the largest weight, then the other player (B) will be able to select it and, thus, player A will obtain a lower score, while player B will obtain a higher score. This is sufficient motivation for player A to pick the unmarked vertex with the largest weight.
We now have a way of solving the problem, but not in a very efficient way. After adding a new edge we update the weights of the endpoints of the edge, sort the vertices again (either in O(Nxlog(N)) time, or in O(N) time, since we just need to change the position of at most two vertices) and then recompute DIF. This has a time complexity of O(MxNxlog(N)) (or O(MxN)) and is too slow for obtaining 100 points.
In order to obtain 100 points we need to recompute DIF more efficiently. I will present here an approach based on using a segment tree.
We will create O(N+M) tuples (i,k,weight), one for each time a vertex’s weight w(i) is updated after adding a new edge. We will initially have N vertex tuples corresponding to the N initial vertices, all of them having weight zero. We also initialize all the values w(i) to 0. Then we start adding the edges one by one. Let’s assume that the current edge has index k, has cost c and connects the vertices i and j. If i\neq j then we increment both w(i) and w(j) by c and then we add two new tuples (i,k,w(i)) and (j,k,w(j)). If i=j then we increment w(i) by 2xc and we only add one tuple (i,k,w(i)).
Once we have all these tuples we sort them in decreasing order of the parameter weight. For each edge with index k we will maintain the positions of the two (or one) tuples added for this edge in the sorted order. Let these positions be pa(k) and pb(k).
We will now construct a segment tree over the O(N+M) tuples, but only the N initial tuples will be enabled. Each node of the segment tree will contain two values: maxdif=the maximum difference that player 1 can obtain if he plays considering only the tuples enabled in this node’s interval, and cnt=how many tuples are enabled in this node’s interval. The answer we are interested in will always be available at the root of the segment tree.
We will now add edges one by one. At the same time we will maintain for each vertex i a value pos(i)=the position of the only enabled tuple corresponding to vertex i (this is because at each moment we will have exactly one tuple enabled for each vertex, i.e. N tuples enabled overall). Let’s assume that the current edge is k and connects the vertices i and j. Let’s consider the case i\neq j first. We need to disable the tuples on the positions pos(i) and pos(j) and then enable the tuples on the positions pa(k) and pb(k). Afterwards we set pos(i)=pa(k) and pos(j)=pb(k).
The case i=j is similar. We disable the tuple on the position pos(i), enable the tuple on the position pa(k) and then set pos(i)=pa(k).
Note that we perform O(N+M) Enable and Disable operations. In the pseudocode below you can see how to perform each of these operations in O(log(N+M)) time using the segment tree.
void UpdateSegmentTree(int node, int op) {
// node = segment tree leaf node corresponding to the updated tuple
// op = 1, for enabling the tuple; -1, for disabling the tuple
if (op < 0) segtree[node].maxdif = segtree[p].cnt = 0;
else {
// tuple(node) is the tuple corresponding to the segment tree leaf node *node*
segtree[node].maxdif = tuple(node).weight;
segtree[node].cnt = 1;
}
node >>= 1;
while (node >= 1) {
int left_child = (node <>= 1;
}
}
The overall time complexity is (O(N+M)xlog(N+M)).
AUTHOR’S, TESTER’S AND EDITORIALIST’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.