CareerCup

What exactly are the conditions for cheating?
For eg: Consider a 6X3 matrix where
Case1:
X 0 X 0 X 0
0 X 0 X 0 X
X 0 X 0 X 0

VS

Case 2:
X 0 X 0 X 0
0 0 0 0 0 0
X 0 X 0 X 0

My thinking is that you can set up an adaptive system. So depending on the value of k you could start from say Case 2 above which makes the matrix more sparse...and depending on the number of 'unplaced' students left..you could place them like Case 1.

Here's a brute force implementation in Java. The basic algorithm involves placing the first student in matrix[0][0]. For each successive student, evaluate the shortest distance to the next closest student for each cell position and place the student in the cell with the max shortest distance. I'm convinced a Dynamic Programming solution is probably the best option for this kind of a problem.

public static int[][] placeStudents(int width, int height, int numOfStudents) {
	int[][] result = new int[width][height];
	
	Cell c = new Cell();
	c.x = 0; c.y = 0;
	for (int k = 0; k < numOfStudents; ++k) {
		// When k = 0, position will 0,0 in the matrix
		result[c.x][c.y] = k + 1;
		if ((k + 1) < numOfStudents)
			c = evaluateCells(result);
	}
	
	return result;
}

public static Cell evaluateCells(int[][] positions) {
	double maxCost = -1.0; Cell result = new Cell();
	// For each matrix cell
	for (int i = 0; i < positions.length; ++i) {
		for (int j = 0; j < positions[i].length; ++j) {
			if (positions[i][j] > 0) continue;
			// Get the distance to the next closest cell
			double cost = getCost(i, j, positions);
			// If its the max distance, then remember the cell position
			if (cost >= maxCost) {
				maxCost = cost;
				result.x = i;
				result.y = j;
			}
		}
	}
	return result;
}

public static double getCost(int a, int b, int[][] positions) {
	double minDistance = Integer.MAX_VALUE;
	for (int i = 0; i < positions.length; ++i) {
		for (int j = 0; j < positions[i].length; ++j) {
			if (positions[i][j] > 0) {
				// Using the Pythagorean theorem to calculate distance between 
				// coordinates in matrix
				double cost = Math.sqrt(Math.pow(Math.abs(a - i), 2) + Math.pow(Math.abs(b - j), 2));
				if (cost < minDistance)
					minDistance = cost;
			}
		}
	}
	return minDistance;
}

This is a graph coloring problem where two neighboring nodes are required to be of different colors.

The space per student is sps = m*n/k.
Students will like sps < 1. Adequate range is 1..m*n.
For k = m*n there is no choice without digging social networks.
For k = m*n/2 placement should be in columns or in diagonals depending on parity of n.
For k < smth like floor(m*n/4) + floor((m+1)*(n+1)/4) it is possible to place every on diagonals or less sparsely.