MovingRooksDiv1
SRM 618 · 2013-12-22 · by ltaravilse
SRM 618 · 2013-12-22 · by ltaravilse · Advanced Math, Dynamic Programming
Problem Statement
Problem Statement
In this problem, some test cases have more than one correct output. We are using a special checker to verify that the output of your program is correct.
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 aint[] Y with n elements: for each row r, the rook in row r is in column Y[r].
You are given twoint[] 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.
If changing the first chessboard into the second one is impossible, return aint[] with only one element, and that element should be -1.
Otherwise, find any valid sequence of moves that changes the first board into the second board. Each move is uniquely defined by two integers: the rows with the rooks you want to move. If we write down the two rows for each move, we get a sequence of integers that encodes the solution. If that sequence has at most 2500 integers (i.e., encodes at most 1250 moves), return aint[] with the entire sequence.
Otherwise, return a int[] with just the first 2500 integers of your sequence.
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
You are given two
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.
If changing the first chessboard into the second one is impossible, return a
Otherwise, find any valid sequence of moves that changes the first board into the second board. Each move is uniquely defined by two integers: the rows with the rooks you want to move. If we write down the two rows for each move, we get a sequence of integers that encodes the solution. If that sequence has at most 2500 integers (i.e., encodes at most 1250 moves), return a
Notes
- You are not required to find the solution that uses the smallest possible number of moves.
- If your return value has 2500 integers, it will be accepted if and only if it is a valid solution or a proper prefix of some valid solution.
- If your return value has fewer than 2500 integers, it will be accepted if and only if it's a valid solution (not a proper prefix).
Constraints
- Y1 will contain between 1 and 2500 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
0)
{0}
{0}
Returns: { }
1)
{1,0}
{0,1}
Returns: {0, 1 }
2)
{1,2,0}
{2,0,1}
Returns: {-1 }
3)
{2,1,0,3,5,4}
{0,1,2,3,4,5}
Returns: {0, 1, 0, 2, 1, 2, 4, 5 }
4)
{10,9,8,7,6,5,4,3,2,1,0}
{0,1,2,3,4,5,6,7,8,9,10}
Returns: {0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, 0, 9, 0, 10, 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 10, 2, 3, 2, 4, 2, 5, 2, 6, 2, 7, 2, 8, 2, 9, 2, 10, 3, 4, 3, 5, 3, 6, 3, 7, 3, 8, 3, 9, 3, 10, 4, 5, 4, 6, 4, 7, 4, 8, 4, 9, 4, 10, 5, 6, 5, 7, 5, 8, 5, 9, 5, 10, 6, 7, 6, 8, 6, 9, 6, 10, 7, 8, 7, 9, 7, 10, 8, 9, 8, 10, 9, 10 }
Submissions are judged against all 67 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MovingRooksDiv1 with a public method vector<int> move(vector<int> Y1, vector<int> Y2) · 67 test cases · 2 s / 256 MB per case