HackerRank Liars Problem Solution

In this post, we will solve 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.
Input Format

The first line of the input contains two integers N and M.
Each of next M lines contains three integers:
A B C where the set of soldiers numbered as {A, A+1, A+2, liars. (1 <= Ai <= Bi<=n) and (0 <= Ci <= BI-AI). B). exactly C of them are
Note: N and M are not more than 101, and it is guaranteed the given informations is satisfiable.

Output Format
Print two integers Lmin and Lmax to the output.

Sample Input #1

3 2
1 2 1
2 3 1

Sample Output #1

1 2

Sample Input #2

Sample Output #2

13 14

Explanation
In the first input, the initial line is “3 2”, i.e. that there are 3 soldiers and we have 2 sets of information. The next line says there is one liar in the set of soldiers {1, 2}. The final line says there is one liar in the set {2,3}. There are two possibilities for this scenario: Soldiers number 1 and 3 are liars or soldier number 2 is liar.
So the minimum number of liars is 1 and maximum number of liars is 2. Hence the answer, 1 2.

Table of Contents

Liars C Solution

#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;
    int 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;
    int i;
    int matrix[MAX_N+2][MAX_N+2];
    int 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;
}

Liars C++ Solution

#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));
}

Liars C Sharp Solution


using System;
using System.Collections.Generic;

class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        s = Console.ReadLine().Split(cs, StringSplitOptions.RemoveEmptyEntries);
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

}

class Solution
{
    Scanner cin;

    public static void Main()
    {
        new Solution().calc();
    }

    class C
    {
        public long hash;
        public bool flag;
        public int[] nums;

        public C(int[] _nums)
        {
            flag = false;
            nums = (int[])_nums.Clone();
        }

        public long gethash()
        {
            if (flag) return hash;
            hash = 0; flag = true;
            foreach (var item in nums)
            {
                hash = hash * (long)12361717111 + item * (long)738173493019;
            }
            return hash;
        }
    }

    void calc()
    {
        cin = new Scanner();
        int N = cin.nextInt();
        int M = cin.nextInt();
        int[] start = new int[M];
        int[] goal = new int[M];
        int[] need = new int[M];
        for (int i = 0; i < M; i++)
        {
            start[i] = cin.nextInt() - 1;
            goal[i] = cin.nextInt() - 1;
            need[i] = cin.nextInt();
        }
        List<C> cl = new List<C>();
        C first = new C(new int[M]);
        Dictionary<long, int> min = new Dictionary<long, int>();
        Dictionary<long, int> max = new Dictionary<long, int>();
        min[first.gethash()] = max[first.gethash()] = 0;
        cl.Add(first);
        List<int> l = new List<int>();
        for (int i = 0; i < N; i++)
        {
            List<int> rem = new List<int>();
            for (int j = 0; j < M; j++)
            {
                if (start[j] == i) l.Add(j);
                if (goal[j] == i) rem.Add(j);
            }
            Dictionary<long, int> nmin = new Dictionary<long, int>();
            Dictionary<long, int> nmax = new Dictionary<long, int>();
            List<C> ncl = new List<C>();
            foreach (var now in cl)
            {
                int[] nums = (int[])now.nums.Clone();
                int mi = min[now.gethash()];
                int ma = max[now.gethash()];

                for (int k = 0; k < 2; k++)
                {
                    bool ok = true;
                    if (k == 1)
                    {
                        foreach (var item in l)
                        {
                            nums[item] += 1;
                        }
                    }
                    foreach (var item in rem)
                    {
                        if (nums[item] != need[item])
                        {
                            ok = false;
                            break;
                        }
                    }
                    if (!ok) continue;
                    mi += k; ma += k;
                    C next = new C(nums);
                    if (nmin.ContainsKey(next.gethash()))
                    {
                        if (nmin[next.gethash()] > mi) nmin[next.gethash()] = mi;
                        if (nmax[next.gethash()] < ma) nmax[next.gethash()] = ma;
                    }
                    else
                    {
                        ncl.Add(next);
                        nmin[next.gethash()] = mi;
                        nmax[next.gethash()] = ma;
                    }
                }
            }
            foreach (var item in rem)
            {
                l.Remove(item);

            }

            min = nmin;
            max = nmax;
            cl = ncl;
        }
        int retmin = 1000;
        int retmax = 0;
        foreach (var item in min.Values)
        {
            retmin = Math.Min(retmin, item);
        }
        foreach (var item in max.Values)
        {
            retmax = Math.Max(retmax, item);
        }
        Console.WriteLine(retmin + " " + retmax);
    }


}

Liars Java Solution

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();
    }
}

Liars JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the liars function below.
 */
function liars(n, sets) {
    /*
     * Write your code here.
     */
    var answer = [1,1];
    var matrix = Array(n+1);
    var child = Array(n+1);
    var min = Array(n+1);
    matrix[0] = Array(n+1);
    child[0] = [];
    for(let i=1;i<n;i++){
        matrix[i] = Array(n+1);
        child[i] = [];
        matrix[i][i+1] = 1;
        matrix[i][i-1] = 0;
        child[i].push(i+1);
        child[i].push(i-1);
        min[i] = n+1;
    }
    min[n] = n+1;
    
    matrix[0][1] = 1;
    matrix[0][0] = 0;
    child[0].push(1);
    
    
    matrix[n] = Array(n+1);
    child[n] = [];
    matrix[n][n-1] = 0;
    child[n].push(n-1);
    
    for(let i=0;i<sets.length;i++){
        child[sets[i][0]-1] = child[sets[i][0]-1] || [];
        child[sets[i][1]] = child[sets[i][1]] || [];
        child[sets[i][0]-1].push(sets[i][1]);
        child[sets[i][1]].push(sets[i][0]-1);
        matrix[sets[i][0]-1][sets[i][1]] = sets[i][2];
        matrix[sets[i][1]][sets[i][0]-1] = (sets[i][2] - (2*sets[i][2]));
    }
    min[0] = 0;
    var looper = [0,n+1];
    
    while(looper[1]){
        while(looper[0] < n+1)
        {
            var length = child[looper[0]].length;
            for(let i = 0;i < length;i++){
                if(min[looper[0]] + matrix[looper[0]][child[looper[0]][i]] < min[child[looper[0]][i]]){
                    min[child[looper[0]][i]] = (min[looper[0]] + matrix[looper[0]][child[looper[0]][i]]);
                    looper.push(child[looper[0]][i]);
                }
            }            
            looper.splice(0,1);    
        }
        looper.splice(0,1);
        looper.push(n+1);
    }
    
    answer[1] = min[n];
    
    for(let i=1;i<n+1;i++){
        min[i] = n+1;
    }
    looper = [0,n+1];
    for(let i=0;i<sets.length;i++){
        matrix[sets[i][0]-1][sets[i][1]] = sets[i][1] - (sets[i][0] - 1) - sets[i][2];
        matrix[sets[i][1]][sets[i][0]-1] = (matrix[sets[i][0]-1][sets[i][1]] - (2*(matrix[sets[i][0]-1][sets[i][1]])));
    }
    
    while(looper[1]){
        while(looper[0] < n+1)
        {
            var length = child[looper[0]].length;
            for(let i = 0;i < length;i++){
                if(min[looper[0]] + matrix[looper[0]][child[looper[0]][i]] < min[child[looper[0]][i]]){
                    min[child[looper[0]][i]] = (min[looper[0]] + matrix[looper[0]][child[looper[0]][i]]);
                    looper.push(child[looper[0]][i]);
                }
            }            
            looper.splice(0,1);    
        }
        looper.splice(0,1);
        looper.push(n+1);
    }
    answer[0] = n - min[n];
    return answer;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const nm = readLine().split(' ');

    const n = parseInt(nm[0], 10);

    const m = parseInt(nm[1], 10);

    let sets = Array(m);

    for (let setsRowItr = 0; setsRowItr < m; setsRowItr++) {
        sets[setsRowItr] = readLine().split(' ').map(setsTemp => parseInt(setsTemp, 10));
    }

    let result = liars(n, sets);

    ws.write(result.join(" ") + "\n");

    ws.end();
}

Liars Python Solution

#!/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()