Count Inversions

Count Inversions

Hard PHP PHP Arrays 31 views
Explanation Complexity

Problem Statement

Count pairs i a[j].

Input Format

First n. Next line n integers.

Output Format

One integer inversions.

Example

5
2 4 1 3 5
3

Constraints

n

Input / Output Format

Input Format
First n. Next line n integers.
Output Format
One integer inversions.
Constraints
n

Examples

Input:
5 2 4 1 3 5
Output:
3

Example Solution (Public)

PHP 
<?php
$inputText=trim(stream_get_contents(STDIN));
if($inputText==='') exit;
$tokens=preg_split('/\\s+/', $inputText);
$idx=0; $n=intval($tokens[$idx++] ?? 0);
$a=[];
for($i=0;$i<$n;$i++) $a[] = intval($tokens[$idx++] ?? 0);
function sortCount($arr,&$inv){
  $n=count($arr);
  if($n<=1) return $arr;
  $mid=intdiv($n,2);
  $left=array_slice($arr,0,$mid);
  $right=array_slice($arr,$mid);
  $left=sortCount($left,$inv);
  $right=sortCount($right,$inv);
  $i=0; $j=0; $output=[];
  while($i<count($left) && $j<count($right)){
    if($left[$i] <= $right[$j]) $output[]=$left[$i++];
    else{ $output[]=$right[$j++]; $inv += (count($left)-$i); }
  }
  while($i<count($left)) $output[]=$left[$i++];
  while($j<count($right)) $output[]=$right[$j++];
  return $output;
}
$inv=0;
sortCount($a,$inv);
echo strval($inv);
?>

Official Solution Code

<?php
$inputText=trim(stream_get_contents(STDIN));
if($inputText==='') exit;
$tokens=preg_split('/\\s+/', $inputText);
$idx=0; $n=intval($tokens[$idx++] ?? 0);
$a=[];
for($i=0;$i<$n;$i++) $a[] = intval($tokens[$idx++] ?? 0);
function sortCount($arr,&$inv){
  $n=count($arr);
  if($n<=1) return $arr;
  $mid=intdiv($n,2);
  $left=array_slice($arr,0,$mid);
  $right=array_slice($arr,$mid);
  $left=sortCount($left,$inv);
  $right=sortCount($right,$inv);
  $i=0; $j=0; $output=[];
  while($i<count($left) && $j<count($right)){
    if($left[$i] <= $right[$j]) $output[]=$left[$i++];
    else{ $output[]=$right[$j++]; $inv += (count($left)-$i); }
  }
  while($i<count($left)) $output[]=$left[$i++];
  while($j<count($right)) $output[]=$right[$j++];
  return $output;
}
$inv=0;
sortCount($a,$inv);
echo strval($inv);
?>
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.