Connection Status:
Competition Arena > BasicSorting

BasicSorting

TCCC05 Finals · 2005-01-10 · by lars2520

TCCC05 Finals · 2005-01-10 · by lars2520 · Graph Theory, Recursion, Search, Sorting
Class Name: BasicSorting
Return Type: int
Method Name: minSortTime
Arg Types: (vector<int>)
Problem Statement

Problem Statement

You have a few very large files and they need to be sorted according to a total order that is defined for them. The only information you can use to sort them is the relative orders of pairs of files. Unfortunately, finding the relative order of a pair takes N*M minutes where N and M are the sizes of the two files being compared. Given the sizes of the files being sorted, your task is to find a comparison plan that guarantees you will find the correct order in the minimal amount of time. You should return that minimum.

Notes

  • No two files are 'equal' -- one of them always belongs strictly after the other in the ordering.

Constraints

  • sizes will contain between 2 and 6 elements, inclusive.
  • Each element of sizes will be between 1 and 100, inclusive.
Examples
0)
{1,2,3}
Returns: 11

With 3 files, you must compare all 3 pairs of files to figure out the order. The total time is thus 1*2 + 1*3 + 2*3 = 11 minutes.

1)
{1,1,1,1}
Returns: 5

One way to do this is to find the order on three of the files, which takes 3 minutes. Then, compare the fourth file to the middle one of those three files. Finally, if the fourth file comes after the middle file, compare it to the last file, while if it comes before the fourth file, compare it to the first file.

2)
{15,74,61,34,21}
Returns: 12477
3)
{1,2,3,4,5,6}
Returns: 128
4)
{1,1,1,1,1,1}
Returns: 10

Submissions are judged against all 77 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BasicSorting with a public method int minSortTime(vector<int> sizes) · 77 test cases · 2 s / 256 MB per case

Submitting as anonymous