Statistics

Problem Statement for "PaperScraps"

Problem Statement

You have two cutout pieces of paper, each of which may have one or more sections missing. You wish to arrange those two pieces, possibly overlapping, to cover the largest possible rectangular area. Each of the pieces may be rotated (in 90 degree increments), or flipped over.

You are given String[]s paper1 and paper2, where each character of each element is a '.' or an uppercase 'X' indicating whether or not the paper has a hole at that location, respectively.

Return the area of the largest rectangular region you can cover using the two pieces of paper.

Definition

Class:
PaperScraps
Method:
biggestRectangle
Parameters:
String[], String[]
Returns:
int
Method signature:
int biggestRectangle(String[] paper1, String[] paper2)
(be sure your method is public)

Constraints

  • paper1 will contain between 1 and 5 elements, inclusive.
  • Each element of paper1 will contain between 1 and 5 characters, inclusive.
  • Each element of paper1 will contain the same number of characters.
  • Each character of each element of paper1 will be uppercase 'X' or '.'.
  • paper2 will contain between 1 and 5 elements, inclusive.
  • Each element of paper2 will contain between 1 and 5 characters, inclusive.
  • Each element of paper2 will contain the same number of characters.
  • Each character of each element of paper2 will be uppercase 'X' or '.'.

Examples

  1. {"X"}

    {"X"}

    Returns: 2

    Put the two pieces of paper next to each other to make a 2x1 rectangle.

  2. {"XX"}

    {"X", "X"}

    Returns: 4

    Rotate one of the two papers, and then put them together to make a 2x2, or a 4x1 rectangle.

  3. {"XXX", ".X."}

    {"XX"}

    Returns: 5

    We can arrange the papers to get a 2x2: XXX XXX YX. .X. Y.. .Y. .Y. ...but even better is to get a 5x1 like this: XXXYY .X.

  4. {"XXX", "X.X", "XXX"}

    {"XX", "X."}

    Returns: 9

    We can use the second piece to cover the hole in the first, and make a 3x3 rectangle. Note that the overlap is permitted.

  5. {"XXXXX", "XXXX.", "XXX..", "XX...", "X...."}

    {"XXXXX", "XXXX.", "XXX..", "XX...", "X...."}

    Returns: 30

  6. {".XX.X","XXX.X","XX.XX","X.X..","....X"}

    {"X.XXX","....X","X..X.","X.XX.",".XX.X"}

    Returns: 15

  7. {"XX.X.","X..XX","XXXX.","X..X.","...XX"}

    {"XXXX.","XXXXX","XXXX.","..XXX",".XX.X"}

    Returns: 24

  8. {"XXXXX","XX...","X....","XX.XX","XX.X."}

    {"XXXX.","XXX.X","XXX..",".X.X.","..XXX"}

    Returns: 20

  9. {"..XX.",".X.XX",".XXXX",".XXX.",".XXX."}

    {".XXX.","XX.X.","..XX.",".X.XX",".X.XX"}

    Returns: 20

  10. {"..X.X","..X..","XXXXX",".XXXX",".X.XX"}

    {".XXX.","...XX","X.X.X","X.XXX","X.XXX"}

    Returns: 20

  11. {".X..X","X..X.","XX...",".XX..","..X.X"}

    {"X..X.","..X.X","...XX","XX.X.","..XXX"}

    Returns: 10

  12. {"XX.XX","X....","XXX..","..X.X",".X..X"}

    {"..XXX","XXX..","XX.XX",".XXXX","X.XXX"}

    Returns: 15

  13. {"...XX",".X..X","X.XX.","X.XXX",".X..X"}

    {"XXXXX","X...X","XXXX.",".X...","...XX"}

    Returns: 15

  14. {"XX..X","..XX.","X.XXX","XX.XX","...XX"}

    {"XX...",".X...","X..XX",".X.XX","..XXX"}

    Returns: 15

  15. {".X.X.","...XX","..X.X","X....","XXXXX"}

    {"XXX..","..XX.","...XX",".XXX.","...XX"}

    Returns: 15

  16. {".X.XX","..X.X","XX..X",".XXX.","XXXXX"}

    {"X..XX",".XXX.",".X.X.",".X.X.",".X..X"}

    Returns: 16

  17. {".XXX.","XXXXX","X..XX","X.XX.",".XXX."}

    {".XX.X","XXXX.","...XX","X.XX.","..X.X"}

    Returns: 20

  18. {".X.XX","XXX.X","X..XX","..XXX","XXX.X"}

    {"X..X.","XX.XX",".X.XX","X..XX","X.XX."}

    Returns: 16

  19. {"XX.XX",".X..X",".XX..","XXX.X","X..X."}

    {"XXX.X","XXXX.",".XX..","X.XXX","X.X.X"}

    Returns: 18

  20. {"XXXXX","XX.X.","XXXX.","XX.X.","....."}

    {".X...",".X.XX","....X","XX.XX","XX.XX"}

    Returns: 20

  21. {"..X.X","X.XXX",".....","XXXXX","XX..X"}

    {"X.XX.","X.XX.",".X.X.","XX.XX","..XXX"}

    Returns: 16

  22. {"..XXX",".XXX.","XXX.X","XXX..","XXX.."}

    {"..XX.",".X.X.","XX.XX",".XX.X",".X.XX"}

    Returns: 16

  23. {"XXX.X","X..XX","X.XX.",".XXXX","..X.."}

    {"X.XXX","..X..",".XX.X","..XXX","XXX.X"}

    Returns: 16

  24. {"XX..X","X....",".XXXX","X.XXX",".XX.."}

    {".XXX.","X...X","X.XX.",".XXXX","XXXX."}

    Returns: 20

  25. {"X.XXX","XXX.X","..XXX",".XXXX",".XX.X"}

    {"...XX","XXX.X","XXXX.","X.X.X","..X.."}

    Returns: 20

  26. {"XX.XX","..X..","XXXXX","XXX.X","X..XX"}

    {"XXX..",".X..X","XXX.X","...XX",".X.X."}

    Returns: 16

  27. {"XXX.X","XX.X.",".X.XX",".X.XX",".X.XX"}

    {"X.X.X",".X..X","X.XX.",".....","XX.XX"}

    Returns: 15

  28. {"XXXXX","X.XX.","...XX","XX..X","XXX.X"}

    {".X.X.","XXXXX",".XXX.","X.XX.","....."}

    Returns: 20

  29. {"XX..X","...XX",".X..X","X.XXX","X.X.X"}

    {"XXX..",".....","XXXXX","XXXXX","....X"}

    Returns: 16

  30. {"XX.X.","X....",".X.XX",".X..X","XXX.X"}

    {"X.X.X","XXXXX","XXXX.",".XXX.","X...X"}

    Returns: 18

  31. {".XXXX","...XX","XX..X","X.X..","...XX"}

    {"..X..","..X.X","XX.X.","XXXXX","XX..X"}

    Returns: 15

  32. {"XX.XX","XXXXX","..X.X",".XXXX","XX.XX"}

    {"X...X","XX..X","XXXXX",".X.X.",".XX.."}

    Returns: 20

  33. {"XXXX.","X....","X.X.X","..X..","..XXX"}

    {"XXXXX","XX.X.","..X.X",".XXX.","..XX."}

    Returns: 12

  34. {"X..XX",".XX..","XXXXX","XXX.X","X..XX"}

    {"XX.XX","XXX.X",".X.XX","..X.X","XXX.."}

    Returns: 18

  35. {"..XX.","XX...","XX.XX","XXXX.",".XXXX"}

    {"XX...",".X...","..X..","...X.",".X..."}

    Returns: 16

  36. {"X..X.","X...X",".X.X.","XX..X","XXXXX"}

    {"XX.XX","XXX..","XX..X","X.X..","X..XX"}

    Returns: 15

  37. {"XXXXX",".XX..","X.XX.","XXXX.","XXXXX"}

    {".X.X.","XXXXX","XXXX.",".....","XX.XX"}

    Returns: 20

  38. {"X...X",".....","...XX",".XXXX","XXXX."}

    {"XXXXX","XXXXX","....X",".XX.X","XX.XX"}

    Returns: 20

  39. {".X.XX","XXX.X","XXX.X",".X..X","X.XXX"}

    {"...XX","X..XX","XXX.X",".X..X","XX.XX"}

    Returns: 20

  40. {"XX...","..X.X","XXXX.","X..XX","X..X."}

    {"XXXXX",".XX.X","...XX","X.X.X","XXX.."}

    Returns: 18

  41. {"XXXX.","XX.XX",".X.XX",".XXX.","X.XX."}

    {".XXXX","XXX..","XX..X",".X.XX",".X.XX"}

    Returns: 24

  42. {"XX.XX",".XX.X",".X..X",".XX.X","..X.X"}

    {"XX...","XX..X",".XXX.",".....",".XX.X"}

    Returns: 12

  43. {"..X.X","X.X.X","XXX..","XX.XX","....."}

    {"X.XXX",".XXX.",".X.X.","..XXX","X..XX"}

    Returns: 16

  44. {"XX.X.","X.XXX",".X.XX","XXXX.",".XX.."}

    {".X.XX","XXX..","XX.X.",".X.X.","XX..X"}

    Returns: 20

  45. {".X.X.","XXXX.",".X...","..XXX",".X.XX"}

    {"XX..X",".X.X.",".XXXX","XXXX.","X..XX"}

    Returns: 16

  46. {"XXX.X","X.XXX",".XXXX","XXX..","X..XX"}

    {"X.XXX",".XXX.","X...X","X.X.X",".XXXX"}

    Returns: 20

  47. {"XX...",".XX.X","XXXXX","X..X.","XX.X."}

    {".XXXX","XXX.X","X...X","X.X.X",".XXXX"}

    Returns: 20

  48. {"XXXX.","X.X..","X..X.",".XXXX","..X.X"}

    {".X.XX","XX.XX","XX.XX",".XX.X","X...X"}

    Returns: 20

  49. {"XXXXX","X.XX.","X.XXX","X.XXX",".XX.X"}

    {"..X..",".....","XX.XX","XX.X.","..XXX"}

    Returns: 20

  50. {"X.XXX","X.X..","XX.X.","X.X.X",".XXX."}

    {"XXXXX",".XXXX","XXXX.","X..X.","X..XX"}

    Returns: 20

  51. {"XX..X","XX.XX",".XXX.","..XXX","XX..."}

    {".X.XX","..XXX","XXXX.",".X.X.","XXX.."}

    Returns: 16

  52. {".X..X",".X.X.","X.XXX","XXXXX","XXXXX"}

    {"XXXX.","X.X..","X.XXX","XXXX.","XX..."}

    Returns: 24

  53. {"XXXXX","XXXX.","....X","XX.XX","XXX.X"}

    {".X.XX","XXXXX","XX.XX","XXXXX","XXXXX"}

    Returns: 28

  54. {"..X.X","XXXX.","XXX..","XXX..","...XX"}

    {"...X.","X..XX","X..XX","XXXX.",".X.XX"}

    Returns: 16

  55. {"XX.X.","XXXXX",".X.XX",".XXXX","XXXX."}

    {"XXXXX","XXXX.","X.XXX","XXXX.",".X.XX"}

    Returns: 25

  56. {"."}

    {"."}

    Returns: 0

  57. {"XXXXX","XXXXX","XXXXX","XXXXX","XXXXX"}

    {"XXXXX","XXXXX","XXXXX","XXXXX","XXXXX"}

    Returns: 50

  58. {"XXXXX", "XXXXX", "XXXXX", "XXXXX", "XX.X."}

    {"XXXXX", "XXXXX", "XXXXX", "XXXXX", "XXXXX"}

    Returns: 45

  59. {"XXXXX", "XXXXX", "XXX.X", "XXXX.", ".XXXX"}

    {".XXX.", "XXXX.", "XXXXX", "XXXXX", "XXXXX"}

    Returns: 35

  60. {"XX..X", ".XXXX", ".XXXX", "..XXX", "XXXXX"}

    {"XXXXX", "XXXXX", "XXXXX", "XXXXX", "XXXXX"}

    Returns: 32

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

    {"X....", "....X", ".X...", "..X..", ".X..."}

    Returns: 1

  62. {"X...X", "X..X.", ".....", "X.X..", ".X..X"}

    {".X...", ".....", ".....", "X..X.", "...XX"}

    Returns: 5

  63. {"XXX", "XX.", "XXX", "XX."}

    {"XX."}

    Returns: 10

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

    {"XXX", "XXX", "XXX", "XXX"}

    Returns: 12

  65. {"X", ".", "X"}

    {"."}

    Returns: 1

  66. {"XXX", "XX.", "XX."}

    {"X", "X", "X"}

    Returns: 9

  67. {".X.", ".XX", "XXX" }

    {"XXX", "X.X", "X.." }

    Returns: 12

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: