[Reserach] The application of ML techniques on certain problems (i.e. How to make crazy hard problems that nobody can solve)

Revision en2, by Nisiyama_Suzune, 2018-07-25 16:25:10


The idea of this article originated from a contest (Petrozavodsk Summer-2016. Petr Mitrichev Contest 14), which I believe is attributed to Petr. In this contest, an interesting problem is proposed:

"Cosider this process: pick a random number ni uniformly at random between 10 and 100. Generate ni random points with integer coordinates, picking each coordinate independently and uniformly at random from all integers between 0 and 109, inclusive. Find the convex hull of those points.

Now you are given 10000 polygons generated by this program. For each polygon, you need to guess the value ni that was used for generating it."

Unfortunately, I didn't really manage to work this one out during our 5-hour training session. After the training is over, however, I have tried to read the solution program written by Petr, which looks like the following:

public class h {
	static int[] splitBy = new int[] {/* 1000 elements */};
	static double[] splitVal = new double[] {/* another 1000 elements */};
	static double[] adjYes = new double[] {/* Another 1000 elements */};
	static double[] adjNo = new double[] {/* ANOTHER 1000 elements, I'm really at my wit's end */};
	public static void main(String[] args) {
		/* Process the convex hull, so that
			key.data[0] is the average length of the convex hull to four sides of the square border
				(i.e. (0, 0) - (1E9, 1E9));
			key.data[1] is the area of the hull;
			key.data[2] is the number of points on the hull.
		double res = 0;
		for (int ti = 0; ti < splitBy.length; ++ti) {
			if (key.data[splitBy[ti]] >= splitVal[ti]) {
				res += adjYes[ti];
			} else {
				res += adjNo[ti];
		int guess = (int) Math.round (res);
		if (guess < 10) guess = 10;
		if (guess > 100) guess = 100;
		pw.println (guess);

While I was struggling to understand where all the "magic numbers" come from, I do realize that the whole program is somewhat akin to a "features to output" black box, which is extensively studied in machine learning. So, I have made my own attempt at building a learner that can solve the above problem.

Tags machine learning


  Rev. Lang. By When Δ Comment
en10 English Nisiyama_Suzune 2018-07-30 20:31:14 447
en9 English Nisiyama_Suzune 2018-07-30 19:03:01 1209 (published)
en8 English Nisiyama_Suzune 2018-07-30 18:44:06 10936
en7 English Nisiyama_Suzune 2018-07-30 18:40:46 896
en6 English Nisiyama_Suzune 2018-07-30 18:30:23 1845
en5 English Nisiyama_Suzune 2018-07-26 02:20:14 146
en4 English Nisiyama_Suzune 2018-07-26 00:32:18 95
en3 English Nisiyama_Suzune 2018-07-25 16:48:45 901
en2 English Nisiyama_Suzune 2018-07-25 16:25:10 1523
en1 English Nisiyama_Suzune 2018-07-25 15:55:53 830 Initial revision (saved to drafts)