import java.io.*; import java.util.*; import java.awt.geom.*; /** * Solution to Stamp Stamp * * Every nub on the stamp makes two marks on the paper. * For every nub, the two marks will be different by some di and some dj. * For every nub, the di and dj will be the same. * We'll call [di,dj] a Vector. So, the problem has 2 parts: * * 1) Finding vectors to test * 2) Testing a vector to see if it's possible, and if so, what's the minimum number of nubs. * * Part 2) is O(n^2) no matter how you approach it. It was the author's * intent that competitors find an O(n) way of finding vectors to test. * This can be done by finding the convex hull of the points, and only considering * edges on the convex hull (unless they're in a line, then you have to * consider all differences). It'll take O(n^2) or O(nlogn) to find the convex hull, * and the hull will have O(n) vectors to test, bringing the whole thing in at O(n^3). * * However, there's enough redundancy in the vectors that significant pruning is possible, * and O(n^4) solutions will work. This program is an example of an O(n^4) solution * with heavy pruning. * * @author vanb */ public class stampstamp_vanb { public Scanner sc; public PrintStream ps; /** The paper - a char array of #s and .s */ public char paper[][]; /** * This is the (i,j) coordinate of a mark on the paper. * * @author vanb */ public class Mark { public int i, j; /** * Create a mark. * * @param i Row * @param j Column */ public Mark( int i, int j ) { this.i = i; this.j = j; } } /** This is a list of all of the marks on the paper. */ public LinkedList marks = new LinkedList(); /** n = # rows, m = # columns */ public int n, m; /** The best we've found so far */ public int best; /** The best answer possible */ public int bestpossible; /** A set of vectors we've already seen */ public HashSet seen = new HashSet(); /** * Test a vector, with lots of pruning. * * Look at a sequence of marks, with each different from the previous * by [di,dj]. They form a line. So, we've got to: * 1) find the starting point of the line * 2) count the number of marks in the line * * Finding the starting point is easy. A mark is the * starting point of a line if there's no mark [-di,-dj] away. * * If the number of marks in a line is 1, then it's impossible for * this to be a vector of a double stamp. You've got a mark * which can't be from the first stamp (since there's no second stamp * [di,dj] away) and can't be from the second stamp (since it's not * [di,dj] away from another mark). * * If the number of marks in a line is >1, then if its' even: * ######## * Then you only need length/2 nubs to make that mark: * #.#.#.#. * If it's odd: * ######### * Then you need length/2+1 * #.#.#.#.# * * @param di Delta-row * @param dj Delta-column */ public void test( int di, int dj ) { // Some pruning. // If we've already found the best possible, no need to look any further. // If we've already handled this vector, no need to do it again. if( best>bestpossible && !seen.contains( ""+di+":"+dj ) ) { // Add this vector to the "seen" set seen.add( ""+di+":"+dj ); // Also add the negative of this vector, // since (di,dj) and (-di,-dj) represent the same double-stamp seen.add( ""+(-di)+":"+(-dj) ); // This is the number of nubs int nubs = 0; // No need to go through the entire nxm matrix, // just look at the marks for( Mark mark : marks ) { // Go back 1 before the mark on this line int ii = mark.i-di; int jj = mark.j-dj; // If there's no mark there, then this is the start of a line if( ii<0 || ii>=n || jj<0 || jj>=m || paper[ii][jj]=='.' ) { // Count the number of marks in this line. // This may look like an O(n^3) algorithm // ( O(n^2) marks, with an O(n) loop ) // but it's not. Each mark will only be considered // for the start of a line once, and since each mark is // only on one line, it will only be counted here once. // So, it's a prorated O(n^2) int count = 0; for( ii=mark.i, jj=mark.j; ii>=0 && ii=0 && jj=best ) break; } } } if( nubs>0 && nubsrights[i] ) rights[i]=j; if( ilowers[j] ) lowers[j]=i; // Count it ++best; } } // The best possible is half the number of marks // (+1 if the number of marks is odd) bestpossible = best/2; if( (best&1)==1 ) ++bestpossible; // Now, to find vectors to test. // No matter what the original stamp looks like, // there has to be some nub on the edge for which both // marks made by that nub are on the edge of the double-stamp. // So, we'll just go through the edges and look at all possible vectors. // Since testing a vector is O(n^2), the whole thing will be O(n^4), // but with significant pruning, we'll be OK. // Start with the left edge for( int i=0; i=0 ) for( int j=i+1; j=0 ) test( j-i, lefts[j]-lefts[i] ); // Right edge for( int i=0; i=0 ) for( int j=i+1; j=0 ) test( j-i, rights[j]-rights[i] ); // Upper edge for( int i=0; i=0 ) for( int j=i+1; j=0 ) test( uppers[j]-uppers[i], j-i ); // Lower edge for( int i=0; i=0 ) for( int j=i+1; j=0 ) test( lowers[j]-lowers[i], j-i ); // Here's the best! ps.println( best ); } /** * @param args */ public static void main( String[] args ) throws Exception { new stampstamp_vanb().doit(); } }