Statistics

Problem Statement for "FoxConnection"

Problem Statement

There are N cities in Treeland. The cities are numbered 1 through N. The roads in Treeland have the topology of a tree. That is, there are exactly N-1 bidirectional roads in Treeland, each connecting a pair of cities, and it is possible to travel between any two cities along the roads. For the purpose of this problem, all roads have the same length, and this length is our unit of distance.

You are given two int[]s A and B that describe the tree. Each of these int[]s has N-1 elements. For each valid i, there is a road that connects the cities A[i] and B[i].

There are some foxes in Treeland. Currently, each of the foxes lives in a different city. You are given a String haveFox with N characters. For each i, character i of haveFox is 'Y' if there is a fox in city i+1, or 'N' otherwise.

The foxes would like to live closer to each other. To achieve that, some foxes (possibly all of them or none at all) will move to different cities. There are three constraints for the move:
  1. After the foxes move, there must again be at most one fox in each city. (There are no restrictions on how the foxes travel while they are moving.)
  2. After the foxes move, the set of cities inhabited by the foxes must be connected. That is, for any two different cities i and j that both contain a fox, all the cities on the (only) path between i and j must also contain a fox.
  3. The total distance traveled by the foxes during the move must be as small as possible.


Return the smallest possible sum of distances traveled by the foxes.

Definition

Class:
FoxConnection
Method:
minimalDistance
Parameters:
int[], int[], String
Returns:
int
Method signature:
int minimalDistance(int[] A, int[] B, String haveFox)
(be sure your method is public)

Constraints

  • N will be between 2 and 50, inclusive.
  • A will contain exactly N-1 elements.
  • Each element of A will be between 1 and N, inclusive.
  • B will contain exactly N-1 elements.
  • Each element of B will be between 1 and N, inclusive.
  • The graph described by A and B will be a tree.
  • haveFox will contain exactly N characters.
  • Each character in haveFox will be either 'Y' or 'N'.

Examples

  1. {1,2,3}

    {2,3,4}

    "YNNY"

    Returns: 2

    Treeland looks as follows: 1-2-3-4. Two foxes are located in city 1 and city 4. One optimal solution is: The fox located in city 1 moves to city 2. The fox located in city 4 moves to city 3.

  2. {1,1,1,1}

    {2,3,4,5}

    "NYYYY"

    Returns: 1

    We can move any one of the foxes to city 1. After that the cities with foxes will form a connected set.

  3. {1,3,4,5,4}

    {2,2,2,4,6}

    "YNYNYY"

    Returns: 2

  4. {1,2,3,4,5,6,7,8,9}

    {2,3,4,5,6,7,8,9,10}

    "YNNNYNYNNY"

    Returns: 7

  5. {1,2,3,4,3,6,8,7}

    {2,3,4,5,6,8,9,6}

    "YNNYYNYYY"

    Returns: 3

  6. {1}

    {2}

    "NY"

    Returns: 0

    There can be only 1 fox.

  7. {1}

    {2}

    "NN"

    Returns: 0

    And there can be no foxes.

  8. {7,19,4,18,5,16,3,22,15,8,10,1,2,17,12,21,9,20,13,14,6,11}

    {23,7,23,23,4,19,4,18,3,16,16,10,10,15,8,1,21,17,17,13,14,14}

    "NYNYYNYNYNYNYYYYNNNYYYN"

    Returns: 12

  9. {39,19,36,30,4,7,23,33,15,14,40,5,11,16,2,27,34,9,38,31,22,28,25,24,8,12,32,29,10,13,21,35,3,1,17,26,37,18,20}

    {6,39,39,36,36,30,6,23,23,39,36,39,14,4,16,36,27,14,14,9,15,27,2,14,25,5,25,32,25,28,34,38,8,24,25,28,35,12,26}

    "NNNNNNNNNNNNNNYNNNNNNNNNYNNNNYNNYNYNNNNN"

    Returns: 10

  10. {37,17,29,1,12,36,38,15,26,4,9,19,7,33,3,35,16,25,5,10,18,23,31,11,14,32,28,8,34,6,22,13,2,27,30,39,24,21}

    {20,37,17,17,1,1,20,20,1,20,15,37,4,36,19,37,35,29,37,15,29,19,19,3,10,31,35,25,37,9,16,4,1,15,31,31,4,9}

    "YYYYYYNYYNYYYYYNYYYYYYYYYYYYYYYYYYYYYYY"

    Returns: 2

  11. {4,18,17,20,3,21,1,5,23,19,7,15,11,16,10,22,24,12,14,9,2,13,6}

    {8,8,4,17,8,4,4,8,5,5,1,5,7,23,16,21,7,19,19,14,24,24,23}

    "NNNNYYNYNYNYNNNYNYNNNYYY"

    Returns: 5

  12. {3,12,7,2,4,9,5,1,6,8,11}

    {10,3,12,7,2,4,9,5,1,6,8}

    "YNNNNYNYYNNY"

    Returns: 5

  13. {8,3,5,4,1,7,9,11,10,2}

    {6,8,3,8,4,5,7,1,1,9}

    "YNNNYYNYYYY"

    Returns: 5

  14. {25,20,29,22,24,16,15,17,7,19,18,2,13,32,8,12,9,14,11,27,26,4,1,3,6,5,10,28,33,23,31,21}

    {30,25,25,20,25,29,16,22,24,16,16,30,19,29,17,29,32,24,15,9,27,2,13,2,13,18,12,13,9,9,27,23}

    "YYNNYNNNNYNYNYYYYNNYNYYYYNYYNYYNY"

    Returns: 9

  15. {31,39,21,8,2,7,3,19,30,24,43,1,13,44,42,33,11,45,37,5,35,29,40,46,17,34,25,4,41,20,28,18,27,36,9,6,23,10,22,16,12,15,14,38,26}

    {32,32,31,39,32,32,21,3,7,2,19,19,24,8,30,8,42,7,43,39,30,39,31,29,44,33,34,21,21,32,11,25,40,19,30,24,42,25,30,24,22,6,23,46,15}

    "NNNNYYNNNYYYNYYYYYYNNNNYNNNYYNNNYNNYYNYNNYYNNY"

    Returns: 25

  16. {3,7,4,2,9,10,6,1,5}

    {8,3,3,4,7,9,4,2,10}

    "YNYNYYYNYN"

    Returns: 3

  17. {5,2,11,12,17,6,18,8,19,15,4,1,9,7,10,16,3,14}

    {13,13,5,13,11,11,17,12,11,8,8,4,15,11,6,15,12,9}

    "NNNNNNNNNNNNNNNNNNN"

    Returns: 0

  18. {4,3,8,26,7,38,13,34,10,31,37,2,33,11,27,30,6,24,12,1,17,18,36,16,23,29,20,21,32,22,5,15,19,9,35,25,14}

    {28,4,3,4,8,3,38,28,38,3,4,37,34,37,38,31,10,38,34,2,10,6,11,1,33,6,1,23,21,29,36,18,20,23,19,9,9}

    "YNNNYNNNNNNYYNNNNYYNNNYNNNNNNNNNNNNNNN"

    Returns: 17

  19. {3,1}

    {2,3}

    "YNY"

    Returns: 0

  20. {10,18,38,30,45,11,28,33,46,6,8,3,29,2,36,20,40,19,16,43,39,9,25,35,26,24,31,13,34,4,21,15,44,42,27,37,7,41,12,22,1,23,14,5,17}

    {32,10,32,10,30,32,45,11,45,38,18,46,28,46,2,32,33,32,3,28,30,36,11,3,35,43,19,45,38,16,26,33,9,9,13,36,34,38,40,4,38,42,40,11,3}

    "YYYYYNYYYYNYYYYYYNYYYYYYYYYNYYNYYNNYNNYYYYNYYY"

    Returns: 8

  21. {4,2,3}

    {1,1,4}

    "NYYY"

    Returns: 1

  22. {42,13,7,37,5,41,18,14,32,6,16,2,19,48,33,12,24,38,36,31,45,46,3,1,40,22,29,20,44,27,34,47,17,15,35,39,11,21,25,10,49,28,23,4,30,43,9,8}

    {26,26,26,26,7,13,41,18,13,14,32,42,18,13,6,42,41,24,48,38,31,36,32,3,46,46,36,3,48,38,3,38,24,22,44,17,22,35,29,40,27,35,29,28,23,39,47,15}

    "YYYYYYYYYYYYNYNYYYYYYYYYNYYYYNNYYYYYYNYYNNNYYYYYY"

    Returns: 8

  23. {38,18,13,31,22,19,28,34,11,43,26,24,27,4,8,29,3,9,5,6,30,16,25,41,45,36,21,1,35,2,20,12,23,17,14,33,15,32,39,10,7,42,44,40}

    {37,37,37,38,18,37,13,31,13,38,28,34,31,31,27,22,38,28,34,13,28,38,22,37,38,13,9,34,25,35,27,16,9,41,35,20,29,3,9,3,9,20,23,7}

    "NNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNYNYNNNNNNNNNN"

    Returns: 8

  24. {17,1,3,5,20,22,12,19,6,16,11,18,23,8,2,13,21,9,7,4,15,14,25,24}

    {10,17,17,10,1,5,3,12,12,6,12,19,6,16,18,2,23,2,21,7,9,4,7,15}

    "YNYYNYNYYYNNYNYYNNYYNYYYN"

    Returns: 13

  25. {15,34,28,30,12,6,27,13,22,4,10,3,17,9,33,25,32,21,31,11,19,20,16,29,26,14,18,8,5,24,23,7,2}

    {1,1,1,28,30,28,15,28,1,12,13,4,15,3,34,30,15,9,21,1,13,19,1,16,31,28,32,6,18,26,16,31,29}

    "YYYYYYYYYYYYYYYNYYYNYYYYYNNYYNYYYN"

    Returns: 4

  26. {19,21,16,1,5,4,18,8,13,17,7,2,10,12,15,23,9,20,22,11,3,14}

    {6,6,6,6,16,21,19,4,6,16,18,18,2,5,19,10,16,8,2,8,7,17}

    "NYYYNNYNNYNYYNNNNNNNYNN"

    Returns: 7

  27. {29,2,35,20,25,18,16,37,9,17,12,21,26,4,32,6,1,7,15,11,30,34,5,38,23,31,13,36,39,8,27,3,14,10,24,28,22,33}

    {19,29,19,19,19,2,20,19,25,29,2,16,37,21,37,4,25,4,17,12,2,21,7,26,15,2,20,18,13,36,36,36,38,14,32,26,1,34}

    "YYYYYYYYYYYYYYYYYYNYYYYYNYYYYYYYYYYYNYY"

    Returns: 4

  28. {4,11,6,9,7,2,1,3,5,12,8,13}

    {10,4,11,4,9,9,9,11,9,5,3,3}

    "YNYNNNNYNYYYY"

    Returns: 3

  29. {16,1,24,4,3,23,2,11,9,7,8,22,5,18,6,10,19,14,13,17,21,12,15}

    {20,20,20,1,16,1,24,24,2,2,2,11,9,9,7,18,22,5,6,6,14,17,13}

    "NNNYNNYYNYNYNNYNNNYNNNNN"

    Returns: 11

  30. {27,33,10,9,32,26,30,4,34,15,11,24,3,28,36,17,35,18,13,16,5,12,21,8,23,20,25,19,1,2,6,29,14,7,22}

    {31,27,33,31,33,33,32,30,27,30,4,9,15,15,3,9,36,34,28,32,15,13,11,17,16,24,5,3,23,16,13,17,18,2,21}

    "NNNNNYYYNYNYYYYNYYNYNYNYNNNNNNNNYYYN"

    Returns: 17

  31. {10,11,16,12,14,1,3,18,5,6,19,8,24,4,2,15,13,23,7,22,20,17,9}

    {21,10,10,11,21,16,11,14,1,5,18,18,6,6,18,2,12,14,15,15,2,20,24}

    "YNNNNYYYYYYNNNYNNNNYNYNY"

    Returns: 15

  32. {18,19,26,14,7,6,20,29,23,13,2,17,3,15,5,22,16,25,28,24,30,9,11,1,4,8,12,27,10}

    {21,21,18,19,14,14,7,6,29,29,13,13,17,17,3,5,22,22,16,25,24,30,9,11,11,4,4,8,12}

    "NYNNNNNNNNNNNNNNNNNNNNNNNNNNNN"

    Returns: 0

  33. {5,45,17,33,39,2,10,18,19,36,12,15,27,43,24,46,25,47,13,30,40,35,26,23,6,37,4,44,48,21,11,31,14,34,1,29,3,42,41,16,32,7,28,8,38,9,22}

    {20,20,45,45,45,5,20,10,18,18,18,36,10,19,36,15,43,19,19,15,12,24,24,47,47,46,37,13,30,44,48,11,48,44,14,4,1,11,48,29,14,34,7,42,8,42,9}

    "NYNYYNNNNNYNNNYNNNNYNYNYNNNNNNNNNNNNNNNNNNNNNNNN"

    Returns: 15

  34. {29,11,2,3,27,31,24,16,7,14,25,22,20,10,23,1,4,28,6,5,9,30,21,13,26,12,15,18,19,8}

    {17,17,29,17,11,11,31,3,29,31,27,24,7,7,22,23,7,10,25,20,6,1,5,5,13,9,5,30,30,18}

    "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYNY"

    Returns: 1

  35. {15,9,22,14,24,1,11,6,2,23,13,19,17,20,21,25,8,18,3,10,5,12,7,16}

    {4,15,4,15,9,14,22,14,11,6,11,13,13,19,17,20,21,21,18,18,8,3,10,7}

    "YNNYNYNNYYNYYYNNYYNYYYYNY"

    Returns: 7

  36. {6,14,19,2,7,8,12,5,13,28,1,4,27,26,31,23,15,21,9,16,20,10,29,3,11,25,18,30,17,24}

    {22,22,22,19,22,2,19,22,7,12,14,12,12,19,26,12,14,26,6,28,8,21,23,1,21,31,29,23,15,10}

    "YNYYNYYYYYYYNNYYYNYYYYYYYYYYNYY"

    Returns: 4

  37. {7,11,3,5,2,4,13,10,12,8,6,14,1}

    {9,7,9,7,11,11,9,2,5,10,7,4,4}

    "YYYYNNNNYYYNNY"

    Returns: 2

  38. {3,2}

    {1,1}

    "YYN"

    Returns: 0

  39. {5,10,1,12,7,8,3,2,4,11,9}

    {6,5,10,1,6,6,6,5,12,1,3}

    "YYYYYNYYYYYY"

    Returns: 1

  40. {30,13,16,2,3,21,11,5,32,17,8,25,19,14,26,6,29,18,7,31,15,20,22,4,1,27,28,24,33,10,23,9}

    {12,12,12,13,13,3,3,13,5,21,32,3,13,13,3,11,14,3,17,26,7,8,25,26,31,4,18,7,18,24,1,4}

    "YYNNNYYYNYYNNNNYYNYNNNNNYNYNYNYNY"

    Returns: 12

  41. {8,5,6,1,2,3,9,7}

    {4,4,5,5,8,5,3,9}

    "YYYYYYYYY"

    Returns: 0

  42. {39,9,1,27,21,15,36,12,34,38,13,4,22,33,37,10,11,5,40,35,20,30,25,18,2,16,7,23,32,31,6,17,14,8,19,29,3,28,26}

    {24,24,24,9,39,9,15,24,24,9,27,9,39,27,15,12,37,15,24,9,35,35,5,22,11,33,4,10,27,9,7,34,11,36,20,35,7,3,37}

    "NNNYNNNNNNNNNNNNNNNNYNNNYNNYNNNNYNNNNNNN"

    Returns: 8

  43. {8,1,5,11,2,3,9,10,6,7}

    {4,8,4,1,5,2,3,11,5,6}

    "NNNYNNNNNNN"

    Returns: 0

  44. {5,22,3,18,19,14,10,11,23,2,15,6,7,24,8,16,1,20,21,17,4,12,13}

    {9,9,9,9,5,19,9,14,18,3,18,9,2,9,9,14,5,19,9,22,6,17,8}

    "NYYYNNYNYNYYYNYNNYYNYYNY"

    Returns: 6

  45. {10,5,1,4,7,12,9,13,3,11,8,6,14}

    {2,2,5,5,4,2,10,5,7,3,11,2,5}

    "YNNYYYYYYYYYNY"

    Returns: 3

  46. {5,2,3,1}

    {4,4,5,2}

    "NNNNN"

    Returns: 0

  47. {6,21,31,10,28,23,20,15,9,26,35,3,7,17,11,13,12,16,4,34,32,36,27,33,8,14,18,29,2,24,19,5,25,30,22}

    {1,6,21,6,1,1,21,6,6,9,1,6,15,15,23,3,35,15,1,6,31,35,34,13,20,28,13,14,12,33,8,16,34,25,36}

    "NNNNNNYNNNNNNNYNNNNNNNYNNNNNNNNYNNNN"

    Returns: 4

  48. {4,1,5,2}

    {3,4,4,5}

    "NYNNN"

    Returns: 0

  49. {28,5,26,8,10,39,37,34,14,30,31,3,9,13,24,2,23,36,12,17,4,7,11,32,20,21,6,29,18,16,27,1,40,33,38,15,22,19,25}

    {35,35,28,35,35,28,5,28,35,39,34,10,37,3,13,5,8,39,31,13,17,39,26,17,39,5,39,6,10,30,34,17,39,12,37,30,7,18,27}

    "YYYYNNYYYYYYNYYYYNYNNYYYYNNYNYNNNNYYYYNN"

    Returns: 8

  50. {19,21,22,20,16,2,12,17,18,30,32,13,5,9,3,7,8,27,26,15,24,25,29,6,14,28,11,23,31,10,1}

    {4,4,19,19,4,20,22,22,19,21,16,18,30,22,13,16,9,9,17,16,17,26,18,27,25,32,7,6,23,14,7}

    "YNYNYNNNNNNNNNYNYNYNYYNNYNYNNNYN"

    Returns: 12

  51. {5,12,31,29,10,17,24,22,14,7,30,4,18,8,32,19,11,15,21,2,28,25,26,27,6,20,1,13,23,9,3}

    {16,16,12,31,29,5,16,24,31,5,24,17,5,7,10,12,5,29,10,18,22,19,30,22,10,21,14,11,26,18,26}

    "NNNNNNNNYNNNYNNNNNNNNNNNNNNNNNNY"

    Returns: 8

  52. {11,20,8,14,3,12,5,18,1,9,7,6,2,13,16,10,17,19,15}

    {4,4,4,20,14,3,20,12,12,14,14,1,7,3,2,1,16,1,2}

    "NNNNYNYNNYYNNNNNNYNN"

    Returns: 7

  53. {21,17,27,2,4,30,10,32,37,31,26,38,29,28,36,34,6,35,19,13,16,3,33,22,15,20,12,11,18,23,14,25,8,1,5,9,24}

    {7,7,17,27,27,4,21,10,7,4,21,27,30,4,28,27,32,34,4,32,29,32,35,6,29,13,22,28,15,34,33,20,15,33,33,33,5}

    "NNNNYYNNNYYNNNNNNNYYNYNNNYNNNNNYNYNNNY"

    Returns: 13

  54. {18,5,20,8,19,22,3,21,9,14,6,12,16,2,1,23,10,13,4,17,11,7}

    {15,15,5,20,18,5,20,5,18,20,15,8,12,19,6,22,20,6,19,1,23,16}

    "YYNNNNNNYYYNYYNNYNYYNYY"

    Returns: 7

  55. {5,38,9,45,42,28,26,39,49,43,33,35,21,37,41,14,48,40,13,44,31,27,32,20,8,6,2,18,17,47,22,25,16,7,50,30,15,46,24,1,3,36,12,11,29,34,23,4,10}

    {19,5,5,38,19,9,9,5,38,45,42,42,9,21,9,35,39,35,21,35,49,40,27,48,44,39,21,13,26,27,14,2,32,2,38,5,25,2,47,39,39,43,7,42,26,43,32,21,25}

    "NNYYNYYNYNYYYNNNYNYYYYYYYYNYNNYNYNNNNNYYNYYNYYYNNN"

    Returns: 10

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

    {5,5,1,6,3}

    "NNNYNN"

    Returns: 0

  57. {17,12,16,24,7,9,39,31,8,33,19,34,36,4,18,35,22,20,38,27,13,28,25,11,1,26,6,2,37,14,30,23,21,32,5,10,29,40,3}

    {15,15,12,12,24,15,7,24,17,31,7,12,33,9,15,17,24,35,34,9,8,27,17,8,4,9,22,4,27,1,37,30,28,35,4,34,2,2,37}

    "NNNNNNNNNNNNNYNNNNYYNNYNYYNNNYNNYNYNYNNY"

    Returns: 15

  58. {14,16,20,27,24,19,11,25,34,36,4,38,37,1,23,7,12,13,21,2,35,30,33,32,6,9,22,10,3,5,28,18,17,8,31,29,15}

    {26,14,16,14,26,27,16,26,14,16,26,14,26,11,19,14,25,20,34,26,26,12,35,16,24,11,36,2,35,23,24,12,16,27,26,6,23}

    "NYNNYYNNNNNNNNNNYNNNNNNNYYYNYYNNYNNYNN"

    Returns: 9

  59. {1,2,15,16,29,28,35,22,6,24,12,30,25,19,14,5,8,18,9,21,32,23,26,20,33,17,27,4,31,3,10,7,34,36,13}

    {11,1,11,11,2,1,15,16,22,15,15,28,12,6,12,30,5,28,28,25,5,22,19,29,14,9,16,25,33,24,21,16,29,14,20}

    "NYYYYYNYNYYNYYYYNNNNNNNYNYNNNNNYNYNY"

    Returns: 17

  60. {3,4,6,1,5}

    {2,2,4,2,1}

    "YNYYYY"

    Returns: 1

  61. {21,20,9,11,5,36,34,28,8,19,27,23,7,1,3,17,2,22,14,15,30,18,10,32,26,33,35,12,16,4,6,25,13,29,31}

    {24,21,21,9,24,21,36,5,34,11,8,34,27,7,36,7,1,3,17,2,15,22,17,18,14,22,15,35,18,32,10,10,33,16,35}

    "YYYNYYYYYYNYYYYYYNYYYYYYNYYYYYYNNYNN"

    Returns: 7

  62. {8,14,13,6,7,5,2,19,20,12,11,17,1,22,15,4,16,18,9,21,3}

    {10,8,10,13,14,6,6,13,6,13,13,5,7,20,17,7,11,5,13,14,20}

    "NYNYNNYNNYNNNNNNNNYNNY"

    Returns: 7

  63. {14,15,18,23,10,4,36,21,11,30,22,20,33,16,8,25,17,6,37,13,29,32,5,12,3,9,31,27,24,19,28,39,35,26,1,2,38,34,7}

    {40,14,14,14,18,18,40,36,21,15,14,30,4,36,11,8,36,15,16,30,14,14,37,32,20,22,20,32,17,6,31,37,29,8,9,12,28,38,35}

    "YNYNYNNYYNYYNYYNYYYYYNNYYNNNYYYNYNYYNYNN"

    Returns: 10

  64. {14,3,13,7,1,10,2,11,4,5,9,8,6,15}

    {12,14,14,3,7,13,13,1,7,4,5,9,9,8}

    "YYYYNYYYYYYYYYY"

    Returns: 2

  65. {8,26,39,13,28,37,36,30,12,3,25,17,23,19,22,32,38,18,24,15,5,31,29,4,10,2,1,11,14,16,21,6,40,20,33,35,34,7,27,9}

    {41,41,41,41,41,39,13,28,30,36,13,25,36,25,3,41,28,22,36,8,41,32,23,29,4,38,18,19,26,24,1,30,21,22,4,31,40,17,23,25}

    "YYYNYNNNNYNYYYNNNYNNYNNNYNYNNNYYYNYYNYYNN"

    Returns: 11

  66. {18,6,13,9,17,3,21,8,22,25,23,20,5,4,19,12,10,2,24,15,1,11,14,7}

    {16,18,6,18,9,17,6,6,21,3,16,18,21,25,16,6,22,3,20,8,19,13,8,1}

    "YYYYYYYYNYNNYYYYYNYYYNYNY"

    Returns: 5

  67. {19,25,4,11,12,24,27,2,22,16,3,23,6,20,18,17,10,1,15,14,5,13,9,26,21,7}

    {8,19,8,25,11,12,24,4,4,11,16,27,4,25,8,24,17,3,23,22,1,16,8,14,12,24}

    "YNNNYNNYYYYNNYYNNNYNNNYNYYY"

    Returns: 13

  68. {1,2,3,5,6}

    {4,4,1,2,2}

    "YYNNNN"

    Returns: 1

  69. {12,37,14,4,33,2,13,36,34,28,31,5,9,22,18,7,30,23,25,3,20,32,1,8,38,16,26,21,15,19,10,27,17,6,11,39,24,29}

    {35,35,12,35,37,37,12,4,14,13,14,28,2,2,33,9,28,22,22,25,34,3,25,3,32,23,8,30,8,16,15,1,16,32,21,11,11,11}

    "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN"

    Returns: 0

  70. {12,16,15,10,1,2,4,11,5,14,8,7,3,6,13}

    {9,12,16,15,10,1,2,4,11,5,14,8,7,3,6}

    "NYYYYNYYYYYYNYNY"

    Returns: 7

  71. {11,13,5,15,3,1,2,10,12,16,7,6,8,14,4}

    {9,9,9,11,13,15,3,2,2,2,12,12,6,6,6}

    "YYYNYNNNYYNNYYYY"

    Returns: 4

  72. {1,3,4,6,5}

    {2,1,1,4,4}

    "NNNNNN"

    Returns: 0

  73. {2}

    {1}

    "NN"

    Returns: 0

  74. {17,1,24,5,22,31,7,18,11,29,20,14,4,2,21,10,30,8,15,27,13,19,26,25,23,3,6,16,12,9}

    {28,17,17,17,17,17,17,22,5,28,18,17,7,4,14,14,2,22,24,8,29,4,14,20,8,20,19,10,30,23}

    "NNNNYNNNNNNNNNNNNNNNNNNNNNNNNNN"

    Returns: 0

  75. {3,1}

    {2,3}

    "YNN"

    Returns: 0

  76. {10,29,17,6,2,21,5,22,8,7,13,23,1,3,26,11,18,25,4,16,14,20,27,15,24,19,12,28}

    {9,10,29,17,6,2,21,5,22,8,7,13,23,1,3,26,11,18,25,4,16,14,20,27,15,24,19,12}

    "NYNYYNYYYYYNYNNNYYYNNYYYNNNNY"

    Returns: 37

  77. {36,37,25,2,22,12,11,17,16,24,34,31,32,18,9,39,15,29,27,14,5,30,33,26,28,7,20,19,4,21,8,23,6,13,3,40,10,38,35}

    {1,36,36,36,25,2,1,36,17,37,17,22,16,17,31,36,2,31,16,2,11,9,16,17,2,18,7,34,34,26,20,39,4,33,28,39,27,28,4}

    "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNN"

    Returns: 0

  78. {41,27,38,23,12,6,44,34,1,11,31,36,21,43,10,25,47,22,26,9,39,8,28,42,7,2,32,15,45,46,13,37,18,20,17,40,19,35,29,4,33,14,30,3,5,24}

    {16,16,27,16,23,23,6,41,12,6,34,11,11,21,44,44,21,31,11,22,31,39,47,8,28,47,8,42,39,32,28,45,2,37,13,20,18,19,13,19,40,18,17,40,40,30}

    "NNNNNNNNNNNNYNNNNNNNNNNNNNNNNNYNNNNNNYNNNNNNNNN"

    Returns: 10

  79. {6,28,10,37,25,9,11,24,5,32,27,14,4,22,31,2,36,21,33,20,23,1,35,26,7,34,17,15,13,19,18,8,30,29,12,16}

    {3,3,6,10,37,10,37,25,9,11,28,11,9,14,11,25,14,2,5,21,31,4,10,2,1,32,7,22,25,35,34,18,32,27,34,4}

    "NYNYNYNNYNYNYYYNYNNYNYNNYNYNNYYYNNYNN"

    Returns: 8

  80. {18,14,30,16,28,27,19,17,31,24,11,4,10,5,22,21,7,6,2,15,12,25,8,3,20,13,9,23,26,1}

    {29,18,14,30,16,16,27,27,19,31,24,31,11,4,4,4,10,7,21,7,6,2,15,15,8,3,3,9,20,9}

    "YYNYYYNNYYNYYYYYYYYYYYYYNYYYYNN"

    Returns: 12

  81. {4,2,1,5}

    {3,3,2,2}

    "NNNYN"

    Returns: 0

  82. {9,1,7,8,10,13,11,12,6,3,4,5}

    {2,9,9,1,7,8,13,11,11,12,3,4}

    "NNNNNYYNNNNNN"

    Returns: 5

  83. {15,24,14,18,4,1,16,3,19,13,17,21,6,8,2,7,5,22,9,23,20,10,12}

    {11,15,24,11,24,24,4,11,1,11,4,13,1,13,8,15,16,19,6,21,5,23,23}

    "YYYYYNYYYNNYYNNYYYYYYNNY"

    Returns: 4

  84. {9,13,33,17,29,19,35,39,28,18,32,14,23,12,30,36,21,22,31,10,2,40,6,43,3,16,11,34,20,24,26,42,27,25,5,8,37,4,15,41,7,38}

    {1,9,13,33,17,9,33,29,9,29,39,28,32,35,32,32,28,36,36,36,10,31,21,30,40,36,21,16,11,11,3,40,26,20,16,5,8,34,37,8,41,15}

    "YNNYYNYNNNNYNNYYYYYYYNYNYNNYNNNYNYYYNNNNYNN"

    Returns: 12

  85. {12,6,20,1,17,5,21,14,9,3,4,8,11,19,2,18,15,22,10,16,7,13}

    {23,12,6,6,20,20,1,23,1,21,3,17,1,11,21,8,2,4,11,18,16,19}

    "NNNNNNNNNNNNNNNNNNNYNNN"

    Returns: 0

  86. {24,7,25,10,1,22,23,3,20,5,9,6,14,18,17,15,8,13,16,12,21,2,4,11}

    {19,24,19,19,25,10,22,19,10,25,24,5,22,1,20,1,5,14,3,22,15,25,1,21}

    "YYYYYNYYYYYYYYYYYYYYYYYYY"

    Returns: 0

  87. {8,12,5,1,13,10,3,9,4,11,2,6}

    {7,8,7,12,8,12,1,10,9,10,3,3}

    "NYNYYYYYNNYNN"

    Returns: 7

  88. {21,30,4,1,20,25,29,6,12,34,31,35,28,2,22,26,33,8,13,19,18,9,32,27,11,7,14,23,24,10,3,36,17,5,16}

    {15,21,21,21,1,20,30,21,29,30,4,34,29,12,29,12,31,31,26,22,2,22,33,32,33,13,27,27,23,32,24,10,10,17,23}

    "NNNNNNNYNNNYNNNNNNYNNNNNYNNNNYYNNNYY"

    Returns: 11

  89. {9,8,7,17,16,15,12,18,11,10,5,2,3,14,13,6,4,1,21,19}

    {20,20,20,8,9,9,20,16,16,7,16,17,16,3,5,20,7,14,7,16}

    "NNNYYYYNYNYNYNYYYNNNN"

    Returns: 2

  90. {14,16,3,8,5,12,6,1,9,17,2,18,10,7,19,13,20,15,11,4}

    {21,21,14,21,3,3,14,21,12,1,1,2,6,18,2,18,13,2,2,20}

    "YYYYNYYYYYYYYYNYYYYYY"

    Returns: 0

  91. {13,27,18,10,23,4,12,22,20,19,11,8,21,2,3,1,24,16,17,9,5,7,6,15,25,26}

    {14,14,27,13,10,10,13,18,13,23,20,10,14,12,11,23,4,20,13,12,23,24,17,5,16,3}

    "NNNNNNNNYNNYYNNYNYNNNNNYNNY"

    Returns: 5

  92. {7,15,18,19,3,20,10,1,29,21,27,9,6,14,16,17,12,24,11,23,22,26,4,25,13,30,5,28,31,8}

    {2,7,15,18,19,19,20,10,1,1,21,27,27,9,6,14,17,12,24,24,11,22,22,26,25,25,30,5,5,31}

    "YNNNNNNYYYYNNNYNNYNNNNNNNYNNYYN"

    Returns: 34

  93. {7,1,15,21,36,37,18,23,26,2,5,20,27,35,48,25,39,38,30,28,42,33,10,32,8,40,14,31,13,16,29,43,19,22,12,24,45,17,41,11,3,4,44,9,47,46,6}

    {34,7,1,34,21,36,37,7,34,7,15,15,5,37,18,48,21,23,37,48,39,26,26,33,5,5,1,42,23,20,21,13,29,25,27,21,19,45,5,42,33,40,8,3,30,35,38}

    "YYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYNYYYYYYN"

    Returns: 1

  94. {8,15,12,17,5,9,11,4,3,7,14,6,1,16,2,13}

    {10,10,15,8,8,12,17,12,5,3,11,4,3,7,14,14}

    "YYYYYNYYYYYYYNYYN"

    Returns: 4

  95. {15,5,12,18,3,19,16,10,13,14,17,9,20,8,6,7,11,2,4}

    {1,15,15,1,12,15,12,12,18,10,16,3,19,17,16,17,6,9,17}

    "YYNYYNNYYYNNNYNYNNYN"

    Returns: 6

  96. {4,1,3,2,5}

    {6,6,4,3,3}

    "YNYNYN"

    Returns: 2

  97. {3,8,1,9,7,5,4,10,11,6}

    {2,3,8,1,8,9,8,8,4,3}

    "YNNYYNYNNNN"

    Returns: 2

  98. {25,13,26,31,3,29,36,22,42,43,19,5,15,16,14,12,10,41,27,23,7,9,34,28,37,32,8,24,11,35,21,20,2,1,33,18,39,6,40,30,38,4}

    {17,17,13,26,25,13,26,13,31,3,31,22,13,43,17,13,22,10,41,43,29,13,14,25,23,15,3,17,9,5,7,27,14,19,17,14,31,19,41,24,12,34}

    "NYNYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYNNYYYYYYY"

    Returns: 2

  99. {17,8,28,19,12,18,9,1,30,22,15,5,20,14,16,11,3,4,7,6,25,13,26,2,10,24,21,23,27}

    {29,29,29,28,8,28,18,18,9,1,22,15,22,15,20,16,11,11,3,4,4,25,13,25,13,2,10,21,21}

    "YYYYNYYYYYNYYYNYNNYYYYYYYYYYNY"

    Returns: 7

  100. {13,17,5,18,15,14,11,10,3,20,7,1,16,8,9,21,12,2,6,4}

    {19,19,19,19,18,15,14,14,14,3,3,7,7,20,8,8,21,12,12,21}

    "YNNYNYNYYYNNNNYNYNNNN"

    Returns: 9

  101. {6,10,9,7,5,11,3,8,2,4}

    {1,1,10,10,1,9,9,9,7,8}

    "NYNYNYNNYYY"

    Returns: 3

  102. {21,18,7,6,4,12,5,20,28,19,8,35,33,37,10,25,36,2,14,39,1,16,3,9,26,15,11,13,31,17,22,24,32,38,29,34,30,23}

    {27,21,21,18,6,6,4,6,18,28,28,28,12,5,37,5,37,20,8,14,37,2,25,37,14,25,14,2,26,26,1,17,17,32,13,11,38,13}

    "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYY"

    Returns: 0

  103. {4,46,22,14,44,45,34,17,16,5,39,3,20,24,42,43,36,21,7,1,40,38,27,29,2,41,23,32,18,30,28,37,25,9,15,8,35,12,10,13,19,11,31,26,6}

    {33,4,4,33,4,4,4,34,45,44,33,45,4,20,20,22,3,5,44,7,39,45,21,14,36,36,42,36,27,20,23,5,24,20,32,28,41,40,25,35,8,36,39,10,30}

    "YYYYYYYNYYYYNYYYYNYYYYYNYNNYYNYYYYYNYYNYYYNYYY"

    Returns: 6

  104. {40,22,26,8,28,24,34,9,23,45,30,36,14,12,7,3,37,38,20,19,27,41,33,4,10,21,6,5,32,39,17,16,42,44,18,47,2,43,13,46,11,35,25,1,31,29}

    {15,40,15,40,26,26,8,15,15,22,26,28,8,14,30,23,28,22,36,37,45,20,30,19,28,45,34,26,23,30,32,3,16,17,30,28,32,15,47,2,21,23,46,45,30,1}

    "YYYYYYYYYYYYNYYYNYYYYYYYYYYYYYYYYYYYYYNYYYYYYYY"

    Returns: 1

  105. {7,27,38,23,6,31,30,12,19,15,36,11,16,14,28,3,9,37,39,13,22,2,18,1,4,20,8,35,33,25,10,34,29,5,21,24,32,26}

    {17,17,17,27,17,23,23,27,6,27,7,30,15,11,6,15,28,3,28,3,31,15,36,2,9,15,31,1,19,15,25,12,15,2,4,28,29,10}

    "NNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNN"

    Returns: 4

  106. {18,4,7,10,13,1,12,15,6,17,9,8,2,11,14,3,5}

    {16,18,16,16,4,7,10,7,16,16,17,7,1,12,8,14,6}

    "YNNNNNNNNNNYNYNNNN"

    Returns: 4

  107. {23,14,7,15,18,13,6,8,1,25,5,24,20,10,21,11,17,12,22,3,19,2,16,4}

    {9,23,14,7,15,15,18,6,6,8,25,5,5,24,20,10,21,17,12,22,3,19,2,2}

    "NNNNNNNNYNNNYYNNYNNYYNNNN"

    Returns: 19

  108. {1,28,6,9,23,12,4,18,26,8,2,19,16,31,27,5,30,3,22,20,24,25,13,7,10,15,14,29,21,17}

    {11,11,28,28,9,9,23,12,4,26,8,8,2,19,16,31,5,5,3,22,20,20,24,25,7,10,10,15,14,29}

    "YYYYYYYNYYNYYYYYNNYYNNYYNYYYNNY"

    Returns: 9

  109. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}

    "YYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYY"

    Returns: 312

  110. {1, 2, 3, 4, 3, 6, 8, 7 }

    {2, 3, 4, 5, 6, 8, 9, 6 }

    "YNNYYNYYY"

    Returns: 3

  111. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 10, 20, 21, 22 }

    {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23 }

    "YYYYYYYYNNNYYYYYYYYYYYN"

    Returns: 8

  112. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 20, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48 }

    {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49 }

    "NNNNYNNNYYNNYNNYNNYNNYNNYNYNYNYNNYNNYNYNNYNYNYYYY"

    Returns: 101

  113. {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    {1, 2, 2, 1, 5, 5, 6, 7, 8, 5, 8, 6, 12, 14, 2, 12, 4, 9, 2, 17, 10, 19, 16, 10, 18, 7, 7, 13, 28, 6, 23, 31, 21, 13, 15, 5, 27, 4, 32, 15, 4, 40, 19, 18, 34, 19, 8, 32, 30 }

    "NNNNYYNNYNNNNNYYNNNNNNYNYNNYYYNYNYNYNNNNNYYNNNNNYY"

    Returns: 19

  114. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 20, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48 }

    {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49 }

    "NNNNYNNNYYNNYNNYNNYNNYNNYNYNYNYNNYNYYNYNNYNYNYYYY"

    Returns: 93

  115. {1, 1, 2, 3, 4, 6, 5, 7, 8, 10, 12, 13, 14, 8, 16, 9, 11, 18, 19, 20, 9, 22 }

    {2, 3, 4, 5, 6, 8, 7, 9, 10, 12, 13, 14, 15, 16, 17, 11, 18, 19, 20, 21, 22, 23 }

    "YYYYYYYNNNNYYYYYYYYYYYY"

    Returns: 8

  116. {1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 3, 6, 12 }

    {2, 3, 4, 6, 7, 8, 10, 12, 12, 14, 15, 13, 14, 15 }

    "YYYYYYYYYYYYNNN"

    Returns: 6

  117. {1, 1, 2, 1, 4, 4, 2, 5, 6, 10, 4, 11, 4, 2, 12, 10, 7, 15, 7, 17, 4, 1, 17, 24, 16, 21, 19, 16, 24, 26, 20, 14, 14, 4, 32, 8, 32, 1, 17, 36, 41, 20, 39, 1, 36, 32, 46, 6, 24 }

    {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    "NYYYNYYYNYYNYNYNNYYNNYYNYYYNNNYNYYNNYYYNNNNYYNNNNN"

    Returns: 11

  118. {1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 7 }

    {2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 12 }

    "YYYYYNNYYYYNNYYYYY"

    Returns: 8

  119. {1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 6, 7, 13, 14, 15, 14, 17, 18, 19, 20, 21, 22 }

    {2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23 }

    "YYYYYYYYYYYYNYYYNYYYYYY"

    Returns: 5

  120. {1, 2, 3, 4, 5 }

    {2, 3, 4, 5, 6 }

    "YNYYNY"

    Returns: 2

  121. {1, 1, 1, 1 }

    {2, 3, 4, 5 }

    "NYYYY"

    Returns: 1

  122. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49 }

    {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    "NYNYYNYNYYNYNYYNYNYYNYNYYNYNYYNYNYYNYNYYNYNYYNYNYY"

    Returns: 150

  123. {1, 1, 2, 2, 3, 3 }

    {2, 3, 4, 5, 6, 7 }

    "NYYYYYY"

    Returns: 2

  124. {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    {1, 2, 1, 3, 4, 6, 2, 5, 3, 1, 4, 9, 5, 11, 3, 14, 4, 9, 13, 10, 11, 20, 23, 15, 15, 23, 13, 5, 2, 4, 18, 2, 23, 12, 17, 20, 31, 28, 5, 13, 5, 10, 21, 18, 24, 15, 35, 41, 29 }

    "NNYNYNYYNNYNYYNNYNNNNNNNYYNNYNYNNNNYYNYYNNYYYYYNYY"

    Returns: 16

  125. {1, 1, 2, 2, 3, 3, 4, 7 }

    {2, 3, 4, 5, 6, 7, 8, 9 }

    "NYYYYYYYY"

    Returns: 2

  126. {1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 10, 12, 13, 14 }

    {2, 3, 4, 6, 10, 12, 5, 7, 8, 9, 11, 13, 14, 15 }

    "YNNNYYYYYNYYYYY"

    Returns: 4

  127. {1, 1, 2, 2, 5, 5, 6 }

    {2, 4, 3, 5, 8, 6, 7 }

    "NYYYNYYY"

    Returns: 2

  128. {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 1, 1, 1 }

    {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 2, 18, 34 }

    "NNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNYYNNNNNNNNNNNNNNNY"

    Returns: 59

  129. {1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 10, 12, 13, 14, 16, 11, 15, 18, 19 }

    {2, 3, 4, 6, 10, 16, 5, 7, 8, 9, 11, 13, 14, 15, 12, 17, 18, 19, 20 }

    "YNNNYYYYYNYYYYYNYYYY"

    Returns: 8

  130. {10, 1, 1, 10, 4, 4, 10, 7, 7 }

    {1, 2, 3, 4, 5, 6, 7, 8, 9 }

    "YYYYYYYYYN"

    Returns: 2

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: