10057  A midsummer night's dream.
Moderator: Board moderators
10057  A midsummer night's dream.
Hi!
I have a small problem with this task...
It looks quite easy  you only have to find median and say how many numbers are medians....
Do you know any tricky inputs for this task ??
Because I have WA
Pls help...
I have a small problem with this task...
It looks quite easy  you only have to find median and say how many numbers are medians....
Do you know any tricky inputs for this task ??
Because I have WA
Pls help...
Exceeding time limit!
My algorithm is like this:
step 3 and step 4 counts the underlined elements in the following example:1) sort all inputs in array with shell sort
2) output the median (i.e. a[total/2])
3) while ( a[total/2] == a[total/2  j] )
count++; j++
4) j=0;
while ( a[total/2+1] == a[total/2 + 1 + j] )
count++; j++
5) output count & ( a[total/2+1]  a[total/2] + 1 )
How can I improve efficiency?1 2 5 5 5 5 6 6 7 98 9999
Hi!
So about efficiency :
change method of sorting. Shell sort is not so efficient
You can see that all input values will be less than 65000 (or something like this
So you can prepare an array with 65000 elements and use sorting in O(n) time.
And I think that this will help you to improve your efficiency.
Good Luck
change method of sorting. Shell sort is not so efficient
You can see that all input values will be less than 65000 (or something like this
So you can prepare an array with 65000 elements and use sorting in O(n) time.
And I think that this will help you to improve your efficiency.
Good Luck

 New poster
 Posts: 30
 Joined: Wed Oct 23, 2002 6:53 am

 New poster
 Posts: 1
 Joined: Thu May 29, 2003 9:18 am
Hallo, I got problem with problem number 10057. It's look easy. But I got stucked with the input.
The problem said, ".... Each block will start with a number n (0<n<=1000000) indicating how many numbers....". How can I prepare 1000000 array in my program!!!! The memory won't enough. My compiler, BC 3.1 said "the array size is too large".
The second problem is if someone inputs 0 then there will be no A. What should my program prints in stdout?
Help me, please!!!
The problem said, ".... Each block will start with a number n (0<n<=1000000) indicating how many numbers....". How can I prepare 1000000 array in my program!!!! The memory won't enough. My compiler, BC 3.1 said "the array size is too large".
The second problem is if someone inputs 0 then there will be no A. What should my program prints in stdout?
Help me, please!!!
can you explain me about the output
For each set of input there will be one line of output. That line will contain the minimum possible value for A. > I understand this one
but I'm a bit confused with these two
Next it will contain how many numbers are there in the input that satisfy the property of A (The summation of absolute deviation from A is minimum). And finally you have to print how many possible different integer values are there for A (these values need not be present in the input). These numbers will be separated by single space.
can someone make it clear to me?
For each set of input there will be one line of output. That line will contain the minimum possible value for A. > I understand this one
but I'm a bit confused with these two
Next it will contain how many numbers are there in the input that satisfy the property of A (The summation of absolute deviation from A is minimum). And finally you have to print how many possible different integer values are there for A (these values need not be present in the input). These numbers will be separated by single space.
can someone make it clear to me?
I solved this problem 10057 & got AC just now. I also confused with those descriptions.r.z. wrote:can you explain me about the output
For each set of input there will be one line of output. That line will contain the minimum possible value for A. > I understand this one
but I'm a bit confused with these two
Next it will contain how many numbers are there in the input that satisfy the property of A (The summation of absolute deviation from A is minimum). And finally you have to print how many possible different integer values are there for A (these values need not be present in the input). These numbers will be separated by single space.
can someone make it clear to me?
The second output value is the number that how many medians are there in the data set.
Of course, there may be one or two medians.
We have to count how many data which are same value as median.
Please see the following input :
Code: Select all
5
1
2
2
2
4
8
3
5
6
6
7
7
10
11
Code: Select all
2 3 1
6 4 2
 median = 2, and there are three same values in the data set.
3 5 6 6 7 7 10 11
 median = 6 and 7, and there are four same values (two 6 + two 7) in the data set.
The third output value is the defference(?) between two medians. In the case of above, median are 6 & 7, so we should calculate 7  6 + 1 = 2.
If n is odd (1, 3, 5, ...), the output is 1.
This problem needs large size of memory, so if you want to be ranked high, you should do sort quickly.
My code is too slow...
Best regards.
Problem descripiton was really confusing to me. Thanks to tan_Yui for explaining it. But I am still getting WA. Can somebody say if I am correct with my understanding?
 1st number to output is the median
2nd number to output is the frequency of median(s) in the input
3rd number to output is 1 if n is odd, median2  median1 + 1 otherwise.