Connection Status:
Competition Arena > FoxAndPhotography

FoxAndPhotography

TCO12 Round 1B · 2012-03-27 · by ir5

TCO12 Round 1B · 2012-03-27 · by ir5 · Dynamic Programming, Search
Class Name: FoxAndPhotography
Return Type: int
Method Name: getMinimumSwaps
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

Fox Ciel is attending a party. During the party, people decided to take a commemorative photograph. Ciel picked up a camera to take a photograph. In the party, there are 2*N people (not including Ciel).

For taking the photograph, people formed two rows, each containing N people. In each row, Ciel numbered the people from 0 to N-1 from left to right. The people were aligned so that for each i, person i in the back row was standing exactly behind person i in the front row.

Initially, the people lined up arbitrarily. Therefore it is possible that some of the people in the back row are obscured by people in the front row. You are given two int[]s: heightsFront and heightsBack. For each i, heightsFront[i] is the height of person i in the front row and heightsBack[i] is the height of person i in the back row. The person in the back row is obscured by the person in the front row if and only if heightsFront[i] >= heightsBack[i].

If there are some obscured people, Ciel wants to fix it. The only operation she may do is to select two adjacent people in the same row and swap them. Compute and return the smallest number of such operations necessary to rearrange the people so that nobody in the back row is obscured. If no such sequence of operations exists, return -1.

Constraints

  • heightsFront will contain between 2 and 16 elements, inclusive.
  • heightsBack will contain the same number of elements with heightForward.
  • Each element of heightsFront and heightsBack will be between 140 and 190, inclusive.
Examples
0)
{140, 150}
{160, 150}
Returns: 1

Initially, person 1 (0-based index) in the back row is obscured. One optimal solution is to swap people 0 and 1 in the front row. Another optimal solution is to swap people 0 and 1 in the back row.

1)
{140, 140, 140, 140}
{190, 190, 190, 190}
Returns: 0

Nobody is obscured, so no swaps are needed.

2)
{170, 170, 170}
{160, 170, 180}
Returns: -1

Person 0 in the back row is too short. Regardless of how we swap the people, this person will always be obscured.

3)
{140, 141, 142, 143}
{144, 143, 142, 141}
Returns: 6
4)
{140, 170, 140, 170, 140, 170, 140, 170, 140, 170}
{180, 180, 180, 180, 180, 150, 150, 150, 150, 150}
Returns: 15

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

Coding Area

Language: C++17 · define a public class FoxAndPhotography with a public method int getMinimumSwaps(vector<int> heightsFront, vector<int> heightsBack) · 91 test cases · 2 s / 256 MB per case

Submitting as anonymous