Table of Contents
Liars – 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++ Liars HackerRank Solution
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 150;
typedef pair<int, int> P;
int d[MAXN];
vector<P> e[MAXN];
int a[MAXN], b[MAXN], c[MAXN];
deque<int> dq;
int inq[MAXN];
int n, m;
int getMin() {
for (int i = 0; i <= n; ++i) e[i].clear();
for (int i = 1; i <= n; ++i) {
e[i - 1].push_back(P(i, 0));
e[i].push_back(P(i - 1, -1));
}
for (int i = 0; i < m; ++i) {
e[b[i]].push_back(P(a[i] - 1, -c[i]));
e[a[i] - 1].push_back(P(b[i], c[i]));
}
fill(d, d + (n + 1), 0);
d[0] = 0;
for (int c = 0; c <= n; ++c)
for (int u = 0; u <= n; ++u)
for (int j = 0; j < e[u].size(); ++j) {
int v = e[u][j].first;
if (d[u] + e[u][j].second > d[v]) d[v] = d[u] + e[u][j].second;
}
return d[n];
fill(inq, inq + (n + 1), 0);
inq[0] = 1;
while (!dq.empty()) dq.pop_back();
dq.push_back(0);
while (!dq.empty()) {
int u = dq.front();
dq.pop_front();
inq[u] = 0;
for (int j = 0; j < e[u].size(); ++j) {
int v = e[u][j].first;
if (d[u] + e[u][j].second > d[v]) {
d[v] = d[u] + e[u][j].second;
if (!inq[v]) {
inq[v] = 1;
dq.push_back(v);
}
}
}
}
return d[n];
}
int getMax() {
for (int i = 0; i <= n; ++i) e[i].clear();
for (int i = 1; i <= n; ++i) {
e[i].push_back(P(i - 1, 0));
e[i - 1].push_back(P(i, 1));
}
for (int i = 0; i < m; ++i) {
e[b[i]].push_back(P(a[i] - 1, -c[i]));
e[a[i] - 1].push_back(P(b[i], c[i]));
}
fill(d, d + (n + 1), n * 2);
d[0] = 0;
for (int c = 0; c <= n; ++c)
for (int u = 0; u <= n; ++u)
for (int j = 0; j < e[u].size(); ++j) {
int v = e[u][j].first;
if (d[u] + e[u][j].second < d[v]) d[v] = d[u] + e[u][j].second;
}
return d[n];
fill(inq, inq + (n + 1), 0);
inq[0] = 1;
while (!dq.empty()) dq.pop_back();
dq.push_back(0);
while (!dq.empty()) {
int u = dq.front();
dq.pop_front();
inq[u] = 0;
for (int j = 0; j < e[u].size(); ++j) {
int v = e[u][j].first;
if (d[u] + e[u][j].second < d[v]) {
d[v] = d[u] + e[u][j].second;
if (!inq[v]) {
inq[v] = 1;
dq.push_back(v);
}
}
}
}
return d[n];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i) {
scanf("%d%d%d", a + i, b + i, c + i);
}
printf("%d %d\n", getMin(), getMax());
}
Java Liars HackerRank Solution
import java.util.*;
import java.io.*;
import static java.lang.Math.*;
public class Solution {
/*
* difference constraints
* add new constraint d[N]-d[0] = k and check if k is feasible
*/
static class Foo51 {
int N;
int[][] edges;
void main() {
BufferedReader br = null;
try {
br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().trim().split(" ");
N = Integer.parseInt(s[0].trim());
int M = Integer.parseInt(s[1].trim());
edges = new int[2*M+2*N+2][3];
for (int i = 0; i < M; i++) {
s = br.readLine().trim().split(" ");
int u = Integer.parseInt(s[0].trim());
int v = Integer.parseInt(s[1].trim());
int weight = Integer.parseInt(s[2].trim());
edges[2*i] = new int[] {u-1, v, weight};
edges[2*i+1] = new int[] {v, u-1, -weight};
}
for (int i = 0; i < N; i++) {
edges[2*i+2*M] = new int[] {i+1, i, 0};
edges[2*i+2*M+1] = new int[] {i, i+1, 1};
}
edges[2*M+2*N][0] = edges[2*M+2*N+1][1] = 0;
edges[2*M+2*N+1][0] = edges[2*M+2*N][1] = N;
int[] res = foo();
System.out.println(res[0] + " " + res[1]);
} catch (Exception e) {
e.printStackTrace();
} finally {
if (br != null) {
try { br.close(); } catch (Exception e) { e.printStackTrace(); }
}
}
}
int[] foo() {
// binary search is better, but since the constraint is low, just linear traverse
int[] res = {N, 0};
for (int k = 0; k <= N; k++) {
if (ok(k)) {
res[0] = min(res[0], k);
res[1] = max(res[1], k);
}
}
return res;
}
boolean ok(int K) {
int m = edges.length;
edges[m-2][2] = K;
edges[m-1][2] = -K;
int[] d = new int[N+1];
for (int i = 0; i < N+1; i++) {
for (int j = 0; j < m; j++) {
int u = edges[j][0];
int v = edges[j][1];
d[v] = min(d[v], d[u]+edges[j][2]);
}
}
for (int j = 0; j < m; j++) {
int u = edges[j][0];
int v = edges[j][1];
if (d[v] > d[u] + edges[j][2])
return false;
}
return true;
}
}
public static void main(String[] args) {
Foo51 foo = new Foo51();
foo.main();
}
}
Python 3 rep HackerRank Solution
from sys import stdin
from math import inf
from queue import Queue
def find_liars(num_soldiers, source_soldier, dest_soldier, edges):
liars = [inf] * (num_soldiers + 1)
liars[source_soldier] = 0
for fodder in range(0, num_soldiers + 1):
for edge in edges:
soldier, next_soldier, liar_count = edge
calc_liars = liar_count + liars[soldier]
if calc_liars < liars[next_soldier]:
liars[next_soldier] = calc_liars
return liars[dest_soldier]
def run():
soldiers, num_info = [int(info) for info in input().strip().split(' ')]
edges = [[(i, i+1, 1)] for i in range(0, soldiers)]
edges.append([])
for i in range(0, soldiers):
edges[i + 1].append((i+1, i, 0))
# read information input
for line in stdin:
first_soldier, second_soldier, liars = [int(info) for info in line.strip().split(' ')]
edges[first_soldier - 1].append((first_soldier - 1, second_soldier, liars))
edges[second_soldier].append((second_soldier, first_soldier - 1, -liars))
edges = [edge for edge_soldiers in edges for edge in edge_soldiers ]
max_liars = find_liars(soldiers, 0, soldiers, edges)
min_liars = -find_liars(soldiers, soldiers, 0, edges)
print(min_liars, max_liars)
run()
Python 2 Liars HackerRank Solution
#Write your Python code here. Input is from STDIN and output to STDOUT. Please refer FAQ for more details.\
#!/usr/bin/python
def get(n, limit):
edges = []
virtual = n+1
for x in xrange(n):
edges.append((x+1, x, 0))
edges.append((x, x+1, 1))
for x in xrange(n+1):
edges.append((virtual, x, 0))
for a, b, c in limit:
edges.append((a-1, b, c))
edges.append((b, a-1, -c))
dist = [10**10] * (n+2)
dist[virtual] = 0
for x in xrange(n+1):
for a, b, c in edges:
dist[b] = min(dist[b], dist[a] + c)
return dist[n] - dist[0]
getnums = lambda: map(int, raw_input().strip().split())
n, m = getnums()
limit = []
reverse = []
for x in xrange(m):
a, b, c = getnums()
limit.append((a, b, c))
reverse.append((a, b, b-a+1-c))
print get(n, limit), n-get(n, reverse)
C Liars HackerRank Solution
#include <stdio.h>
#define N 500
#define eps 0.00000000000001
long long MM,NN,baza[500],i,j,k,l,m,n,interval[N][3],je_v_bazi[N];
long double a[N][N],b[N],c[N],r,s,t,z;
void pivotuj(long long mm,long long nn, long long kk, long long ii)
{
long long jj,ll;
long double rr;
baza[kk] = ii;
rr= a[kk][ii];
for(jj=0;jj<nn;jj++) a[kk][jj] /= rr;
b[kk]/=rr;
for(ll=0;ll<mm;ll++)
{
if(ll==kk) continue;
rr = -a[ll][ii];
if(rr<eps && rr>-eps) continue;
b[ll] += b[kk]*rr;
for(jj=0;jj<nn;jj++)
a[ll][jj] += a[kk][jj]*rr;
}
rr = -c[ii];
//printf("%lld %lld %lld %lld %llf\n",mm,nn,kk,ii,rr);
for(jj=0;jj<nn;jj++) c[jj] += rr*a[kk][jj];
z -= rr*b[kk];
//printf("%llf..\n",z);
return;
}
void vypis(long long mm, long long nn)
{
long long ii,jj;
return;
for(ii=0;ii<mm;ii++)
{
for(jj=0;jj<nn;jj++) printf("%5.2llf ",a[ii][jj]);
printf("| %llf baza %lld\n",b[ii],baza[ii]);
}
printf("---------------------\n");
for(jj=0;jj<nn;jj++) printf("%5.2llf ",c[jj]);
printf("%llf=z\n\n\n",z);
return;
}
long long simplex(long long mm, long long nn)
{
long long ii,jj,p_riadok, p_stlpec;
long double rr;
rr=1;
for(ii=0;ii<nn;ii++)
if(c[ii]<rr) {rr = c[ii]; p_stlpec=ii;}
if(rr>-eps)
{
// printf("koncim!!\n");
return 0;
}
p_riadok = -1;
rr = -1;
for(jj=0;jj<mm;jj++)
if(a[jj][p_stlpec]>eps)
if(rr<0 || b[jj]/a[jj][p_stlpec] < rr) {rr = b[jj]/a[jj][p_stlpec];p_riadok = jj;}
if(rr<-eps)
{
// printf("neobmedznee!!\n");
return 0;
}
//printf("%lld %lld - pivotujem\n",p_riadok, p_stlpec);
pivotuj(mm,nn,p_riadok,p_stlpec);
vypis(mm,nn);
return 1;
}
int main()
{
scanf("%lld %lld",&n,&m);
for(i=0;i<m;i++)
{
scanf("%lld %lld %lld",&interval[i][0],&interval[i][1],&interval[i][2]);
interval[i][0]--;
interval[i][1]--;
}
for(i=0;i<m;i++)
for(j=interval[i][0];j<=interval[i][1];j++)
a[i][j] = 1;
for(i=m;i<m+n;i++)
a[i][i-m] = 1;
for(i=0;i<n+m;i++) a[i][i+n]=1;
for(i=0;i<m;i++) b[i] = interval[i][2];
for(i=m;i<m+n;i++) b[i] = 1;
for(i=n;i<n+m;i++) c[i]=1;
//for(i=0;i<n+m;i++) baza[i] = i+n;
z=0;
vypis(m+n,2*n+m);
for(i=0;i<m+n;i++)
pivotuj(m+n,2*n+m,i,i+n);
//nuluj_b(m+n,2*n+m);
vypis(m+n,2*n+m);
while(simplex(m+n,2*n+m));
//simplex(m+n,2*n+m);
//if(z>eps || z<-eps) {printf("nema ries\n");return 0;}
//return 0;
//for(i=0;i<m+n;i++) if(baza[i]<n) printf("%lld %llf\n", baza[i],b[i]);
//for(i=0;i<2*n+m;i++) neni[i]=1;
//for(i=0;i<m+n;i++) neni[baza[i]]=0;
vypis(m+n,2*n+m);
for(i=0;i<m+n;i++)
if(baza[i]>=n && baza[i]<n+m)
{
// printf("..%lld %llf\n", baza[i],b[i]);
j=0;
while(j<2*n+m && ((j>=n && j<m+n) || (a[i][j]<eps && a[i][j]>-eps)))
j++;
if(j>=2*n+m) {
//printf("bug!!\n");
continue;}
// printf("piv %lld %lld %lld\n",i,j,baza[i]);
pivotuj(m+n,m+2*n,i,j);
}
//vypis(n+m,2*n+m);
//return 0;
l=0;
for(i=0;i<m+n;i++)
if(baza[i]>=n && baza[i]<n+m)
{
l++;
// printf("......%lld %llf\n", baza[i],b[i]);
}
for(i=0;i<m+2*n;i++) je_v_bazi[i]=0;
for(i=0;i<m+n;i++) je_v_bazi[baza[i]]=1;
MM = m+n;
NN = n;
for(i=n;i<2*n+m;i++)
if(je_v_bazi[i] || i> n+m)
{
for(k=0;k<m+n;k++) a[k][NN] = a[k][i];
c[NN] = c[i];
for(k=0;k<m+n;k++) if(baza[k]==i) baza[k] = NN;
NN++;
}
z = 0.0;
for(i=0;i<n;i++) c[i] = 1.0;
for(i=n;i<NN;i++) c[i] = 0.0;
//printf("druha faza\n");
//vypis(MM,NN);
//return 0;
//return 0;
for(i=0;i<MM;i++)
pivotuj(MM,NN,i,baza[i]);
vypis(MM,NN);
//return 0;
while(simplex(MM,NN));
vypis(MM,NN);
printf("%lld", (long long)(z+0.5));
//return 0;
z = 0;
for(i=0;i<n;i++) c[i] = -1;
for(i=n;i<NN;i++) c[i] = 0;
//printf("druha faza\n");
for(i=0;i<MM;i++) pivotuj(MM,NN,i,baza[i]);
vypis(MM,NN);
while(simplex(MM,NN));
printf(" %lld\n", (long long)(-z+0.5));
return 0;
}
Leave a comment below
