Viz Zadání.

Myšlenka řešení:

0. Úlohu neumíme obecně řešit v polynomiálním čase. Když budou laboratoře jen dvě, jedná se o variantu klasické úlohy o dělení kořisti mezi loupežníky (viz Partition problem), kterou dosud neumí nikdo řešit v polynomiálním čase.

1. Backtrack: Zkoušíme postupně plnit zásilky pro jednotlivé laboratoře, když je aktuální zásilka neperspektivní, vracíme se v rekurzi, tj. prořezáváme strom rekurze.

2. Prořezávání: Pokud mají být všechny zásilky co nejvíce váhově stejné, pak každá musí být také co nejvíce podobná průměrné váze všech zásilek. Sestavenou zásilku, která se příliš liší od průměru, považujeme za neperspektivní.

3. Postupně nalézáme lepší a lepší řešení, každé aktuální řešení používáme jako nástroj k prořezávání.

Nechť je již sestaveno k zásilek, nechť součet vah všech vzorků je S, nechť hodnota nejlepšího dosud nalezeného řešeni je M. Pokud pro váhu V (k+1)-ní zásilky platí, že

|V - S/L| >= M ,

kde L je počet laboratoří resp. zásilek, pak již zřejmě nemá cenu sestavovat (k+2)-ou a další zásilky, a je nutno zkusit sestavit (k+1)-ní zásilku nějak jinak, pokud to jde, a pokud už to nejde, vrátit se z rekurze.

Také si udržujeme (což udělal asi každý řešitel) rozdíl mezi maximální a minimální váhou dosud sestavených zásilek. Pokud tento rozdíl přesáhne hodnotu dosavadního nejlepšího řešení, vracíme se v rekurzi.

4. Na začátku může být výhodné “uhodnout” nějaké dobré řešení s malou hodnotou rozdílu mezi nejtěžší a nejlehčí zásilkou, aby se pomocí něj dalo co nejefektivněji prořezávat. Lze použít rozdělení vzorků v pořadí uvedeném na vstupu. Dále lze obětovat nějaký zlomek sekundy na zcela náhodné prohazování prvků v zásilkách. Je to rychlé a pokusy ukazují, že takto lze získat až několikanásobně lepší počáteční řešení.

5. Autorský postup řešení úlohy prořezává pouze po zkompletování celé jedné zásilky. Nezkouší žádnou variantu, která by se snažila odhadnout již v průběhu kompletování jedné zásilky, zda to bude neperspektivní zásilka nebo ne. O případném zrychlení nebo zpomalení pomocí takové varianty tedy nic nevíme. Jiné výrazně odlišné postupy jsme rovněž nezkoušeli/nepromýšleli.

package a01;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.Random;
 
 
public class A01 {
 
static int N, L;
static int m [][]; // mass 
static boolean used [][];  
 
static int  min_diff_so_far;
static int [] lab;
static int low_avg, high_avg; 
static int sum_of_all;
static int calls = 0;  // used in measurement, remove in deploy version
 
static void getvals() { try {
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  StringTokenizer st = new StringTokenizer(br.readLine());
  N = Integer.valueOf(st.nextToken());
  L = Integer.valueOf(st.nextToken());
 
  m = new int [N][L];
  used = new boolean [N][L];
  lab = new int [L];
 
  sum_of_all = 0;
  for(int i = 0; i < N; i++) {
	st = new StringTokenizer(br.readLine());		
	     for(int j = 0; j < L; j++) {
	     m[i][j] = Integer.valueOf(st.nextToken());
	sum_of_all += m[i][j];
	}
    }
	}
  catch (IOException ee) {
		System.out.printf("Santa Maria Madre de Dios! Excepcion, Excepciooon!!\n"); 
	}
}
 
static void low_and_high_average() {
	low_avg = sum_of_all / L;
	high_avg = low_avg;
	if (low_avg * L < sum_of_all)
		high_avg = low_avg+1;
}
 
void deal_0th_site_WLOG() {
  for(int j = 0; j < L; j++) 
	  lab[j] = m[0][j];
}
 
 
// the function supposes vector of nonzero length
static int max_minus_min(int [] x) {
	int i, min, max;
	// initialize min, max and search index i
	if (x.length % 2 == 0) { // even length  
		if(x[0] < x[1]) { min = x[0]; max = x[1]; }
		else            { min = x[1]; max = x[0]; } 
		i = 2;
	}
	else { // odd length
		min = max = x[0]; 
		i = 1;
	}
	// run search
	while(i < x.length) {
		if (x[i] < x[i+1]){
			if (x[i] < min)   min = x[i];
			if (x[i+1] > max) max = x[i+1];
		}
		else {  // (x[i] >= x[i+1])
			if (x[i] > max)   max = x[i];
			if (x[i+1] < min) min = x[i+1];			
		}
		i += 2;
	}
	return max-min;
}
 
 
static int randomSwapSearch (int time_limit_millis) {
	long time_start_millis = System.currentTimeMillis();
	//Random ra = new Random(time_start_millis); // random seed 
	Random ra = new Random(39980183); // random seed 
 
	// initialize column sums
	int [] sumColumn = new int[L];
	for(int i = 0; i < N; i++)
		for(int j = 0; j < L; j++)
			sumColumn[j] += m[i][j];
 
	int min_difference = max_minus_min(sumColumn);
 
	int i, j1, j2;                // indices of items to be swapped
	int sample1, sample2;         // auxilliary swap variables
 
	while (System.currentTimeMillis() - time_start_millis < time_limit_millis){
		// choose randomly indices of two items 
		// from the same site belonging to different labs
		i = ra.nextInt(N);
		j1 = ra.nextInt(L);
		do {
		  j2 = ra.nextInt(L);
		} while (j1 == j2);
 
		// swap those two items between their respective labs
		sample1 = m[i][j1];
		sample2 = m[i][j2];
		m[i][j1] = sample2;
		m[i][j2] = sample1;
		sumColumn[j1] += sample2-sample1;
		sumColumn[j2] += sample1-sample2;
 
		// maybe the swap made the difference smaller?
		min_difference =  Math.min(min_difference, max_minus_min(sumColumn));
	}
	return min_difference;
}
 
static void search(int i_site, int j_lab) {
	//calls++;
	// TERMINATION:
	if (j_lab == L) { //all labs filled
		int difference = max_minus_min(lab);
		if(difference < min_diff_so_far) {
			min_diff_so_far = difference;			
			//System.out.printf("%d\n",min_diff_so_far);
		}
		return;  
	} // end of recursion
 
	// PRUNING:
	// Before we start filling another lab check if the currently 
	// filled lab is a promissing one, otherwise retun.
	if (i_site == 1) { 
		// check if the last lab is under- or over- saturated. 
		if (j_lab > 0) {
			if (lab[j_lab-1]+min_diff_so_far <= high_avg) return;
			if (lab[j_lab-1]-min_diff_so_far >= low_avg) return;
		}
		// check if current deal is worse than the best deal so far 
		for(int k = 0; k < j_lab-1; k++)
			if (Math.abs(lab[k] - lab[j_lab-1]) > min_diff_so_far) 
				return;
	}
 
	int nexti_site = (i_site == N-1)? 1: i_site+1;
	int nextj_lab = (nexti_site == 1) ? j_lab+1 : j_lab; 
 
	// RECURSION:
	// try to give each available sample from the i-th site to the j_th lab
	for(int k = 0; k < L; k++) 
		if (used[i_site][k] == false) {
			used[i_site][k] = true;
			lab[j_lab] += m[i_site][k];  
			search(nexti_site, nextj_lab);
			lab[j_lab] -= m[i_site][k];
			used[i_site][k] = false;
		} 
}
 
 
public static void main(String[] args) {
	long t1, t2;	
 
	getvals(); 
        t1 = System.currentTimeMillis();
 
	low_and_high_average();
 
        int duration_random_search_milisec = 100*L;
        min_diff_so_far = randomSwapSearch(duration_random_search_milisec); 
 
	//System.out.printf("   --> %d\n",min_diff_so_far);
 
	// deal the 0-th site completely to all labs, it is a "WLOG" operation 
	for(int j = 0; j < L; j++) 
	    lab[j] = m[0][j];
 
	search(1,0);
 
	t2 = System.currentTimeMillis();
        System.out.printf("%d\n", min_diff_so_far); 
        //System.out.printf("calls %d\n", calls); 
        //System.out.printf("time %d\n", t2-t1); 
}
 
}