Warning

Dragon Tree Fields

Komentář k řešení: pdf.

Kód řešení v Jave:

import java.io.*;
import java.util.*;

// ---------------------------------------------------------------------------
//       O N E    F I E L D   R E P R E S E N T A T I O N
// ---------------------------------------------------------------------------

class Field implements Comparable <Field> {
int i, j, k;       // coords and size
long quality;      // sum of field's elements

// constructor
public Field ( int i_coord, int j_coord, int k_size , long aSum ){
i = i_coord; j = j_coord; k = k_size; quality = aSum;
}

// check if two fields overlap
public boolean isDisjointWith( Field f2 ){
return
this.i + this.k <= f2.i  ||  f2.i + f2.k <= this.i
|| this.j + this.k <= f2.j  ||  f2.j + f2.k <= this.j;
}

@Override
public int compareTo( Field f2 ){
if( this.quality < f2.quality ) return -1; else return 1;
}

public void print(){ // useful in debugging
System.out.printf( "[%d] %d %d %d   ", this.quality, this.i-1, this.j-1, this.k );
}
}

// ---------------------------------------------------------------------------
//                     S O L U T I O N   C L A S S
// ---------------------------------------------------------------------------

public class Solution01 {

static int N;
static long Q1, Q2;
static long [][] upLeftSums;   // just one array suffices to solve the problem

// feasible field == field which quality is in the range[Q1, Q2]
static ArrayList<Field> feasibleFields = new ArrayList<>();

static void collectFeasibleFields() {
long fieldQuality;
for( int i = 1; i < N; i++ )
for( int j = 1; j < N; j++ ){
upLeftSums[i][j] += upLeftSums[i][j-1] + upLeftSums[i-1][j]
- upLeftSums[i-1][j-1];
for( int k = 1; k <= Math.min(i, j); k++ ){
fieldQuality =   upLeftSums[i][j]   - upLeftSums[i-k][j]
- upLeftSums[i][j-k] + upLeftSums[i-k][j-k];
if( Q1 <= fieldQuality && fieldQuality <= Q2 )
feasibleFields.add( new Field(i, j, k, fieldQuality) );
}
}
}

static void findMinimumDifference(){
int j, imin = -1, jmin=-1;
long diff, mindiff = Long.MAX_VALUE;

// go searching, suppose feasible fields are sorted by their qualities
for( int i = 0; i < feasibleFields.size()-1; i++ ){
j = i;
while( true ) {
j++;
if( j >=  feasibleFields.size() ) break;
if( feasibleFields.get(i).isDisjointWith( feasibleFields.get(j) ) ){
diff = feasibleFields.get(j).quality - feasibleFields.get(i).quality;
if( diff <= mindiff ) // register new min
{ mindiff = diff; imin = i; jmin = j; }
break;
}
} // while
} // for
System.out.printf( "%d %d\n", feasibleFields.get(imin).quality,
feasibleFields.get(jmin).quality );
}

// ..........................................................................
//                   M A I N
public static void main(String[] args)  throws IOException {
collectFeasibleFields();
Collections.sort( feasibleFields );
findMinimumDifference();
}

// ..........................................................................
//                 I N P U T
static void loadData()  throws IOException {
StringTokenizer st = new StringTokenizer( br.readLine() );

N = Integer.valueOf( st.nextToken() );

// artificially, the array is bigger, it has additional zero row and column
// at the top and at the left ([i][0] and [0][j] are all  0),
// this trick simplifies processing  -- no need for border checking.
upLeftSums = new long [N+1][N+1];

for( int i = 1; i <= N; i++ ){
st = new StringTokenizer( br.readLine() );
for( int j = 1; j <= N; j++ )
upLeftSums [i][j] = Long.valueOf( st.nextToken() );
}

st = new StringTokenizer( br.readLine() );
Q1 = Long.valueOf( st.nextToken() );
Q2 = Long.valueOf( st.nextToken() );
}

}