# HackerRank Liars problem solution

In this HackerRank Liars problem solution, You have N soldiers numbered from 1 to N. Each of your soldiers is either a liar or a truthful person. You have M sets of information about them. Each set of information tells you the number of liars among a certain range of your soldiers. Let L be the total number of your liar soldiers. Since you can't find the exact value of L, you want to find the minimum and maximum value of L.

## Problem solution in Python.

```#!/bin/python3

import os
import sys

#
# Complete the liars function below.
#
def get(n, limit):
edges = []
virtual = n + 1
for x in range(n):
edges.append((x + 1, x, 0))
edges.append((x, x + 1, 1))
for x in range(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 range(n + 1):
for a, b, c in edges:
dist[b] = min(dist[b], dist[a] + c)
return dist[n] - dist[0]

def liars(n, sets):
rev = [[a, b, b - a + 1 - c] for [a, b, c] in sets]
return get(n, sets), n - get(n, rev)

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nm = input().split()
n = int(nm[0])
m = int(nm[1])
sets = []
for _ in range(m):
sets.append(list(map(int, input().rstrip().split())))
result = liars(n, sets)
fptr.write(' '.join(map(str, result)))
fptr.write('\n')
fptr.close()
```

{"mode":"full","isActive":false}

## Problem solution in Java.

```import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.AbstractMap;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Solution {

static int findMax(int n, int[][] sets, boolean opposite) {
final Map<Integer, Integer>[] ws = new Map[n + 1];
for (int i = 0; i <= n; i++) {
ws[i] = new HashMap<>(n);
}
for (int i = 0; i < n; i++) {
ws[i].put(i + 1, 1);
ws[i + 1].put(i, 0);
}
if (opposite) {
for (int[] s : sets) {
int w = s[1] - s[0] - s[2] + 1;
ws[s[0] - 1].put(s[1], w);
ws[s[1]].put(s[0] - 1, -w);
}
} else {
for (int[] s : sets) {
ws[s[0] - 1].put(s[1], s[2]);
ws[s[1]].put(s[0] - 1, -s[2]);
}
}

return minPath(ws);
}

static int minPath(Map<Integer,Integer>[] ws){
int n = ws.length;
int[] d = new int[n];
Arrays.fill(d, Short.MAX_VALUE);
d[0] = 0;

boolean[] state = new boolean[n];

Queue<Integer> q = new LinkedList<>();
while (!q.isEmpty()){
int v = q.poll();
state[v] = false;
for(AbstractMap.Entry<Integer, Integer> jw: ws[v].entrySet()){
int j = jw.getKey();
int w = d[v]+jw.getValue();
if(w < d[j]){
d[j] = w;
if (!state[j]){
state[j] = true;
}
}
}
}
return d[n-1];
}

/*
* Complete the liars function below.
*/
static int[] liars(int n, int[][] sets) {
int min = n - findMax(n, sets, true);
int max = findMax(n, sets, false);

return new int[]{min, max};
}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

String[] nm = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

int n = Integer.parseInt(nm[0]);

int m = Integer.parseInt(nm[1]);

int[][] sets = new int[m][3];

for (int setsRowItr = 0; setsRowItr < m; setsRowItr++) {
String[] setsRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

for (int setsColumnItr = 0; setsColumnItr < 3; setsColumnItr++) {
int setsItem = Integer.parseInt(setsRowItems[setsColumnItr]);
sets[setsRowItr][setsColumnItr] = setsItem;
}
}

int[] result = liars(n, sets);

for (int resultItr = 0; resultItr < result.length; resultItr++) {
bufferedWriter.write(String.valueOf(result[resultItr]));

if (resultItr != result.length - 1) {
bufferedWriter.write(" ");
}
}

bufferedWriter.newLine();

bufferedWriter.close();

scanner.close();
}
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <algorithm>
#include <climits>
#include <cstdio>
#include <utility>
#include <vector>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define pb push_back
#define fi first
#define se second

int ri()
{
int x;
scanf("%d", &x);
return x;
}

const int N = 102;
vector<pair<int, int> > e[N];
int q[N], d[N];
bool in[N];

int moore(int n, int src, int sink)
{
int *fo = q, *re = q;
fill_n(d, n, INT_MAX);
fill_n(in, n, false);
d[src] = 0;
*re++ = src;
while (fo != re) {
int u = *fo++;
if (fo == q+n) fo = q;
in[u] = false;
for (auto i: e[u])
if (d[u]+i.se < d[i.fi]) {
d[i.fi] = d[u]+i.se;
if (! in[i.fi]) {
in[i.fi] = true;
*re++ = i.fi;
if (re == q+n) re = q;
}
}
}
return d[sink];
}

void add(int u, int v, int w)
{
e[u].pb(make_pair(v, w));
}

int main()
{
int n = ri(), m = ri();
while (m--) {
int u = ri(), v = ri(), w = ri();
}
REP(i, n) {
}
printf("%d %d\n", -moore(n+1, n, 0), moore(n+1, 0, n));
}```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include<stdio.h>
#include<string.h>
#define INF 1000000
#define MAX_N 101
int dist(int N, int matrix[MAX_N+2][MAX_N+2], int weight[MAX_N+2][MAX_N+2], int min)
{
int i, j, k, dist[MAX_N+2];
for( i = 0 ; i <= N ; i++ )
{
dist[i] = INF;
}
if(min)
{
dist[N+1] = 0;
}
else
{
dist[0] = 0;
}
int max_vertex = min ? N + 1 : N;
for( i = 1 ; i <= max_vertex ; i++ )
{
for( j = 0 ; j <= max_vertex ; j++ )
{
for( k = 0 ; k <= max_vertex ; k++ )
{
if( dist[j] != INF && matrix[j][k] && ( dist[k] == INF || dist[j] + weight[j][k] < dist[k] ) )
{
dist[k] = dist[j] + weight[j][k];
}
}
}
}
return min ? -dist[0] : dist[N];
}
int min(int a, int b)
{
return a < b ? a : b;
}
int main()
{
int N, M, A, B, C, i, matrix[MAX_N+2][MAX_N+2], weight[MAX_N+2][MAX_N+2];
scanf("%d %d", &N, &M);
for( i = 0 ; i < N ; i++ )
{
matrix[i][i+1] = 1;
weight[i][i+1] = 1;
matrix[i+1][i] = 1;
weight[i+1][i] = 0;
}
for( i = 0 ; i <= N ; i++ )
{
matrix[N+1][i] = 1;
weight[N+1][i] = 0;
}
for( i = 0 ; i < M ; i++ )
{
scanf("%d %d %d", &A, &B, &C);
if( !matrix[A-1][B] || C < weight[A-1][B] )
{
matrix[A-1][B] = 1;
weight[A-1][B] = C;
}
if( !matrix[B][A-1] || -C < weight[B][A-1] )
{
matrix[B][A-1] = 1;
weight[B][A-1] = -C;
}
}
printf("%d %d\n", dist(N, matrix, weight, 1), dist(N, matrix, weight, 0));
return 0;
}
```

{"mode":"full","isActive":false}