Table of Contents
Police Operation – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ replace HackerRank Solution
#include <stdio.h>
int n, h, st, ed;
long long inp[2000010], deq[2000010], dp[2000010];
inline long long sq(long long x) {
return x * x;
}
inline long long calc(long long x1, long long v1, long long x2, long long v2) {
return (v1 - v2 - x2*x2 + x1*x1 + 2*(x1-x2) - 1) / ( 2*(x1-x2));
}
int main() {
scanf("%d%d", &n, &h);
for (int i=1; i<=n; i++) scanf("%lld", &inp[i]);
st = 0;
ed = 0;
deq[st++] = 0;
for (int i=1; i<=n; i++) {
while (st > ed + 1 && dp[deq[ed]] + sq(inp[i] - inp[deq[ed]+1]) >=
dp[deq[ed+1]] + sq(inp[i] - inp[deq[ed+1]+1])) {
ed ++;
}
dp[i] = dp[deq[ed]] + sq(inp[i] - inp[deq[ed]+1]) + h;
if (i < n) {
while (st > ed + 1 && calc(inp[deq[st-1]+1], dp[deq[st-1]], inp[deq[st-2]+1], dp[deq[st-2]]) >=
calc(inp[i+1], dp[i], inp[deq[st-1]+1], dp[deq[st-1]])) {
st --;
}
deq[st++] = i;
}
}
printf("%lld\n", dp[n]);
return 0;
}
Java rep HackerRank Solution
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());
}
}
Python 3 rep HackerRank 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()
Python 2 rep HackerRank Solution
C rep HackerRank 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);
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
