In this HackerRank Problem solution, N problems numbered 1..N which you need to complete. You've arranged the problems in increasing difficulty order, and the ith 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?
Problem solution in Python.
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))))
Problem solution in Java.
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
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
*/
static int MAXN = 301;
static int[] match = new int[MAXN];
static List<Integer>[] radj = new List[MAXN];
static {
for (int i = 0; i < MAXN; i++) radj[i] = new ArrayList<>();
}
static boolean[] visited = new boolean[MAXN];
static int[] a;
static int N;
public static int problemSolving(int k, List<Integer> v) {
a = v.stream().mapToInt(x -> x).toArray();
N = a.length;
Arrays.fill(match, -1);
for (int i = 0; i < N; i++) radj[i].clear();
for (int i = 0; i < N; i++) {
for (int j = 0; j < i; j++) {
if (Math.abs(a[i]-a[j]) >= k) {
// j .. i
radj[i].add(j);
}
}
}
int cnt = 0;
for (int i = 0; i < N; i++) {
Arrays.fill(visited, false);
if (!try_extend(i)) cnt++;
}
return cnt;
}
static boolean try_extend(int u) {
if (visited[u]) return false;
visited[u] = true;
for (int v : radj[u]) {
if (match[v] == -1 || try_extend(match[v])) {
match[v] = u;
return true;
}
}
return false;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int t = Integer.parseInt(bufferedReader.readLine().trim());
while (t-- > 0) {
String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
int n = Integer.parseInt(firstMultipleInput[0]);
int k = Integer.parseInt(firstMultipleInput[1]);
List<Integer> v = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList());
int result = Result.problemSolving(k, v);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
}
bufferedReader.close();
bufferedWriter.close();
}
}
Problem solution in C++.
#include <iostream>
#include <string.h>
using namespace std;
#define MAXN 301
#define inf 1000000000
#define _clr(x) memset(x,0xff,sizeof(int)*n)
int kuhn_munkras(int m,int n,int mat[][MAXN],int* match1,int* match2){
int s[MAXN],t[MAXN],l1[MAXN],l2[MAXN],p,q,ret=0,i,j,k;
for (i=0;i<m;i++)
for (l1[i]=-inf,j=0;j<n;j++)
l1[i]=mat[i][j]>l1[i]?mat[i][j]:l1[i];
for (i=0;i<n;l2[i++]=0);
for (_clr(match1),_clr(match2),i=0;i<m;i++){
for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)
for (k=s[p],j=0;j<n&&match1[i]<0;j++)
if (l1[k]+l2[j]==mat[k][j]&&t[j]<0){
s[++q]=match2[j],t[j]=k;
if (s[q]<0)
for (p=j;p>=0;j=p)
match2[j]=k=t[j],p=match1[k],match1[k]=j;
}
if (match1[i]<0){
for (i--,p=inf,k=0;k<=q;k++)
for (j=0;j<n;j++)
if (t[j]<0&&l1[s[k]]+l2[j]-mat[s[k]][j]<p)
p=l1[s[k]]+l2[j]-mat[s[k]][j];
for (j=0;j<n;l2[j]+=t[j]<0?0:p,j++);
for (k=0;k<=q;l1[s[k++]]-=p);
}
}
for (i=0;i<m;i++)
ret+=mat[i][match1[i]];
return ret;
}
int main()
{
int v[301], match1[301], match2[301];
int mat[301][301];
int T;
cin >> T;
for (int t = 0; t < T;t++)
{
int N, K;
cin >> N >> K;
for (int i=0;i<N;i++)
cin >> v[i];
for (int i=0;i<N;i++)
for (int j=0;j<N;j++)
mat[i][j] = 0;
for (int i=0;i<N;i++)
for (int j=i+1;j<N;j++)
{
if (abs(v[i]-v[j]) >= K)
mat[i][j] = 1;
}
cout << N - kuhn_munkras(N, N, mat, match1, match2) << endl;;
}
return 0;
}Problem solution in C.
#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;
}
0 Comments