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.LinkedList;
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<>();
        q.add(0);
        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;
                        q.add(j);
                    }
                }
            }
        }
        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();
    add(u-1, v, w);
    add(v, u-1, -w);
  }
  REP(i, n) {
    add(i, i+1, 1);
    add(i+1, i, 0);
  }
  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}