Time Has Arrived

QUESTION

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.\n\nThere 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.\n\nYour 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.\n\nInput:\n\nIn 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.\n\nOutput:\n\nOutput exactly T lines, and in the ith of them, print a single integer denoting the answer.

“TESTCASE_1”: “4 1\n2 15 36 43\n###—###SEPERATOR—###—\n41”, “TESTCASE_2”: “3 2\n27 30 35\n###—###SEPERATOR—###—\n5”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include <iostream>
 
using namespace std;
 
long min_len;
 
//brute using backtracking...too slow
void find_max_jump(long *stones,int N,int cur_stone, int jumps_left, long max_len)
{
    if(!jumps_left && cur_stone==N-1)
    {
        //reached end
        if(max_len<min_len)
            min_len=max_len;
    }
    else if(jumps_left)
    {
        for(int i=cur_stone+1;i<N;i++)
        {
            if(jumps_left==1)
                i=N-1;
            if(max_len<stones[i]-stones[cur_stone])
                max_len=stones[i]-stones[cur_stone];
            find_max_jump(stones,N,i,jumps_left-1,max_len);
        }
    }
}
 
int valid_len(long *stones,long m,int N,int K)
{
    //check if we can reach end using max step len of m and min steps
    long prev=0,cur=1,steps=0;
    for(int i=0;i<N && cur<N;i++)
    {
        while(cur<N && stones[cur]-stones[prev]<=m)
            cur++;  //direct jump from prev to cur
        steps++;
        prev=cur-1; //cannot direct jump from prev anymore, update prev
    }
    if(steps>K) //used more than K steps
        return 0;
    else if(cur==N) //reached end using <=K steps
        return 1;
    return 0;
}
 
int main() 
{
        int N,K;
        long stones[100000];
        min_len=0xfffffff;
        
        cin>>N>>K;
        for(int i=0;i<N;i++)
            cin>>stones[i];
        
        //find_max_jump(stones,N,0,K,0);
        long l=1,u=1e9;
        long m;
        long ans=1e9;
        while(l<=u)
        {
            m=(l+u)/2;
            if(valid_len(stones,m,N,K))
            {
                //check smaller len
                u=m-1;
                ans=m;
            }
            else
                l=m+1;
        }
        cout<<ans<<endl;
    return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.