hunger-games

You have reached the final level of Hunger Games and as usual a tough task awaits you.
You have a circular dining table and N hungery animals.You need to place them on the table.Each animal has a hunger value.
You can place the animals in any order on the circular table.Once you place them you need to calculate the Danger value of your arrangement.
The danger value of the arrangement is the maximum difference of hunger values of all the adjacent seated animals.You need to keep this danger value as low as possible.

Input:
The first line contains N integers.
The second line contains the hunger values of N animals.  

Output:
Print the minimum possible danger value.  

Constraints:
3 ≤ N ≤ 1000
1 ≤ Hunger Value ≤ 1000  

SAMPLE INPUT
4
5 10 6 8

SAMPLE OUTPUT
4

Explanation

The optimal arrangement is :

           5

    /             \
 6                  8
     \           /
          10

The adjacent pair values are 1 for(6-5),3 for(8-5),4 for(10-6),2 for(10-8).Since danger value is the maximum value so it's 4.

Source: hackerearth | Difficulty: EASY
Tags: Sorting

Mathematics


Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'


def final_table (animalsHunger):
	length = len(animalsHunger)
	table = [None] * length
	end = length-1
	middle = int (length/2)

	table[0] = animalsHunger[0]
	table[middle] = animalsHunger[end]

	assing_value (table,animalsHunger,0,middle,end,1)

	return table



def assing_value(list_dest, list_sorce, inicial, middle, end,incremet):
	empty = True
	pos_list_sorce_min = (2 * incremet) -1
	pos_list_sorce_max = (end - pos_list_sorce_min)
	
	index = calc_index(end, inicial, incremet)
	empty_index = find_empty(list_dest,index)

	if ( empty_index == -1):
		empty = False
	else:
		list_dest[empty_index] = list_sorce[pos_list_sorce_min]

	index = calc_index(end, inicial, -incremet)
	empty_index = find_empty(list_dest,index)

	if (empty_index == -1):
		empty = False
	else:
		list_dest[empty_index] = list_sorce[pos_list_sorce_min+1]

	index = calc_index(end, middle, incremet)
	empty_index = find_empty(list_dest,index)

	if (empty_index == -1):
		empty = False
	else:
		list_dest[empty_index] = list_sorce[pos_list_sorce_max]

	index = calc_index(end, middle, -incremet)
	empty_index = find_empty(list_dest,index)

	if (empty_index == -1):
		empty = False
	else:
		list_dest[empty_index] = list_sorce[pos_list_sorce_max-1]	
	
	if (empty):
		assing_value(list_dest, list_sorce, inicial, middle, end,incremet+1)



def find_empty (list1, index):
	end = len(list1) -1

	if (list1[index] == None):
		return index
	else:
		index_temp = calc_index(end,index,1)
		if (list1[index_temp] == None):
			return index_temp
		else:
			index_temp = calc_index(end,index,-1)
			if (list1[index_temp] == None):
				return index_temp
			else:
				return -1

def calc_index(end,refernce, incremet):
	index = refernce + incremet
	if (index > end):
		return index % (end+1)
	elif (index < 0): 
		if (abs(index) % (end+1) == 0):
			return 0
		else:
			return end + 1 - (abs(index) % (end+1))
	else:
		return index


def hunger_games (animalsHunger):

	animalsHunger.sort()

	table = final_table(animalsHunger)

	max_hunger = 0

	for i, animal in enumerate(table):
		if (i > 0 and i < len(table)-1):
			max_hunger = max(abs(animal - table[i-1]), abs(animal - table[i+1]), max_hunger)
		else:
			if (i == 0):
				max_hunger = max(abs(animal - table[len(table)-1]), max_hunger)		
	
	print(max_hunger)

	

input ()
animalsHunger = list(map(int,input().split(' ')))

hunger_games (animalsHunger)




n=eval(input())
ans=0
l=sorted(map(int,input().split()))
for i in range(0,len(l)-2):
	a=abs(l[i]-l[i+1])
	b=abs(l[i]-l[i+2])
	c=max(a,b)
	if c>ans:
		ans=c
print(ans)
		
	


import sys

input()

N = list(map(int, input().strip().split()))
N.sort()
if len(N) == 3: 
	print(N[2] - N[0])
	sys.exit()

maxDVal = 0
for i in [2,3]:
	j = i
	while j < len(N):
		curDVal = N[j] - N[j-2]
		if curDVal > maxDVal: maxDVal = curDVal
		j += 2
		
print(maxDVal)



'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
n=int(input())
assert n>2 and n<=1000
h=input().split()
for i in range(0,len(h)):
	h[i]=int(h[i])
	assert h[i]>0 and h[i]<=1000
h=sorted(h)
m=h[1]-h[0]
for i in range(0,len(h)-2):
	d=h[i+2]-h[i]
	if d>m:
		m=d
d=h[n-1]-h[n-2]
if d>m:
	m=d
print(m)


if __name__ == '__main__':
	n = int(input())
	h_v = (list(map(int, input().split())))
	assert 3 <= n <= 1000
	assert len(h_v) == n
	h_v.sort()
	one = []
	two = []
	counter = 1
	for each in h_v:
		if counter % 2 == 0:
			two.append(each)
		else:
			one.append(each)
		counter += 1
	two.reverse()
	final = one + two
	print(max([abs(j-i) for i, j in zip(final[:-1], final[1:])]))