Table of Contents
Animal Transport – 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++ Animal Transport HackerRank Solution
#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lp(i,a,n) for(int i=a;i<=n;++i)
#define lpd(i,a,n) for(int i=a;i>=n;--i)
#define mem(a,b) memset(a,b,sizeof a)
#define all(v) v.begin(),v.end()
#define println(a) cout <<(a) <<endl
#define sz(x) ((int)(x).size())
#define readi(x) scanf("%d",&x)
#define read2i(x,y) scanf("%d%d",&x,&y)
#define read3i(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define mod 1000000007
#define eps 1e-8
#define infi 1000000000
#define infll 1000000000000000000ll
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef set<int> si;
typedef map<int,int> mii;
const int N = 50002;
int t,m,n,dp[N][2];
int tree[4*N][2],lazy[4*N][2];
int type[N],s[N],d[N];
vvi g(N);
void propagate(int i, int j, bool leaf){
tree[i][j] += lazy[i][j];
if(!leaf){
lazy[2*i][j] += lazy[i][j];
lazy[2*i+1][j] += lazy[i][j];
}
lazy[i][j] = 0;
}
int query(int i, int start, int end, int l, int r, int j){
propagate(i, j, start == end);
if(l <= start && r >= end) return tree[i][j];
if(r < start || l > end) return 0;
int mid = (start+end)/2;
return max(query(2*i,start,mid,l,r,j), query(2*i+1,mid+1,end,l,r,j));
}
void update(int i, int start, int end, int l, int r, int j, int v){
propagate(i, j, start == end);
if(l <= start && r >= end){
lazy[i][j] += v;
propagate(i, j, start == end);
return;
}
if(r < start || l > end) return;
int mid = (start+end)/2;
update(2*i, start, mid, l, r, j, v);
update(2*i+1, mid+1, end, l, r, j, v);
tree[i][j] = max(tree[2*i][j], tree[2*i+1][j]);
}
int main(){
readi(t);
while(t--){
read2i(m,n);
lp(i,1,n){
char c;
scanf(" %c", &c);
type[i] = c == 'D' or c == 'M' ? 0 : 1;
}
lp(i,1,n) readi(s[i]);
lp(i,1,n) readi(d[i]), g[d[i]].pb(i);
lp(i,1,m){
for(int idx : g[i]) if(s[idx] < i) update(1,1,m, 1, s[idx], !type[idx], 1);
dp[i][0] = query(1,1,m, 1, i, 1);
dp[i][1] = query(1,1,m, 1, i, 0);
update(1,1,m, i, i, 0, dp[i][0]);
update(1,1,m, i, i, 1, dp[i][1]);
}
vi ans;
lp(i,1,m) ans.pb(max(dp[i][0], dp[i][1]));
lp(i,1,n){
int x = lower_bound(all(ans), i) - ans.begin() + 1;
if(x == m+1) x = -1;
printf("%d ", x);
}
puts("");
g.clear();
g.resize(N);
mem(tree, 0);
mem(lazy, 0);
}
}
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
*/
Java Animal Transport HackerRank Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
static int[] minimumZooNumbers(int m, int n, List<Boolean>[] type, List<Integer>[] start) {
SegRangeAddMax seg0 = new SegRangeAddMax(m);
SegRangeAddMax seg1 = new SegRangeAddMax(m);
int[] res0 = new int[m];
//supposed to be that si != di
for(int i=1; i<m; i++){
List<Boolean> ty = type[i];
List<Integer> st = start[i];
for(int j=0; j<st.size(); j++){
boolean t = ty.get(j);
int s = st.get(j);
SegRangeAddMax affected = t ? seg1 : seg0;
affected.modify(0, s, 1);
}
int qmax = Math.max(seg0.query(0, i-1), seg1.query(0, i-1));
seg0.modify(i, i, qmax);
seg1.modify(i, i, qmax);
res0[i] = qmax;
}
//System.out.println(Arrays.toString(res0));
int[] res = new int[n];
for(int i=0; i<n; i++){
res[i] = -1;
}
for(int i=m-1; i>=1; i--){
if(res0[i] - 1 >= 0) res[res0[i]-1] = i+1;
}
int prev = -1;
for(int i=n-1; i>=0; i--){
if(res[i] == -1) res[i] = prev;
prev = res[i];
}
//System.out.println(Arrays.toString(res));
return res;
//List<Integer>
// Return a list of length n consisting of the answers
//return new int[1];
}
public static void main(String[] args) {
FasterScanner in = new FasterScanner(System.in);
int cases = in.nextInt();
for(int a0 = 0; a0 < cases; a0++){
int m = in.nextInt();
int n = in.nextInt();
List<Boolean>[] type = new ArrayList[m];
List<Integer>[] start = new ArrayList[m];
//stupid one-indexed elements -_-
for(int i=0; i<m; i++){
type[i] = new ArrayList<Boolean>();
start[i] = new ArrayList<Integer>();
}
for(int i=0; i<n; i++){}
//boolean[] t = new boolean[n];
char[] t = new char[n];
for(int t_i = 0; t_i < n; t_i++){
//char c = in.next().charAt(0);
//t[t_i] = c == 'D' || c == 'M';
t[t_i] = in.next().charAt(0);
}
int[] s = new int[n];
for(int s_i = 0; s_i < n; s_i++){
s[s_i] = in.nextInt()-1;
}
int[] d = new int[n];
for(int d_i = 0; d_i < n; d_i++){
d[d_i] = in.nextInt()-1;
//if(s[d_i] >= d[d_i]) throw new RuntimeException();
//^ sanity check. Huge troll if they decide to put this in.
//^ though I will say that I can cope w/ it quite easily in case they do troll.
//^ just don't push to your lists when this condition fails
//^ todo later: implement that since dunno if full test suite runs later.
}
for(int i=0; i<n; i++){
if(s[i] >= d[i]) continue;
type[d[i]].add(t[i] == 'D' || t[i] == 'M');
start[d[i]].add(s[i]);
}
int[] result = minimumZooNumbers(m, n, type, start);
for (int i = 0; i < result.length; i++) {
System.out.print(result[i] + (i != result.length - 1 ? " " : ""));
}
System.out.println("");
}
//int[] testA = new int[]{1, 3, 5, 4, 0};
//SegRangeAddMax test = new SegRangeAddMax(testA);
//System.out.println(test.query(3,3));
}
}
//DUNNO IF THIS WORKS YET. gonna test on hr: animal transport
class SegRangeAddMax{
int[] t, d;
int n, h;
SegRangeAddMax(int[] base){
this(base.length);
for(int i=0; i<n; i++)
t[i+n] = base[i];
for(int i=n-1; i>0; i--)
t[i] = t[i<<1] + t[i<<1|1];
}
SegRangeAddMax(int n){
this.n = n;
h = 32 - Integer.numberOfLeadingZeros(n);
t = new int[2*n];
d = new int[n];
}
//k is the width of the interval denoted by p
void apply(int p, int val){
t[p] += val;
if(p < n) d[p] += val;
}
void calc(int p){
t[p] = Math.max(t[p<<1],t[p<<1|1]) + d[p];
}
//before and after the build() function is called,
//invariant that t[p] == t[p] of both children + d[p]*k, holds. < ignore this.
void build(int p){
//int k = 2;
for(p+=n; p>1;){
p >>= 1;
calc(p);
}
}
//its obvious that invariant t[p] == t[p] of both children + d[p]*k holds during a push. < ignore this.
void push(int p){
//int k = 1 << (h-1);
int s = h;
for(p+=n; s>0; s--){
int i = p >> s;
if(d[i] != 0){
apply(i<<1, d[i]);
apply(i<<1|1, d[i]);
d[i] = 0;
}
}
}
void modify(int l, int r, int val){
r++;
if(val == 0) return;
//push(l);
//push(r-1);
int l0=l, r0=r;
for(l+=n, r+=n; l<r; l >>= 1, r >>= 1){
if((l&1) == 1) apply(l++, val);
if((r&1) == 1) apply(--r, val);
}
build(l0);
build(r0-1);
}
int query(int l, int r){
r++;
push(l);
push(r-1);
int res = Integer.MIN_VALUE;
for(l+=n, r+=n; l<r; l >>= 1, r >>= 1){
if((l&1) == 1) res = Math.max(res, t[l++]);
if((r&1) == 1) res = Math.max(res, t[--r]);
}
return res;
}
}
class FasterScanner {
private InputStream mIs;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public FasterScanner() {
this(System.in);
}
public FasterScanner(InputStream is) {
mIs = is;
}
public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = mIs.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
//nextString
public String next() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public long nextLong() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int nextInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
