Connection Status:
Competition Arena > DemocraticAssignment

DemocraticAssignment

2015 TCO Final · 2015-04-08 · by lg5293

2015 TCO Final · 2015-04-08 · by lg5293 · Graph Theory
Class Name: DemocraticAssignment
Return Type: int[]
Method Name: findAssignment
Arg Types: (vector<int>)
Problem Statement

Problem Statement

Byteland is currently solving a problem with housing.


There are n people who need housing. There are also exactly n houses available, and each house can accommodate a single person. Both the people and the houses are numbered 0 through n-1. The problem is that the n houses are different and therefore different people may have different housing preferences.


Each of the n people has provided a permutation of {0,...,n-1}: all house numbers ordered according to their preference, starting with the most wanted one. These n permutations have been concatenated to produce a single sequence with n^2 elements. You are given this sequence: a int[] preferences. Formally, for each i and j between 0 and n-1, inclusive, the value preferences[i*n+j] is the j-th element (0-based index) in the preference list of person i.


An assignment is a permutation P of {0,...,n-1} where the value P[i] denotes the house assigned to person i.

Given two assignments A and B, we say that person i prefers A over B if the house A[i] is earlier than the house B[i] in person i's preference list. (Note that if A[i] equals B[i], person i doesn't prefer either assignment over the other.)

Given two assignments A and B, we say that the group prefers A over B if the number of people who prefer A over B is strictly greater than the number of people who prefer B over A.


The government of Byteland is looking for an assignment A with a special property: there must be no assignment B such that the group prefers B over A.

If there is such an assignment, find and return it as a int[] with n elements. If there are multiple solutions, return the lexicographically smallest one. If there are no solutions, return the int[] {-1}. (That is, a int[] with a single element. The value of the element is -1.)

Constraints

  • n will be between 2 and 50, inclusive.
  • preferences will contain exactly n*n elements.
  • For each x between 0 and n-1, the sequence preferences[n*x+0], preferences[n*x+1], ..., preferences[n*x+n-1] will be a permutation of {0,...,n-1}.
Examples
0)
{0,1,2,
 1,2,0,
 2,1,0}
Returns: {0, 1, 2 }

Everyone can be assigned to their favorite house.

1)
{1,0,2,
 1,0,2,
 1,0,2}
Returns: {-1 }

In this case, it's impossible to find an assignment that satisfies the condition.

2)
{3,2,1,0,
 3,1,2,0,
 3,0,2,1,
 1,0,3,2}
Returns: {2, 3, 0, 1 }

Note that {3,2,0,1} is also a valid assignment, but it is not lexicographically smallest.

3)
{1,0,
 1,0}
Returns: {0, 1 }
4)
{4,3,2,1,0,
 0,1,2,3,4,
 0,4,2,3,1,
 0,3,2,1,4,
 4,0,1,2,3}
Returns: {3, 1, 2, 0, 4 }

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

Coding Area

Language: C++17 · define a public class DemocraticAssignment with a public method vector<int> findAssignment(vector<int> preferences) · 75 test cases · 2 s / 256 MB per case

Submitting as anonymous