10057 - A mid-summer night's dream.

[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...

[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

[cyfra]

My program gives:

3 1 6
2 2 4

I think it is OK.
Or maybe it isn't ??

[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?

[cyfra]

Got it

I have really misunderstood the meaning

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

Maybe you have other inputs ??

Thanks in advance

[cyfra]

Found my misteke....

I forgot that there could be 0 in the input

Thanx for reading

[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?

[cyfra]

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

[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

[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

[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!!!

[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.

[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?

[tan_Yui]

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.

[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.