Statistics

Problem Statement for "CCChecker2"

Problem Statement

Mojtaba is Arpa's kind teacher. Once, he gave Arpa a problem to solve. The problem looked as follows:

There is an n times n chessboard, with both rows and columns numbered from 1 to n. Some unit cubes are placed onto the chessboard in such a way that each cube occupies a single cell. Each cube has a different color, and a different target cell it should occupy. You can move cubes by sliding them. More precisely, in a single move you can slide a single cube from its current cell into an empty adjacent cell. Find one sequence of moves that will move all cubes to their target cells.

Arpa has already implemented his solution and he asked Mojtaba to test it. As the solution is not unique, Mojtaba would need a checker. But now he is occupied with the preparation of Qadir festival, so he kindly asked you to help and do that.

You are given the int n: the dimension of the chessboard. You are also given the int[]s startRow, startCol, destRow, and destCol. The length of startRow is the number of cubes. For each valid i, there is a cube that starts in row startRow[i] and column startCol[i], and this cube should be pushed to row destRow, column destCol. This is the input data for the problem, and you can assume that it is valid.

Finally, you are given the int[]s moveStartRow, moveStartCol, moveDestRow, and moveDestCol. These contain Arpa's solution. Their meaning is as follows: for each valid index i (starting with 0, 1, 2, ...), one should move the cube that is currently in row moveStartRow[i] and column moveStartCol[i], and slide this cube to row moveDestRow, column moveDestCol.

We already did some simple tests for you: we made sure that all four arrays that describe Arpa's solution have the same length and contain integers only. The rest is up to you.

Return "valid" if the arrays move* contain a valid solution to the puzzle described by the other parameters. Otherwise, return "invalid".

Definition

Class:
CCChecker2
Method:
check
Parameters:
int, int[], int[], int[], int[], int[], int[], int[], int[]
Returns:
String
Method signature:
String check(int n, int[] startRow, int[] startCol, int[] destRow, int[] destCol, int[] moveStartRow, int[] moveStartCol, int[] moveDestRow, int[] moveDestCol)
(be sure your method is public)

Constraints

  • n will be between 1 and 6.
  • Length of startRow, startCol, destRow, and, destCol will be equal, and it will be between 0 and 5, inclusive.
  • Length of moveStartRow, moveStartCol, moveDestRow, and, moveDestCol will be equal, and they will be between 0 and 50, inclusive.
  • Each element of startRow, startCol, destRow, and, destCol will be between 1 and n, inclusive.
  • Each element of moveStartRow, moveStartCol, moveDestRow, and, moveDestCol can be any 32-bit integer.
  • Start position of cubes will not coincide.
  • Destinations of cubes will not coincide.

Examples

  1. 2

    {1}

    {1}

    {2}

    {2}

    {1, 1}

    {1, 2}

    {1, 2}

    {2, 2}

    Returns: "valid"

    There is a single cube. It starts at (1,1) and we should move it to (2,2). The last four arrays describe one valid solution: in step 0 we move a cube from (1,1) to (1,2), and in step 1 we then move a cube from (1,2) to (2,2).

  2. 2

    {1, 2}

    {1, 2}

    {1, 2}

    {2, 1}

    {2, 1, 2, 1, 2, 1, 2, 2}

    {2, 1, 1, 2, 2, 1, 1, 2}

    {1, 2, 2, 1, 1, 2, 2, 2}

    {2, 1, 2, 1, 2, 1, 2, 1}

    Returns: "valid"

    Now there are two cubes: a red cube that should go from (1,1) to (1,2), and a blue cube that should go from (2,2) to (2,1). Again, the move* arrays represent a valid solution. It's not the shortest solution possible, but that is not required.

  3. 2

    {2, 2}

    {1, 2}

    {2, 2}

    {2, 1}

    {2, 2, 1, 2, 1, 2, 2, 1}

    {2, 1, 2, 2, 1, 1, 2, 2}

    {1, 2, 1, 1, 2, 2, 2, 2}

    {2, 2, 1, 2, 1, 2, 1, 2}

    Returns: "valid"

  4. 5

    {1}

    {2}

    {1}

    {1}

    {1, 1, 1, 1, 1, 1, 1}

    {2, 3, 4, 5, 4, 3, 2}

    {1, 1, 1, 1, 1, 1, 1}

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

    Returns: "valid"

  5. 5

    {5, 5, 5, 5, 5}

    {5, 4, 3, 2, 1}

    {5, 5, 5, 5, 5}

    {1, 2, 3, 4, 5}

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

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

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

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

    Returns: "valid"

  6. 6

    {6, 5, 4, 3, 2}

    {6, 6, 6, 6, 6}

    {2, 3, 4, 5, 6}

    {6, 6, 6, 6, 6}

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

    {6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 6, 6, 6, 6, 6, 5, 5, 5, 6, 6, 6, 6, 5, 5, 6, 6, 6, 5, 6, 6, 5, 5, 5, 5, 5}

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

    {6, 5, 6, 5, 6, 5, 6, 5, 6, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 6, 6, 6, 6, 5, 5, 5, 5, 6, 6, 6, 5, 5, 5, 6, 6, 5, 5, 6, 5, 6, 6, 6, 6, 6}

    Returns: "valid"

  7. 5

    {5, 2}

    {2, 4}

    {3, 1}

    {2, 3}

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

    {4, 4, 2, 2, 2, 2, 3, 4, 5, 4, 3, 3, 5, 4}

    {1, 1, 4, 3, 2, 2, 2, 2, 2, 2, 3, 3, 1, 1}

    {4, 5, 2, 2, 2, 3, 4, 5, 4, 3, 3, 2, 4, 3}

    Returns: "valid"

  8. 2

    {1, 2}

    {1, 2}

    {2, 1}

    {2, 1}

    {1, 2, 1, 1}

    {1, 2, 2, 2}

    {1, 1, 1, 2}

    {2, 2, 1, 2}

    Returns: "invalid"

  9. 3

    {1, 3}

    {1, 3}

    {3, 1}

    {3, 1}

    {1, 3, 3, 3, 2, 2, 2}

    {1, 3, 2, 1, 1, 2, 3}

    {2, 3, 3, 2, 1, 2, 3}

    {2, 2, 1, 1, 1, 3, 3}

    Returns: "invalid"

  10. 3

    {1, 3}

    {1, 3}

    {3, 1}

    {3, 1}

    {1, 3, 3, 3, 2, 1, 2}

    {1, 3, 2, 1, 1, 3, 3}

    {1, 3, 3, 2, 1, 2, 3}

    {3, 2, 1, 1, 1, 3, 3}

    Returns: "invalid"

  11. 6

    {6, 5, 4, 3, 2}

    {6, 6, 6, 6, 6}

    {2, 3, 4, 5, 6}

    {6, 6, 6, 6, 6}

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

    {6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 6, 6, 6, 6, 6, 5, 5, 5, 6, 6, 6, 6, 5, 5, 6, 6, 6, 5, 6, 6, 5, 5, 5, 5}

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

    {6, 5, 6, 5, 6, 5, 6, 5, 6, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 6, 6, 6, 6, 5, 5, 5, 5, 6, 6, 6, 5, 5, 5, 6, 6, 5, 5, 6, 5, 6, 6, 6, 6}

    Returns: "invalid"

  12. 6

    {}

    {}

    {}

    {}

    {}

    {}

    {}

    {}

    Returns: "valid"

    If there are no cubes, then doing nothing is a valid solution.

  13. 3

    {1}

    {1}

    {1}

    {1}

    {-47}

    {-42}

    {125216547}

    {125216547}

    Returns: "invalid"

    Arpa's program has produced some garbage. These are not even valid coordinates!

  14. 3

    {1}

    {1}

    {1}

    {3}

    {1}

    {1}

    {1}

    {3}

    Returns: "invalid"

    In each step we have to move a cube by a single cell.

  15. 6

    {1}

    {1}

    {2}

    {2}

    {1}

    {1}

    {2}

    {2}

    Returns: "invalid"

    Diagonal moves are not allowed either.

  16. 3

    {1,1}

    {1,2}

    {1,1}

    {3,2}

    {1,1}

    {1,2}

    {1,1}

    {2,3}

    Returns: "invalid"

    Here we have two cubes. One starts at (1,1) and should end at (1,3), the other should start and end at (1,2). The arrays move* describe two instructions: move a cube from (1,1) to (1,2), and move a cube from (1,2) to (1,3). This is not a valid solution. In step 0 we cannot move the cube from (1,1) to (1,2), because this cell is currently occupied.

  17. 3

    {1,1}

    {1,2}

    {1,1}

    {3,2}

    {1,1}

    {2,1}

    {1,1}

    {3,2}

    Returns: "invalid"

    This is the same collection of cubes and destinations as in the previous example. This solution is not valid either: the cubes are at the destination cells, but their positions are swapped. Remember that each cube has its own color and its own designated cell.

  18. 3

    {1,1}

    {1,2}

    {1,1}

    {3,2}

    {1,1,1,2}

    {2,1,2,2}

    {2,1,1,1}

    {2,2,3,2}

    Returns: "valid"

    For the third time we have the same cubes and the same destinations. Now we have a valid solution: move the cube from (1,2) to row 2, in two moves get the cube from (1,1) to (1,3), and then return the other cube from (2,2) back to (1,2) where it belongs.

  19. 5

    {}

    {}

    {}

    {}

    {1}

    {1}

    {2}

    {1}

    Returns: "invalid"

  20. 5

    {1}

    {1}

    {1}

    {1}

    {1}

    {1}

    {1}

    {1}

    Returns: "invalid"

  21. 2

    { }

    { }

    { }

    { }

    {1, 1 }

    {1, 2 }

    {1, 2 }

    {2, 2 }

    Returns: "invalid"

  22. 2

    { }

    { }

    { }

    { }

    {1 }

    {1 }

    {2 }

    {2 }

    Returns: "invalid"

  23. 3

    {1, 2, 3 }

    {1, 1, 1 }

    {2, 1, 3 }

    {1, 1, 1 }

    {1 }

    {1 }

    {2 }

    {1 }

    Returns: "invalid"

  24. 3

    {1, 1 }

    {1, 2 }

    {1, 1 }

    {3, 2 }

    {1, 1 }

    {2, 1 }

    {1, 1 }

    {3, 2 }

    Returns: "invalid"

  25. 6

    {1 }

    {1 }

    {2 }

    {2 }

    {1 }

    {1 }

    {2 }

    {2 }

    Returns: "invalid"

  26. 3

    {1, 2 }

    {1, 2 }

    {1, 2 }

    {2, 1 }

    {1, 2 }

    {1, 2 }

    {2, 1 }

    {1, 2 }

    Returns: "invalid"

  27. 1

    {1 }

    {1 }

    {1 }

    {1 }

    {100 }

    {100 }

    {100 }

    {100 }

    Returns: "invalid"

  28. 2

    {1 }

    {1 }

    {2 }

    {2 }

    {1, 1 }

    {1, 2 }

    {1, 2 }

    {2, 2 }

    Returns: "valid"

  29. 1

    {1 }

    {1 }

    {1 }

    {1 }

    {1, 0 }

    {1, 1 }

    {0, 1 }

    {1, 1 }

    Returns: "invalid"

  30. 2

    {1 }

    {1 }

    {2 }

    {2 }

    {2, 1, 1 }

    {1, 1, 2 }

    {2, 1, 2 }

    {2, 2, 2 }

    Returns: "invalid"

  31. 3

    {1 }

    {1 }

    {1 }

    {2 }

    {1 }

    {1 }

    {1 }

    {2 }

    Returns: "valid"

  32. 2

    {2 }

    {2 }

    {1 }

    {1 }

    {2, 3, 3, 2 }

    {2, 2, 1, 1 }

    {3, 3, 2, 1 }

    {2, 1, 1, 1 }

    Returns: "invalid"

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: