CDOUT6-Editorial

editorial
1

PROBLEM LINK

Practice

Contest

Author: Md Majid Jahangir

Tester : Md Majid Jahangir

Editorialist: Md Majid Jahangir

DIFFICULTY:

Cakewalk

PREREQUISITES:

Dynamic programming

PROBLEM:

Sucho and his students went out to the field to play football. During the match, an ice cream guy arrives. Now Sucho wants his students to form a line to avoid chaos. But being a caring teacher, he wants his students to form the line with the least possible moves. All his students are scattered around the field and their position is given by a pair (x, y) of integer coordinates. Students can move- in one move, one student can go 1 unit up, down, left or right(hence, he can change his x or his y co-ordinate by 1 or -1 in one move). The students want to get into a horizontal line next to each other (so that their final positions are (x, y), (x+1, y), …, (x+N-1, y), for some x and y). Integers x and y, as well as the final order of soldiers along the horizontal line is arbitrary. Two or more students can never occupy the same position at the same time. Sucho is busy managing his students. Can you help him determine the minimum total number of moves of all the students that takes them into such configuration?/p> EXPLANATION: In this problem, the final position of each student can be determined individually, irrespective of the positions of the other students. Here, the y will be same for all the resultant positions. Hence, the final y coordinate can be determined by finding the median of all the given y coordinates. Now, to determine the starting x coordinate, the values of x of all students are iterated from lowest to highest and their respective difference from i, where 0 ≤ i < N is calculated and stored in an array. The median of this array is the final starting x coordinate. The closest student to every (x+i, y) position occupies the position, and hence the distance is calculated.

C Code:

#include <stdio.h>
#include <stdlib.h>
#define MAX_STUDENTS 10000

struct t_student
{
	int x, y;
} students[MAX_STUDENTS];

int sort_y(const void *a,const void *b)
{
	if (((struct t_student *) a)->y > ((struct t_student *) b)->y )
		return 1;

	if (((struct t_student *) a)->y < ((struct t_student *) b)->y )
		return -1;

	return 0;
}

int sort_x(const void *a,const void *b)
{
	if (((struct t_student *) a)->x > ((struct t_student *) b)->x)
		return 1;

	if (((struct t_student *) a)->x < ((struct t_student *) b)->x)
		return -1;

	return 0;
}

int sort_x_dec(const void *a, const void *b)
{
	if (*((int *) a) > *((int *) b))
		return 1;

	if (*((int *) a) < *((int *) b) )
		return -1;

	return 0;
	}

int main()
{
	int i, N;
	int dest_y, dest_x;
	int x_dec[MAX_STUDENTS];
	long ans;

	scanf( "%d", &N );
	for (i = 0;i < N;i++)
	{
		scanf("%d%d",&(students[i].x), &(students[i].y));
	}

	qsort(students, N, sizeof(students[0]), sort_y);

	dest_y=students[N / 2].y;

	qsort(students, N, sizeof(students[0]), sort_x);

	for (i = 0;i < N;i++)
		x_dec[i]=students[i].x - i;

	qsort(x_dec, N, sizeof(x_dec[0]), sort_x_dec);
	
	dest_x = x_dec[N / 2];

	ans = 0;

  	for (i = 0;i < N;i++)
    	ans += abs(students[i].x - (dest_x + i)) + abs(students[i].y - dest_y);

    printf("%ld",ans);
    return 0;
}