fork download 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Ideone
  6. {
  7. 	static void swap(int indices[], int a, int b)
  8. 	{
  9. 		int temp = indices[a];
  10. 		indices[a] = indices[b];
  11. 		indices[b] = temp;
  12. 	}
  13.  
  14. 	static boolean beat(int i, int j)
  15. 	{
  16. 		if (i < j)
  17. 			return games[i][j] == 1;
  18. 		else
  19. 			return games[j][i] == 0;
  20. 	}
  21.  
  22. 	static int loser(int i, int j)
  23. 	{
  24. 		if (beat(i, j))
  25. 			return j;
  26. 		else
  27. 			return i;
  28. 	}
  29.  
  30. 	static void removeIndex(int i)
  31. 	{
  32. 		swap(indices, i, --indicesCount);
  33. 	}
  34.  
  35. 	static int n = 100;
  36. 	static int[][] games = new int[n][n];
  37. 	static int[] indices = new int[n];
  38. 	static int indicesCount = n;
  39.  
  40. 	public static void main (String[] args) throws java.lang.Exception
  41. 	{
  42. 		Random random = new Random();
  43. 		for (int j = 0; j < n; j++)
  44. 		for (int i = 0; i < j; i++)
  45. 			// doing this heavily biases higher values for wins
  46. 			// since we're only filling in the top-right half of the matrix 
  47. 			if (random.nextInt(n/5) == 0) games[i][j] = 1;
  48.  
  49. 		// solve this problem using brute force to validate the correctness of the algorithm
  50. 		int[] losses = new int[n];
  51. 		for (int j = 0; j < n; j++)
  52. 		for (int i = 0; i < j; i++)
  53. 			losses[loser(i, j)]++;
  54.  
  55. 		Set<Integer> output = new TreeSet<Integer>();
  56. 		for (int i = 0; i < n; i++)
  57. 			if (losses[i] <= 10)
  58. 				output.add(i);
  59. 		System.out.println("Brute force winners: " + output);
  60.  
  61.  
  62.  
  63. 		for (int i = 0; i < n; i++)
  64. 			indices[i] = i;
  65.  
  66. 		losses = new int[n];
  67.  
  68. 		for (int a = 0; a < indicesCount; )
  69. 		{
  70. 			for (int b = a+1; losses[indices[a]] <= 10 && b < indicesCount; )
  71. 			{
  72. 				losses[loser(indices[a], indices[b])]++;
  73.  
  74. 				if (losses[indices[b]] > 10)
  75. 					removeIndex(b);
  76. 				else
  77. 					b++;
  78. 			}
  79. 			if (losses[indices[a]] > 10)
  80. 				removeIndex(a);
  81. 			else
  82. 				a++;
  83. 		}
  84.  
  85. 		output.clear();
  86. 		for (int i = 0; i < indicesCount; i++)
  87. 		{
  88. 			int lossCount = 0;
  89. 			for (int j = 0; j < n; j++)
  90. 				if (indices[i] == j)
  91. 					continue;
  92. 				else if (beat(j, indices[i]))
  93. 					lossCount++;
  94. 			if (lossCount <= 10)
  95. 				output.add(indices[i]);
  96. 		}
  97. 		System.out.println("O(n) algorithm winners: " + output);
  98. 	}
  99. }
Success #stdin #stdout 0.04s 4386816KB
comments (?)
stdin 
Standard input is empty
stdout 
Brute force winners: [93, 94, 95, 96, 97, 98, 99]
O(n) algorithm winners: [93, 94, 95, 96, 97, 98, 99]
https://ideone.com/dFi37o
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!