HackerRank Problem solving Problem Solution

In this post, we will solve HackerRank Problem solving Problem Solution.

There are N problems numbered 1..N which you need to complete. You’ve arranged the problems in increasing difficulty order, and the i^th problem has estimated difficulty level i. You have also assigned a rating vi to each problem. Problems with similar vi values are similar in nature. On each day, you will choose a subset of the problems and solve them. You’ve decided that each subsequent problem solved on the day should be tougher than the previous problem you solved on that day. Also, to make it less boring, consecutive problems you solve should differ in their vi rating by at least K. What is the least number of days in which you can solve all problems?

Input Format

The first line contains the number of test cases T. T test cases follow. Each case contains an integer N and K on the first line, followed by integers v1,…,vn on the second line.

Constraints

1 <= T <= 100
1 <= N <= 300
1 <= vi <= 1000
1 <= K <= 1000

Output Format

Output T lines, one for each test case, containing the minimum number of days in which all problems can be solved.

Sample Input

Sample Output

2  
1

Explanation

For the first example, you can solve the problems with rating 5 and 7 on the first day and the problem with rating 4 on the next day. Note that the problems with rating 5 and 4 cannot be completed consecutively because the ratings should differ by at least K (which is 2). Also, the problems cannot be completed in order 5,7,4 in one day because the problems solved on a day should be in increasing difficulty level.

For the second example, all problems can be solved on the same day.

HackerRank Problem solving Problem Solution

Problem solving C Solution

#include<stdio.h>
#include<string.h>
#include <math.h>
#define SIZE 310

int N, K;
int v[SIZE];

int size_a, size_b;
int set_a[SIZE], set_b[SIZE];
int visit_a[SIZE], visit_b[SIZE];
int edg[SIZE][SIZE];

int ans;

int DFS( int v ){
    int i;
    visit_a[v]= 1;
    for( i=1; i<=size_b; i++ )
    if( edg[v][i] && !visit_b[i] ){
        visit_b[i]= 1;
        if( !set_b[i] || DFS( set_b[i] ) ){
            set_a[v]= i;
            set_b[i]= v;
            return 1;
        }
    }
    return 0;
}
void B_match(  ){
    int i;
    ans= 0;
    for( i=1; i<=size_a; i++ )
    if( !set_a[i] ){
        memset( visit_a, 0, sizeof( visit_a ) );
        memset( visit_b, 0, sizeof( visit_b ) );
        if( DFS( i ) )  ans++;
     }
}

int main(int argc, const char *argv[])
{
    int T;
    int i, j, k;

    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &N, &K);
        for (i = 0; i < N; i++) {
            scanf("%d", v+i);
        }
        memset( set_a, 0, sizeof( set_a )  );
        memset( set_b, 0, sizeof( set_b )  );
        memset( edg, 0, sizeof( edg )  );
        for (i = 0; i < N; i++) {
            for (j = i+1; j < N; j++) {
                k = abs(v[i] - v[j]);
                if (k >= K) {
                    edg[i+1][j+1] = 1;
                }
            }
        }
        size_a = size_b = N;
        ans= 0;
        B_match();
        printf("%d\n", N-ans);
    }
    return 0;
}

Problem solving C++ Solution

#include <bits/stdc++.h>
using namespace std;
const int N = 601;
const int M = 300;
bool vis[N];
int tc;
int n, k;
int match;

struct Node {
  int val;
  int mtc;
  vector<int> adj;
} node[N];

void input() {
  cin >> n >> k;
  match = 0;
  for (int i = 0; i < n; ++i) {
    cin >> node[i].val;
  }
  for (int i = 0; i < n; ++i) {
    node[i].adj.clear();
    node[i].mtc = node[i + M].mtc = -1;
    for (int j = i + 1; j < n; ++j) {
      if (abs(node[i].val - node[j].val) >= k) {
        node[i].adj.push_back(M + j);
      }
    }
  }
}

bool dfs(int u) {
  if (vis[u])
    return 0;
  vis[u] = 1;
  for (int v : node[u].adj) {
    if (node[v].mtc == -1 || dfs(node[v].mtc)) {
      node[u].mtc = v;
      node[v].mtc = u;
      return 1;
    }
  }
  return 0;
}

void solve() {
  while (1) {
    bool ok = 0;
    memset(vis, 0, sizeof vis);
    for (int i = 0; i < n; ++i) {
      if (node[i].mtc == -1 && dfs(i)) {
        match++;
        ok = 1;
      }
    }
    if (!ok) {
      break;
    }
  }
  cout << n - match << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> tc;
  while (tc--) {
    input();
    solve();
  }
}

Problem solving C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

    /*
     * Complete the 'problemSolving' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER k
     *  2. INTEGER_ARRAY v
     */

    private static bool check(int x, List<List<int>> a, List<int> match, HashSet<int> visit)
    {
        for (int i = 0; i < a[x].Count; i++)
        {
            if (!visit.Contains(a[x][i]))
            {
                visit.Add(a[x][i]);
                if (match[a[x][i]] == -1 || check(match[a[x][i]], a, match, visit))
                {
                    match[a[x][i]] = x;
                    return true;
                }
            }
        }

        return false;
    }

    public static int problemSolving(int k, List<int> v)
    {
        var a = v.Select((val, idx) =>
                v.Select((innerVal, innerIdx)=>(innerVal, innerIdx))
                    .Skip(idx + 1)
                    .Where(inner => Math.Abs(val - inner.Item1) >= k)
                    .Select(inner=>inner.Item2)
                    .ToList()
        ).ToList();
        var match = v.Select(val => -1).ToList();

        var res = 0;

        for (int i = 0; i < v.Count; i++)
        {
            res += check(i, a, match, new HashSet<int>())?1:0;
        }

        return v.Count - res;
    }

}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int t = Convert.ToInt32(Console.ReadLine().Trim());
        for(var i=0; i<t; i++){

        string[] firstMultipleInput = Console.ReadLine().TrimEnd().Split(' ');

        int n = Convert.ToInt32(firstMultipleInput[0]);

        int k = Convert.ToInt32(firstMultipleInput[1]);

        List<int> v = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(vTemp => Convert.ToInt32(vTemp)).ToList();

        int result = Result.problemSolving(k, v);

        textWriter.WriteLine(result);
        }
        textWriter.Flush();
        textWriter.Close();
    }
}

Problem solving Java Solution

import java.io.*;
import java.util.*;

public class Solution {

    private void solution() throws IOException {
        int ts = in.nextInt();
        while (ts-- > 0) {
            int n = in.nextInt();
            int k = in.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; ++i) {
                a[i] = in.nextInt();
            }

            int size = 2 * n + 2;
            int[][] cap = new int[size][size];
            int[][] flow = new int[size][size];

            for (int i = 0; i < n; ++i) {
                for (int j = i + 1; j < n; ++j) {
                    if (Math.abs(a[i] - a[j]) >= k) {
                        cap[i][n + j] = 1;
                    }
                }
            }

            int s = size - 2;
            int t = size - 1;

            for (int i = 0; i < n; ++i) {
                cap[s][i] = 1;
                cap[n + i][t] = 1;
            }

            boolean[] used = new boolean[size];
            int res = 0;
            while (dfs(s, t, cap, flow, used)) {
                ++res;
                Arrays.fill(used, false);
            }
            out.println(n - res);
        }
    }

    private boolean dfs(int at, int t, int[][] cap, int[][] flow, boolean[] used) {
        if (used[at]) {
            return false;
        }
        if (at == t) {
            return true;
        }
        used[at] = true;

        for (int next = 0; next < cap.length; ++next) {
            if (!used[next] && cap[at][next] > flow[at][next]) {
                if (dfs(next, t, cap, flow, used)) {
                    ++flow[at][next];
                    --flow[next][at];
                    return true;
                }
            }
        }
        return false;
    }

    public void run() {
        try {
            solution();
            in.reader.close();
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    private class Scanner {
        StringTokenizer tokenizer;

        BufferedReader reader;

        public Scanner(Reader reader) {
            this.reader = new BufferedReader(reader);
            this.tokenizer = new StringTokenizer("");
        }

        public boolean hasNext() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                String line = reader.readLine();
                if (line == null) {
                    return false;
                }
                tokenizer = new StringTokenizer(line);
            }
            return true;
        }

        public String next() throws IOException {
            hasNext();
            return tokenizer.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }

    public static void main(String[] args) throws IOException {
        new Solution().run();
    }

    Scanner in = new Scanner(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
}

Problem solving JavaScript Solution

//Logic inspired from https://code.google.com/codejam/contest/dashboard?c=204113#s=a&a=2
// Exercise is pointless. There is no correlation between the statement and the expected results in the test cases
function Graph(N) {
    var i;
    
    this.N = N;
    this.edges = [];
    for(i = 0; i < N; i++) {
        this.edges[i] = [];
    }
}
Graph.prototype = (function() {
    function addEdge(i, j) {
        this.edges[i][j] = true;
    }
    
    function augmentingPathExists(i, edges, visited, matchedWith) {
        var j;
        if(i == -1) { return true; }
        
        if(visited[i]) { return false; }
        visited[i] = true;
        
        for(j in edges[i]) {
            if(augmentingPathExists(matchedWith[j], edges, visited, matchedWith)) {
                matchedWith[j] = i;
                return true;
            }
        }
        return false;
    }
    function getMaximumMatching() {
        var i, N = this.N, edges = this.edges, cnt = 0, matchedWith = {};
        
        for(i = 0; i < N; i++) {
            matchedWith[i] = -1;
        }        
        for(i = 0; i < N; i++) {
            if(augmentingPathExists(i, edges, {}, matchedWith)) {
                cnt++;
            }
        }
        return cnt;
    }
    return {
        addEdge: addEdge,
        getMaximumMatching: getMaximumMatching
    };
})();
function getMinPathCover(K, arr) {
    var i, j, val, len = arr.length;
    var graph = new Graph(len);
    for(i = 0; i < len; i++) {
        val = arr[i];
        for(j = 0; j < i; j++) {
            if(Math.abs(arr[j] - val) >= K) {
                graph.addEdge(j, i);
            }
        }
    }
    return len - graph.getMaximumMatching();
}
function processData(input) {
    var lines = input.split('\n');
    var getIntArrFromLine = function(line) {
        return line.split(' ').map(function(e) { return parseInt(e, 10); });
    };
    var i, K, arr;
    
    for(i = 1; i < lines.length; i += 2) {
        arr = getIntArrFromLine(lines[i]);
        K = arr[1];
        arr = getIntArrFromLine(lines[i + 1]);
        console.log(getMinPathCover(K, arr));
    }
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Problem solving Python Solution

#!/bin/python3

import os
import sys

#
# Complete the problemSolving function below.
#
def problemSolving(k, v):
    #
    # Write your code here.
    #

    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input())

    nk = input().split()

    n = int(nk[0])

    k = int(nk[1])

    v = list(map(int, input().rstrip().split()))

    result = problemSolving(k, v)

    fptr.write(str(result) + '\n')

    fptr.close()
def hung(i,s):
    for x in E[i]:
        if F[x]!=s:
            F[x]=s
            if B[x]==-1 or hung(B[x],s):
                B[x]=i
                return 1
    return 0
for _ in range(int(input().strip())):
    N,K = map(int,input().strip().split(' '))
    D,F,B = [int(x) for x in input().strip().split()],[-1]*N,[-1]*N
    E = [list(filter(lambda j:abs(D[j]-D[i])>=K,range(i+1,N))) for i in range(N)]
    print(N - sum(map(lambda i :hung(i,i),range(N))))

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python