Police Operation


Problem Statement :


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 (xi,yi) and (x2,y2) equals to  sqrt((x1,y1)^2+(y1-y2)^2).

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*10^6), number of criminals, and h (0 <= h <= 10^9) , the cost of recruiting a police officer. The next line contains n space separated integers. The ith integer indicates the position of the  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 10^9 and are given in increasing order in the input.

Output Format

Print the minimum amount of money required to complete the operation.


Solution :



title-img 


                            Solution in C :

In C++ :





#include <cstdio>
#include <algorithm>
#include <vector>

#define MAXN 3000000
#define INF 123456789012345LL

#define X first
#define Y second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair< ll, ll > pll;

vector< pll > S;
int A[ MAXN + 1 ];
ll dp[ MAXN + 1 ];

ll intersect( pll A, pll B ) {
    if( A.X == B.X ) return 0;
    return ( B.Y - A.Y ) / ( A.X - B.X );
}

ll evaluate( int idx, ll x ) {
    return S[ idx ].X * x + S[ idx ].Y;
}

ll find( ll x ) {
    int lo = 0, hi = S.size() - 1;
    while( lo < hi ) {
        int mid = ( lo + hi ) / 2;
        if( evaluate( mid, x ) <= evaluate( mid + 1, x ) ) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return evaluate( lo, x );
}

void insert( pll A ) {
    while( S.size() >= 2 && intersect( 
      A, S[ S.size() - 2 ] ) > intersect( S[ S.size() - 2 ], S[ S.size() - 1 ] ) )
      {
        S.pop_back();
    }
    S.pb( A );
}
int main() {
    int N, H;
    scanf("%d%d", &N, &H );
    for( int i = 1; i <= N; i++ ) {
        scanf("%d", &A[ i ] );
    }
    sort( A + 1, A + N + 1 );
    for( int i = 1; i <= N; i++ ) {
        insert( mp( ( ll )A[ i ], dp[ i - 1 ] + ( ll )1LL*A[ i ] * A[ i ] + H ) );
        dp[ i ] = ( ll )1LL*A[ i ] * A[ i ] + find( -2*A[ i ] );
    }
    printf("%lld\n", dp[ N ] );
    return 0;
}








In Java :





import java.io.*;
import java.util.*;

public class Solution {

	BufferedReader br;
	PrintWriter out;
	StringTokenizer st;
	boolean eof;

	static class Line {
		long k;
		long b; // y = k * x + b

		public Line(long k, long b) {
			this.k = k;
			this.b = b;
		}

		double cross(Line o) {
			return 1.0 * (o.b - b) / (k - o.k);
		}

		long vect(Line a) {
			return k * a.b - a.k * b;
		}
	}

	boolean badTurn(Line a, Line b, Line c) {
		return a.vect(b) + b.vect(c) + c.vect(a) >= 0;
	}

	void solve() throws IOException {
		int n = nextInt();
		int h = nextInt();
		int[] xs = new int[n];
		for (int i = 0; i < n; i++) {
			xs[i] = nextInt();
		}
		if (n == 0) {
			out.println(0);
			return;
		}
		if (n == 1) {
			out.println(h);
			return;
		}
		long[] dp = new long[n + 1];
		Line[] s = new Line[n + 1];
		int sz = 0;
		s[sz++] = new Line(-2 * xs[0], h + sqr(xs[0]));
		double[] c = new double[n + 1];
		for (int i = 0; i < n; i++) {
			int pos = Arrays.binarySearch(c, 0, sz - 1, xs[i]);
			if (pos < 0) {
				pos = -pos - 1;
			}
			dp[i + 1] = Long.MAX_VALUE;
			for (int j = pos - 1; j <= pos + 1; j++) {
				if (j >= 0 && j < sz) {
					dp[i + 1] = Math.min(dp[i + 1], s[j].k * xs[i] + s[j].b);
				}
			}
			dp[i + 1] += sqr(xs[i]);
			if (i != n - 1) {
				Line add = new Line(-2 * xs[i + 1], h + dp[i + 1] + sqr(xs[i + 1]));
//				System.err.println(dp[i + 1] + ", " + add.k + " " + add.b);
				while (sz > 1 && badTurn(s[sz - 2], s[sz - 1], add)) {
					sz--;
				}
				s[sz++] = add;
				c[sz - 2] = s[sz - 2].cross(s[sz - 1]);
			}
		}
		out.println(dp[n]);
	}

	static long sqr(long x) {
		return x * x;
	}

	Solution() throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}

	public static void main(String[] args) throws IOException {
		new Solution();
	}

	String nextToken() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				eof = true;
				return null;
			}
		}
		return st.nextToken();
	}

	String nextString() {
		try {
			return br.readLine();
		} catch (IOException e) {
			eof = true;
			return null;
		}
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
}








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);
}








In Python3 :






#!/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()








View More Similar Problems

Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

View Solution →

QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element

View Solution →

Jesse and Cookies

Jesse loves cookies. He wants the sweetness of all his cookies to be greater than value K. To do this, Jesse repeatedly mixes two cookies with the least sweetness. He creates a special combined cookie with: sweetness Least sweet cookie 2nd least sweet cookie). He repeats this procedure until all the cookies in his collection have a sweetness > = K. You are given Jesse's cookies. Print t

View Solution →

Find the Running Median

The median of a set of integers is the midpoint value of the data set for which an equal number of integers are less than and greater than the value. To find the median, you must first sort your set of integers in non-decreasing order, then: If your set contains an odd number of elements, the median is the middle element of the sorted sample. In the sorted set { 1, 2, 3 } , 2 is the median.

View Solution →

Minimum Average Waiting Time

Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. Different kinds of pizzas take different amounts of time to cook. Also, once h

View Solution →

Merging Communities

People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w

View Solution →