SINGTOUR-Editorial

infinitepro · October 20, 2019, 12:55pm

PROBLEM LINK:

Practice

Editorialist: Adithya Dsilva

DIFFICULTY:

EASY

PREREQUISITES:

Sorting, Pair (its equivalent in your language)

PROBLEM:

You are given the voice ranges \{L,U\} of N singers.
If singers i and j\space(i\not=j) compete with each other,

singer i gets 2 points if range \{L_i,U_i\} completely covers range \{L_j,U_j\} and some more values.
singer j gets 2 points if range \{L_j,U_j\} completely covers range \{L_i,U_i\} and some more values.
otherwise, both singers i and j get 1 point each.

The lower and upper bounds of all the singers are distinct.

Given that every singer competes with every other singer exactly once, determine the total points scored by each person at the end.

EXPLANATION:

For the sake of convenience, let us consider singers i and j such that L_i < L_j.

What are the different possibilities of intersection between the voice ranges \{L_i,U_i\} and \{L_j,U_j\} of singers i and j?

Partial Intersection: In this, L_i < L_j < U_i < U_j.
No Intersection: Here, L_i < U_i < L_j < U_j.
Complete Intersection: In this scenario, L_i < L_j < U_j < U_i.

These are the only 3 cases (can be verified trivially)!

Case (1) and (2) gives singers i and j one point each. Case (3) however gives singer i two points and singer j no points.

Notice that singer i always gets at least 1 point, whatever the intersection with the range of singer j is.
Also note that the only case when singer i gets +2 is when U_j < U_i.

Could we try generalizing the above observations?

Claim : If L_i < L_j for some (valid) singers i and j, singer i gets at least 1 point on competing with singer j.

Proof

We follow from the 3 cases mentioned above.
Notice that Complete Intersection is the only case which gives 0 points to one singer.
However, this case (where singer i gets 0 points) is not possible (why?) as L_i < L_j.

Thus, when L_i < L_j, singer i gets at least 1 point.

We can now extend this claim the other way round, that is

Claim : If U_j < U_i for some (valid) singers j and i, singer i gets at least 1 point on competing with singer j.

Proof

<almost-copy-pasted-part>
Notice that Complete Intersection is the only case which gives 0 points to one singer.
However, this case (where singer i gets 0 points) is not possible (why?) as U_j < U_i.

Thus, when U_j < U_i, singer i gets at least 1 point.

</almost-copy-pasted-part>

Let us combine the above claims and apply them to the 3 cases mentioned above (with L_i < L_j).

Case 1

Partial Intersection: In this, L_i < L_j < U_i < U_j.

L_i < L_j \Rarr Singer i gets 1 point. \text{(Claim 1)}
U_i < U_j \Rarr Singer j gets 1 point. \text{(Claim 2)}

Thus, singers’ i and j get 1 point each. This is true.
Verified for Case 1.

Case 2

No Intersection: Here, L_i < U_i < L_j < U_j.

L_i < L_j \Rarr Singer i gets 1 point. \text{(Claim 1)}
U_i < U_j \Rarr Singer j gets 1 point. \text{(Claim 2)}

Thus, singers’ i and j get 1 point each. This is true.
Verified for Case 2.

Case 3

Complete Intersection: In this scenario, L_i < L_j < U_j < U_i.

L_i < L_j \Rarr Singer i gets 1 point. \text{(Claim 1)}
U_j < U_i \Rarr Singer i gets 1 point. \text{(Claim 2)}

(Notice the U_j < U_i above, as compared to the U_i < U_j in the other cases!)

Thus, singer i gets 2 points, while singer j gets 0 points. This is true.
Verified for Case 3.

While processing the L/U in the above claims, notice that we never relied on the corresponding U/L range, respectively. This implies that both the claims could be executed independently, and their results combined thereafter.
This is an important observation that leads us to the following intuition :

The total points scored by a singer i \rarr (the number of singers x with L_i < L_x) + (the number of singers y with U_y < U_i)

The reader is advised to verify the above statement with examples!
The proof for this can be trivially obtained by applying \text{(Claim 1)} and \text{(Claim 2)} on singer i with all other singers!

Verification

We shall use the sample test case given.

N=3
Voice range’s \Rarr\{10,22\}, \{13,21\}, \{15,20\}

Singer 1

Number of singers x with L_1 < L_x \Rarr 2
Number of singers x with U_x < U_1 \Rarr 2

Thus, points scored by singer 1 \Rarr 4

Singer 2

Number of singers x with L_2 < L_x \Rarr 1
Number of singers x with U_x < U_2 \Rarr 1

Thus, points scored by singer 2 \Rarr 2

Singer 3

Number of singers x with L_3 < L_x \Rarr 0
Number of singers x with U_x < U_3 \Rarr 0

Thus, points scored by singer 3 \Rarr 0

Thus the points scored by the singers are 4, 2, 0 respectively, which is true!

Thus, for singer i, total points scored is equal to

|\text{Singers $x$ with }L_i<L_x| + |\text{Singers $y$ with }U_y<U_i|

where |\dots| represent the size of the set.

An efficient method to calculate the terms in the above equation would be by sorting the input according to the order of the L and U values (separately, as they are independently calculated) and finding the count of terms after/before a particular L/U value in the sorted array.

Very vague right? I know! A detailed explanation is given in the implementation section below!

IMPLEMENTATION:

Since we are computing points scored over range L and U independently, we would want to have two arrays to store the values separately.
The final answer for each of the N singers is stored in array Sol[N]. All values are initially 0.
- Make an array of pair<int, int> to store the values of L for every singer i.
  The values in the pair<> correspond to \{L_i, i\} which represents the left range of singer i.
  Let this array be array L.
- Make a similar array of pair<int, int> to store the values of U for every singer i. The pair<> is mapped similar to the above array (\{U_i, i\}). Let this array be array U.
An ideal C++ container would be vector<pair<int, int>> L, U.
Next we sort both the arrays, according to ascending order of the first term of the pair.
This is easily achieved in C++ using sort(L.begin(), L.end()).
Now, we iterate through the arrays. Let us start by iterating through array L.
At any point k in the iteration, we know that L[k].first < L[k + 1].first over all k (since its sorted in this fashion). Thus the count of singers with start range more than L[k].first is (N-1)-k (assuming we’re using 0-based indexing).
Therefore, there are (N-1)-k singers whose lower ranges are greater than the lower range of singer L[k].second. So we add N-1-k to Sol[L[k].second].
We iterate through array R similarly. However, the only difference is that, at a point k, there are exactly k singers with upper range less than the U[k].first (taking 0-based indexing). So we add k to Sol[U[k].first].
Finally, we print the values from Sol[], which correspond to the total points scored by each singer!

SOLUTION SNIPPET:

sort(L.begin(), L.end()); //Sort based on first element of the pair
sort(U.begin(), U.end());

for(int k = 0; k < N; k++)
	Sol[L[k].second] += N - 1 - k; //Add N - 1 - k to Sol[L[k].second]
        
for(int k = 0; k < N; k++)
	Sol[U[k].second] += k; //Add k to Sol[U[k].second]
        
//print the final answer
for(auto i : Sol)
	cout << i << " ";

cout << endl;

TIME COMPLEXITY:

Sorting the two arrays takes O(N\log N). Since only 1 iteration is being done through both the arrays, the time complexity of this task is O(N).

The overall complexity is thus

O(N\log N+N) \approx O(N\log N)

SOLUTIONS:

Editorialist’s solution can be found here.