Count Inversions
Hard
Python
Functions
14 views
Problem Statement
Read n integers. Use function mergesort_count(arr) to return inversion count and output it.
Input Format
First line n. Second line n integers.
Output Format
One integer inversions.
Example
5 2 4 1 3 5
3
Constraints
1
Input / Output Format
Input Format
First line n. Second line n integers.
Output Format
One integer inversions.
Constraints
1
Examples
Input:
5
2 4 1 3 5
Output:
3
Example Solution (Public)
import sys
sys.setrecursionlimit(1_000_000)
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
n=int(p[0])
a=list(map(int,p[1:1+n]))
def sort_count(arr):
ln=len(arr)
if ln<=1:
return arr,0
mid=ln//2
left,inv1=sort_count(arr[:mid])
right,inv2=sort_count(arr[mid:])
i=0
j=0
inv=inv1+inv2
out=[]
while i<len(left) and j<len(right):
if left[i]<=right[j]:
out.append(left[i]); i+=1
else:
out.append(right[j]); j+=1
inv += len(left)-i
if i<len(left):
out.extend(left[i:])
if j<len(right):
out.extend(right[j:])
return out,inv
_,ans=sort_count(a)
sys.stdout.write(str(ans))
Official Solution Code
import sys
sys.setrecursionlimit(1_000_000)
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
n=int(p[0])
a=list(map(int,p[1:1+n]))
def sort_count(arr):
ln=len(arr)
if ln<=1:
return arr,0
mid=ln//2
left,inv1=sort_count(arr[:mid])
right,inv2=sort_count(arr[mid:])
i=0
j=0
inv=inv1+inv2
out=[]
while i<len(left) and j<len(right):
if left[i]<=right[j]:
out.append(left[i]); i+=1
else:
out.append(right[j]); j+=1
inv += len(left)-i
if i<len(left):
out.extend(left[i:])
if j<len(right):
out.extend(right[j:])
return out,inv
_,ans=sort_count(a)
sys.stdout.write(str(ans))
Please login to submit solutions.