Statistics

Problem Statement for "MovingRooksDiv2"

Problem Statement

This problem is about chessboards with rooks. A rook is a chess piece that moves arbitrarily far, either horizontally or vertically. Both rows and columns of chessboards in our problem are numbered starting from 0.
An n times n chessboard is called peaceful if it contains exactly n rooks and no two rooks attack each other. In other words, there cannot be two rooks in the same row or in the same column of the chessboard. A peaceful chessboard can be described by a int[] Y with n elements: for each row r, the rook in row r is in column Y[r].
You are given two int[]s Y1 and Y2 with n elements each. Each of them represents one peaceful chessboard.
You want to change the first chessboard into the second one. There is only one type of moves you are allowed to make: On the first chessboard, you can choose two rooks in positions (r1,c1) and (r2,c2) such that r1 < r2 and c1 > c2, and move them to (r1,c2) and (r2,c1). Note that the new chessboard is peaceful again.
Return "Possible" (quotes for clarity) if it is possible to change the first chessboard into the second one. Otherwise, return "Impossible".

Definition

Class:
MovingRooksDiv2
Method:
move
Parameters:
int[], int[]
Returns:
String
Method signature:
String move(int[] Y1, int[] Y2)
(be sure your method is public)

Constraints

  • Y1 will contain between 1 and 8 elements, inclusive.
  • Y2 will contain the same number of elements as Y1.
  • Each element of Y1 will be between 0 and n-1, inclusive, where n is the number of elements of Y1.
  • Each element of Y2 will be between 0 and n-1, inclusive, where n is the number of elements of Y2.
  • All elements of Y1 will be distinct.
  • All elements of Y2 will be distinct.

Examples

  1. {0}

    {0}

    Returns: "Possible"

    Both boards are already equal, we don't even have to make any moves.

  2. {1,0}

    {0,1}

    Returns: "Possible"

    Initially, the rooks on the first chessboard are on the cells (0,1) and (1,0). There is one valid move: moving these two rooks to (0,0) and (1,1). After this move, the first chessboard is identical to the second one.

  3. {0,1}

    {1,0}

    Returns: "Impossible"

    There are no valid moves so there's no way to reach the goal.

  4. {3,1,2,0}

    {0,2,1,3}

    Returns: "Possible"

  5. {3,1,2,0}

    {3,2,0,1}

    Returns: "Impossible"

  6. {2,0,1}

    {0,1,2}

    Returns: "Possible"

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

    {1,2,3,0,4}

    Returns: "Possible"

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

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

    Returns: "Impossible"

  9. {2,1,6,4,0,5,3}

    {0,2,4,5,6,3,1}

    Returns: "Impossible"

  10. {0,3,6,4,1,2,5}

    {1,6,5,2,0,3,4}

    Returns: "Impossible"

  11. {3,0,2,1}

    {2,3,0,1}

    Returns: "Impossible"

  12. {0,4,2,5,3,1}

    {5,1,2,0,3,4}

    Returns: "Impossible"

  13. {2,0,3,1,4}

    {0,1,2,4,3}

    Returns: "Impossible"

  14. {3,6,2,4,1,5,0}

    {6,4,0,2,1,3,5}

    Returns: "Impossible"

  15. {2,0,1}

    {1,0,2}

    Returns: "Possible"

  16. {1,0,4,5,3,2}

    {0,3,4,1,5,2}

    Returns: "Impossible"

  17. {0,1,2}

    {1,2,0}

    Returns: "Impossible"

  18. {2,0,1}

    {0,2,1}

    Returns: "Possible"

  19. {2,1,0,3,4}

    {3,1,4,2,0}

    Returns: "Impossible"

  20. {1,0,3,4,2,6,5}

    {3,0,1,5,6,2,4}

    Returns: "Impossible"

  21. {4,2,0,3,1}

    {2,1,0,4,3}

    Returns: "Possible"

  22. {4,6,1,0,2,5,3}

    {4,5,2,0,1,3,6}

    Returns: "Impossible"

  23. {6,0,5,1,3,4,2}

    {0,3,6,1,5,4,2}

    Returns: "Possible"

  24. {5,2,4,3,1,0}

    {0,5,2,3,4,1}

    Returns: "Possible"

  25. {7,6,5,4,3,2,1,0}

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

    Returns: "Possible"

  26. {6,7,5,4,3,2,1,0}

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

    Returns: "Impossible"

  27. {7, 6, 5, 4, 3, 2, 1, 0 }

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

    Returns: "Possible"

  28. {3, 1, 2, 0 }

    {0, 2, 1, 3 }

    Returns: "Possible"

  29. {2, 1, 0 }

    {0, 2, 1 }

    Returns: "Possible"

  30. {7, 6, 5, 4, 3, 2, 1, 0 }

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

    Returns: "Possible"

  31. {5, 6, 7, 4, 3, 2, 1, 0 }

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

    Returns: "Possible"

  32. {4, 0, 5, 3, 6, 2, 7, 1 }

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

    Returns: "Impossible"

  33. {3, 1, 0, 2 }

    {1, 3, 2, 0 }

    Returns: "Impossible"

  34. {3, 1, 2, 0 }

    {1, 2, 0, 3 }

    Returns: "Possible"

  35. {0, 1 }

    {1, 0 }

    Returns: "Impossible"

  36. {3, 7, 2, 4, 0, 1, 5, 6 }

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

    Returns: "Impossible"

  37. {6, 2, 4, 0, 1, 5, 7, 3 }

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

    Returns: "Possible"

  38. {7, 6, 5, 4, 3, 2, 1, 0 }

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

    Returns: "Possible"

  39. {2, 1, 0, 3 }

    {1, 2, 3, 0 }

    Returns: "Impossible"

  40. {1, 2, 0, 3 }

    {0, 1, 3, 2 }

    Returns: "Impossible"

  41. {3, 1, 2, 0 }

    {2, 3, 0, 1 }

    Returns: "Impossible"

  42. {0, 1, 2, 3, 4, 5, 6, 7 }

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

    Returns: "Impossible"

  43. {0, 1 }

    {0, 1 }

    Returns: "Possible"

  44. {1, 0 }

    {0, 1 }

    Returns: "Possible"

  45. {0, 7, 6, 5, 4, 3, 2, 1 }

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

    Returns: "Impossible"

  46. {0, 1, 2, 3 }

    {0, 1, 3, 2 }

    Returns: "Impossible"

  47. {2, 1, 3, 0 }

    {2, 0, 3, 1 }

    Returns: "Possible"

  48. {7, 6, 5, 4, 3, 2, 1, 0 }

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

    Returns: "Possible"

  49. {3, 0, 1, 2 }

    {0, 3, 2, 1 }

    Returns: "Impossible"

  50. {7, 6, 5, 4, 3, 1, 2, 0 }

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

    Returns: "Impossible"

  51. {0, 1, 3, 2 }

    {1, 0, 2, 3 }

    Returns: "Impossible"

  52. {3, 1, 2, 0, 7, 6, 5, 4 }

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

    Returns: "Impossible"

  53. {7, 6, 4, 3, 2, 1, 0, 5 }

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

    Returns: "Impossible"

  54. {0, 2, 1, 3 }

    {0, 1, 3, 2 }

    Returns: "Impossible"

  55. {4, 3, 0, 1, 2 }

    {0, 1, 2, 3, 4 }

    Returns: "Possible"

  56. {4, 2, 6, 3, 7, 5, 1, 0 }

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

    Returns: "Possible"

  57. {2, 0, 1 }

    {1, 0, 2 }

    Returns: "Possible"

  58. {0, 1, 4, 3, 2 }

    {1, 0, 2, 3, 4 }

    Returns: "Impossible"

  59. {1, 0, 2 }

    {0, 2, 1 }

    Returns: "Impossible"

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: