Author: Misha Chorniy
Tester: Sergey Kulik
Editorialist: Pawel Kacprzak
Given integers a, b, c, d find the number of integer solutions of inequality x < y, where a ≤ x ≤ b and c ≤ y ≤ d. In one test file there are several test cases to handle.
Iterate through all possible values of x and for each one, count the number of valid values of y to pair with it.
In the first subtask, we know that a, b, c, d ≤ 103. For such low constraints, it can observed that in any valid pair of x < y, both x and y are less or equal than 103 as well. With this observation, it is possible to iterate over all possible x, y ≤ 103. Thus, for each fixed pair x, y, we can explicitly check if x < y and add 1 to the result if the inequality is fulfilled.
In the second subtask we have a, b, c, d ≤ 106, so iterating over all possible values of x and y explicitly is not possible here. However, constraints are small enough to iterate over all possible values of one of the variables. Let’s say that we are going to iterate explicitly over all possible values of x. For one such fixed value of x, the problem reduces to how many values of y are there such that c ≤ y ≤ d and x < y. In other words, the task is to count the number of integers y, such that y ≥ max(c, x + 1) and y ≤ d. Let’s assume that c ≤ d, otherwise, there are no valid values of y of course. It follows, that for a fixed x, there are d - max(c, x+1) + 1 valid values of y, because the number of integers in a range [R1, R2] is given by R2 - R1 + 1.
The final result is the accumulated result for each possible value of x computed as described above. Total time complexity of this method is linear in terms of the number of possible values of x, which is at most 106.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution will be uploaded soon.
Tester’s solution can be found here.
Editorialist’s solution can be found here.