Statistics

Problem Statement for "Projections"

Problem Statement

This problem contains HTML superscripts and images which will not display correctly for plugin users

Consider a finite two-dimensional grid where each cell is either occupied or empty. You are given two Strings, front and right, the frontal and right projections of the grid, respectively. The ith character of front indicates whether the ith column of grid is completely empty or not ("." for empty, lowercase "x" if the column contains at least one occupied cell). The ith character of right indicates whether the ith row of grid is completely empty or not.

Return a int[] containing exactly two elements. The first element is the minimum possible number of occupied cells on the grid, and the second element is the maximum possible number of occupied cells.

Definition

Class:
Projections
Method:
count
Parameters:
String, String
Returns:
int[]
Method signature:
int[] count(String front, String right)
(be sure your method is public)

Constraints

  • front will contain between 1 and 50 elements, inclusive.
  • right will contain between 1 and 50 elements, inclusive.
  • Each character in front and right will be "." or "x".
  • Both front and right will contain at least one "x" character.

Examples

  1. "x"

    "x"

    Returns: {1, 1 }

    There is only one cell on the grid and it is obviously occupied.

  2. "x."

    ".x"

    Returns: {1, 1 }

    There is only one possible 2x2 grid with such projections (dark squares represent occupied cells):

  3. "xxxx"

    "x..x"

    Returns: {4, 8 }

    One possible assignment with the minimum possible number of cells occupied is the following: The only possible assignment with the maximum possible number of cells occupied is the following:

  4. "x.x.x.x"

    "x.x.x.x"

    Returns: {4, 16 }

  5. "x...xx..x.xxx..x.xx."

    ".xx..xxx.xx."

    Returns: {10, 70 }

  6. ".x..x.xxx.xxxxxxxxxxx......x.x."

    "x.xx..x..x...x"

    Returns: {18, 108 }

  7. ".x.xxx.xxxxx.xx.xx...xxxx.xxx...x"

    "x...x..x"

    Returns: {21, 63 }

  8. ".x.x"

    "xxx.xx...xxx.x.xxx.xx.xx.x.x.x."

    Returns: {19, 38 }

  9. ".x....x.x.x...x.x.xx.xx.x..xxx.."

    "...xx.x.x.x.x...xx.x.....xx..xx.xx.x"

    Returns: {16, 224 }

  10. ".x..x..xx..x.xx..x.xx...x.x..xx."

    "xxxxxx.xxx..x...xxxx.xxx.xxx......x...xx.x"

    Returns: {24, 336 }

  11. "xx....xx.xx..x...x..x.x.x.xxxx.xx.x..x.xx"

    ".x...xxx.xx..xxxx..x..x.xxx.."

    Returns: {21, 315 }

  12. "x."

    "..xx...xx......xxx....x....."

    Returns: {8, 8 }

  13. "..x.x..xxxx..xxxxx..xxx.xxx"

    "xxx..x..xxxxx.x..xxxxx.xxx...x.xxx.x.x.xxxx.x."

    Returns: {29, 493 }

  14. "x.x.x.x.xx.xx.xx.xxx.x.."

    ".xx..xx.x..x...x.x.xxx..x.x...xxxxx"

    Returns: {18, 252 }

  15. "...x....xx...xx...xx....xx...x"

    "xxx.x.....x."

    Returns: {10, 50 }

  16. "..x.xx...xxxx.x..xx.xxxxx.x.xx..x.xx..x.xxxx"

    "xx..x.xxx.x....x...x.xx.xx.."

    Returns: {26, 338 }

  17. ".....xx.xx."

    "x...x.xxxxxxx..xx.x..x.xxxxxxxx...xx."

    Returns: {23, 92 }

  18. ".x.x.x.xxx.xx...x...x.x..xx."

    ".x....x.xx..xxx.x...x.x.."

    Returns: {13, 130 }

  19. "xx"

    "..x.x.x.xxx.xx...xx.x."

    Returns: {11, 22 }

  20. "..xx.x..x.....x.xxxxx"

    "....xx.x.x..x.xx.x.x.xx..x.xx.xx...xx..x.....x.."

    Returns: {20, 200 }

  21. "xx.....x."

    "x.x..xxxx.....x..x.x"

    Returns: {9, 27 }

  22. ".x..x.xx.x...x.x....x.x..x...xx"

    "x.....x"

    Returns: {12, 24 }

  23. "x."

    "xxxxxx.x.xxxxxxxxx"

    Returns: {16, 16 }

  24. ".x.x.x...xxxxxx...xx.x..xxxxx.xxxxx...xx.x.xx"

    "....xx.xxx.x.xx..xx......"

    Returns: {27, 270 }

  25. "..x..xxx.xx.x..x.x"

    "x.....x..xxx...."

    Returns: {9, 45 }

  26. "xxx...xxx..xx.x....xx."

    "..xx...x.xxx.x."

    Returns: {11, 77 }

  27. ".xxxxx..x..xx..."

    "xxx.....x..xx.x........xx....x.x.x."

    Returns: {12, 96 }

  28. "xx.x.....x.xxxxx...x.....xx"

    ".xxx..x.xx.."

    Returns: {12, 72 }

  29. "x."

    "xxxxxxxxxxx...x....xx..x..x.xx.x.x.x.xxxx...."

    Returns: {25, 25 }

  30. "..xxxx...x..x.x...xx..xx...x"

    ".xxx.xxxx.x..x.x.x.xx......xx...xx...xx...x.xx"

    Returns: {22, 264 }

  31. ".xx...xx.xxxx.....xx....x.x.x....xxx.....x..x."

    ".x.x..xxx.xx..x..xxx..xxx"

    Returns: {18, 252 }

  32. "xx.xx.x..x..xxx..x.xxx...xx....x.x...x.xx...x.."

    "..x....xxxx.xxxxxx.x.x.xx...xxxxxx.xx....x.x..x.x"

    Returns: {27, 567 }

  33. "...xxx.....x.x.xxx..xx.xxxxx.xxx."

    ".....x.xxxxxx....x"

    Returns: {18, 144 }

  34. "...xxx..x.xx..xxx....x.x."

    ".xxx."

    Returns: {11, 33 }

  35. "x.x.x.xxxxx"

    ".......xxxxxxx"

    Returns: {8, 56 }

  36. "x"

    "xx"

    Returns: {2, 2 }

  37. "x...xx..x.xxx..x.xx."

    ".xx..xxx.xx."

    Returns: {10, 70 }

  38. "x...xx..x.xxx..x.xx."

    ".xx..xxx.xx.xxx"

    Returns: {10, 100 }

  39. "xx"

    "xxx"

    Returns: {3, 6 }

  40. "x.x.x.x"

    "x.x.xxx"

    Returns: {5, 20 }

  41. ".xx..xxx.xx."

    "x...xx..x.xxx..x.xx."

    Returns: {10, 70 }

  42. ".x."

    "xxxx.xx.x...x.xx..xx"

    Returns: {12, 12 }

  43. "x"

    "x"

    Returns: {1, 1 }

  44. ".x."

    ".x..x..x"

    Returns: {3, 3 }

  45. ".xx..xxx.xx..xx..xxx.xx..xx..xxx.xx."

    "x...xx..x.xxx..x.xx..xx..xxx.xx."

    Returns: {21, 357 }

  46. "xx.."

    "xxxx"

    Returns: {4, 8 }

  47. "xx"

    "..xx"

    Returns: {2, 4 }

  48. "xx..."

    "xxxxx"

    Returns: {5, 10 }

  49. ".xx..xxx.xx..xx..xxx.xx..xx..xxx.xx."

    "x...xx..x.xxx..x.xx..xx..xxx.xx.xxxxxx"

    Returns: {23, 483 }

  50. "x."

    "xxxx.."

    Returns: {4, 4 }

  51. "x.x"

    "xxx"

    Returns: {3, 6 }

  52. "xx"

    "x.x.x"

    Returns: {3, 6 }

  53. ".x"

    "xxx"

    Returns: {3, 3 }

  54. "x.x.x.x"

    "x.x.x.x.x"

    Returns: {5, 20 }

  55. "x.."

    "xxx"

    Returns: {3, 3 }

  56. "x"

    ".x"

    Returns: {1, 1 }

  57. "..x."

    ".xxx"

    Returns: {3, 3 }

  58. "...x.x.xxx"

    "x.xxx.x.x.x"

    Returns: {7, 35 }

  59. ".xx.xx.xx"

    "x...xx..x.xxx..x.xx."

    Returns: {10, 60 }

  60. "x."

    "xx"

    Returns: {2, 2 }

  61. "x..x"

    "xxxx"

    Returns: {4, 8 }

  62. "x."

    ".xxxxxxx"

    Returns: {7, 7 }

  63. "x"

    "xxxxxxxxx"

    Returns: {9, 9 }

  64. "x.."

    ".xx"

    Returns: {2, 2 }

  65. "xx."

    "xxxxxxxxxxxxxxxxxxxxxxxxxxx.x"

    Returns: {28, 56 }

  66. ".x.....x.x...x.....x..x.xx...xxx..x...x....x.x..xx"

    "x.xxxxxxxxxxxxxx.xxxxxxxxxx.xxxxxxxxxxxxx.xxxx.xxx"

    Returns: {45, 765 }

  67. "xxxxx.x.....xx.x.x..x..x....xx..."

    "...xx.x.x.x..x.....xx......x...x......xx"

    Returns: {14, 168 }

  68. "x"

    "x.x.x.x"

    Returns: {4, 4 }

  69. "x...xx.."

    ".xx..xxx.xx."

    Returns: {7, 21 }

  70. "xx..xx..xx..xx..xx..xx..xxxx...."

    ".......xx....xxx..."

    Returns: {16, 80 }

  71. "x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x."

    ".x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x"

    Returns: {25, 625 }

  72. "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx."

    ".x"

    Returns: {47, 47 }

  73. "x."

    "xxxxxx"

    Returns: {6, 6 }

  74. "xx"

    "..xxx"

    Returns: {3, 6 }

  75. "x"

    ".xxx"

    Returns: {3, 3 }

  76. "x"

    "xxxxxx"

    Returns: {6, 6 }

  77. ".x..."

    ".xx.x"

    Returns: {3, 3 }

  78. ".x"

    "xx"

    Returns: {2, 2 }

  79. ".xx."

    "xxxx"

    Returns: {4, 8 }

  80. "x"

    "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"

    Returns: {50, 50 }

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: