SABOTEUR june challenge

general
1

Can anyone explain how to solve the problem SABOTEUR and ES as I couldn’t find any editorials on it??plzz help!!

1 Like
2

Practice,
Contest

Sharing my solution for Saboteur which got 90.41403 pts. Quick explanation, I tried to solve the exact solution for each subtask and created a randomized tree creating solution for the random subtask.

Observation

First, observe that the complement of the problem is keeping a subgraph that forms a tree. Therefore, we can also solve the problem by constructing the maximum spanning tree and bomb the complement.

Compression

Also, observe that we can merge nodes with a bridge between them. Reason being, if we keep one of the nodes, it makes sense to also keep the other node since that act won’t form any cycles. So we can create a compressed graph with supernodes based on this compression technique to get a smaller graph to work with. We can build constructive algorithms for that. I did this using Tarjan’s bridge finding and union find.

Solutions

  1. Small n \leq 20

    You can solve the small case in with 2^n states. Many ways to do this, you can do brute force DFS or
    similar. What I did was the do DP with bitmasking to construct the tree to keep. You can keep a tree with
    k nodes if there is a subtree with k-1 nodes and the extra node to add has only edge incident to it.

  2. Smallish n \leq 40

    Unfortunately, I wasn’t able to solve this one for the exact case. I’m still finding a solution for this, so if you have a solution in mind, do share :slight_smile:

  3. Almost Tree m = n

    Observe that after bridge compression, there are no more bridges so the graph is one big cycle (necklace, everyone having degree 2). This means we just have to pick the minimum node to bomb, and we’re done.

  4. Close-enough Tree m <= n + 3

    I did a special compression for this. First, observe that the graph will have at most 2^{m - n} \leq 2^3 = 8 cycles in total. There will only be some nodes that are shared in some cycles. In order to keep a tree, we have to find a set of nodes that span all cycles, and get the minimum set to bomb. The way I did it was to further compress the graph. After removing bridges, the nodes with degree 2 contribute the most to the size of the graph (think of a necklace with at most 3 crossings). Now, if we consider contiguous “chain” of nodes of degree 2, the minimal way to bomb that chain is to bomb only the representative minimum of that chain. Therefore, we can actually compress “chains” in the necklace into a supernode and get a really small graph. You can prove that n \leq 16 nodes after this compression. Finally, we can do brute force with the reduced graph to get the exact answer.

  5. Complete Graph m = \frac{n(n-1)}{2}

    This one is easy. Any three nodes will form a cycle, so we get two adjacent nodes that give maximum cost and bomb the rest.

  6. Wheel Graph (reference)

    Two cases for this one. If we bomb the center, the graph becomes a cycle so we only need to bomb one more node to keep a tree. If we don’t bomb the center, we have to pick the maximum independent set from the cycle around the center. We can solve the latter using DP on a cycle, where we either pick the first node or not.

  7. Random Graph n \leq 10000

    For the random subtask, what I did was randomly generate a spanning tree with A-star based on heuristics. To construct the tree, I would have a priority queue based on a heuristic value I put on the node. To check if a node to add doesn’t form a cycle, I did efficient bit counting against the AND of the edge list and the currently visited array. Just take a look at my solution for the details.

    Here are some of the heuristics I used:

    1. Greedy by cost (prefer if c[u] > c[v])

    2. Greedy by cost and degree (prefer if c[u] - adj[u].size() > c[v] - adj[v].size())

    3. Uniformly random (random shuffle, prefer if ord[u] > ord[v])

    4. Greedily random (random shuffle, prefer if c[u] + ord[u] > c[v] + ord[v])

For the last two heuristics, I ran my solution until I exhausted the time. For some reason, the uniformly random actually gave the best results at least for my points.

Hope that was helpful. I’m interested in knowing of any approaches to the smallish subtask, as well as alternative solutions to the close-enough tree one. I hope solvers can share some thoughts. You can also read my solution for the details, it’s heavily commented. Just leave a reply if you have any questions :slight_smile:

Here’s the solution link.

5 Likes
3

Thanks for the explaination…but i think i have much to cover before i can understand this!!

4

Its well explained, tho i dont know even half the concepts XD.