// Author: Marko Berezovsky /* The solution idea is a usual backtrack with some pruning. The path is build site by site, starting from the (fixed) origin. The obvious pruning method is - Do not try to extend paths which are already too long. - Extend first to the sites which are closest to the current site. - Skip sites which contain only pokemons(types) already present on the path. Another improvement is to consider the geometrical properties of at least one optimal path. 1. With some 1D exceptions the optimal path does not intersect itself. Therefore, do not extend a path in a way that would result in (nontrivial) self-intersection of the path. 2. No site on the path lies inside a bounding box of two earlier succesive sites on the path. Again, when building the path, avoid this situation. Disclaimer: I did not even try to formulate exactly 1. and 2., not to speak about a necessary proof. The strategy works on the given 13 examples and few trivial ones I verified by hand. Without the proof, the strategy cannot be deemed reliable in general. */ /* A particular *type* in this solution is a particular pokemon (the word pokemon is too long.) Start site with coords (0, 0) is treated as a regular site with no types in it. */ import java.io.*; import java.util.*; public class Pokemon { static int Nsites, Ntypes; static int [] x, y; static int [][] typesHere; // 0/1, sites * types // each site has a characteristic 0/1 vector of // types available in the site static int [][] distVal, distWho; // distances to other sites, sorted // in ascending order on each row (= site) // Val store distances, Who stores ID's of the sites static int bestDist; static int noUnUsedTypes; static int [] usedTypes; static boolean [] usedSites; static int [] path; // debug arr static int calls = 0; static boolean [][][][] isCross; // checks if two segments ([i][j]) and ([k][l]) intersect // i,j,k,l are sites static boolean [][][] isInSegment;; // [i][j][k] is site i inside segment ([j][k])? static int [] cutDepths; // debug/exploratory static boolean isCross( int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4 ){ int det123 = (x2-x1)*(y3-y1)-(y2-y1)*(x3-x1); int det124 = (x2-x1)*(y4-y1)-(y2-y1)*(x4-x1); int det342 = (x4-x3)*(y2-y3)-(y4-y3)*(x2-x3); int det341 = (x4-x3)*(y1-y3)-(y4-y3)*(x1-x3); return ( det123 * det124 < 0 ) && ( det342 * det341 <0 ); } static boolean doesCrossHappen( int site, int depth, int next ){ for( int i = 0; i < depth; i++ ) if( isCross [path[i]] [path[i+1]] [site] [next] ) return true; return false; } static boolean isInsideSegment( int x1, int y1, int x2, int y2, int x3, int y3 ){ // is point (x1, y1) inside segment (x2, y2), (x3, y3)? // 0 determinant and negative scalar product return( ((x2-x1)*(y3-y1)-(y2-y1)*(x3-x1) == 0) && ((x2-x1)*(x3-x1) + (y2-y1)*(y3-y1) < 0) ); } static boolean isPtInSomeSegment( int depth, int next ){ for( int i = 0; i < depth; i++ ) if( isInSegment[next][path[i]][path[i+1]] ) return true; return false; } static boolean isPtInSomeSegmentBoundBox( int depth, int next ){ for( int i = 0; i < depth; i++ ) if( (x[next] - x[path[i]])*(x[next] - x[path[i+1]]) < 0 && (y[next] - y[path[i]])*(y[next] - y[path[i+1]]) < 0 ) return true; return false; } static void search( int site, int distSoFar, int depth ){ //for( int j = 0; j < depth; j++ ) System.out.printf( " "); //System.out.printf( "in site %d noUnused %d\n", site, noUnUsedTypes ); path[depth] = site; calls++; // all types collected? if( noUnUsedTypes == 0 ){ /* System.out.printf( "path: " ); for( int i = 0; i <= depth; i++ ) System.out.printf( " %d ", path[i] ); System.out.printf( " len %d best %d calls %d\n", distSoFar + distVal[site][0], bestDist, calls ); */ distSoFar += distVal[site][0]; if( distSoFar < bestDist ) bestDist = distSoFar; distSoFar -= distVal[site][0]; return; } // otherwise try to move to some another suitable site int neigh, newDist, NNewTypes; for( int i_neigh = 1; i_neigh < Nsites; i_neigh++ ){ neigh = distWho[site][i_neigh]; // consider only new sites if( usedSites[neigh] ) continue; // distance pruning newDist = distSoFar + distVal[site][i_neigh]; //if( newDist +distVal[neigh][0] >= bestDist ) { cutDepths[depth]++; continue; } if( newDist >= bestDist ) { cutDepths[depth]++; continue; } // more involved? // brings new types? NNewTypes = 0; for( int j = 0; j < Ntypes; j++ ) if( typesHere[neigh][j] > 0 && usedTypes[j] == 0 ) NNewTypes++; //if( NNewTypes == 0 ) { cutDepths[depth]++; continue; } // only non-crossing paths allowed //if( doesCrossHappen( site, depth, neigh ) ) { cutDepths[depth]++; continue; } // forbid returning to a site inside a traversed segment // -- unnecessary if segmentBoundBox check is on //if( isPtInSomeSegment(depth, neigh ) ) { cutDepths[depth]++; continue; } // do not return to the already traversed bounding box //if( isPtInSomeSegmentBoundBox(depth, neigh ) ) { cutDepths[depth]++; continue; } // recurse noUnUsedTypes -= NNewTypes; for( int j = 0; j < Ntypes; j++ ) usedTypes[j] += typesHere[neigh][j]; usedSites[neigh] = true; search( neigh, newDist, depth+1 ); usedSites[neigh] = false; for( int j = 0; j < Ntypes; j++ ) usedTypes[j] -= typesHere[neigh][j]; noUnUsedTypes += NNewTypes; } } // ---------------------------------------------------------------------------- // M A I N // ---------------------------------------------------------------------------- public static void main(String[] args) { long t1, t2; t1 = System.currentTimeMillis(); loadAndInit(); search(0, 0, 0); t2 = System.currentTimeMillis(); // hmmm... //if( bestDist == 48 ) bestDist = 52; System.out.printf( "%d\n", bestDist ); //System.out.printf( "calls %d\n", calls ); //System.out.printf( "time %d\n", t2-t1 ); /* System.out.printf( "cut depths: \n" ); for( int i = 0; i < Nsites; i++ ) System.out.printf( "%2d %d\n", i, cutDepths[i] ); */ } static void loadAndInit(){ try { BufferedReader br = new BufferedReader( new InputStreamReader(System.in) ); StringTokenizer st = new StringTokenizer( br.readLine() ); int N = 1+Integer.valueOf( st.nextToken() ); x = new int [N]; y = new int [N]; String name = ""; int xx, yy, pred; Ntypes = 0; Nsites = 0; ArrayList names = new ArrayList(); ArrayList [] typHere = new ArrayList[N]; for( int i = 0; i < N; i++ ) typHere[i] = new ArrayList(); x[0] = y[0] = 0; // start; Nsites = 1; for( int i = 1; i < N; i++ ){ st = new StringTokenizer( br.readLine() ); xx = Integer.valueOf( st.nextToken() ); yy = Integer.valueOf( st.nextToken() ); name = st.nextToken(); names.add( name ); for( pred = 1; pred < i; pred++ ) if( x[pred] == xx && y[pred] == yy ){ // find old site if it eex typHere[pred].add(name); break; } if( pred == i ) { x[Nsites] = xx; y[Nsites] = yy; typHere[Nsites++].add(name); } } /* System.out.printf( "N sites %d\n", Nsites ); for( int i = 0; i < Nsites; i++ ){ System.out.printf( "%3d %3d ", x[i], y[i] ); for( String s : typHere[i] ) System.out.printf( " %s ", s ); System.out.printf( "\n" ); } */ Collections.sort(names); /* for( int j = 0; j < names.size(); j++ ) System.out.printf( " .%s. ", names.get(j)); System.out.printf( "\n" ); */ Ntypes = 1; int w = 1; while( w < names.size() ) if( names.get(w).equals(names.get(w-1)) ) names.remove(w); else w++; Ntypes = names.size(); /* for( int j = 0; j < names.size(); j++ ) System.out.printf( " .%s. ", names.get(j)); System.out.printf( "\n" ); System.out.printf( "N types %d\n", Ntypes ); */ typesHere = new int [Nsites][Ntypes]; for( int i = 0; i < Nsites; i++ ) for( String typename : typHere[i] ) typesHere[i][names.indexOf(typename)] = 1; /* for( int i = 0; i < Nsites; i++ ) { for( int j = 0; j < Ntypes; j++ ) System.out.printf( "%d ", typesHere[i][j] ); System.out.printf( "\n" ); } */ path = new int [Nsites]; usedTypes = new int[Ntypes]; usedSites = new boolean[Nsites]; noUnUsedTypes = Ntypes; bestDist = Integer.MAX_VALUE; distVal = new int[Nsites][Nsites]; distWho = new int[Nsites][Nsites]; for( int i = 0; i < Nsites; i++ ) for( int j = 0; j < Nsites; j++ ) { distVal[i][j] = distVal[j][i] = Math.abs(x[i]-x[j]) + Math.abs(y[i]-y[j]); distWho[i][j] = j; distWho[j][i] = i; } /* System.out.printf( "\n" ); for( int i = 0; i < Nsites ; i++ ){ for( int j = 0; j < Nsites ; j++ ) System.out.printf( " %2d[%2d] ", distWho[i][j], distVal[i][j] ); System.out.printf( "\n" ); } */ //sortDists(); /* System.out.printf( "\n" ); for( int i = 0; i < Nsites ; i++ ){ for( int j = 0; j < Nsites ; j++ ) System.out.printf( " %2d[%2d] ", distWho[i][j], distVal[i][j] ); System.out.printf( "\n" ); } */ // segments crossing part isCross = new boolean [Nsites][Nsites][Nsites][Nsites]; for( int i1 = 0; i1 < Nsites-1; i1++ ) for( int j1 = i1+1; j1 < Nsites; j1++ ) for( int i2 = 0; i2 < Nsites-1; i2++ ) for( int j2 = i2+1; j2 < Nsites; j2++ ) if( i2 != i1 && i2 != j1 && j2 != i1 && j2 != j1 ) isCross[i1][j1][i2][j2] = isCross[i1][j1][j2][i2] = isCross[j1][i1][i2][j2] = isCross[j1][i1][j2][i2] = isCross( x[i1], y[i1], x[j1], y[j1], x[i2], y[i2], x[j2], y[j2] ); /* for( int i1 = 0; i1 < Nsites-1; i1++ ) for( int j1 = i1+1; j1 < Nsites; j1++ ) for( int i2 = 0; i2 < Nsites-1; i2++ ) for( int j2 = i2+1; j2 < Nsites; j2++ ) if( isCross[i1][j1][i2][j2] ) //System.out.printf( "cross [%d,%d]-[%d,%d] x [%d,%d]-[%d,%d] \n", // x[i1], y[i1], x[j1], y[j1], x[i2], y[i2], x[j2], y[j2] ); System.out.printf( "cross %d-%d x %d-%d \n", i1, j1, i2, j2 ); */ // sites inside segments part isInSegment = new boolean [Nsites][Nsites][Nsites]; for( int i = 0; i < Nsites; i++ ) for( int j = 0; j < Nsites-1; j++ ) for( int k = j; k < Nsites; k++ ) if( k != i && j != i ) isInSegment[i][j][k] = isInSegment[i][k][j] = isInsideSegment( x[i], y[i], x[j], y[j], x[k], y[k] ); /* for( int i = 0; i < Nsites; i++ ) for( int j = 0; j < Nsites-1; j++ ) for( int k = j; k < Nsites; k++ ) if( isInSegment[i][j][k] ) System.out.printf( " %d inside %d-%d\n", i, j, k ); */ cutDepths = new int[Nsites]; } // try part catch (IOException ee) {} } static void sortDists() { long [] sortArr = new long [Nsites-1]; final long ff = 0x100000000L; for( int i = 0; i < Nsites; i++ ){ for( int j = 1; j < Nsites; j++ ) sortArr[j-1] = distVal[i][j] * ff + distWho[i][j]; Arrays.sort( sortArr ); for( int j = 1; j < Nsites; j++ ){ distVal[i][j] = (int)(sortArr[j-1] / ff); distWho[i][j] = (int)(sortArr[j-1] % ff); } } } /* Review: The problem ----------- The problem difficulty is medium, conceptually. The implementation seems to be a bit more technical, both Java solutions (which use different strategy) containt at least 7 different arrays and both occupy about 200 lines of code. So, I expect it to be one of the most laborious problems in the final set. Data ---- Data sizes seem to be OK. The maximum number of sites (stops) 20 is enough to exclude any solution based on trivial brute force approach. I suggest to include a secret data set in which all pokemons are in the origin site(0, 0) like e.g: 2 0 0 a 0 0 b with the result equal to 0. Submissions ----------- My review solution uses simple backtrack which a. explores the sites in the ascending order of their distance from the current site, b. cuts off incomplete paths which are too long compared to to the current best path, c. skips sites containing only pokemons which were found earlier on the current path. The number of recursive calls is about 10^4 in the most difficult case, which is fast enough with big margin. Obviously, the problem allows for various succssfull solution strategies. Problem statement ----------------- The last sentence in the input specification "Multiple pok\'{e}mon can reside at a single pok\'{e} stop and are listed on separate lines." was too much condensed for me, I had to look into the secret data to understand the input data format correctly. I suggest to break the sentence into two or more sentences with little more detail. Something like e.g. (in my bad English): "Multiple pok\'{e}mon can reside at a single pok\'{e} stop. In such case, each of the pok\'{e}mons on thae stop is listed on a separate line and all those lines contain the coordinates of the given stop." Gentlemen, input13.ans contains value 52 while my own manual and also via program checks report the answer to be 48. 10 1 2 a 2 3 b 5 5 a 6 6 b 1 6 c 6 1 c 4 5 d 10 10 a 8 8 b 1 8 a 4 1 2 a 2 3 b 1 6 c 4 5 d 7 1 2 a 2 3 b 5 5 a 6 6 b 1 6 c 6 1 c 4 5 d 6 1 2 a 2 3 b 5 5 a 6 6 b 1 6 c 4 5 d 5 1 2 a 2 3 b 5 5 a 1 6 c 4 5 d */ }