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
Super Maximum Cost Queries
Victoria has a tree, T , consisting of N nodes numbered from 1 to N. Each edge from node Ui to Vi in tree T has an integer weight, Wi. Let's define the cost, C, of a path from some node X to some other node Y as the maximum weight ( W ) for any edge in the unique path from node X to Y node . Victoria wants your help processing Q queries on tree T, where each query contains 2 integers, L and
View Solution →Contacts
We're going to make our own Contacts application! The application must perform two types of operations: 1 . add name, where name is a string denoting a contact name. This must store name as a new contact in the application. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting partial with and print the co
View Solution →No Prefix Set
There is a given list of strings where each string contains only lowercase letters from a - j, inclusive. The set of strings is said to be a GOOD SET if no string is a prefix of another string. In this case, print GOOD SET. Otherwise, print BAD SET on the first line followed by the string being checked. Note If two strings are identical, they are prefixes of each other. Function Descriptio
View Solution →Cube Summation
You are given a 3-D Matrix in which each block contains 0 initially. The first block is defined by the coordinate (1,1,1) and the last block is defined by the coordinate (N,N,N). There are two types of queries. UPDATE x y z W updates the value of block (x,y,z) to W. QUERY x1 y1 z1 x2 y2 z2 calculates the sum of the value of blocks whose x coordinate is between x1 and x2 (inclusive), y coor
View Solution →Direct Connections
Enter-View ( EV ) is a linear, street-like country. By linear, we mean all the cities of the country are placed on a single straight line - the x -axis. Thus every city's position can be defined by a single coordinate, xi, the distance from the left borderline of the country. You can treat all cities as single points. Unfortunately, the dictator of telecommunication of EV (Mr. S. Treat Jr.) do
View Solution →Subsequence Weighting
A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence. You are given a sequence A in which every element is a pair of integers i.e A = [(a1, w1), (a2, w2),..., (aN, wN)]. For a subseqence B = [(b1, v1), (b2, v2), ...., (bM, vM)] of the given sequence : We call it increasing if for every i (1 <= i < M ) , bi < bi+1. Weight(B) =
View Solution →