## 10057 - A mid-summer night's dream.

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

### 10057 - A mid-summer 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...

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
My program gives:
3 1 6
2 2 4
I think it is OK.
Or maybe it isn't ??

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Got it

I have really misunderstood the meaning

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

Maybe you have other inputs ??

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Found my misteke....

I forgot that there could be 0 in the input

haaaz
New poster
Posts: 29
Joined: Sun Sep 08, 2002 8:02 am

### Exceeding time limit!

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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

### 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

haaaz
New poster
Posts: 29
Joined: Sun Sep 08, 2002 8:02 am
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
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 am
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
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?

cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:
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.
Learning poster
Posts: 56
Joined: Thu Jun 05, 2003 1:57 pm
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
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
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.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm