QuickTableau | Topcoder Archive

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.

Definition

Class:: QuickTableau
Method:: numSwaps
Parameters:: int[]
Returns:: int
Method signature:: int numSwaps(int[] table)
(be sure your method is public)

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

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

Returns: 0

We already have a Young tableau.

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

Returns: 6

{
 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.

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

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.