Statistics

Problem Statement for "HexagonalBattlefield"

Problem Statement

You may have heard of the game "Heroes of Might and Magic". Recently, battles in this game have been broadcast online, and the weekly battles between Petr and Vasyl have been very popular. Petr usually wins these battles, so Vasyl has decided to develop a new strategy.


The battlefield in this game consists of equal hexagonal cells arranged in the form of a larger hexagon. The number of cells on each side of the battlefield represents the size of the field. The coordinate system is shown in the following figure, which depicts a battlefield of size 3:

This week, Petr and Vasyl are playing on a battlefield of size N. Some of the cells are already occupied by Petr's heroes. The locations of these cells are given in the int[]s X and Y, where (X[i], Y[i]) is the location of Petr's i-th hero. To defeat Petr, Vasyl must occupy every single free cell with his own heroes. Unfortunately, Vasyl only has equestrian heroes, each of which occupy exactly two adjacent cells. No two heroes can occupy a single cell. One possible correct arrangement is shown in the following figure:

Vasyl wants to simulate a battle with every possible arrangement of his heroes so that he can determine the optimal one. Calculate the number of different possible arrangements he will consider. The answer might be very large, so return the number modulo 2000000011.

Definition

Class:
HexagonalBattlefield
Method:
countArrangements
Parameters:
int[], int[], int
Returns:
int
Method signature:
int countArrangements(int[] X, int[] Y, int N)
(be sure your method is public)

Constraints

  • N will be between 1 and 8, inclusive.
  • X will contain between 1 and 50 elements, inclusive.
  • X and Y will each contain the same number of elements.
  • All points (X[i], Y[i]) will lie inside the battlefield of size N.
  • All points (X[i], Y[i]) will be distinct.

Examples

  1. {-2,0,1,1,0}

    {-2,0,1,0,2}

    3

    Returns: 10

    This is the battlefield shown in the figure above.

  2. {0}

    {0}

    2

    Returns: 2

  3. {0}

    {0}

    3

    Returns: 104

  4. {-1,0,0,1,2}

    {0,0,1,0,0}

    3

    Returns: 6

  5. {0,1}

    {0,1}

    2

    Returns: 0

  6. {-1,0}

    {-1,0}

    2

    Returns: 0

  7. {-1,0}

    {0,0}

    2

    Returns: 0

  8. {-1,0,1}

    {0,1,1}

    2

    Returns: 2

  9. {0,1,1}

    {1,1,0}

    2

    Returns: 2

  10. {1,1,0}

    {1,0,-1}

    2

    Returns: 2

  11. {1,0,-1}

    {0,-1,-1}

    2

    Returns: 2

  12. {-1,-1,0}

    {-1,0,1}

    2

    Returns: 2

  13. {-1,0,1}

    {-1,0,1}

    2

    Returns: 1

  14. {-1,0,1}

    {0,0,0}

    2

    Returns: 1

  15. {0,0,0}

    {1,0,-1}

    2

    Returns: 1

  16. {0,1,-1,0,1}

    {0,0,-1,-1,1}

    2

    Returns: 1

  17. {0,0,0,2,2,2,1,1,-1,-1,-3,-3,-3,-2,-3}

    {3,2,1,3,2,1,-2,-1,-3,-2,-3,-2,0,0,-1}

    4

    Returns: 4

  18. {0}

    {0}

    4

    Returns: 78408

  19. {0,-3,-2,-1,0,1,2,3,3,3,3,2,1,0,-1,-2,-3,-3,-3}

    {0,0,1,2,3,3,3,3,2,1,0,-1,-2,-3,-3,-3,-3,-2,-1}

    4

    Returns: 104

  20. {-1,0,0,1,2}

    {0,0,1,0,0}

    3

    Returns: 6

  21. {0,0,0,0,0,0,1,2,3,4,4,4,4,3,2,1,0,-1,-2,-3,-4,-5,-5,-4,-3,-3,-4,-4,-4,-5,-6,-6,-6,-6,1,2,3,4,5,5,4,3,2,5,6,6,6,6,6}

    {7,6,5,4,3,2,2,2,2,2,1,0,-1,-2,-3,-4,-5,-5,-5,-5,-5,-5,-4,-3,-2,-1,-1,0,1,1,0,-1,-2,-3,4,4,4,4,5,6,6,6,6,4,4,3,2,1,0}

    8

    Returns: 1424364185

  22. {0}

    {0}

    8

    Returns: 1931935224

  23. {0,-1,0,1,1,0,-1}

    {0,0,1,1,0,-1,-1}

    8

    Returns: 1961167642

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

    {2,1,0,-1,-1,0,1,2,3,1,5,4,3,2,2,3,4,5,-2,-3,-4,-3,-4,-5,-5,-2,-2,-3,-4}

    8

    Returns: 0

  25. {0,0,0,0,0,0,1,2,3,4,5,6,0,0,0,1,2,3,4,5,6,7,7,4,5,6,7,7,1}

    {4,3,2,1,0,-1,-1,-1,-1,-1,-1,-1,5,6,7,0,1,2,3,4,5,6,5,0,1,2,3,7,4}

    8

    Returns: 469208086

  26. {0,-1,0,0,0,0}

    {0,-1,-1,-2,-3,-4}

    8

    Returns: 0

  27. {0,-1,-2,-3,1,2,3,1,2,3,-1,-2,-3,0,0,0,0,0,0}

    {0,0,0,0,1,2,3,0,0,0,-1,-2,-3,-1,-2,-3,1,2,3}

    8

    Returns: 633767932

  28. {7,7,7,7,7,7,7,7,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-7,-7,-7,-7,-7,-7,-7,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,0}

    {7,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-7,-7,-7,-7,-7,-7,-7,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,7,7,7,7,7,7,0}

    8

    Returns: 605569627

  29. {0,1,1,0,-1,-1}

    {1,1,0,-1,-1,0}

    8

    Returns: 0

  30. {0}

    {0}

    7

    Returns: 605569627

  31. {0,-1,-1,0,1,1,0}

    {0,0,-1,-1,0,1,1}

    7

    Returns: 580197178

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

    {6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6}

    7

    Returns: 0

  33. {0,0,0,0,0,0,0,0,0,0,0,0,3}

    {6,5,4,3,2,1,0,-1,-2,-3,-4,-6,2}

    7

    Returns: 1466676064

  34. {0,1,2,3,4,5,6,6,6,6,6,6,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-6,-6,-6,-6,-6,-6,-5,-4,-3,-2,-1,0}

    {6,6,6,6,6,6,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-6,-6,-6,-6,-6,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,0}

    7

    Returns: 406209421

  35. {-1,-1,0,1,1,1,0,-1,4}

    {0,-1,-1,0,1,2,2,1,0}

    7

    Returns: 1748808595

  36. {-1,-1,0,1,1,0,2,3,2,3,-2,-3,-2,-3,0,0,0,0,0}

    {0,-1,-1,0,1,1,2,3,0,0,-2,-3,0,0,2,3,-2,-3,0}

    7

    Returns: 1628846618

  37. {0,1,2,2,1,0,-1,-2,-2,-1,0}

    {6,6,6,5,4,3,3,3,4,5,0}

    7

    Returns: 360188106

  38. {0}

    {0}

    6

    Returns: 406209421

  39. {0,0,1,2,3,4,5,5,5,5,5,5,4,3,2,1,0,-1,-2,-3,-4,-5,-5,-5,-5,-5,-5,-4,-3,-2,-1}

    {0,5,5,5,5,5,5,4,3,2,1,0,-1,-2,-3,-4,-5,-5,-5,-5,-5,-5,-4,-3,-2,-1,0,1,2,3,4}

    6

    Returns: 683342244

  40. {0,-1,-1,0,1,1,0}

    {0,0,-1,-1,0,1,1}

    6

    Returns: 960488277

  41. {0,-1,-1,0,1,1,0,-1,-2,-2,-2,-1,0,1,2,2,2,1,0}

    {0,0,-1,-1,0,1,1,1,0,-1,-2,-2,-2,-1,0,1,2,2,2}

    6

    Returns: 1073593597

  42. {-1,-2,2,2,-1,1,4,4,-5}

    {4,-1,2,-1,-4,-4,0,4,0}

    6

    Returns: 1944139575

  43. {0,0,0,0,0,0,0,0,0,0,0}

    {2,1,0,-1,-2,-3,-4,-5,3,4,5}

    6

    Returns: 466156658

  44. {0,1,2,3,4,4,4,4,4,3,2,1,0,-1,-2,-3,-4,-4,-4,-4,-4,-3,-2,-1,0}

    {4,4,4,4,4,3,2,1,0,-1,-2,-3,-4,-4,-4,-4,-4,-3,-2,-1,0,1,2,3,0}

    5

    Returns: 78408

  45. {0}

    {0}

    5

    Returns: 683342244

  46. {-1,-1,0,1,2,2,2,1,0,-1,-2}

    {2,1,1,1,1,0,-1,-2,-3,-3,-3}

    5

    Returns: 130410

  47. {2,1,0,-1,-2,-2,-1,0,1,2,2,1,0,-1,-2}

    {3,3,3,2,1,0,0,0,0,0,-1,-2,-3,-3,-3}

    5

    Returns: 2552

  48. {4,3,2,2,1}

    {4,3,2,1,2}

    5

    Returns: 26385328

  49. {0,0,4,4,0,-4,-4}

    {0,4,4,0,-4,-4,0}

    5

    Returns: 25885744

  50. {1,1,-1,-1,-1,1,1,-1,0}

    {4,3,3,2,1,2,1,0,-1}

    5

    Returns: 631496

  51. {-7}

    {-7}

    8

    Returns: 317493966

  52. {-2,1,1,-2,3,3,-2,-3,1,1,-1,1,3,-1,-3,0,0,0,0,3,1,-2,-3,-3,2,-1,2,-1,0,0,-2,-1,2,2,2,-1,0}

    {1,0,-2,-3,2,0,0,-2,2,1,2,3,1,-2,-1,-1,0,3,1,3,-1,-1,0,-3,1,1,-1,-3,-2,-3,-2,0,2,3,0,-1,2}

    4

    Returns: 1

  53. {0,2,-2,1,0,-1,2,-2,1,1,0,-1,-2,2,1,0,0,-1,-1}

    {2,0,-1,1,0,-2,2,0,-1,0,1,-1,-2,1,2,-1,-2,0,1}

    3

    Returns: 1

  54. {0}

    {0}

    1

    Returns: 1

  55. {0,1,0,0,1,-1,-1}

    {0,0,-1,1,1,0,-1}

    2

    Returns: 1

    Here the entire battlefield is occupied by Petr's heroes. Therefore there exists only one possible arrangement.

  56. {-4, 6, 3, 4, 2 }

    {-4, 6, 3, 4, 2 }

    8

    Returns: 1520429571

  57. {-1, 0, 0, 1, 2 }

    {0, 0, 1, 0, 0 }

    5

    Returns: 29452464

  58. {0 }

    {0 }

    8

    Returns: 1931935224

  59. {7 }

    {7 }

    8

    Returns: 317493966

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: