Exercise 4 | RACSO

Exercise _‹4_›:

Committee

Solve the following exercise by means of a reduction to SAT:

A large company has to form a committee from all of its members to decide its comercial plan. Each member has a different set of preferences: (i) some do not care about being in the committee, (ii) others want to be in it either way, (iii) some say that they are okay not being part of the committee as long as all their chosen representants are in it, (iv) others say that, if any of the members with whom they have opposite views are part of the committee, then they must be in it too, and (v) the rest do not want to be part of it under any circumstance. Moreover, there are pairs of conflictive members, such that not both of them can be in the committee at the same time. Determine if it is possible to arrange a (non-empty!) committee that satisfies everyone.

The input of the exercise and the output with the solution (when the input is solvable) are as follows:

```
members: array of struct {
   preference: int
   representants: array of int
   opposition: array of int
}
conflicts: array of array [2] of int
```
The array members contains the preferences for each of the members of the company. In particular, for the $i$ ’th member, the field member[i].preference specifies her preferences with any of the following identifiers:
- 1: she doesn’t care about being in the committee.
- 2: she must be in the committee.
- 3: she is okay not being part of the committee as long as all the members in members[i].representants are in it.
- 4: she must be in the committee if any of the members in members[i].opposition is in it.
- 5: she must not be in the committee.
The array conflicts has one element for each pair of conflictive members. Members are identified by its index in the array members, i.e., a number between 0 and members.size-1.
```
committee: array of int
```
The output is a list containing the identifiers of the members that are part of the committee.

Authors: Nil Mamano / Documentation: