Statistics

Problem Statement for "Regions"

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

  1. {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.

  2. {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.

  3. {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.

  4. {9,0}

    {0,9}

    Returns: 9

  5. {0,9}

    {0,9}

    Returns: 9

  6. {0,9}

    {0,1}

    Returns: 9

  7. {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.

  8. {1000,100000,100000}

    {0,100000,1000000000}

    Returns: 1000099000

  9. {1000,100000,100000}

    {0,101000,1000000000}

    Returns: 1000098000

  10. {1,2,3,4,5,6,7,8,9,8,7,7}

    {100,200,300,400,500,600,700,800,900,900,900,901}

    Returns: 811

  11. {1000,100000,100000}

    {0,100999,1000000000}

    Returns: 1000099000

  12. {1,2,3,4,5,6,7,8,9,8,7,7}

    {100,200,300,400,500,600,700,800,900,900,900,900}

    Returns: 810

  13. {100,200,300,400,500,600,700,800,900,900,900,900}

    {1,2,3,4,5,6,7,8,9,8,7,7}

    Returns: 810

  14. {1,1,1}

    {999999999,999999999,999999999}

    Returns: 0

  15. {1,1,1}

    {999999999,1,999999999}

    Returns: 1999999996

  16. {1,1,1,1}

    {999999999,1,999999999,2}

    Returns: -1

  17. {999999999,1,999999999,999999999}

    {1,1,1,5}

    Returns: 2000000000

  18. {999999999,1,999999999,999999999}

    {1,1,1,6}

    Returns: -1

  19. {345111111,100234567,123456,654321}

    {251435123,412345123,341235643,123123123}

    Returns: 795650520

  20. { 0, 1000000000, 6 }

    { 0, 999999999, 18 }

    Returns: -1

  21. { 4, 2, 3 }

    { 4, 2, 6 }

    Returns: 7

  22. { 0, 10, 10 }

    { 0, 2, 2 }

    Returns: 10

  23. { 55, 455, 86, 500, 500, 333, 444, 5, 834, 5, 999, 55, 455, 86, 500, 500, 333, 444, 5, 834, 5, 999, 5, 834, 5, 999, 55, 455, 500, 444, 456, 19, 300, 55, 89, 33, 100, 1, 2, 3, 4, 5, 6, 7, 866, 56, 111, 48, 444 }

    { 43, 9, 86, 500, 500, 333, 333, 994, 934, 22, 82, 55, 455, 86, 500, 500, 333, 444, 5, 834, 5, 999, 4, 934, 22, 82, 55, 455, 99, 1000, 1, 2, 3, 4, 5, 99, 455, 333, 698, 453, 756, 243, 567, 44, 12, 15, 16, 88, 1000 }

    Returns: 29428

  24. { 0, 2, 0, 1, 1, 3 }

    { 0, 2, 2, 0, 1, 30000 }

    Returns: 30009

  25. { 5, 9 }

    { 6, 10 }

    Returns: 4

  26. { 0, 2 }

    { 0, 10 }

    Returns: 10

  27. { 0, 100000000 }

    { 0, 100000000 }

    Returns: 100000000

  28. { 0, 50 }

    { 0, 38 }

    Returns: 86

  29. { 321654987, 326598741, 1354689, 321654987, 12326547, 6546313, 6587313, 513847, 1681, 654987333, 1, 2 }

    { 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 2, 321654 }

    Returns: -1

  30. { 0, 3 }

    { 0, 5 }

    Returns: 7

  31. { 0, 4 }

    { 0, 6 }

    Returns: 10

  32. { 0, 1000000000, 0, 1000000000, 0, 1000000000, 0, 1000000000, 0, 1000000000 }

    { 0, 1000000000, 0, 1000000000, 0, 1000000000, 0, 1000000000, 0, 1000000000 }

    Returns: -1

  33. { 321, 3, 21, 18, 4, 7, 11, 13, 16, 79 }

    { 0, 2, 7, 11115, 12, 14, 19, 1, 7, 6 }

    Returns: 22673

  34. { 1, 2 }

    { 1, 6 }

    Returns: 5

  35. { 0, 6 }

    { 0, 20 }

    Returns: 26

  36. { 0, 1, 2, 3, 4, 5, 34543, 4343, 345345, 6747, 7436, 436, 34 }

    { 0, 2, 5, 9, 14, 20, 23478, 3245, 765, 64250, 64250, 3245, 34 }

    Returns: 926322

  37. { 4, 2, 3, 0, 10, 10 }

    { 4, 2, 6, 0, 2, 2 }

    Returns: 26

  38. { 0, 2, 777777700 }

    { 0, 4, 777777700 }

    Returns: 1555555400

  39. { 0, 65536 }

    { 0, 65536 }

    Returns: 65536

  40. { 0, 1 }

    { 0, 1 }

    Returns: 1

  41. { 0, 1000000000, 0, 100000000, 0, 100000000, 0, 9999999, 0, 99999992, 3, 99999994, 9873, 5186, 1873, 18438, 112 }

    { 1000000000, 0, 1000000000, 0, 1000000000, 0, 1000000000, 0, 1000000000, 0, 1000000000, 6548, 153, 4831, 13, 23, 4 }

    Returns: -1

  42. { 0, 4 }

    { 0, 2 }

    Returns: 6

  43. { 0, 5 }

    { 0, 7 }

    Returns: 11

  44. { 42, 532553, 42424 }

    { 242424, 525, 777 }

    Returns: 1264784

  45. { 0, 2 }

    { 0, 4 }

    Returns: 6

  46. { 99999999, 0 }

    { 99999997, 0 }

    Returns: 199999995

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: