Statistics

Problem Statement for "GrandpaField"

Problem Statement

Josh's grandfather has a N x N square field. Each cell in the field is a 1 x 1 square and contains a single type of fruit. Josh's grandfather said to Josh: "You can have any square section of my field, but with one condition. The section must not contain more than two different types of fruits and must not contain fruits of type 0 (zero)."

The field contains a maximum of 8 types of fruits. The content of the field can be determined from the String[] changes. Each element of changes is formatted "X Y L F" (quotes for clarity only), where X and Y are the 0-based coordinates of the upper left corner of a square area, and L is the length of one side of the square (the upper left corner of the field is at (0, 0)). F is the type of fruit that will be planted in that square area. Initially, each cell contains fruit of type 0. The elements of changes should be applied, in order, to determine the final content of the field. Whenever a new type of fruit is planted in a certain area, it will entirely replace any existing fruit that was there before.

Josh is greedy, so he wants to maximize the area of his section. Return the area of the largest square section of the field that contains no more than 2 different types of fruits and doesn't contain fruits of type 0. If no section can be chosen, return 0. See examples and constraints for more clarifications.

Definition

Class:
GrandpaField
Method:
getArea
Parameters:
int, String[]
Returns:
int
Method signature:
int getArea(int N, String[] changes)
(be sure your method is public)

Constraints

  • N will be between 1 and 1000, inclusive.
  • changes will contain between 0 and 50 elements, inclusive.
  • Each element of changes will be formatted "X Y L F" (quotes for clarity).
  • In each element of changes, X and Y will be integers between 0 and N-1, inclusive, with no extra leading zeroes. L will be an integer between 1 and N, inclusive, with no extra leading zeroes. X+L and Y+L will each be between 1 and N, inclusive. F will be an interger between 0 and 7, inclusive, with no extra leading zeroes.

Examples

  1. 3

    {"0 0 3 1"}

    Returns: 9

    The field will look like: 111 111 111 Here, he can choose the whole field, so the answer is 9.

  2. 3

    {"1 1 1 7"}

    Returns: 1

    000 070 000 The answer is 1. The chosen square is the square that contains the fruit of type 7.

  3. 7

    {"0 0 7 7", "2 2 4 1", "3 5 1 5"}

    Returns: 25

    The field looks like: 7777777 7777777 7711117 7711157 7711117 7711117 7777777 The optimal way is to choose the square with the top-right corner at (0,0) and side 5. This square contains fruits of type 7 and fruits of type 1. The answer is 25.

  4. 7

    {"0 0 7 7", "2 2 4 1", "3 5 1 5", "1 1 1 5", "5 1 1 5"}

    Returns: 16

    The field looks like: 7777777 7577777 7711117 7711157 7711117 7511117 7777777 The biggest square with fruits of type 7 and 5 has area 4, type 7 and 1 has area 9. But the answer is 16 : the square that contains frutis of type 1 and 5 with the corner at (2, 2) is the optimal solution.

  5. 1000

    {"0 0 1000 0", "20 20 980 1", "40 40 960 0", "60 60 940 2", "80 80 920 0", "100 100 900 3", "120 120 880 0", "140 140 860 4", "160 160 840 0", "180 180 820 5", "200 200 800 0", "250 250 22 1", "250 250 1 0"}

    Returns: 441

  6. 1000

    {"0 0 1000 0", "20 20 980 1", "40 40 960 0", "60 60 940 2", "80 80 920 0", "100 100 900 3", "120 120 880 0", "140 140 860 4", "160 160 840 0", "180 180 820 5", "200 200 800 0", "220 220 780 6", "240 240 760 0", "260 260 653 7", "499 499 3 0"}

    Returns: 168921

  7. 1000

    {"0 0 1000 0", "20 20 980 1", "40 40 960 0", "60 60 940 2", "80 80 920 0", "100 100 900 3", "120 120 880 0", "140 140 860 4", "160 160 840 0", "180 180 820 5", "200 200 800 0", "250 250 22 1", "250 250 1 0", "345 78 225 1", "345 222 77 0", "400 200 78 0"}

    Returns: 19600

  8. 1000

    {"0 0 1000 0", "20 20 980 1", "40 40 960 0", "60 60 940 2", "80 80 920 0", "100 100 900 3", "120 120 880 0", "140 140 860 4", "160 160 840 0", "180 180 820 5", "200 200 800 0", "123 321 123 7", "236 209 23 0", "232 890 90 0", "250 250 22 1", "250 250 1 0", "345 78 225 0", "345 222 77 0", "400 200 78 0"}

    Returns: 15129

  9. 1000

    {}

    Returns: 0

  10. 1000

    {"1 1 1 1", "2 2 2 2", "3 3 3 3", "4 4 4 4", "5 5 5 5", "6 6 6 6", "7 7 7 7", "8 8 8 0", "9 9 9 1", "10 10 10 2", "11 11 11 3", "12 12 12 4", "13 13 13 5", "14 14 14 6", "17 17 17 7", "18 18 18 0", "19 19 19 1", "20 20 20 2", "21 21 21 3", "22 22 22 4", "23 23 23 5", "24 24 24 6", "25 25 25 7", "26 26 26 0", "27 27 27 1", "28 28 28 2", "29 29 29 3", "30 30 30 4", "31 31 31 5", "32 32 32 6", "33 33 33 7", "34 34 34 0", "35 35 35 1", "36 36 36 2", "37 37 37 3", "38 38 38 4", "39 39 39 5", "40 40 40 6", "41 41 41 7", "42 42 42 0", "43 43 43 1", "44 44 44 2", "45 45 45 3", "46 46 46 4", "47 47 47 5", "48 48 48 6", "49 49 49 7", "50 50 50 0"}

    Returns: 16

  11. 998

    {"1 1 1 1", "44 44 44 2", "48 48 48 6", "2 2 2 2", "3 3 3 3", "4 4 4 4", "5 5 5 5", "6 6 6 6", "7 7 7 7", "8 8 8 0", "9 9 9 1", "10 10 10 2", "11 11 11 3", "12 12 12 4", "13 13 13 5", "45 45 45 3", "46 46 46 4", "47 47 47 5", "14 14 14 6", "17 17 17 7", "18 18 18 0", "19 19 19 1", "23 23 23 5", "24 24 24 6", "25 25 25 7", "26 26 26 0", "27 27 27 1", "28 28 28 2", "29 29 29 3", "30 30 30 4", "40 40 40 6", "41 41 41 7", "42 42 42 0", "43 43 43 1","31 31 31 5", "20 20 20 2", "21 21 21 3", "22 22 22 4", "32 32 32 6", "33 33 33 7", "34 34 34 0", "35 35 35 1", "36 36 36 2", "37 37 37 3", "38 38 38 4", "39 39 39 5", "49 49 49 7", "50 50 50 0"}

    Returns: 121

  12. 1000

    {"0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1","0 0 1000 1"}

    Returns: 1000000

  13. 1

    {"0 0 1 0"}

    Returns: 0

  14. 1

    {"0 0 1 1"}

    Returns: 1

  15. 2

    {"0 0 2 1", "0 1 1 2", "1 1 1 3"}

    Returns: 1

  16. 3

    {"1 1 2 1", "0 0 2 2", "0 0 1 0", "2 2 1 0"}

    Returns: 1

  17. 1000

    {"33 33 700 1", "25 89 900 0", "3 654 29 1", "23 633 40 0", "876 765 20 2", "242 256 40 3", "270 230 40 0"}

    Returns: 3136

  18. 870

    {"0 0 500 1", "0 1 499 0", "3 2 600 2", "4 2 599 0", "860 860 6 0", "860 860 2 1", "861 860 1 0"}

    Returns: 1

  19. 1000

    {"0 0 1000 0", "0 0 1000 1", "500 500 500 2", "0 0 1000 1", "500 500 1 0", "750 750 1 0", "250 250 1 0", "333 333 1 0", "250 789 1 0", "750 277 1 0"}

    Returns: 249001

  20. 800

    {"0 0 800 0", "700 700 100 1", "600 600 100 1", "600 700 100 2", "700 600 100 3", "600 700 100 3"}

    Returns: 40000

  21. 800

    {"0 0 800 0", "700 700 100 1", "600 600 100 1", "600 700 100 2", "700 600 100 3", "600 700 100 3", "0 0 399 5", "198 198 4 0", "199 199 1 2"}

    Returns: 40000

  22. 800

    {"0 0 800 0", "0 0 100 1", "100 100 100 1", "0 100 100 2", "100 0 100 3", "0 100 100 3", "401 401 399 5", "598 598 4 0", "599 599 1 2", "0 0 1 0"}

    Returns: 39601

  23. 878

    {"0 0 800 0", "0 0 100 1", "100 100 100 1", "0 100 100 2", "100 0 100 3", "0 100 100 3", "401 401 399 5", "598 598 4 0", "599 599 1 2"}

    Returns: 40000

  24. 800

    {"0 0 800 0", "0 700 100 1", "100 700 100 1", "0 600 100 2", "100 700 100 3", "0 600 100 3", "401 401 399 5", "598 598 4 0", "599 599 1 2", "0 0 1 0"}

    Returns: 39204

  25. 800

    {"0 0 800 0", "700 0 100 1", "700 100 100 1", "600 0 100 2", "100 700 100 3", "600 0 100 3", "401 401 399 5", "598 598 4 0", "599 599 1 2", "0 0 1 0"}

    Returns: 39204

  26. 1000

    {"0 0 1000 0", "0 0 1000 1", "0 0 1000 2", "0 0 1000 3", "0 0 1000 4", "0 0 1000 5", "0 0 1000 6", "0 0 1000 7", "1 1 999 0", "1 1 999 1", "1 1 999 2","1 1 999 3", "1 1 999 4", "1 1 999 5","1 1 999 6", "1 1 999 7", "2 2 600 0", "3 3 601 1", "3 3 602 2", "3 3 601 3", "3 3 600 4", "3 3 601 5", "3 3 700 6", "3 3 706 7", "100 100 800 0", "100 100 900 1", "100 100 800 2", "100 100 800 3", "100 100 900 4", "100 100 800 5", "100 100 800 6", "100 100 900 7", "300 300 600 0", "300 300 500 1", "300 300 400 2", "300 300 300 3", "300 300 200 4", "300 300 700 5", "300 300 600 6", "300 300 688 7", "600 0 300 0", "600 0 100 1", "600 0 100 2"}

    Returns: 490000

  27. 1000

    {"0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0", "0 0 1000 1","0 0 1000 0" }

    Returns: 0

  28. 1000

    {"0 0 500 4", "0 0 400 5", "0 0 300 6", "0 0 200 7", "1 1 9 0", "1 1 9 1", "1 1 99 2","1 1 99 3", "1 1 90 4", "1 1 89 5","1 1 89 6", "1 1 89 7", "2 2 600 0", "3 3 61 1", "3 3 62 2", "3 3 61 3", "3 3 60 4", "3 3 61 5", "3 3 70 6", "3 3 76 7", "100 100 80 0", "100 100 90 1", "100 100 80 2", "100 100 80 3", "100 100 90 4", "100 100 80 5", "100 100 80 6", "100 100 90 7", "300 300 60 0", "300 300 50 1", "300 300 40 2", "300 300 30 3", "300 300 20 4", "300 300 70 5", "300 300 60 6", "300 300 68 7", "600 0 30 0", "600 0 10 1", "600 0 10 2", "501 0 499 0", "750 500 250 0", "885 750 115 0", "925 865 75 0", "0 0 15 0", "0 15 50 0", "0 65 75 0", "0 140 100 0", "0 240 200 0", "0 440 300 0", "0 740 260 0"}

    Returns: 8100

  29. 1000

    {"0 0 1000 0", "20 20 980 1", "40 40 960 0", "60 60 940 2", "80 80 920 0", "100 100 900 3", "120 120 880 0", "140 140 860 4", "160 160 840 0", "180 180 820 5", "200 200 800 0", "250 250 22 1", "250 250 1 0" }

    Returns: 441

  30. 1000

    {"0 0 999 1" }

    Returns: 998001

  31. 1000

    {"0 0 500 1", "0 500 500 2", "500 0 500 3", "500 500 500 4" }

    Returns: 250000

  32. 10

    {"0 0 1 0" }

    Returns: 0

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: