HackerRank Liars Problem Solution Yashwant Parihar, May 21, 2023May 28, 2024 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 areNote: N and M are not more than 101, and it is guaranteed the given informations is satisfiable. Output FormatPrint 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 20 11 3 8 4 1 9 6 1 13 9 5 11 5 4 19 12 8 13 5 4 8 4 7 9 2 10 13 3 7 16 7 14 19 4 Sample Output #2 13 14 ExplanationIn 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. HackerRank Liars Problem Solution 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() c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython