// RoadConstruction.cpp : Defines the entry point for the console application.
// by Adrian Dale 15/12/2008
// Solution to the IEEE Challenge 2008 - Road Construction
// This code works by first parsing the input data into a minimal set of constraints
// needed to solve the problem. That is, we only need to take into account the houses
// that are closest to each side of the road. So, for each row we store the widest allowed
// distance from the road to the left of the road and to the right of the road.
// We then use a recursive function to try out all possible starting positions of
// each parcel of land to see what area of land they give.
// We record the maximum area once all possible parcel subdivisions have been tested
// and output it as the puzzle answer.
using namespace std;
// Data structures to hold the road map data
// We don't need to hold a 2D array, since some of the house data is likely
// to be redundant.
// All we need to know for each row is the smallest possible rectangle we
// could fit on that row
typedef vector<BoardRow>::iterator BoardIter;
// We get given this number - the number of parcels of land we must divide the
// map into
int Parcels = 0;
// We get given this number - Height is how long the road is
int Height = 0;
int Width = 0;
// We need this to store the maximum area so far as we go through our recursive
int MaxParcelArea = 0;
// ReadInput reads the challenge parameters from stdin.
// See challenge for input format.
// Note that this function assumes the input data is valid.
// Not a great assumption but should do for this quick and dirty code.
int Houses = 0;
// Height of the board comes first in the input
cin >> Height;
// We'll have a row for each square of height
// Next input value is width
cin >> Width;
// Width of map marks the min and max possible widths of a rectangle
// at each y coordinate. Note that a Width of n is equivalent to a house at n+1
// Adding in the houses will narrow these constraints
for( BoardIter it=Board.begin(); it != Board.end(); ++it )
it->Left = -1 * (Width+1);
it->Right = Width+1;
// Read in count of number of parcels of land
cin >> Parcels;
// Read in the number of houses - we use this to tell us how many
// sets of input coordinates to expect
cin >> Houses;
for( int i=0; i<Houses; ++i )
int HouseX = 0;
int HouseY = 0;
cin >> HouseY;
cin >> HouseX;
// Decrement HouseY so we can use it as an array index.
// For some reason the rows seem to
// be numbered from 1 in the input.
if ( HouseX < 0 )
// Only update the board with the house coordinates if it narrows the
if ( HouseX > Board[HouseY].Left)
Board[HouseY].Left = HouseX;
if ( HouseX < Board[HouseY].Right)
Board[HouseY].Right = HouseX;
// GetParcelArea returns the area covered by the passed in
// allocation of the parcels
int GetParcelArea( vector<int> &ParcelList )
int TotalParcelArea = 0;
// Parcel list comes in as a vector of starting positions
// for each parcel, numbered from 0.
// Go through each parcel in the list and add its area to the
for ( int parcelNo=0; parcelNo<ParcelList.size(); ++parcelNo )
// We're given the start row of each parcel.
// The end row is the one before the start of the next parcel,
// or the top of the map for the last parcel
int ParcelStart = ParcelList[parcelNo];
if ( parcelNo < ParcelList.size() - 1 )
ParcelEnd = ParcelList[parcelNo+1];
ParcelEnd = Height;
// Work out the widest rectancle we can fit in this parcel's
// range of rows by looping through the constraints for each
// row that makes up the parcel
int MaxLeft = -1*(Width+1);
int MinRight = Width+1;
for( int i=ParcelStart; i<ParcelEnd; ++i )
if ( Board[i].Left > MaxLeft)
MaxLeft = Board[i].Left;
if ( Board[i].Right < MinRight)
MinRight = Board[i].Right;
// Very simple formula for area of a rectangle!
int ParcelArea = (MinRight - MaxLeft - 1) * (ParcelEnd - ParcelStart);
TotalParcelArea += ParcelArea;
// This function recursively tries all possible parcel
// sizes into the parcel list
void TryParcelList( vector<int> ParcelList, int parcelNo )
if ( parcelNo == Parcels )
// We've filled our list of guesses, so try it out
int GuessArea = GetParcelArea( ParcelList );
if ( GuessArea > MaxParcelArea )
MaxParcelArea = GuessArea;
// Still some more parcels to allocate, so call this fn recursively
// for each possible parcel left at this level, starting from
// where the previous ones left off, and finishing with enough room for
// all remaining parcels of minimum size
for (int i=ParcelList[parcelNo-1] + 1; i <= Height - Parcels + parcelNo; ++i )
ParcelList[parcelNo] = i;
TryParcelList( ParcelList, parcelNo + 1 );
// This function kicks off the recursive search for the best possible subdivision
// of the map into parcels.
MaxParcelArea = 0;
// First piece always starts at zero
ParcelList = 0;
// Kick off the recursive function
TryParcelList( ParcelList, 1 );
int _tmain(int argc, _TCHAR* argv)
cout << GetMaxParcelArea() << endl;