Introduction
I am going to describe a simple randomised approach to solve this problem 723E - One-Way Reform.
Problem Overview
You have an undirected graph. You want to turn it into a directed graph by choosing a direction for each edge. Also you want to choose directions such that the number of vertices with equal out-degrees and in-degrees is maximised.
The Basic Random Approach That Does Not Work
The basic random approach is to randomly assign all edges directions (i.e for a given edge make it point in one direction with probability 0.5 and in the other with probability 0.5) and hope if we do this enough times we get an optimal solution.
However there a simple obstruction that stops this from working. Assume our original graph is a cycle. Then we can make every edge have the same out-degree and in-degree by creating a directed cycle. We can see the probability of this happening with our basic random approach is roughly 0.5n for a cycle with n nodes. If the cycle is large it unlikely we will be able to find this solution within a reasonable number of random attempts.
Modifying The Basic Approach To Work
There is a simple modification to the basic approach that makes it work. We still randomly assign the edges directions as in the basic approach.
The modification is after we assign the edge directions we try to improve our solution. For a given directed edge from u to v if the out-degree of u is greater than its in-degree and the in-degree of v is greater than its out degree we swap the direction of the edge to go from v to u.
We check each edge exactly once, record how good our solution is and repeat the process with a new random assignment. It is clear that this should deal with the case when our graph is just a big cycle. Surprisingly if you repeat this process 1000 times and take the best answer found in all trails it passes all the testcases. Code 34649661
Conclusion
This approach feels like a hill-climbing algorithm. We start at a random position and head to a local optimum. To increase the odds that we find a global optimum we choose a variety of different starting positions. It could be possible that a well constructed graph would cause this approach to fail with a high probability. However, I do not know how to construct such a graph.
Nice blog, it seems that your solution is based on a technique called simulated annealing. And i still don't understand why people downvote such a good blog like this xd.
I think that the basic difference between simple hill climbing and simulated annealing is that simulated annealing allows one to explore locally suboptimal states with some probability with a hope that this might lead to the globally optimal state, but hill climbing never explores locally suboptimal states and greedily picks the locally best solution. The approach described in this blog never tries to explore locally suboptimal solutions. So I don't think this solution is based on simulated annealing. Rather it's simple hill climbing with a 1000 different starting states. I am not very much experienced with either of hill climbing or simulated annealing. So I might be wrong.
nice one and new .