Statistics

Problem Statement for "ChristmasTwins"

Problem Statement

Christmas is hard when you have twins. You have to buy all presents twice, and divide everything evenly. Problems arise when your cooking skills aren't up to par and one of your cakes ends up having a weird shape. How shall you divide it?

The cake is a rectangular bitmap: the cells marked '#' form the cake, all other cells are marked '.' and represent empty space.

The cake must be divided into two geometrically equivalent parts. (I.e., you must be able to transform one part into the other by applying translations, rotations and mirror images.) Each cell must completely belong into one of the two parts. Each part must hold together.

Count the number of ways in which this can be done. (Two ways of cutting are different if the unordered pairs of sets of cells differ.)

Definition

Class:
ChristmasTwins
Method:
countCuts
Parameters:
String[]
Returns:
long
Method signature:
long countCuts(String[] bitmap)
(be sure your method is public)

Constraints

  • bitmap will be a rectangle.
  • bitmap will contain at most 50 characters.
  • Each character in bitmap will be '#' or '.'.
  • bitmap will contain between 1 and 42 '#' characters.

Examples

  1. {".####", "#####", "###.."}

    Returns: 1

    The only valid way to cut this cake: .1122 11222 112..

  2. {"###", "###"}

    Returns: 3

    Solutions: 111 222 112 122 122 112

  3. {"#####", "#.#..", ".....", "..#.#", "#####"}

    Returns: 1

  4. {"#####", "#.#..", ".....", "..###", "#####"}

    Returns: 0

  5. {"###", ".#.", ".#.", ".#."}

    Returns: 1

  6. {"####", "####", "####", "####"}

    Returns: 22

    Some of the solutions: 1111 1111 2222 2222 1111 1121 2122 2222 1111 1222 1112 2222 1112 1112 1222 1222 1122 1122 1122 1122

  7. {"#.#.#.#"}

    Returns: 0

  8. {"########", "########", "########", "########", "########"}

    Returns: 1675

  9. {"#######", "#######", "#######", "#######", "#######", "#######"}

    Returns: 2947

  10. {"##########", "##########", "##########", "##########"}

    Returns: 1228

  11. {"##############", "##############", "##############"}

    Returns: 495

  12. {"#####################", "#####################"}

    Returns: 21

  13. {"##########################################"}

    Returns: 1

  14. {".#####", "######", "######", "####.."}

    Returns: 0

  15. {"#"}

    Returns: 0

  16. {"##"}

    Returns: 1

  17. {"#","#"}

    Returns: 1

  18. {"#####","#####","#####","#####","####."}

    Returns: 0

  19. {".####.", "######", "######", "######", "######", ".####."}

    Returns: 318

  20. {".##....", ".#####.", ".######", ".######", "..###.."}

    Returns: 1

  21. {".######", "#######", "#######", "#######", "#####.."}

    Returns: 1

    .112222 1122222 1121122 1111222 11112..

  22. {".#####.", "#######", "#######", "##...##", "#######", "#######", ".#####." }

    Returns: 688

  23. {"##.##########.##", "#####.####.#####", "##.##########.##"}

    Returns: 55

  24. {"###########.####", ".##.####.#..####", "################"}

    Returns: 0

  25. {"####..#############..####", "#######.###.#.###.#######"}

    Returns: 0

  26. {"########.#.###.###.############.###.###.#.########"}

    Returns: 0

  27. {"##.##", "#####", "##.##", "#####", "#####", ".#.#.", "##.##", "#####", "#.#.#", "#####"}

    Returns: 0

  28. {"######.##.######", "#####.####.#####", "######.##.######"}

    Returns: 0

  29. {"#######", "##.#.##", "#######", "#######", "#######", "##.#.##", "##...##"}

    Returns: 0

  30. {"############", ".##########.", "#.##.##.##.#", "############"}

    Returns: 1

  31. {"###", ".##", ".##", "###", "##.", "##.", "###", "###", "###", "###", "#.#", ".##", "###", "###", "###", "###"}

    Returns: 0

  32. {"##########", "##.####.##", "#..####..#", "####..####", "##########"}

    Returns: 1

  33. {"###.", "####", "####", "####", "####", "###.", "##..", "####", "###.", "###.", "####", "####"}

    Returns: 0

  34. {".####.", "######", "######", "#.##.#", "######", "######", "######", "##..##"}

    Returns: 1

  35. {"#", "#", ".", "#", "#", "#", "#", "#", "#", "#", ".", ".", "#", "#", ".", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", ".", "#", "#", "#", "#", "#", "#", ".", "#", "#", "#", ".", "#", ".", "#"}

    Returns: 0

  36. {"##.#.", "#####", "#####", ".####", "##.##", "##.##", ".####", "#####", "#####", "##.#."}

    Returns: 1

  37. {"###########.", "##.#####.###", "##.#####.###", "###########."}

    Returns: 1

  38. {"###.##.#####", "#########.##", "##.######.##", "#.##########"}

    Returns: 0

  39. {"########", "##.##.##", "###..###", "###..###", "##.##.##", "########"}

    Returns: 56

  40. {"#########.###.#####.#.######.#.#####.###.#########"}

    Returns: 0

  41. {"######.##.######", "#.############.#", "######.##.######"}

    Returns: 3

  42. {"#.##########.##.", "##.####.########", "#########.######"}

    Returns: 0

  43. {"#.#", "#.#", "###", "###", "###", "#.#", "###", "#.#", "###", "###", "#.#", "###", "###", "#.#", "###", "###"}

    Returns: 0

  44. {"#######.#########.###.####.#..#########..#########"}

    Returns: 0

  45. {"#.####", ".#####", "######", "#.####", "#.####", "######", ".#####", "#.####"}

    Returns: 0

  46. {"##", "##", "..", "##", "##", "##", "##", "##", "..", "##", "##", "##", "##", "##", "##", "##", "..", "##", "##", "##", "##", "##", "..", "##", "##"}

    Returns: 0

  47. {"#######", "###.###", "#.###.#", "#######", "###.###", "#######", "##...##"}

    Returns: 0

  48. {"######", "######", "######", "######", "..##..", "######", "######", "##..##"}

    Returns: 1

  49. {".#.#.", "#####", ".#.#.", "#####", "#####", "#.#.#", "#####", "#####", "#####", "#####"}

    Returns: 0

  50. {"####.##", "######.", "#######", ".##.##.", "#######", "######.", "####.##"}

    Returns: 0

  51. {".########.", "##########", "##..##..##", "##########", ".########."}

    Returns: 269

  52. {"##.####.##", "##########", "####..####", "#.#.##.#.#", "##########"}

    Returns: 1

  53. {"###.########.###", "#.############.#", "######.##.######"}

    Returns: 1

  54. {"######", "####.#", ".#####", "##.#..", "####.#", "######", "######", "######"}

    Returns: 0

  55. {"###.###", "#######", "##.#.##", "###.###", "###.###", "##.#.##", "#######"}

    Returns: 0

  56. {"###.###.########.#####.####.#####.########.###.###"}

    Returns: 0

  57. {"############.#####.##.##..##.##.#####.############"}

    Returns: 0

  58. {"..", "..", "##", "##", "##", "##", "##", "##", "##", "##", "##", "##", "##", "##", "##", "##", "##", "##", "##", "##", "##", "##", "##", "..", ".."}

    Returns: 21

  59. {"######..##.#####.########", ".######.#####.#####.#####"}

    Returns: 0

  60. {"#######...########.####.#.##.#.###################"}

    Returns: 0

  61. {"#", "#", "#", "#", "#", "#", "#", "#", ".", "#", "#", "#", "#", "#", ".", "#", "#", ".", "#", "#", "#", "#", "#", "#", ".", ".", "#", "#", "#", "#", "#", "#", ".", "#", "#", ".", "#", "#", "#", "#", "#", ".", "#", "#", "#", "#", "#", "#", "#", "#"}

    Returns: 0

  62. {"################", ".###.##..##.###.", "################"}

    Returns: 113

  63. {"###.####.#######..##############..#######.####.###"}

    Returns: 0

  64. {"###", "###", "###", "###", "###", "###", "###", "###", "##.", "###", "###", "###", "..#", "#.#", "#.#", ".##"}

    Returns: 0

  65. {"#.####.#", "########", "########", "###..###", "########", ".######."}

    Returns: 1

  66. {"#####", "##.##", "#####", "##.##", "#.#.#", "#.#.#", "##.##", "#####", "##.##", "#####"}

    Returns: 0

  67. {"####.#.###", "##########", "#.#.#.##.#", "##########", "####.#.###"}

    Returns: 0

  68. {"####.######.####", "#####..##..#####", "################"}

    Returns: 1

  69. {"######.###########.##.##.####.########.##.###.####"}

    Returns: 0

  70. {"####.##.##.#.########################.#.##.##.####"}

    Returns: 0

  71. {"###.######.###.######.###", "###.######.###.######.###"}

    Returns: 0

  72. {"####.##########.#####.###", "##.############....######"}

    Returns: 0

  73. {"..###..", "#######", "#######", "###.###", "#######", "#######", "..###.."}

    Returns: 734

  74. {".......", "#######", "#######", "#######", "#######", "#######", "#######"}

    Returns: 2947

  75. {"..####..", "########", "########", "########", "########", ".######."}

    Returns: 1

  76. {".######.", "########", "####.###", "###.####", "########", ".######."}

    Returns: 682

  77. {"####", "####", "####", "####" }

    Returns: 22

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: