In this post, we will solve HackerRank Police Operation Problem Solution.
Roy is helping the police department of his city in crime fighting. Today, they informed him about a new planned operation.
Think of the city as a 2D plane. The road along the X-axis is very crime prone, because n criminals live there. No two criminals live at the same position.
To catch these criminals, the police department has to recruit some police officers and give each of them USD h as wages. A police officer can start his operation from any point a. drive his car to point b in a straight line, and catch all the criminals who live on this way. The cost of fuel used by the officer’s car is equal to the square of the euclidean distance between points a and b (Euclidean distance between points (x1,y1) and (x2, y2) equals to root(x1-x2)square + (y1-y2)square
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.
Input Format
The first line contains two integers n (0 ≤ n ≤ 2 x 10 power 6), number of criminals, and h (0 <h< 109), the cost of recruiting a police officer. The next line contains n space separated integers. The ith integer indicates the position of the ith criminal on X-axis (in other words, if the ith integer is x, then location of the ith criminal is (x, 0)). The value of the positions are between 1 and 109 and are given in increasing order in the input.
Output Format
Print the minimum amount of money required to complete the operation.
Sample Input
5 10
1 4 5 6 9
Sample Output
34Explanation
For the sample test case, police department recruits 3 officers who get paid 3 x 10 = 30. The first officer starts at point (1, 0) and catches the criminal there. So he does not use any fuel. The second officer catches criminals at points (4,0), (5,0) and (6, 0). He burns fuel worth USD 4. The third officer catches the criminal at point (9, 0). He also does not burn any fuel. The total money spent by the department is, 30+ 4 = 34,
Police Operation C Solution
#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);
}
Police Operation C++ Solution
#include <algorithm>
#include <cstdio>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define REP1(i, n) for (int i = 1; i <= (n); i++)
#define ROF(i, a, b) for (int i = (b); --i >= (a); )
#define P(x) ((x)*(x))
#define F(x,y) (P(a[(y)+1])-P(a[(x)+1])+dp[y]-dp[x])
int ri()
{
int x;
scanf("%d", &x);
return x;
}
const int N = 2000000;
int q[N+1];
long a[N+1], dp[N+1];
int main()
{
int n = ri(), x = ri(), *fr = q, *re = q+1;
REP1(i, n)
a[i] = ri();
n = unique(a+1, a+n+1) - (a+1);
REP1(i, n) {
while (fr+1 < re && 2*a[i]*(a[fr[1]+1]-a[*fr+1]) > F(*fr, fr[1]))
fr++;
dp[i] = dp[*fr]+P(a[i]-a[*fr+1])+x;
if (i < n) {
while (fr <= re-2 && F(re[-2], re[-1]) / (a[re[-1]+1]-a[re[-2]+1]) > F(re[-1], i) / (a[i+1]-a[re[-1]+1]))
re--;
*re++ = i;
}
}
printf("%ld\n", dp[n]);
}Police Operation C Sharp Solution
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
static long policeOperation(long h, int[] crims)
{
if (h == 0 || crims == null || crims.Length == 0)
return 0;
else if (h == 1)
return crims.Length;
if (crims.Length == 1)
return h;
//Array.Sort(crims);
var cost = new long[crims.Length + 1];
var next = new KeyValuePair<long,long>[crims.Length];
int s = 0;
int c = 0;
cost[0] = 0;
for (int i = 0; i < crims.Length; ++i)
{
long pos = crims[i];
long nextcost = h + pos * pos + cost[i];
while (
s > 1
&&
(nextcost - next[s - 2].Value) * (next[s - 1].Key - next[s - 2].Key)
<=
(next[s - 1].Value - next[s - 2].Value) * (pos - next[s - 2].Key)
)
{
s--;
c--;
if (c < 0) c = 0;
}
next[s] = new KeyValuePair<long,long>(pos, nextcost);
s++;
while (
c < s - 1
&&
next[c + 1].Value - 2 * next[c + 1].Key * pos < next[c].Value - 2 * next[c].Key * pos
)
c++;
cost[i + 1] = next[c].Value + pos * pos - 2 * next[c].Key * pos;
}
return cost[cost.Length - 1];
}
static void Main(string[] args) {
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
string[] nh = Console.ReadLine().Split(' ');
int n = Convert.ToInt32(nh[0]);
int h = Convert.ToInt32(nh[1]);
if(n == 0 || h == 0)
{
textWriter.WriteLine("0");
}
else
{
int[] criminals = Array.ConvertAll(Console.ReadLine().Split(' '), criminalsTemp => Convert.ToInt32(criminalsTemp));
long result = policeOperation(h, criminals);
textWriter.WriteLine(result);
}
textWriter.Flush();
textWriter.Close();
}
}Police Operation Java Solution
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();
}
}Police Operation Python Solution
#!/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()
