#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

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.5ⁿ 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.