You are not logged in. Please login at www.codechef.com to post your questions!

×

DELHISTR - Editorial

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

mmmreddy's gravatar image

0★mmmreddy
121
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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

question asked: 12 Jan, 15:56

question was seen: 144 times

last updated: 12 Jan, 15:56