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 :
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
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 →Maximum Element
You have an empty sequence, and you will be given N queries. Each query is one of these three types: 1 x -Push the element x into the stack. 2 -Delete the element present at the top of the stack. 3 -Print the maximum element in the stack. Input Format The first line of input contains an integer, N . The next N lines each contain an above mentioned query. (It is guaranteed that each
View Solution →Balanced Brackets
A bracket is considered to be any one of the following characters: (, ), {, }, [, or ]. Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and (). A matching pair of brackets is not balanced if the set of bra
View Solution →