RankingStudents | Topcoder Archive

Problem Statement

You are a teacher of a class with n students, numbered 0, 1, ..., n - 1.

You are given the int[] f with n elements, and the int[]s a, and b, both with the same number of elements. You want to order the students into a line under the following constraints:

For each valid i, the number of students before i should not exceed f[i].
For each valid i, student a[i] must come before student b[i].

Return "Possible" if such a ranking is possible, and "Impossible" if it isn't.

Definition

Class:: RankingStudents
Method:: rankingPossible
Parameters:: int, int[], int[], int[]
Returns:: String
Method signature:: String rankingPossible(int n, int[] f, int[] a, int[] b)
(be sure your method is public)

Constraints

n will be between 1 and 1000, inclusive.
f will have exactly n elements.
Each entry in f will be between 0 and n - 1, inclusive.
a will have between 0 and 1000 elements, inclusive.
a and b will have the same number of elements.
Each element of a and b will be between 0 and n - 1, inclusive.
For each valid i, a[i] != b[i]

Examples

```
3
```
```
{0, 1, 2}
```
```
{0, 1}
```
```
{2, 2}
```
```
Returns: "Possible"
```
Students have to stand in the order 0, 1, 2.
```
3
```
```
{2, 2, 2}
```
```
{0, 1, 2}
```
```
{1, 2, 0}
```
```
Returns: "Impossible"
```
We cannot satisfy all constraints of the second type.
```
4
```
```
{1, 1, 1, 3}
```
```
{1}
```
```
{3}
```
```
Returns: "Impossible"
```
In any ordering, the first condition must be violated for atleast one of the first 3 students.
```
6
```
```
{5, 5, 5, 1, 5, 4}
```
```
{0, 2, 4}
```
```
{1, 3, 5}
```
```
Returns: "Possible"
```
There are three valid orders of these students in the line: 230451, 234051, and 234501.

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.