Problem link: SPOJ Problem Set (classical): 17707. Constructible Regular Polygons
As stated in the problem description, you are required to utilize this page. As there are only 5 Fermat Primes, you can easily do a pre-processing up to 106 in constant time (25×5) and answer each query in O(1).
Problem link: SPOJ Problem Set (classical): 9942. Holiday Accommodation
Given a weighted tree, consider there are N people in N nodes. You have to rearrange these N people such that everyone is in a new node, and no node contains more than one people and maximizes the cost. Here cost is the distance travelled for each person.
First observation is, in order to maximize cost, all edges will be used to travel around. So, if we can calculate how many times each edge will be used, we can calculate the cost.
Now for any edge Ei, we can partition the whole tree into two subtrees, if one side has n nodes, the other side will have N - n nodes. Also, note that, min(n, N-n) people will be crossing the edge from each side. Because if more people cross the edge, then by pigeon-hole principle in one side, we will get more people than available node which is not allowed in the problem statement. So, Ei will be used a total of 2 * min(n, N-n) times.
Thus the final result is:
cost = ∑ 2*min(ni, N-ni)*wieght(Ei) | for each edge Ei
Here, ni is the count for nodes in one side of the edge Ei and N-ni on the other side. So, we can use simple DFS algorithm to solve the problem. During the traversal, just count number of nodes in the subtree for an edge u⇒v and calculate result for each edge in the process.
Problem link: SPOJ Problem Set (classical): 211. Primitivus recurencis
Given a list of directed edges or features, we have to find the smallest possible sequence of nodes where all the given edges are present without violating the direction.
Although at first this may seem to be a bipartite matching problem or problem related to strongly connected component. But I am not sure whether this particular problem can be solved using any of those techniques. Here we have two things to observe.
1 ⇒ Ordering for each weakly connected component is independent. So, we can add up the results for each weakly connected component as we can arrange them in any order, because they don't have any node in common.
2 ⇒ The minimum length will be the length of eulerian circuit for each component. We can break the circuit at suitable places to make it a chain. Considering [1], we can break the chain anywhere we want. Because other components have nothing to do with it.
So, for each weakly connected component, it boils down to finding minimum number of edges need to be added to make the component an euler circuit. For each component Gi, we can find the minimum number of additional edges by the following formula (Note, the formula will also handle the components which are already an euler circuit).
Number of additional edges = ∑max( cnt(Gi) / 2, 1 ) for all i
Note: if you already have an euler circuit, i.e. cnt(Gi) = 0, then you still need 1 additional term in the sequence. The simplest example is two edges, 1-2 and 2-1. You will need either 1-2-1, or 2-1-2 sequence.
And to find the value of cnt() for a component Gi, we just add the absolute difference of in and out degree count for each node in that component.
cnt(Gi) = ∑|d+(u) - d-(u)| for each u ∈ Gi Here, d+(u) ⇒ indegree count for u, and d-(u) ⇒ outdegree count for u.
So, the overall solution outline is something like this, first use disjoint set data structure, or commonly known as union-find to mark the components. You can also use simple DFS / BFS as well. Ofcourse we are ignoring direction in this stage as we want to generate weakly connected components. Then for each node, calculate total indegree and outdegree counts. Now for each component, use the above formula to find additional edges xadd, thus the final answer is N + xadd, here x is the given number of edges.
