new-world-11

The time has arrived when the world is going to end. But don't worry, because the new world yuga will start soon. Manu (carrier of mankind) has been assigned the job to carry all the necessary elements of current yuga to the upcoming yuga.

There are N stones arranged in a straight line. In order to fulfill the task, Manu has to travel from the first stone to the last one in a very specific way. First of all, he has to do it using exactly K jumps. In a single jump, he can jump from a stone with coordinate xi to a stone with coordinate xj if and only if xi < xj. We denote the value xj - xi as the length of such a jump.

Your task is to help Manu minimize the maximum length of a jump he makes in his journey, in order to reach the last stone in exactly K jumps and save the mankind. This is the answer you have to provide.

Input:

In the first line, there is a single integer T denoting the number of test cases to handle. Then, description of T tests follow. In the first line of each such description, two integers N and K are given. This is followed by N space separated integers in the second line, each one denoting a single stone location.

Output:

Output exactly T lines, and in the i^th of them, print a single integer denoting the answer to the i^th test case.

Constraints:

1 ≤ T ≤ 10
2 ≤ N ≤ 10^5
1 ≤ K ≤ (N-1)
1 ≤ Coordinates of stones ≤ 10^9

Note:

It is not necessary that Manu steps on each stone.

Location of all stones are given in ascending order.SAMPLE INPUT
2
4 1
2 15 36 43 
3 2
27 30 35 

SAMPLE OUTPUT
41
5

Explanation

Case #1: Since we have to make exactly 1 jump, we need to jump directly from the first stone to the last one, so the result equals 43 - 2 = 41.

Case#2: Since we have to make exactly 2 jumps, we need to jump to all of the stones. The minimal longest jump to do this is 5, because 35 - 30 = 5.

Source: hackerearth | Difficulty: EASY
Tags: Sorting

Greedy algorithms


Solutions:
stone= [0] * 10000000
def check(jump,n,k):
	i=ans=0
	j=0
	j1=0
	flag=0
	for i in range(n):
			   
		while(j<n and stone[j]-stone[j1]<=jump):
			j+=1
		ans+=1
		j1=j-1;
		if(j==n):
		   flag=1
		   break
	if(ans<=k and flag==1):
	   return 1
	return 0

if __name__ == "__main__":
	testcases = eval(input())
	for caseNr in range(1, testcases+1):
	   
		temp = list(map(int,input().split()))
		arr = list(map(int,input().split()))
		#stone[i]=arr[i]+stone[i]
		for i in range(temp[0]):
			stone[i]=arr[i]
		low=0
		high=1e9
		mid=0
		while(low<high):
			mid=(low+high)//2
			if(check(mid,temp[0],temp[1])):
				high=mid                
			else:
				low=mid+1
		print(int(high))
			


def func(s,val):
	cfc=0
	x=0
	length=len(s)
	for i in range(length):
		if x+s[i]<=val:
			x+=s[i]
		else:
			cfc+=1
			x=s[i]
	return cfc+1		
t=eval(input())
for i in range(t):
	l1=list(map(int,input().strip().split()))
	n=l1[0]
	j=l1[1]
	route=list(map(int,input().strip().split()))
	s=[]
	minimum=0
	for k in range(1,n):
		x=route[k]-route[k-1]
		s.append(x)
		if x>minimum:
			minimum=x
	large=route[n-1]-route[0]
	
	if j==1:
		print(large)
		continue
	r=func(s,minimum)
	if r==j:
		print(minimum)
		continue
	
	while minimum<large:
		if large-minimum==1:
			if func(s,minimum)<=j:
				print(minimum)
			else:
				print(large)
			break
		now=(large+minimum)/2
		r=func(s,now)
		if r<=j:
			large=now
		else:
			minimum=now


def func(s,val):
	cfc=0
	x=0
	length=len(s)
	for i in range(length):
		if x+s[i]<=val:
			x+=s[i]
		else:
			cfc+=1
			x=s[i]
	return cfc+1		
t=eval(input())
for i in range(t):
	l1=list(map(int,input().strip().split()))
	n=l1[0]
	j=l1[1]
	route=list(map(int,input().strip().split()))
	s=[]
	minimum=0
	for k in range(1,n):
		x=route[k]-route[k-1]
		s.append(x)
		if x>minimum:
			minimum=x
	large=route[n-1]-route[0]
	
	if j==1:
		print(large)
		continue
	r=func(s,minimum)
	if r==j:
		print(minimum)
		continue
	
	while minimum<large:
		if large-minimum==1:
			if func(s,minimum)<=j:
				print(minimum)
			else:
				print(large)
			break
		now=(large+minimum)/2
		r=func(s,now)
		if r<=j:
			large=now
		else:
			minimum=now


mod = 10**9 + 7
stone= [0] * 10000000
def check(jump,n,k , stone):
	i=ans=0
	j=0
	j1=0
	flag=0
	for i in range(n):
			   
		while(j<n and stone[j]-stone[j1]<=jump):
			j+=1
		ans+=1
		j1=j-1;
		if(j==n):
		   flag=1
		   break
	if(ans<=k and flag==1):
	   return 1
	return 0


test = int(input())
for i in range(test):
	n , k = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	for i in range(n):
		stone[i] = arr[i]
	l , h = 1 , 10**9
	while l <= h:
		mid = (l + h) // 2
		if check(mid , n , k , stone):
		
			h = mid - 1
		else:
			l = mid + 1
	print(int(h) + 1)
			


stone= [0] * 10000000
def check(jump,n,k):
	i=ans=0
	j=0
	j1=0
	flag=0
	for i in range(n):
			   
		while(j<n and stone[j]-stone[j1]<=jump):
			j+=1
		ans+=1
		j1=j-1;
		if(j==n):
		   flag=1
		   break
	if(ans<=k and flag==1):
	   return 1
	return 0

if __name__ == "__main__":
	testcases = eval(input())
	for caseNr in range(1, testcases+1):
	   
		temp = list(map(int,input().split()))
		arr = list(map(int,input().split()))
		#stone[i]=arr[i]+stone[i]
		for i in range(temp[0]):
			stone[i]=arr[i]
		low=0
		high=1e9
		mid=0
		while(low<high):
			mid=(low+high)//2
			if(check(mid,temp[0],temp[1])):
				high=mid                
			else:
				low=mid+1
		print(int(high))
			


def func(s,val):
	cfc=0
	x=0
	length=len(s)
	for i in range(length):
		if x+s[i]<=val:
			x+=s[i]
		else:
			cfc+=1
			x=s[i]
	return cfc+1		
t=eval(input())
for i in range(t):
	l1=list(map(int,input().strip().split()))
	n=l1[0]
	j=l1[1]
	route=list(map(int,input().strip().split()))
	s=[]
	minimum=0
	for k in range(1,n):
		x=route[k]-route[k-1]
		s.append(x)
		if x>minimum:
			minimum=x
	large=route[n-1]-route[0]
	
	if j==1:
		print(large)
		continue
	r=func(s,minimum)
	if r==j:
		print(minimum)
		continue
	
	while minimum<large:
		if large-minimum==1:
			if func(s,minimum)<=j:
				print(minimum)
			else:
				print(large)
			break
		now=(large+minimum)/2
		r=func(s,now)
		if r<=j:
			large=now
		else:
			minimum=now