Loading...
Loading...
Loading...
Two judges ranked the same n students in a college coding contest. Students are numbered 1 to n. Each judge gives a list of all n student numbers, from first place to last place.
A pair of students is a disagreement if one judge puts student x above student y, but the other judge puts y above x. Print the number of disagreements.
Example 1
Input
4 1 2 3 4 2 4 1 3
Output
3
The pairs (1, 2), (1, 4) and (3, 4) are ordered differently by the two judges. Every other pair agrees, so the answer is 3.
Example 2
Input
3 3 1 2 3 1 2
Output
0
The judges agree completely.
Try the problem first. Open one hint at a time.
Rename the students by their place in judge B's list. Then write judge A's list using these places.
Now a disagreement is a pair where a bigger place comes before a smaller place in that new list.
Checking every pair is O(n^2), which is too slow for 10^5. Count these pairs while you merge sort the list.
While merging, when a value from the right half is taken before the values left in the left half, every one of those left values forms a pair with it. Use long for the count.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor