CPMagical CP Library

Problem solution · Java

CCC 2010 S3 - Firehose

CCC 2010 S3 - Firehose: a Java solution using binary search. Learn the idea, check the complexity, and read the full code, with credit to CCCSolutions.

Technique
Binary search
Source
CCCSolutions
Length
186 lines
Start with the idea.

Try the problem first. If you get stuck, read the approach below, then write your own solution. The full code is at the bottom.

Approach

Binary search

For CCC 2010 S3 - Firehose, the implementation exploits a monotonic condition to discard half of the remaining search space after every check.

  1. Identify the ordered answer range or sorted search domain.
  2. Write a predicate whose truth changes only once.
  3. Move the appropriate boundary after each midpoint check and return the final feasible position.

Code notes

  • 186 lines of Java from the credited upstream file ccc10s3.java.
  • The implementation visibly relies on sequence storage.
  • 11 loop blocks detected.

Complexity

Multiply the logarithmic number of midpoint checks by the cost of one predicate evaluation.

Check the problem constraints before deciding whether this complexity will pass.

Source

Code and credit

This code comes from CCCSolutions by CCCSolutions contributors · Milliken Mills High School and is used under the MIT licence.

Open problem ↗Original source ↗
Full codeCCC 2010 S3 - Firehose · JavaJava
Use this to learn the idea, then write your own version.
// S3 2010 V3: Firehose//// version 3: arrays, sorting and binary search//            (works for all)// version 2: linked lists: start with h hydrants//            combining the closest two to eliminate one//            until K reached (worked for 1 to 5)// version 1: arrays: eliminate the k biggest gaps.//            (worked for the first couple of data sets)////// okay, so this uses the following idea. // If you'll need a max hose length of say 200, // then lets use a 200 hose length EVERYWHERE!//// The hose length is a radius. I use a diameter instead// and to find the correct length hose, I try diameters// in a binary search fashion to get to the correct length quickly. // Before starting on the process I simplify things by sorting// and shifting the houses so the biggest gap between houses comes // after the LAST house. Thus there are no "wrap around" // circular issues.//// For a given diameter, I start with the first house and see// which other houses fall within the diameter. That's one. // Then I start at the next house, not covered and cover it// and the next ones till I can't cover any more. That's two.// Eventually I get to the last house and look at my count.// If the count is k, I'm done. (almost)// To be "double sure" I then reduce the diamter by 1 until// my count goes above k. Then (diameter+1)/2 is the answer. //// This took me 1 solid week of study of the TEST data. // One of the toughest problems I've seen so far!  :-)  import java.awt.*;import hsa.*; public class S32010v3{     public static int h, k;    public static int[] house;     public static void main (String[] args)    {	TextInputFile c;	c = new TextInputFile ("s3.1.in");	int diameter, x, high, low; 	// input section	h = c.readInt ();	house = new int [h];	for (int i = 0 ; i < h ; i++)	    house [i] = c.readInt ();	k = c.readInt (); 	if (k >= h)	    System.out.println (0);	else	{	    sortHouses ();	    shiftHouses ();	    	    // bianary search for correct diameter	    diameter = 1000000 / k;	    high = diameter;	    low = 0;	    x = check (diameter);	    while (x != 0)	    {		if (x < 0)		    low = diameter;		else		    high = diameter;		diameter = (low + high) / 2;		x = check (diameter);	    } 	    // when you find a diameter that appears to work,	    // continually reduce it until it doesn't work any more.	    x = check (diameter);	    while (x == 0)	    {		diameter--;		x = check (diameter);	    }	    System.out.println ((float) (diameter + 1) / 2);	}    }      // returns -1 if diameter is too small    // returns  0 if diameter is appears okay    // returns  1 if diameter is too big    //    // Starting at the first house, cover it and     // all subsequent house within the diameter of the hose    // that's one.     // move to the next house and cover again.     // At the end how many coverings did it take?    // if exactly k, that's the correct diameter    // (well maybe... need to verify it by checking    // smaller diameters until the diameter definitely    // stopps working)     public static int check (int diameter)    {	int i = 0;	int start;	int count, startPlace, houseCount; 	start = 0;	i = start;	count = 0;	while (i < h)	{	    startPlace = house [i];	    while (i < h && startPlace + diameter > house [i])		i++;	    count++;	    if (i < h && startPlace + diameter == house [i])		i++;	}	if (count < k)	    return 1;	else if (count > k)	    return -1;	else	    return 0;    }      public static void sortHouses ()    {	int hold, j;	for (int i = 1 ; i < h ; i++)	{	    hold = house [i];	    j = i - 1;	    while (j >= 0 && hold < house [j])	    {		house [j + 1] = house [j];		j--;	    }	    house [j + 1] = hold;	}    }      // this finds the largest gap and rotates it to the end.    // the first house will always be at location 0    // and there will not be any complex "wraparound" issues later.    public static void shiftHouses ()    {	// find largest gap	int largestGap = 1000000 - house [h - 1] + house [0];	int largestI = 0;	int hold;	for (int i = 1 ; i < h ; i++)	    if (house [i] - house [i - 1] > largestGap)	    {		largestGap = house [i] - house [i - 1];		largestI = i;	    }	    	// shift houses	hold = house [largestI];	for (int i = 0 ; i < largestI ; i++)	    house [i] = house [i] + (1000000 - hold);	for (int i = largestI ; i < h ; i++)	    house [i] = house [i] - hold; 	// put them back in order.	sortHouses ();    }      public static void print ()    {	for (int i = 0 ; i < h ; i++)	    System.out.println (house [i]);    }}

Keep practising

Did this explanation save you time? I'm a Grade 11 student building this free library to make difficult algorithms easier to understand.

Buy me a coffee ↗