×

# DELHISTR - Editorial

 0 Angry Battu Problem: practice Tags: Divide and conquer. Author: Shami. The problem is just a paraphrase around computing inversions in an array. An inversion is a pair of elements in an array such that A[i] > A[j] when i < j. The brute force way is to count all pairs. Complexity: O(N^2). This is not good enough for SubTask2. Given that it requires comparing two elements, the lower bound will be same as lower bound for comparison sorting method i.e. Nlog(N). Let’s break the array in two parts – left and right - and count the number of inversion in both. It still does not give us much information about number of inversions between left and right parts. However, if we sort both the parts, and then merge them, we can definitely tell the relative ordering between left and right. This algorithm works just like merge sort with an extra counter for inversions. asked 12 Jan, 15:56 0★mmmreddy 12●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×132