TopCoder problem "Regions" used in SRM 179 (Division I Level Two , Division II Level Three)



Problem Statement

    Our world consists of rows and columns of identical square regions. We have a list of regions that we want to visit, starting from the center of the first region in the list and going in straight lines to the center of each successive region. Every time we cross from one region into the interior of another region (even if we have previously visited it) we will be charged a tax.

Create a class Regions that contains the method numTaxes that takes int[]s rows and columns of the regions on our list and returns the number of taxes we will have to pay. The i-th elements of rows and columns give the location of the i-th region that we must visit. If we must pay more than 2,000,000,000 taxes (!) then return -1.

 

Definition

    
Class:Regions
Method:numTaxes
Parameters:int[], int[]
Returns:int
Method signature:int numTaxes(int[] row, int[] col)
(be sure your method is public)
    
 

Notes

-We are not charged a tax if we just touch the boundary of a region.
 

Constraints

-rows has between 1 and 50 elements inclusive.
-columns has the same number of elements as rows.
-Each element of rows and or columns is between 0 and 1,000,000,000 inclusive.
 

Examples

0)
    
{4,2,3}
{4,2,6}
Returns: 7
Going from the center of 4,4 to the center of 2,2 we pay tax when we enter region 3,3 and when we enter region 2,2. Going from the center of 2,2 to the center of 3,6 we pay tax as we enter 2,3 then 2,4 then 3,4 then 3,5 then 3,6.

1)
    
{0,1000000000,0}
{0,1000000000,0}
Returns: 2000000000
We enter each region along the diagonal on the first leg, a total of 1,000,000,000 regions. On the way back we go back down the diagonal but we still have to pay taxes.

2)
    
{0,10,10}
{0,2,2}
Returns: 10
The first leg enters (1,0),(2,0),(3,1),(4,1),(5,1),(6,1),(7,1),(8,2),(9,2),(10,2). The second leg just stays within region (10,2), paying no additional taxes.
3)
    
{0,1000000000,6}
{0,999999999,18}
Returns: -1
Each of the two legs enters almost 2 billion regions, so the sum of the taxes along this path is greater than 2 billion.
4)
    
{999999999,1,999999999,999999999}
{1,1,1,6}
Returns: -1

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1099

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4715&pm=1099

Writer:

dgoodman

Testers:

lbackstrom , brett1479

Problem categories:

Advanced Math