Statistics

Problem Statement for "FoxAndPhotography"

Problem Statement

Fox Ciel is attending a party. During the party, people decided to take a commemorative photograph. Ciel picked up a camera to take a photograph. In the party, there are 2*N people (not including Ciel).

For taking the photograph, people formed two rows, each containing N people. In each row, Ciel numbered the people from 0 to N-1 from left to right. The people were aligned so that for each i, person i in the back row was standing exactly behind person i in the front row.

Initially, the people lined up arbitrarily. Therefore it is possible that some of the people in the back row are obscured by people in the front row. You are given two int[]s: heightsFront and heightsBack. For each i, heightsFront[i] is the height of person i in the front row and heightsBack[i] is the height of person i in the back row. The person in the back row is obscured by the person in the front row if and only if heightsFront[i] >= heightsBack[i].

If there are some obscured people, Ciel wants to fix it. The only operation she may do is to select two adjacent people in the same row and swap them. Compute and return the smallest number of such operations necessary to rearrange the people so that nobody in the back row is obscured. If no such sequence of operations exists, return -1.

Definition

Class:
FoxAndPhotography
Method:
getMinimumSwaps
Parameters:
int[], int[]
Returns:
int
Method signature:
int getMinimumSwaps(int[] heightsFront, int[] heightsBack)
(be sure your method is public)

Constraints

  • heightsFront will contain between 2 and 16 elements, inclusive.
  • heightsBack will contain the same number of elements with heightForward.
  • Each element of heightsFront and heightsBack will be between 140 and 190, inclusive.

Examples

  1. {140, 150}

    {160, 150}

    Returns: 1

    Initially, person 1 (0-based index) in the back row is obscured. One optimal solution is to swap people 0 and 1 in the front row. Another optimal solution is to swap people 0 and 1 in the back row.

  2. {140, 140, 140, 140}

    {190, 190, 190, 190}

    Returns: 0

    Nobody is obscured, so no swaps are needed.

  3. {170, 170, 170}

    {160, 170, 180}

    Returns: -1

    Person 0 in the back row is too short. Regardless of how we swap the people, this person will always be obscured.

  4. {140, 141, 142, 143}

    {144, 143, 142, 141}

    Returns: 6

  5. {140, 170, 140, 170, 140, 170, 140, 170, 140, 170}

    {180, 180, 180, 180, 180, 150, 150, 150, 150, 150}

    Returns: 15

  6. {160, 160}

    {160, 160}

    Returns: -1

  7. {160, 160}

    {161, 161}

    Returns: 0

  8. {161, 161}

    {160, 160}

    Returns: -1

  9. {140, 161}

    {141, 160}

    Returns: -1

  10. {161, 140}

    {160, 141}

    Returns: -1

  11. {140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155}

    {156,155,154,153,152,151,150,149,148,147,146,145,144,143,142,141}

    Returns: 120

  12. {140,141,143,144,145,146,142,147,148,149,150,151,155,152,153,154}

    {156,154,153,152,151,150,143,149,148,147,146,145,144,142,155,141}

    Returns: 102

  13. {140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155}

    {156,155,154,153,151,150,149,148,147,146,152,145,144,143,142,141}

    Returns: 114

  14. {140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155}

    {155,154,153,156,152,151,150,149,148,147,146,145,144,142,143,141}

    Returns: 116

  15. {140,140,141,141,142,142,143,143,144,144,145,145,146,146,147,147}

    {148,148,147,147,146,146,145,145,144,144,143,143,142,142,141,141}

    Returns: 112

  16. {140,140,140,140,140,140,140,140,180,180,180,180,180,180,180,180}

    {181,181,181,181,181,181,181,181,141,141,141,141,141,141,141,141}

    Returns: 64

  17. {140,140,140,140,140,140,140,140,140,140,140,140,140,140,140,180}

    {181,141,141,141,141,141,141,141,141,141,141,141,141,141,141,141}

    Returns: 15

  18. {190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190}

    {190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190}

    Returns: -1

  19. {190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190, 190}

    {140, 140, 140, 140, 140, 140, 140, 140, 140, 140, 140, 140, 140, 140, 140, 140}

    Returns: -1

  20. {140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155}

    {156,155,154,153,152,150,150,149,148,147,146,145,144,143,142,141}

    Returns: -1

  21. {140,141,142,143,144,146,146,147,148,149,150,151,152,153,154,155}

    {156,155,154,153,152,151,150,149,148,147,146,145,144,143,142,141}

    Returns: -1

  22. {158, 164, 149, 165, 150}

    {154, 166, 187, 160, 189}

    Returns: 3

  23. {190, 158, 167, 171, 187, 186, 142}

    {184, 160, 149, 162, 186, 143, 179}

    Returns: -1

  24. {186, 152, 174, 162, 179, 158, 157, 183, 175}

    {178, 146, 144, 176, 168, 167, 184, 140, 149}

    Returns: -1

  25. {142, 168, 141, 181, 186, 175, 147, 178, 146, 183, 160}

    {140, 176, 185, 164, 165, 165, 173, 146, 146, 148, 143}

    Returns: -1

  26. {159, 190, 158, 152, 173, 146, 156, 176, 143, 162, 181, 186, 151}

    {143, 190, 156, 182, 177, 158, 177, 161, 189, 169, 156, 177, 157}

    Returns: -1

  27. {140, 151, 162, 177, 149, 152, 141, 168, 177, 150, 171, 185, 152, 176, 176, 171}

    {152, 182, 175, 161, 146, 180, 176, 164, 182, 164, 147, 143, 158, 153, 157, 150}

    Returns: -1

  28. {175, 148, 144, 172, 186, 175, 142, 146, 169, 154, 184, 146, 160, 170, 161, 154}

    {157, 171, 181, 152, 143, 164, 167, 187, 175, 147, 158, 186, 173, 143, 164, 189}

    Returns: -1

  29. {177, 148, 161, 179, 168, 159, 147, 165, 169, 182, 161, 162, 142, 183, 174, 157}

    {178, 157, 173, 155, 183, 188, 184, 187, 154, 175, 185, 151, 165, 141, 163, 187}

    Returns: -1

  30. {161, 152, 189, 140, 171, 163, 188, 146, 155, 174, 149, 185, 155, 173, 182, 165}

    {175, 185, 170, 146, 184, 147, 172, 150, 168, 141, 175, 149, 166, 189, 173, 182}

    Returns: -1

  31. {145, 146, 140, 164, 179, 141, 157, 142, 159, 170, 174, 175, 169, 164, 153, 165}

    {169, 140, 185, 141, 190, 178, 147, 170, 160, 146, 189, 174, 148, 167, 165, 155}

    Returns: -1

  32. {140, 148, 144, 142, 146}

    {143, 145, 141, 149, 147}

    Returns: 5

  33. {150, 144, 152, 140, 142, 148, 146}

    {149, 145, 143, 147, 151, 141, 153}

    Returns: 13

  34. {156, 140, 142, 144, 154, 146, 152, 148, 150}

    {145, 149, 147, 143, 151, 157, 141, 153, 155}

    Returns: 20

  35. {160, 152, 148, 156, 158, 154, 142, 144, 150, 146, 140}

    {147, 141, 159, 155, 149, 157, 153, 161, 143, 145, 151}

    Returns: 31

  36. {140, 164, 162, 150, 146, 144, 160, 156, 152, 148, 158, 142, 154}

    {161, 147, 145, 149, 141, 163, 151, 157, 159, 165, 153, 155, 143}

    Returns: 26

  37. {160, 166, 148, 170, 164, 168, 142, 156, 146, 162, 158, 154, 150, 144, 152, 140}

    {141, 143, 153, 157, 145, 149, 163, 167, 161, 159, 165, 147, 169, 151, 155, 171}

    Returns: 71

  38. {160, 164, 148, 144, 140, 168, 154, 156, 150, 152, 142, 146, 170, 162, 166, 158}

    {157, 159, 143, 147, 155, 167, 153, 163, 151, 161, 141, 149, 145, 169, 171, 165}

    Returns: 83

  39. {152, 150, 154, 146, 162, 142, 140, 170, 148, 168, 144, 160, 156, 158, 166, 164}

    {145, 141, 151, 161, 171, 149, 155, 153, 143, 159, 165, 147, 157, 169, 167, 163}

    Returns: 51

  40. {166, 158, 154, 160, 146, 140, 148, 142, 152, 150, 156, 170, 144, 168, 164, 162}

    {169, 161, 143, 167, 155, 159, 149, 145, 163, 165, 171, 141, 153, 157, 147, 151}

    Returns: 53

  41. {152, 156, 168, 140, 166, 154, 150, 164, 170, 142, 148, 158, 162, 146, 160, 144}

    {163, 161, 171, 157, 143, 149, 151, 165, 167, 159, 169, 153, 145, 147, 155, 141}

    Returns: 72

  42. {151, 150}

    {153, 152}

    Returns: 0

  43. {153, 151, 150}

    {152, 154, 155}

    Returns: 1

  44. {151, 152, 150, 152}

    {153, 153, 151, 154}

    Returns: 0

  45. {151, 150, 150, 152, 155}

    {156, 158, 157, 153, 154}

    Returns: 2

  46. {150, 153, 151, 157, 155, 154}

    {156, 159, 154, 158, 152, 160}

    Returns: 3

  47. {151, 155, 156, 150, 152, 157, 153}

    {163, 161, 162, 154, 159, 160, 158}

    Returns: 0

  48. {152, 155, 151, 161, 154, 153, 156, 150}

    {155, 162, 158, 163, 159, 160, 157, 159}

    Returns: 0

  49. {155, 150, 153, 151, 159, 157, 156, 152, 151}

    {158, 163, 162, 153, 159, 164, 154, 161, 160}

    Returns: 2

  50. {154, 156, 155, 165, 158, 150, 160, 151, 153, 152}

    {164, 168, 161, 163, 162, 166, 159, 169, 167, 157}

    Returns: 3

  51. {164, 153, 158, 156, 155, 165, 157, 154, 162, 150, 151}

    {170, 168, 166, 170, 159, 160, 167, 163, 161, 152, 169}

    Returns: 2

  52. {156, 153, 169, 150, 157, 166, 179, 151, 152, 160, 154, 170, 159, 162, 155, 158}

    {176, 173, 180, 167, 175, 161, 174, 177, 181, 163, 165, 171, 164, 172, 178, 168}

    Returns: 3

  53. {165, 161, 160, 174, 159, 152, 158, 156, 163, 171, 170, 153, 150, 155, 151, 154}

    {176, 178, 164, 166, 181, 162, 167, 179, 169, 157, 173, 172, 180, 177, 168, 175}

    Returns: 3

  54. {163, 172, 162, 155, 158, 152, 154, 157, 156, 169, 159, 161, 150, 160, 151, 153}

    {177, 173, 175, 178, 166, 180, 181, 176, 171, 170, 164, 179, 174, 167, 168, 165}

    Returns: 0

  55. {167, 157, 166, 152, 162, 171, 150, 170, 155, 151, 153, 174, 179, 156, 159, 154}

    {172, 164, 177, 180, 176, 160, 173, 158, 175, 163, 168, 169, 178, 165, 181, 161}

    Returns: 5

  56. {161, 166, 154, 171, 157, 151, 164, 155, 176, 159, 160, 168, 153, 156, 167, 150}

    {172, 177, 175, 170, 180, 162, 178, 173, 152, 179, 163, 181, 165, 174, 158, 169}

    Returns: 7

  57. {158, 172, 152, 169, 150, 155, 151, 157, 162, 156, 166, 154, 161, 153, 159, 160}

    {174, 177, 167, 173, 170, 171, 168, 180, 163, 165, 164, 176, 175, 181, 179, 178}

    Returns: 1

  58. {156, 171, 159, 150, 151, 153, 162, 169, 167, 174, 160, 152, 157, 155, 154, 170}

    {163, 178, 173, 168, 161, 180, 179, 165, 164, 166, 158, 176, 181, 172, 175, 177}

    Returns: 6

  59. {151, 159, 153, 150, 161, 152, 168, 155, 163, 156, 164, 160, 162, 166, 177, 170}

    {180, 181, 169, 158, 175, 167, 173, 172, 154, 179, 178, 171, 165, 176, 157, 174}

    Returns: 12

  60. {170, 150, 157, 164, 153, 160, 154, 174, 159, 151, 163, 155, 156, 162, 168, 165}

    {175, 166, 152, 172, 181, 161, 171, 180, 176, 173, 178, 158, 177, 169, 167, 179}

    Returns: 2

  61. {169, 150, 162, 152, 154, 156, 159, 157, 161, 151, 176, 164, 167, 165, 171, 153}

    {163, 178, 160, 170, 172, 168, 158, 166, 181, 175, 179, 173, 180, 155, 174, 177}

    Returns: 5

  62. {154, 153, 157, 172, 150, 155, 155, 159, 165, 158, 152, 171, 159, 156, 161, 164}

    {171, 174, 173, 166, 175, 167, 168, 163, 170, 151, 162, 160, 169, 163, 165, 167}

    Returns: 12

  63. {164, 171, 154, 161, 159, 151, 157, 153, 154, 168, 155, 154, 165, 150, 162, 152}

    {167, 174, 163, 172, 170, 151, 160, 156, 169, 166, 161, 161, 175, 158, 173, 172}

    Returns: 12

  64. {155, 160, 168, 151, 163, 154, 158, 175, 153, 168, 156, 157, 152, 164, 150, 160}

    {167, 176, 176, 172, 162, 173, 159, 165, 169, 171, 170, 170, 161, 177, 166, 174}

    Returns: 5

  65. {160, 153, 150, 158, 162, 159, 151, 154, 168, 157, 167, 165, 152, 164, 161, 155}

    {168, 174, 160, 172, 175, 173, 169, 174, 163, 171, 163, 168, 170, 166, 156, 158}

    Returns: 4

  66. {165, 160, 150, 162, 153, 159, 155, 153, 152, 162, 154, 154, 151, 158, 153, 160}

    {162, 164, 170, 169, 165, 171, 167, 168, 161, 156, 163, 170, 170, 157, 157, 166}

    Returns: 4

  67. {161, 155, 155, 157, 150, 169, 160, 155, 151, 152, 158, 166, 166, 159, 153, 156}

    {173, 164, 173, 174, 174, 170, 160, 169, 168, 165, 154, 162, 167, 172, 163, 171}

    Returns: 4

  68. {159, 164, 157, 152, 156, 153, 162, 158, 152, 150, 168, 151, 150, 152, 155, 162}

    {166, 164, 172, 161, 171, 164, 163, 165, 154, 166, 167, 170, 168, 169, 160, 152}

    Returns: 6

  69. {153, 163, 157, 164, 155, 152, 162, 150, 158, 151, 154, 155, 156, 155, 163, 154}

    {157, 153, 155, 165, 167, 159, 160, 167, 163, 159, 169, 166, 161, 164, 163, 168}

    Returns: 11

  70. {154, 155, 152, 152, 167, 150, 159, 157, 167, 158, 150, 162, 164, 151, 161, 156}

    {165, 151, 155, 166, 171, 153, 158, 168, 170, 162, 169, 171, 163, 160, 171, 169}

    Returns: 8

  71. {158, 154, 157, 151, 159, 152, 162, 153, 155, 156, 150, 160, 160, 167, 150, 161}

    {164, 162, 171, 168, 157, 163, 169, 150, 165, 172, 153, 170, 171, 159, 167, 166}

    Returns: -1

  72. {140, 170, 140, 170, 140, 170, 140, 170, 140, 170 }

    {180, 180, 180, 180, 180, 150, 150, 150, 150, 150 }

    Returns: 15

  73. {176, 145, 156, 161, 181, 167, 150, 189, 156, 150, 157, 156, 145, 163, 181, 179 }

    {177, 151, 190, 157, 162, 180, 164, 157, 182, 146, 158, 182, 151, 146, 157, 168 }

    Returns: 44

  74. {140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155 }

    {156, 155, 154, 153, 152, 151, 150, 149, 148, 147, 146, 145, 144, 143, 142, 141 }

    Returns: 120

  75. {170, 170, 170 }

    {160, 170, 180 }

    Returns: -1

  76. {188, 185, 180, 170, 160, 150, 145, 140, 188, 185, 180, 170, 160, 150, 145, 140 }

    {142, 147, 152, 162, 172, 182, 187, 190, 142, 147, 152, 162, 172, 182, 187, 190 }

    Returns: 56

  77. {140, 170, 140, 180, 140, 170, 140, 170, 140, 170 }

    {180, 180, 180, 180, 180, 150, 150, 160, 150, 150 }

    Returns: -1

  78. {148, 174, 174, 146, 171, 164, 167, 175, 185, 171, 149, 146, 170, 186, 157, 142 }

    {161, 175, 183, 149, 185, 164, 185, 188, 189, 189, 175, 177, 173, 186, 169, 180 }

    Returns: 11

  79. {140, 140, 140, 140, 140 }

    {150, 142, 160, 190, 173 }

    Returns: 0

  80. {141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156 }

    {157, 156, 155, 154, 153, 152, 151, 150, 149, 148, 147, 146, 145, 144, 143, 142 }

    Returns: 120

  81. {190, 140, 140, 140, 140, 140, 140, 140, 140, 140, 140, 140, 140, 140, 140, 140 }

    {160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160 }

    Returns: -1

  82. {143, 161, 168, 183, 160, 157, 154, 161, 150, 171, 174, 145, 153, 149, 176, 140 }

    {179, 169, 177, 155, 146, 173, 167, 165, 185, 151, 142, 165, 170, 182, 173, 170 }

    Returns: 26

  83. {150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165 }

    {160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175 }

    Returns: 0

  84. {160, 150, 140 }

    {190, 190, 190 }

    Returns: 0

  85. {140, 170, 140, 170, 140, 170, 140, 170, 140, 170 }

    {180, 180, 180, 180, 180, 150, 150, 150, 150, 190 }

    Returns: 6

  86. {181, 180, 179, 178, 177, 176, 175, 174, 173, 172, 171, 170, 169, 168, 167, 166 }

    {181, 180, 179, 178, 177, 176, 175, 174, 173, 172, 171, 170, 169, 168, 167, 182 }

    Returns: 15

  87. {143, 143, 141 }

    {142, 144, 144 }

    Returns: 2

  88. {140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155 }

    {141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156 }

    Returns: 0

  89. {149, 153, 163, 159, 141, 157, 155, 169, 171, 147, 165, 145, 143, 167, 151, 161 }

    {142, 144, 146, 148, 150, 152, 154, 156, 158, 160, 162, 164, 166, 168, 170, 172 }

    Returns: 57

  90. {146, 140, 147, 142, 144, 144, 144, 140, 145, 140, 146, 146, 142, 146, 143, 141 }

    {147, 145, 145, 145, 144, 148, 149, 149, 148, 141, 142, 147, 147, 149, 142, 141 }

    Returns: 24

  91. {140, 141, 151, 143, 155, 145, 146, 147, 148, 149, 150, 142, 152, 153, 154, 144 }

    {141, 142, 156, 144, 145, 146, 153, 148, 149, 150, 151, 152, 147, 154, 155, 143 }

    Returns: 32

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: