HackerRank Police Operation problem solution

In this HackerRank Police Operation problem solution, The police department asks Roy to plan this operation. So Roy has to tell them the number of officers to recruit and the routes these officers should take in order to catch all the criminals. Roy has to provide this information while minimizing the total expenses of this operation.

Find out the minimum amount of money required to complete the operation.

Problem solution in Python.

#!/bin/python3

import os
import sys

#
# Complete the policeOperation function below.
#
def cross(f, g):
    return (g[1]-f[1])/(f[0]-g[0])

def policeOperation(h, criminals):
    n = len(criminals)
    dp = 0
    stack = []
    fpos = 0
    for i in range(0,n):
        f = [-2*criminals[i],criminals[i]*criminals[i] + dp,0]
        
        while len(stack) > 0:
            f[2] = cross(stack[-1], f)
            if stack[-1][2] < f[2]:
                break
            stack.pop()
            if len(stack) == fpos:
                fpos -= 1

        stack.append(f)
        x = criminals[i];
        while fpos+1 < len(stack) and stack[fpos+1][2] < x: fpos += 1
        dp = stack[fpos][0] * x + stack[fpos][1] + h + x*x;   

    return dp




if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nh = input().split()

    n = int(nh[0])

    h = int(nh[1])
    result = 0
    if n != 0:
        criminals = list(map(int, input().rstrip().split()))
        result = policeOperation(h, criminals)

    fptr.write(str(result) + '\n')

    fptr.close()

Problem solution in Java.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

  static long square(long x) {
    return x * x; 
  }
  static long[] dp;
  static int[] criminals;

  static long distance(int x, int y) {
    return (square(criminals[y]) - square(criminals[x]) + dp[y] - dp[x]);
  }
  
  static long policeOperation(int n, int h, int[] criminals) {
    dp = new long[n + 1];
    int[] q = new int[n + 1];
    int fr = 0;
    int re = 1;
    for (int i = 1; i <= n; i++) {
      while (fr + 1 < re 
          && 2 * (long)criminals[i-1] * (criminals[q[fr + 1]] - criminals[q[fr]]) > distance(q[fr], q[fr + 1])) {
        fr++;
      }
      dp[i] = dp[q[fr]] + square(criminals[i-1] - criminals[q[fr]]) + h;
      if (i < n) {
        while (fr <= re - 2 
            && distance(q[re - 2], q[re - 1]) / (criminals[q[re - 1]] - criminals[q[re - 2]]) >
        distance(q[re - 1], i) / (criminals[i] - criminals[q[re - 1]])) {
          re--;
        }
        q[re] = i;
        re++;
      }
    }
    return dp[n];
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int h = Integer.parseInt(st.nextToken());

    long result = 0;
    if (h > 0 && n > 0) {
      criminals = new int[n];
      int index = 0;

      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++) {
        int item = Integer.parseInt(st.nextToken());
        if (index == 0 || item > criminals[index]) {
          criminals[index++] = item;
        }
      }
      result = policeOperation(index, h, criminals);
    }

    bw.write(String.valueOf(result));
    bw.newLine();

    br.close();
    bw.close();
  }
}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn=2000001;
double INF = 1e15;

struct line{
	long long k;
	long long b;
	line(long long k=0, long long b=0) :k(k), b(b){};
	bool operator <(const line & rhs) const{
		return k == rhs.k ? b < rhs.b : k < rhs.k;
	}
	double intersect(const line & rhs){
		if (k == rhs.k) return INF;
		return (rhs.b - b)*1.0 / (k - rhs.k);
	}
	bool better(const line pre, const line now){
		return ((long long)(now.k-pre.k))*(pre.b-b) < ((long long)(k-pre.k))*(pre.b-now.b);
	}
};

line li[maxn];

struct convexHull{
	vector<line> vl;
	vector<double> vx;
	long long query(int x){
		if (vl.size() == 1){
			return (long long)((long long)vl[0].k*x + (long long)vl[0].b);
		}
		else{
			int ind = lower_bound(vx.begin(), vx.end(), x)-vx.begin();
			return (long long)((long long)vl[ind].k*x + (long long)vl[ind].b);
		}
	}
    
    void add_line(int ind){//always add line with larger slope
         line p=li[ind];
         while (vl.size()>1){
			line l1 = vl[vl.size() - 2];
			line l2 = vl[vl.size() - 1];
			if (l1.better(l2, p)){
				vl.pop_back();
                vx.pop_back();
			}
			else break;
		}
        vl.push_back(p);
        if(vl.size()>1){
            double intersection=(vl[vl.size()-2].b-vl[vl.size()-1].b)*1.0/(vl[vl.size()-1].k-vl[vl.size()-2].k);
            vx.push_back(intersection);
        }
    }
};

long long a[2000001];
long long dp[2000001];


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int n,h;
    cin>>n>>h;
    if(n==0){
        cout<<0<<endl;
        return 0;
    }
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    dp[0]=h;
    li[0].k=-2*a[0];
    li[0].b=dp[0]+a[0]*a[0];
    convexHull conv;
    conv.add_line(0);
    for(int i=1;i<n;i++){
        long long minV=conv.query(a[i-1])+a[i-1]*a[i-1]+h;
        dp[i]=minV;
        li[i].k=-2*a[i];
        li[i].b=dp[i]+a[i]*a[i];
        conv.add_line(i);
    }
    long long ans=1e18;
    for(int i=0;i<n;i++){
        ans=min(ans,dp[i]+(a[n-1]-a[i])*(a[n-1]-a[i]));
    }
    cout<<ans<<endl;
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
int get_i(double *a,int num,int size);
double med(double *a,int size);
double inter(long long m1,long long n1,long long m2,long long n2);
int a[2000000];
long long dp[2000000],m[2000000],n[2000000];
double aa[2000000];

int main(){
  int N,h,aa_size=0,i,j;
  long long t,tt;
  scanf("%d%d",&N,&h);
  for(i=0;i<N;i++)
    scanf("%d",a+i);
  for(i=0;i<N;i++){
    if(i)
      dp[i]=h+dp[i-1];
    else
      dp[i]=h;
    if(i && a[i]==a[i-1]){
      dp[i]=dp[i-1];
      continue;
    }
    if(aa_size){
      j=get_i(aa,a[i],aa_size-1);
      t=a[i]*(long long)a[i]+m[j]*a[i]+n[j];
      if(t<dp[i])
        dp[i]=t;
    }
    m[aa_size]=-2*a[i];
    if(i)
      n[aa_size]=a[i]*(long long)a[i]+h+dp[i-1];
    else
      n[aa_size]=a[i]*(long long)a[i]+h;
    j=++aa_size;
    while(aa_size>2){
      if(inter(m[aa_size-3],n[aa_size-3],m[j-1],n[j-1])>aa[aa_size-3])
        break;
      aa_size--;
    }
    tt=m[j-1];
    m[j-1]=m[aa_size-1];
    m[aa_size-1]=tt;
    tt=n[j-1];
    n[j-1]=n[aa_size-1];
    n[aa_size-1]=tt;
    if(aa_size>1)
      aa[aa_size-2]=inter(m[aa_size-2],n[aa_size-2],m[aa_size-1],n[aa_size-1]);
  }
  printf("%lld",dp[N-1]);
  return 0;
}
int get_i(double *a,int num,int size){
  if(size==0)
    return 0;
  if(num>med(a,size))
    return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1);
  else
    return get_i(a,num,(size-1)>>1);
}
double med(double *a,int size){
  return a[(size-1)>>1];
}
double inter(long long m1,long long n1,long long m2,long long n2){
  return (n2-n1)/(double)(m1-m2);
}