Stepford Houses

All submissions for this problem are available.
Stepford Street was a dead end street. The houses on Stepford Street were bought by wealthy millionaires. They had them extensively altered so that as one progressed along the street, the height of the buildings increased rapidly. However, not all millionaires were created equal. Some refused to follow this trend and kept their houses at their original heights. The resulting progression of heights was thus disturbed.
A contest to locate the most ordered street was announced by the Beverly Hills Municipal Corporation. The criteria for the most ordered street was set as follows:
If there exists a house with a lower height later in the street than the house under consideration, then the pair (current house, later house) counts as 1 point towards the disorderliness index of the street. It is not necessary that the later house be adjacent to the current house.
Note: No two houses on a street will be of the same height
For example, for the input:
1 2 4 5 3 6
The pairs (4,3), (5,3) form disordered pairs. Thus the disorderliness index of this array is 2.
As the criteria for determining the disorderliness is complex, the BHMC has requested your help to automate the process. You need to write an efficient program that calculates the disorderliness index of a street.
Input
Line 1: N – The size of the array. 1 <= N <= 10^5
Line 2: N integers denoting the heights of the various buildings in order of their locations on the street.
Output
Line 1: The disorderliness index of the street.
Example
Input: 6 1 2 4 5 3 6 Output: 2
Author:  admin 
Tags  admin 
Date Added:  19032009 
Time Limit:  2  7 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 
Its so funny that the same
Its so funny that the same piece of code which was giving TLE some days back ran successfully today.
will the heights of houses be
will the heights of houses be in range 1 to N or it can be anything?
i didn't know this problem
i didn't know this problem can be solved so easily :P
i'm getteing time limit
i'm getteing time limit exceeded.....for N=10000 > 0.24s
but for N=100000 > 14.93s ..how!!!!!!!!
please help me...
i'm very much surprised that
i'm very much surprised that for the problem TURBO SORT (easy)
in which no. of test cases were <10^6 and n<10^6,it took only 3.6sec to do by making and traversing
binary search tree.
but in this problem when no. of case =1 and n<10^5 and time limit is 7 sec ,then just making the binary search tree gives TLE................ :(
i am surprised that my
i am surprised that my solution works for N= 100,000 but get an run time error for N=30,000. I don't understand why? please help
@admin I don't understand
@admin
I don't understand that why is my code giving correct answer and in time for all cases except for N=10000 and N=30000 can you tell me why
How do u solve this in less
How do u solve this in less than O(n^2)
Can we assume that the
Can we assume that the heights of the buildings are only numbers from 1 to N?
No it can be more than N
No it can be more than N also.
my code gets time limit
my code gets time limit exceeded for two test cases (100000,3000) , is this a problem with faster input/output??
yipee Got a correct answer ,
yipee Got a correct answer , was using memset extra :)
@Anurag Aggarwal Make sure
@Anurag Aggarwal
Make sure your scaling works correctly.
@Admins Sir why cant i
@Admins
Sir why cant i submit my solution?
It says wrong pasword or login,while i have already logged in successfuly .. ?
@admin, i am facing same
@admin, i am facing same problem as anurag.. the result says wrong answers only for 30000 and 10000, and correct for rest cases.
@max, scaling of what?
Just making the BST gives
Test N Result
@ Admin: Please care to
I got the right answer :) A
I got the right answer :) A
i got time limit exceeded,
why i m getting wrong answer
why i m getting wrong answer for last two cases???
@Admin: I am amazed why the
@Admin: I am amazed why the solutions (successfully submitted) are producing different results. I am providing the same 10k input file.
I feel that providing the test cases might be a good idea than showing the submitted solutions.
Most likely you are not
Most likely you are not testing them correctly. Input cases can never be revealed or it would ruin the problem.
1000 0.1sec
1000 0.1sec accepted
10000 0.96sec accepted
1 0.0sec accepted
1L 14.93sec TLE
30000 0.06sec accepted
10000 0.02sec accepted
On my machine 1L gives in 0.93 sec :(
Its a simple BST, any suggestions.
Lets say if my input is 74 12
Lets say if my input is
7
4 12 7 5 20 16 21
Will the answer be 4 or 5
125 127 75 2016 1221
1221 is not in the wrong
1221 is not in the wrong order. There are only 4 pairs in the wrong order.
I see comments like.. "1000
I see comments like..
"1000 0.1sec accepted
10000 0.96sec accepted
1 0.0sec accepted
1L 14.93sec TLE
30000 0.06sec accepted
10000 0.02sec accepted"
Does code chef provide such detailed failure reports ? In all the submissions I have made I never get such details. Or do we need to download some explicit test cases from somewhere to get such analysis ?
Don't know how but my (nlogn)
may be bcoz, ur nlogn soln
i don't really understand the
I got the following: Test
i got it correct for 1L but
Is BST good for this
@admin I don't understand
Test N Result
not getting error for 100000
same issue as shrinu...
7.01 second for 100000
Is there any range of height
i don't know how they
san some one tell.. how to
google.com
i solved with merge_sort not
@erzhan don't give hints...
brute force not working ..
O(n log n) passed..:)
O(nlogn) works correctly ...