Optimal Teacher Reassignment

After entering university, n students must choose their courses. In the first year, each student chose one of the three teachers: JYY, YJY, and YYJ. During that year, every student formed impressions of every other student, and each student ranked the other n-1 students from best to worst based on their impressions.

In the second year, every student wishes to change their teacher (i.e. they cannot choose the teacher they had in the first year) and the school administration wants to reschedule the course assignments so that the worst pair‐impression among students taking the same class is as good as possible.

For any two students i and j in the same class, define the impression score as follows. Let pos(i, j) be the 1-indexed position of student j in i's ranking (the smaller the position, the better the impression). Convert this ranking into a score by score(i, j) = n - pos(i, j). Then the pair quality is min(score(i,j), score(j,i)). For a given class (with at least two students) the class quality is the minimum pair quality among all pairs in that class. The overall quality of an assignment is defined as the minimum class quality taken over all classes that have at least two students. (If an assignment results in no class having at least two students then define its overall quality to be n-1.)

Your task is to assign each student a new teacher (subject to the constraint that a student cannot choose the same teacher as in the first year) in order to maximize the overall quality. Output the maximum possible overall quality that can be achieved.

Note: The allowed teachers for a student are exactly the two teachers not chosen in the first year. When listing teachers in a fixed order as [JYY, YJY, YYJ], each student’s allowed teacher set is determined by removing the teacher they had in the first year; then the first allowed teacher is considered option 0 and the second allowed teacher is option 1. Use a brute force search over the 2ⁿ possible assignments. You may assume that n is small (for example, n ≤ 15).

The problem involves some combinatorial optimization and careful handling of pairwise quality computation using LaTeX formatted formulas such as:

$$score(i,j)= n - pos(i,j)$$

and

$$quality(i,j)=\min(score(i,j),\;score(j,i))$$

The overall quality is then:

$$Q=\min_{\text{class } C:\;|C|\ge2} \;\min_{\substack{i,j\in C \\ i<j}} quality(i,j)$$

Your program should output the maximum possible value of \(Q\).

inputFormat

The input is given as follows:

1. An integer n (2 ≤ n ≤ 15) on the first line, representing the number of students.
2. A line with n space‐separated strings, each being one of JYY, YJY, or YYJ, representing the first–year teacher choice for each student (students are numbered from 1 to n).
3. Then follow n lines. The i^th of these lines contains n-1 space-separated integers. These integers form a permutation of the set \(\{1,2,\ldots,n\}\setminus \{i\}\). The order represents student i's ranking of the other students from best to worst.

outputFormat

Output a single integer: the maximum overall quality that can be achieved by a valid re–assignment of teachers, computed as described above.

sample

3
JYY YJY YYJ
2 3
1 3
1 2

2

</p>