### PROBLEM LINK:

**Author:** Praveen Dhinwa

**Testers:** Jakub Safin

**Editorialist:** Praveen Dhinwa

### DIFFICULTY:

simple

### PREREQUISITES:

sorting

### PROBLEM:

There are three people in a team. For each person in the team, you know their scores in three skills - hard work, intelligence, and persistence.

You want to check whether it is possible to order these people (assign them numbers from 1 to 3) in such a way that for each 1 \leq i \leq 2, i+1-th person is strictly better than the i-th person.

A person x is said to be \textit{better} than another person y if x doesn’t score less than y in any of the skills and scores more than y in at least one skill.

Determine whether such an ordering exists.

### SOLUTION

### Checking whether a person x is better than y

Let us first check whether a person x is better than person y or not. This can be checked by directly following the definition. We iterate over each skill of the person and check the condition that person x should not score less than y in any skill. We also check whether there exists a skill in which the person x scores more than y.

Let score[3][3] be a 2-D array, where score[i] denotes the score of i-th person the three skills, e.g. The value score[1][2] will denote the score of 2-nd person in 3rd skill.

```
boolean is_better(x, y):
// Person x should not score less that y in any skill
for i = 0 to 2:
if score[y][i] > score[x][i]:
return false
// check whether there exists a skill in which the person x scores more than y
for i = 0 to 2:
if score[x][i] > score[y][i]:
return true
// Otherwise return false
return false
```

### Solution based on trying all orderings of \{1, 2, 3\}.

Now, we can decide all possible permutations/orderings of \{1, 2, 3\} and check whether for some ordering each person is better than it’s next person. There will be total 3! = 6 such orderings. You can either hardcode these orderings or use three for loops or use next_permutation in C++.

**Hard coding the orderings**

```
ord[6][3] = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]}
```

**Using three for loops**

```
for i = 1 to 3:
for j = 1 to 3:
for k = 1 to 3:
if (i == j or j == k or i == k):
continue
// Here (i, j, k) denotes one possible ordering.
```

**Using next_permutation in C++**

```
vector<int> v{1, 2, 3}
do {
// Here the array v denotes one possible ordering.
} while (next_permuatation(v.begin(), v.end()))
```

### A sorting based solution.

We know that if a person x is better than person y and the person y is better than person z, then person x is better than person z. This is called transitive relation. So, we can sort the person based on the order defined by comparing the two people by checking whether a person is better than or other person or not.

The basic insertion sort code will look like this.

```
for i = 0 to 2:
for j = i + 1 to 2:
if (!is_better(i, j)):
swap(score[i], score[j])
// Now the scores are sorted according to better relationship.
```

Now, the above order will be one possible order if there exists an order of arranging the person. So, for that you can go through the above order and check the i+1-th person is better than the i-th person.

You can also sort the persons using by their standard comparisons by comparing them by their lexicographic ordering. Most of the languages have inbuilt functions for this purpose. C++ contains sort function, Python also contains a sort function.

The overall time complexity of both the solutions will be constant time, \mathcal{O}(1). There are 1000 test cases in the problem, which are quite easy to pass within a minute.