10041 - Vito's Family

[raj]

1
10 30 25 15 1 1 1 23 23 90 10
for this WHY THE OUTPUT BECOMES 163 INSTEAD OF 211??????????????
PLEASE ANYONE TELL ME?????

[lbv]

1
10 30 25 15 1 1 1 23 23 90 10
for this WHY THE OUTPUT BECOMES 163 INSTEAD OF 211??????????????
PLEASE ANYONE TELL ME?????

Take your time to carefully read the problem statement, and then the previous messages from this forum thread. You should come to realize that Vito should locate his house in a street that is the median of all the numbers given in the input.

For the set of integers { 30 25 15 1 1 1 23 23 90 10 }, the median will be 19 (although any integer between 15 and 23 will work equally well). If you add all the distances from each street to the median, your result will be 163. If you try any other number outside the range [ 15 : 23 ] for Vito's house, you'll notice that the result will be a bigger number, so 163 is the optimal answer.

P.S. As you may know, writing something in ALL CAPS is usually interpreted as "shouting". I'd suggest you try to avoid that in a forum like this one.

[raj]

:@ lbv i am extremely sorry for mistakes
i didnt know how to get medians but now i know it
but one thing i can not understand why sometimes MEDIAN doesnt work???
can you please explain...

[lbv]

i am extremely sorry for mistakes

It's okay, we all make mistakes; the important thing is to learn from them .

but one thing i can not understand why sometimes MEDIAN doesnt work???
can you please explain...

I'm not sure what you mean by "median doesn't work". Are you referring to this problem? Do you have an example in mind? If you do, please share it, but carefully check it again. Using the median should always give you the right answer for this problem, so if it doesn't for some reason, it might be a subtle bug in your code.

[raj]

sorry sir...
median works all the time....
i saw a previous post the i think median doesnt work...........
now its accepted... thanks

[mmoonn]

i want to know what is wrong with my code plz,it gives WA

Code: Select all

import java.util.Arrays;
import java.util.Scanner;

public class Main{

	public static int[] streets;

	private static int getDis(int mid) {
		int dis = 0;
		for (int i = 0; i < streets.length; i++) {
			dis += Math.abs(mid - streets[i]);
		}
		return dis;
	}

	public static void main(String[] args) {
		// get median
		Scanner sc = new Scanner(System.in);
		int tests = sc.nextInt();
		int[][] input = new int[tests][];
		sc.nextLine();
		for (int i = 0; i < tests; i++) {
			String[] sp = sc.nextLine().trim().split(" ");
			input[i] = new int[sp.length - 1];
			for (int j = 1; j < sp.length; j++) {
				input[i][j - 1] = Integer.parseInt(sp[j]);
			}
		}

		// evaluate
		for (int i = 0; i < input.length; i++) {
			int mid = 0;
			streets = input[i];
			for (int j = 0; j < input[i].length; j++) {
				mid += input[i][j];
			}
			mid = mid / input[i].length;
			int temp = mid;
			Arrays.sort(streets);
			int min = getDis(mid);
			int j = 0;
			while (j < streets.length) {
				mid += 1;
				int x = getDis(mid);
				if (x < min)
					min = x;
				else
					break;
				j++;
			}
			j = 0;
			mid = temp;
			while (j < streets.length) {
				mid -= 1;
				int x = getDis(mid);
				if (x < min)
					min = x;
				else
					break;
				j++;
			}

			System.out.println(min);
		}
	}
}

[brianfry713]

Input:

Code: Select all

1
6 1 1 1 1 1000 1000

Output should be 1998

[Orni Noor]

I cannot understand why I am getting RUNTIME ERROR in my code. Can anyone please help???

Code: Select all

#include<stdio.h>
#include<stdlib.h>
int compare(const void* p1, const void* p2)
{
    if (*(long*)p1 < *(long*)p2)
    {
    return (-1);
    }
    if(*(long*)p1==*(long*)p2)
    {
    return (0);
    }
    if(*(long*)p1> *(long*)p2)
    {
    return (1);
    }
}
int main()
{
    long n;
    int s,r,i,j,k;
while((scanf("%ld",&n))==1)
{
    scanf("%d",&s);
    long a[500],d[500];
   for(i=0;i<s;i++)
    {
    scanf("%ld",&a[i]);
    }
qsort(a,s,sizeof(long),compare);
long median,sum=0;
if(s%2!=0)
{
    i=(s+1)/2;
    median=a[i-1];
}
else if(s%2==0)
{
    i=s/2;
    j=(s/2)+1;
    median=(a[i-1]+a[j-1])/2;
}
for(k=0;k<s;k++)
{
  d[k]=median-a[k];
  if(d[k]<0)
  {
    d[k]=-d[k];
  }
  sum=sum+d[k];
}
printf("%ld\n",sum);
}
return 0;
}

[uDebug]

Here's some input / output I culled from this thread and that I found useful when testing / debugging.

Input:

Code: Select all

9
2 2 4 
3 2 4 6
6 11 2 1 6 5 11
6 7 8 2 3 6 1
6 1 1 1 1 1000 1000
4 1 2 4 5
10 30 25 15 1 1 1 23 23 90 10
5 1 1 1 2 3 
16 5 49 12 23 29 100 44 47 69 41 23 12 11 6 2 62

AC Output:

Code: Select all

2
4
20
15
1998
6
163
3
347

[uDebug]

I cannot understand why I am getting RUNTIME ERROR in my code. Can anyone please help???

First thing, if you want people to read your code, use the code tags. It improves readability.

Next, your code is going off bounds since you aren't reading in the input correctly.

Since we know how many cases are going to be there, this line

Code: Select all

while((scanf("%ld",&n))==1)

needs to be changed to something like

Code: Select all

/* Read in the number of cases */
scanf("%ld",&n);
/* Process each case */	
for(x = 0; x < n; x++) 
{...

I've made the changes to your program here.
http://pastebin.com/hmcJrDcp
It compiles and runs just fine.

[sejan]

why WA?

Code: Select all

ACCEPTED THANK YOU

[brianfry713]

Make the initial value of temp bigger.
#include <limits.h>
int temp = INT_MAX;

[mpmohi]

1
10 30 25 15 1 1 1 23 23 90 10
for this WHY THE OUTPUT BECOMES 163 INSTEAD OF 211??????????????
PLEASE ANYONE TELL ME?????

Take your time to carefully read the problem statement, and then the previous messages from this forum thread. You should come to realize that Vito should locate his house in a street that is the median of all the numbers given in the input.

For the set of integers { 30 25 15 1 1 1 23 23 90 10 }, the median will be 19 (although any integer between 15 and 23 will work equally well). If you add all the distances from each street to the median, your result will be 163. If you try any other number outside the range [ 15 : 23 ] for Vito's house, you'll notice that the result will be a bigger number, so 163 is the optimal answer.

P.S. As you may know, writing something in ALL CAPS is usually interpreted as "shouting". I'd suggest you try to avoid that in a forum like this one.

though it is very late but how the Medin here can be 19 ?

[brianfry713]

For the set of integers { 1 1 1 10 15 23 23 25 30 90 }, the median will be 19 = (15 + 23) / 2

[mpmohi]

Thanks brainfry713