Hints: G1. Medium Demon Problem (easy version)

Model this as a graph problem. Consider a graph on n vertices where there is an edge from i to r[i].

How will the number of plushies for each spider vary?

• Can it increase?
• Can it decrease?
• Can it remain same?

Consider any spider with 1 plushie.

• In the next round, it can either have 0 or 1 plushie (because it’s not allowed to have more than 1 plushie).

Consider any spider with 0 plushie.

• In the next round, it’d still have 0 plushies. Why? Because 0 plushie indicates that it’s parent is out of plushies in the previous round, so neither the parent nor the child can gain a plushie magically.

This means that spiders with 0 plushies becomes useless for the remainder of the exchange. Hence, we can delete these vertices from the graph altogether. Notice that deletion of a vertex is non stable (the plushie count goes from 1 to 0, therefore the exchange would continue to the next round as well).

Let’s try to figure out an efficient way to delete these vertices (virtually).

In round 1, which vertices will be deleted?

Think about indegrees.

The vertices with indegree 0 would be deleted. Let’s traverse the adjacency list and figure out the indegree of each vertex.

Then, we can simulate round 1 by deleting all vertices with indegree zero.

vector<int> indegree(n);
for (int v = 0; v < n; v++) {
    for (auto child : adj[v]) {
        indegree[child]++;
    }
}

for (int v = 0; v < n; v++) {
    if (indegree[v] == 0) {
        // mark v as deleted
    }
}

In round 2, which vertices will be deleted? Of course, the vertices that were deleted in round 1 would not participate. However, after those vertices were deleted, indegree of some new vertices might have become 0. But if you check the entire vertex to find its updated indegree, the time complexity would be O(n) per round. How do we optimize it?

Notice that indegree is a decreasing function, so you don’t really need to traverse the entire vertex list again. Just traverse the children of the deleted vertex, and as soon as you see a child whose new indegree has become zero, you mark the child for deletion in the next round.

But if you mark the indegree of the child as zero, how do you prevent it from being processed before other indegree zero vertices of this round are processed?

You can use a queue to maintain a First In, First Out (FIFO) order. This is the exact same thing that we do in Topological Sort, i.e, for each child whose new indegree has become zero, you push it to the end of the queue to avoid mixup between the 2 rounds.

In this manner, you can ensure that all vertices of one round are processed before the next. But even if the ordering is correct, how would you know when a round ends and a new one starts?

Maintaing separation between lines is a classical problem by the name : Level Order Traversal : Line by Line. There are 2 tricks to accomplish this.

• You can either add a dummy vertex as a sentinel to the end of the queue after processing all children in round 1. Then, when you encounter the sentinel again, you’d know that one round has completed. Moreover, all the remaining vertices in the queue are candidates for the next round only. So you can simply pluck the sentinel from the front of the queue and insert it at the back. Neat trick!.
• It’s possible to do this without maintaing a sentinel value as well. Before processing a round, inspect the size of the queue. Suppose it is sz. Then, you know that the first sz candidates should be processed in this round. Hence, you process them all at once, and then repeat for the next round.

int year = 1;
while (!q.empty()) {
    year++;

    // Trick to traverse all nodes in a level at once.
    int sz = q.size();
    while (sz--) {
        int v = q.front();
        q.pop();
        for (auto child : adj[v]) {
            indegree[child]--;
            if (indegree[child] == 0) {
                q.push(child);
            }
        }
    }
}

Hence, we can keep deleting zero indegree vertices in each round and simualte the exchanges. But what happens when there are no zero indegree vertices? Can we say for sure that the next round will be stable?

Notice that the outdegree of each vertex is equal to one. Therefore, if each vertex has indegree >= 1, it means that it’d receive exactly 1 plushie from the outside (since it cannot receive more than 1). However, it also has to transer exactly 1 plushie outside, because it’s outdegree is 1.

Therefore, it receives 1 plushie and gives 1 plushie. Hence, the plushie count of each vertex won’t change. Therefore, the game is now stable.

The 3 loops might confuse you into thinking that the time complexity is O(n^3), but it is actually O(V + E). Consider any vertex v. We will only encounter it once inside the while loop, and we will traverse all its children only once. After that, this vertex is forever deleted.

Therefore, the net work that we are doing for each vertex is traversing all its children. This work cannot be more than the number of edges in the graph.

Followup : Using the above technique (which is almost same as Topological Sort, how do you determine if a graph has cycles?)

Code

Warning : I’ve not solved the hard version yet, I’m just thinking out loud.

Why will the same approach not work for the hard version? It’s because an indegree zero vertex might have a lot of plushies and cannot be immediately deleted.

Although I haven’t solved the hard version yet, I’m thinking we could maintain a priority queue instead of a normal queue, and everytime we encounter an indegree zero vertex with plushie count p, we say that it’d be deleted in round current + p. And everytime a vertex gets deleted, the plushie count of its children increases by 1.