Problem Link
Setter: Hasan Jaddouh
Tester: Amr Mahmoud
Editorialist: Bhuvnesh Jain
Difficulty
EASY
Prerequisites
Looping Techniques
Problem
Find a suitable match for every person depending on some constraints mentioned in the statement.
Explanation
The solution is simply doing what the problem statement says. Just maintain a “wait” variable for all players, which when set to 1 means that the player is still waiting for his chance to pair up with someone, and 0 meaning that the person is already paired up.
Thus, for every player, we start from the first person and proceed in increasing order of their times of arrival and break as soon as we get some matching person whose “wait” variable was set to “1”.
To check if any person matches with someone else, we can simply use “if” statements to check the conditions mentioned in the statement.
- The first condition can be checked as follows : y <= x \text{ and } x <= z, meaning that x lies in the range [y, z]
- The second and third condition can be simply checked by comparing the 2 values i.e. time and “rated/unrated” criteria.
- For last condition, we first check to which category it belongs i.e. \{ \text{random, black, white} \}. Then as per the category, we do the corresponding check for the other player i.e. “random” matches with “random”, “black” with “white” and “white” with “black”.
Time Complexity
O(N^2), per test case.
Space Complexity
O(N)