Skip to content
  • Home
  • Contact Us
  • About Us
  • Privacy Policy
  • DMCA
  • Linkedin
  • Pinterest
  • Facebook
thecscience

TheCScience

TheCScience is a blog that publishes daily tutorials and guides on engineering subjects and everything that related to computer science and technology

  • Home
  • Human values
  • Microprocessor
  • Digital communication
  • Linux
  • outsystems guide
  • Toggle search form
HackerRank Police Operation Problem Solution

HackerRank Police Operation Problem Solution

Posted on August 7, 2023August 7, 2023 By Yashwant Parihar No Comments on HackerRank Police Operation Problem Solution

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

34

Explanation
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,

HackerRank Police Operation Problem Solution
HackerRank Police Operation Problem Solution

Table of Contents

  • Police Operation C Solution
  • Police Operation C++ Solution
  • Police Operation C Sharp Solution
  • Police Operation Java Solution
  • Police Operation Python Solution

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()
c, C#, C++, HackerRank Solutions, java, javascript, python Tags:C, cpp, CSharp, Hackerrank Solutions, java, javascript, python

Post navigation

Previous Post: HackerRank Mining Problem Solution
Next Post: HackerRank Zurikela’s Graph Problem Solution

Related Posts

HackerRank Matrix Land Problem Solution HackerRank Matrix Land Problem Solution c
HackerRank Tripartite Matching Problem Solution HackerRank Tripartite Matching Problem Solution c
HackerRank Encryption Problem Solution HackerRank Encryption Problem Solution c
HackerRank Taum and B'day Problem Solution HackerRank Taum and B’day Problem Solution c
HackerRank Alex vs Fedor Problem Solution HackerRank Alex vs Fedor Problem Solution c
HackerRank Letter Islands Problem Solution HackerRank Letter Islands Problem Solution c

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Pick Your Subject
Human Values

Copyright © 2023 TheCScience.

Powered by PressBook Grid Blogs theme