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

Jenny's Subtrees

Jenny loves experimenting with trees. Her favorite tree has n nodes connected by n - 1 edges, and each edge is ` unit in length. She wants to cut a subtree (i.e., a connected part of the original tree) of radius r from this tree by performing the following two steps: 1. Choose a node, x , from the tree. 2. Cut a subtree consisting of all nodes which are not further than r units from node x .

View Solution →

Tree Coordinates

We consider metric space to be a pair, , where is a set and such that the following conditions hold: where is the distance between points and . Let's define the product of two metric spaces, , to be such that: , where , . So, it follows logically that is also a metric space. We then define squared metric space, , to be the product of a metric space multiplied with itself: . For

View Solution →

Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

View Solution →

Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

View Solution →

Array and simple queries

Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty

View Solution →

Median Updates

The median M of numbers is defined as the middle number after sorting them in order if M is odd. Or it is the average of the middle two numbers if M is even. You start with an empty number list. Then, you can add numbers to the list, or remove existing numbers from it. After each add or remove operation, output the median. Input: The first line is an integer, N , that indicates the number o

View Solution →