Connection Status:
Competition Arena > Regions

Regions

SRM 179 · 2004-01-17 · by dgoodman

SRM 179 · 2004-01-17 · by dgoodman · Advanced Math
Class Name: Regions
Return Type: int
Method Name: numTaxes
Arg Types: (vector<int>, vector<int>)
Problem Statement

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.

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)
{9,0}
{0,9}
Returns: 9
4)
{0,9}
{0,9}
Returns: 9
6)
{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.

Submissions are judged against all 46 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Regions with a public method int numTaxes(vector<int> row, vector<int> col) · 46 test cases · 2 s / 256 MB per case

Submitting as anonymous