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.

Post by cyfra » Mon Jun 24, 2002 10:54 am

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:

Post by 10153EN » Mon Jun 24, 2002 11:11 am

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

Post by cyfra » Mon Jun 24, 2002 11:25 am

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:

Post by 10153EN » Mon Jun 24, 2002 11:31 am

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

Post by cyfra » Mon Jun 24, 2002 11:47 am

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

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

Post by cyfra » Mon Jun 24, 2002 12:14 pm

Found my misteke....

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

Thanx for reading :wink:

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

Exceeding time limit!

Post by haaaz » Mon Oct 14, 2002 4:41 pm

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!

Post by cyfra » Tue Oct 15, 2002 7:47 am

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:

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

Post by haaaz » Thu Oct 17, 2002 3:06 pm

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

Post by Amir Aavani » Tue May 06, 2003 11:34 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

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

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Post by cytse » Fri May 30, 2003 6:36 pm

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

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

Post by tan_Yui » Sat Apr 30, 2005 10:14 pm

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
Location: Bangladesh
Contact:

Post by mamun » Tue Dec 20, 2005 10:05 pm

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.

Post Reply

Return to “Volume 100 (10000-10099)”