QuickTableau
TCCC06 Qual 2 · 2006-08-22 · by AdminBrett
TCCC06 Qual 2 · 2006-08-22 · by AdminBrett · Brute Force, Math, Sorting
Problem Statement
Problem Statement
A Young tableau is a two-dimensional array of integers such that each row and column is sorted in ascending order (rows left-to-right, columns top-to-bottom). Given a int[] table with exactly 16 elements, all of which are distinct, you will return the fewest number of swaps required to turn table into a Young tableau. table should be interpreted as a 4 x 4 array of integers. More visually,
table = { A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P }
corresponds to the following 4 x 4 array
A B C D E F G H I J K L M N O P ,where A through P are integers.
Constraints
- table will contain exactly 16 elements.
- table will contain no repeated elements.
- Each element of table will be between 1 and 16, inclusive.
Examples
0)
{
1, 2, 3, 4,
5, 6, 7, 8,
9, 10, 11, 12,
13, 14, 15, 16
}
Returns: 0
We already have a Young tableau.
1)
{1,5,9,13,2,6,10,14,3,7,11,15,4,8,12,16}
Returns: 0
2)
{1,2,3,4,5,6,7,8,9,11,12,13,10,14,16,15}
Returns: 1
3)
{1,2,3,4,5,6,7,8,9,11,12,13,10,16,15,14}
Returns: 1
4)
{1,2,3,4,5,6,7,8,9,10,11,12,13,16,14,15}
Returns: 2
41)
{
2, 1, 3, 4,
5, 6, 7, 8,
9, 10, 11, 12,
13, 14, 15, 16
}
Returns: 1
Here we only need to swap the first 2 values.
Submissions are judged against all 77 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class QuickTableau with a public method int numSwaps(vector<int> table) · 77 test cases · 2 s / 256 MB per case