CCC 2009 S5 - Wireless

1// CCC 20092//3// S5: Wireless4//5// Straight forward approach:6// 1. Input the main dimensions of the city7// 2. for each wirelsss station read, add the8//    bit rate to the coffeshops within the circle9// 3. find the max bitrate coffeshop and print10// 4. count the max bitrates and print11//12// I abandoned this approach for nearly a week trying to 13// think of some clever DP method, or anything else14// that would not involve traversing the array multiple times. 15//16// Eventually I gave up trying to think of something else17// and re focused my efforts at improving the efficiency18// of this straight forward approach.19//20// Here are all my tricks:21// 1. Because java stores arrays row-wise, I turned the city 22//    on its side and make each row 30,000 wide, not 1000.23//    (1000 rows of 30,000 can be traversed faster than the reverse)24// 2. I tightend up the code so that few calculations are25//    done in the inner loop, by usig extra variables26// 3. I process the centre row first and work outward in either 27//    direction. Not sure if it matters much, but I did it.28// 4. Instead of doing x and checking if I'm done, 30,000 times29//    in the inner loop, I do ten things before checking if I'm done yet.30//    This could be increased to prehaps 50 or 100 or more. 31//    (copy and paste is cheap). This was quite a time saver. 32//33// these got 1,2,3 and 6 data sets well within time limits. 34// Sets 4 and 5 still stayed stubbornly at 2:30 sec (approx). 35// The final "Ah Ah" was (after extensive cheating and looking at36// the real data)37//38// 5. Look for and elimitate all the BIG circles. 39//    The idea is that if a station broadcasts to the entire city 40//    it have NO effect on finding the max place. So I simply41//    add up the bitrate for the big stations and add it to the 42//    max at the end. (Who would have guessed there would be lots 43//    of such stations?)44//    BTW a big station has a radius + the long coordinte > 3003345//    provided the radius > the long coordinate. 30033 comes from46//    the fact the worse case is if the station is in the centre at47//    15,000 on one edge. To cover the far corner it takes a radius48//    of 15033. 49//50// that concludes the HARDEST program yet in the CCC because without51// having access to the final test data, why bother going to52// the lengths necessary to tweek a WORKING PROGRAM 53// sufficiently to get in under the wire?54//55 56import java.awt.*;57import hsa.*;58 59public class CCC2009S5Wireless60{61 62    public static int[] [] coffeeShop;63    public static int rows, cols, k;64 65    public static void main (String[] args)66    {67	int col, row, radius, bitrate, max, total;68 69	TextInputFile f = new TextInputFile ("s5.1.in");70 71	cols = f.readInt ();  // transposed72	rows = f.readInt ();73	coffeeShop = new int [rows + 1] [cols + 1];74 75	for (int i = 1 ; i <= rows ; i++)76	    for (int j = 1 ; j <= cols ; j++)77		coffeeShop [i] [j] = 0;78 79	int k = f.readInt ();80	total = 0;81	for (int i = 1 ; i <= k ; i++)82	{83	    row = f.readInt ();84	    col = f.readInt ();85	    radius = f.readInt ();86	    bitrate = f.readInt ();87	    if (col + radius > 30033 && radius > col)88		total += bitrate;89	    else90		process (col, row, radius, bitrate);91	}92 93	max = maxBitRate ();94	System.out.println (max + total);95	System.out.println (countMaxBitRate (max));96    }97 98 99    public static void process (int c, int r, int radius, int bitrate)100    {101 102	int start = Math.max (1, c - radius);103	int stop = Math.min (cols, c + radius);104	int uplimit = Math.min (rows, r + radius);105	int downlimit = Math.max (1, r - radius);106	int square = radius * radius;107	int i, j;108	int t1, t2, t3;                  // not really worth it109	for (i = r ; i <= uplimit ; i++)110	{111	    t1 = i - r;112	    t2 = t1 * t1;113	    t3 = square - t2;114	    while (((start - c) * (start - c)) > t3)115		start++;116	    while (((stop - c) * (stop - c)) > t3)117		stop--;118 119	    // move 10 at once between checking for being at the end120	    // this silliness shaves off nearly 40% of time on set#5121	    for (j = start ; j < stop - 8 ; j++)122	    {123		coffeeShop [i] [j++] += bitrate;124		coffeeShop [i] [j++] += bitrate;125		coffeeShop [i] [j++] += bitrate;126		coffeeShop [i] [j++] += bitrate;127		coffeeShop [i] [j++] += bitrate;128		coffeeShop [i] [j++] += bitrate;129		coffeeShop [i] [j++] += bitrate;130		coffeeShop [i] [j++] += bitrate;131		coffeeShop [i] [j++] += bitrate;132		coffeeShop [i] [j] += bitrate;133	    }134	    while (j <= stop)135		coffeeShop [i] [j++] += bitrate;136 137	}138	start = Math.max (1, c - radius);139	stop = Math.min (cols, c + radius);140	for (i = r - 1 ; i >= downlimit ; i--)141	{142	    t1 = i - r;143	    t2 = t1 * t1;144	    t3 = square - t2;145	    while (((start - c) * (start - c)) > t3)146		start++;147	    while (((stop - c) * (stop - c)) > t3)148		stop--;149	    for (j = start ; j < stop - 8 ; j++)150	    {151		coffeeShop [i] [j++] += bitrate;152		coffeeShop [i] [j++] += bitrate;153		coffeeShop [i] [j++] += bitrate;154		coffeeShop [i] [j++] += bitrate;155		coffeeShop [i] [j++] += bitrate;156		coffeeShop [i] [j++] += bitrate;157		coffeeShop [i] [j++] += bitrate;158		coffeeShop [i] [j++] += bitrate;159		coffeeShop [i] [j++] += bitrate;160		coffeeShop [i] [j] += bitrate;161	    }162	    while (j <= stop)163		coffeeShop [i] [j++] += bitrate;164	}165    }166 167 168    public static int maxBitRate ()169    {170	int max = 0;171	for (int i = 1 ; i <= rows ; i++)172	    for (int j = 1 ; j <= cols ; j++)173		if (coffeeShop [i] [j] > max)174		    max = coffeeShop [i] [j];175	return max;176    }177 178 179    public static int countMaxBitRate (int max)180    {181	int count = 0;182	for (int i = 1 ; i <= rows ; i++)183	    for (int j = 1 ; j <= cols ; j++)184		if (coffeeShop [i] [j] == max)185		    count++;186	return count;187    }188}189 190 191