DemocraticAssignment | Topcoder Archive

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

Definition

Class:: DemocraticAssignment
Method:: findAssignment
Parameters:: int[]
Returns:: int[]
Method signature:: int[] findAssignment(int[] preferences)
(be sure your method is public)

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,1,2,
 1,2,0,
 2,1,0}
```
```
Returns: {0, 1, 2 }
```
Everyone can be assigned to their favorite house.
```
{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.
```
{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.
```
{1,0,
 1,0}
```
```
Returns: {0, 1 }
```

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

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.