Page 1 of 2

10057 - A mid-summer night's dream.

Posted: Mon Jun 24, 2002 10:54 am
by cyfra
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...

Posted: Mon Jun 24, 2002 11:11 am
by 10153EN
I think you *may* intercept the problem description a bit wrongly.

Could you tell me what's the output for the following inputs?
6
1
2
3
8
100
9000
4
2
2
5
10

Posted: Mon Jun 24, 2002 11:25 am
by cyfra
My program gives:
3 1 6
2 2 4
I think it is OK.
Or maybe it isn't ??

Posted: Mon Jun 24, 2002 11:31 am
by 10153EN
My program gives
3 2 6
2 3 4
I think you intercept the output of the problem a bit wrongly.
You want to think it more carefully or need hints?

Posted: Mon Jun 24, 2002 11:47 am
by cyfra
Got it :D

I have really misunderstood the meaning :oops:

But now I have changed it and still have WA...

Maybe you have other inputs ??

Thanks in advance :)

Posted: Mon Jun 24, 2002 12:14 pm
by cyfra
Found my misteke....

I forgot that there could be 0 in the input :oops:

Thanx for reading :wink:

Exceeding time limit!

Posted: Mon Oct 14, 2002 4:41 pm
by haaaz
My algorithm is like this:
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 )
step 3 and step 4 counts the underlined elements in the following example:
1 2 5 5 5 5 6 6 7 98 9999
How can I improve efficiency?

Hi!

Posted: Tue Oct 15, 2002 7:47 am
by cyfra
So about efficiency :
change method of sorting. Shell sort is not so efficient :wink:

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 :wink:

Posted: Thu Oct 17, 2002 3:06 pm
by haaaz
I have solved the efficiency problem. But I still got WA.

Is my output correct?

input:
7
0
3
3
3
3
8
9
my program gives
3 4 1

Posted: Tue May 06, 2003 11:34 am
by Amir Aavani
i think your algorithm has problem when n is odd.
consider the following example :
2 2 2 3 3 3 5
your algorithm say that 2 ( num[7 / 2] ) and 3 ( num[7/2 +1]) both are the answer, but

2 2 2 3 3 3 5
2:0 0 0 1 1 1 3 = 6
3:1 1 1 0 0 0 2 = 5

Posted: Fri May 30, 2003 6:35 am
by linux_akbar
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!!!

Posted: Fri May 30, 2003 6:36 pm
by cytse
Try to use other compilers, like gcc, but if you cannot get other compilers, just simply write your program with a small array and test with small data. Before you submit, change the size of array to the required one.

I don't think there are cases with n=0.

Posted: Fri Jul 04, 2003 3:26 pm
by r.z.
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?

Posted: Sat Apr 30, 2005 10:14 pm
by tan_Yui
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?
I solved this problem 10057 & got AC just now. I also confused with those descriptions.

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
Output is

Code: Select all

2 3 1
6 4 2
1 2 2 2 4
--- 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.

Posted: Tue Dec 20, 2005 10:05 pm
by mamun
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.
I'm passing all the samples posted here.