Stepford HousesProblem code: INSOMA3 |
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
| Date: | 2009-03-19 |
| Time limit: | 7s |
| Source limit: | 50001 |
| Languages: | C C99 strict C++ PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp HASK CAML CLPS PRLG WSPC BF ICK |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
HELP
Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:
- Accepted
Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark. - Time Limit Exceeded
Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach. - Wrong Answer
Your program compiled and ran succesfully but the output did not match the expected output. - Runtime Error
Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section. - Compilation Error
Your code was unable to compile. When you see this icon, click on it for more information.
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
12-5 12-7 7-5 20-16 12-21
12-21 is not in the wrong
12-21 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