Today I want to talk about my solution for a Spoj-problem. Spoj is a website providing a lot of algorithmic problems and you can collect points by solving them. Well, that is the problem, it is called EXPLOSN:

There has been an assault by some rebels at a public place, they caused a big explosion. Some witnesses (at most 100000) are still alive, including at least one rebel. Because we live in a police state, myriads of policemen can arrest all witnesses and rebels, each of them accuse exactly one person to be a “terrorist”, because the inhabitants of the city are very bourgeois, they never lie, but the rebels are humorous and so they sometimes accuse each other, sometimes they lie. However, the government fears for its political power, and thus they want to execute some people. They do not care about careful investigations, but their judgement should be consistent with the testimonies and because the executioners want to earn money, they want to execute as few people as possible (it will be still enough people for an effective deterrence). The program should output the number of people they have to execute. Read the original statement for a pro-government-formulation. ;) You should not read further if you want to solve the problem yourself, and why should you not want to do that? :D

However, actually it is not important if we sympathise with the government or the rebels because we can state it in terms of graph-theory: We want to find a maximum independent set in the accusation-graph, its complement is the minimal set of morituri. Generally this is a very hard problem, 100000 nodes are infeasible, but in our graph the out-degree of each node is exactly one. Such a graph has some special properties: Of course it has a finite number of weakly connected components. Because it has as many vertices as values, there is at least one (undirected) cycle in the component. But this cycle is rectified (? ? ?, not ? ? ?) because otherwise there would be one node in the cycle with out-degree ? 2. Notice: The length of the cycle may be one if a rebel is accusing himself. The subgraph consisting of the other nodes has less vertices than edges, thus it is a forest. We can conclude that the trees in the forest are rectified (child ? parent) using the same argument as before. The root of each tree is accusing an element of the cycle. For each of the trees we can now easily compute the minimal number of morituri recursively, one time considering the root being a moriturus, and one time considering the root not being a moriturus. Then we can sum up those values for each node in the cycle while no two adjacent nodes should stay alive. The ideal constellation of morituri and non-morituri in the cycle can be easily computed using dynamic programming. By adding the result for each weak connected component we gain the result.

Source code.

Leave a Reply

XHTML: Use <blockquote cite="name"> for quotations, <pre lang="text    ∨ cpp-qt ∨ cpp ∨ bash ∨ other language"> for code, [latex] for formulas and <em> for em. Contact me if the comment does not get published, it may have accidentally been marked as spam.

Anti-Spam Quiz: