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.