HackerRank Covering the stains problem solution

YASH PAL,

In this HackerRank Covering the stains problem solution, There is a huge blanket on your bed but unfortunately, it has N stains. You cover them using a single, rectangular silk cloth. The silk is expensive, which is why the rectangular piece needs to have the least area possible. You love this blanket and decide to minimize the area covering the stains. You buy some cleaning liquid to remove the stains but sadly it isn’t enough to clean all of them. You can just remove exactly K stains. The rest of the stains need to be covered using a single, rectangular fragment of silk cloth.

Let X denote the area of the smallest possible silk cloth that may cover all the stains originally. You need to find the number of different ways in which you may remove K stains so that the remaining N-K stains can be covered with silk of area strictly less than X (We are looking for any configuration that will reduce the cost).

HackerRank Covering the stains problem solution

Problem solution in Python.

#!/bin/python3

import os
import sys
def binomial(n,k):
    p=(n,k)
    if p in bin:
        return bin[p]
    if k==0 or k==n:
        return 1
    if k==1 or k+1==n:
        return n
    res= (binomial(n-1,k)+binomial(n-1,k-1))%mod
    bin[p]=res
    return res
bin={}
mod=1000000007
#
# Complete the coveringStains function below.
#
def coveringStains(k, coordinates):
    #
    # Write your code here.
    #
    n=len(coordinates)
    if k in [0,n]:
        return 1
    xmin=ymin=1111111
    xmax=ymax=-1
    for p in coordinates:
        x,y=p
        xmax=max(x,xmax)
        xmin=min(x,xmin)
        ymax=max(y,ymax)
        ymin=min(y,ymin)
    if xmin==xmax or ymin==ymax:
        res=  binomial(n-1,k-1)*2%mod
        if k>1:
            res-=binomial(n-2,k-2)
        return res%mod
    nx1=nx2=ny1=ny2=x1y1=x1y2=x2y1=x2y2=0
    for p in coordinates:
        x,y=p
        if x==xmin:
            nx1+=1
        if x==xmax:
            nx2+=1
        if y==ymin:
            ny1+=1
        if y==ymax:
            ny2+=1
        if x==xmin and y==ymin:
            x1y1+=1
        if x==xmin and y==ymax:
            x1y2+=1
        if x==xmax and y==ymin:
            x2y1+=1
        if x==xmax and y==ymax:
            x2y2+=1
        res=0
    for b in [nx1,nx2,ny1,ny2]:
        if k>=b:
            res+=binomial(n-b,k-b)
    for b in [nx1+nx2,ny1+ny2,nx1+ny1-x1y1,nx1+ny2-x1y2,nx2+ny1-x2y1,nx2+ny2-x2y2]:
        if k>=b:
            res-=binomial(n-b,k-b)
    for b in [nx1+ny1+nx2-x1y1-x2y1,nx1+ny2+nx2-x1y2-x2y2,ny1+nx1+ny2-x1y1-x1y2,ny1+nx2+ny2-x2y1-x2y2]:
        if k>=b:
            res+=binomial(n-b,k-b)
    b=nx1+ny1+nx2+ny2-x1y1-x2y1-x1y2-x2y2
    if k>=b:
        res-=binomial(n-b,k-b)
    return res%mod

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nk = input().split()

    n = int(nk[0])

    k = int(nk[1])

    coordinates = []

    for _ in range(n):
        coordinates.append(list(map(int, input().rstrip().split())))

    result = coveringStains(k, coordinates)

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

    fptr.close()

{“mode”:”full”,”isActive”:false}

Problem solution in Java.

import java.io.PrintWriter;
import java.util.Scanner;

public class Solution{
    public static final int MOD = (int) 1e9 + 7;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        while(sc.hasNext()){
            solve(sc, pw);
        }
        sc.close();
        pw.flush();
        pw.close();
    }

    private static void solve(Scanner sc, PrintWriter pw){
        int N = sc.nextInt();
        int K = sc.nextInt();
        K = N - K;

        int[][] stains = new int[N+1][2];
        int[] vals = new int[]{0,100000,0,100000};
        for(int i = 1; i <= N; i++){
            stains[i][0] = sc.nextInt();
            stains[i][1] = sc.nextInt();
            vals[0] = Math.max(vals[0], stains[i][0]);
            vals[1] = Math.min(vals[1], stains[i][0]);
            vals[2] = Math.max(vals[2], stains[i][1]);
            vals[3] = Math.min(vals[3], stains[i][1]);
        }

        if(K == 0){
            pw.println(1);
            return;
        }

        int[] arr = new int[N+1];
        for(int i = 1; i <= N; i++) {
            int mask = 0;
            for(int j = 0; j < 4; j++){
                if(vals[j] == stains[i][j/2]){
                    mask |= (1 << j);
                }
            }
            arr[i] = mask;
        }

        int[][][] dp = new int[K+1][N+1][16];

        for(int j = 1; j <= N; j++){
            dp[1][j][arr[j]] = 1;
            for(int k = 0; k < 16; k++){
                dp[1][j][k] += dp[1][j-1][k];
            }
        }

        for(int i = 1; i < K; i++){
            for(int j = i; j < N; j++){
                for(int k = 0; k < 16; k++){
                    dp[i+1][j+1][k | arr[j+1]] = (dp[i+1][j+1][k | arr[j+1]] + dp[i][j][k]) % MOD;
                    dp[i+1][j+1][k] = (dp[i+1][j+1][k] + dp[i+1][j][k]) % MOD;
                }
            }
        }

        int ans = 0;
        for(int k = 0; k < 15; k++){
            ans = (ans + dp[K][N][k]) % MOD;
        }
        pw.println(ans);
    }


}

{“mode”:”full”,”isActive”:false}

Problem solution in C++.

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int MOD = 1000000007, MAXN = 1005;

int binom[MAXN][MAXN];

int N, K;
int X[MAXN], Y[MAXN];
int Xmin, Xmax, Ymin, Ymax;
pair<int, int> dude[4];

inline int calc(vector<pair<int, int> > vec) {
   int num = 0;
   for(int i = 0 ; i < N ; i++) {
      for(int j = 0 ; j < (int)vec.size() ; j++) {
         if (vec[j].first == 0 && X[i] == vec[j].second) {
            num++;
            break;
         }   else if (vec[j].first == 1 && Y[i] == vec[j].second) {
            num++;
            break;
         }
      }
   }
   if (num > K) {
      return 0;
   }   else {
      return binom[N - num][K - num];
   }
}

int main() {
   scanf("%d %d", &N, &K);
   binom[0][0] = 1;
   for(int i = 1 ; i <= N ; i++) {
      binom[i][0] = 1;
      for(int j = 1 ; j <= i ; j++) {
         binom[i][j] = (binom[i - 1][j] + binom[i - 1][j - 1]) % MOD;
      }
   }
   
   for(int i = 0 ; i < N ; i++) {
      scanf("%d %d", &X[i], &Y[i]);
   }
   Xmin = X[0];
   Xmax = X[0];
   Ymin = Y[0];
   Ymax = Y[1];
   for(int i = 1 ; i < N ; i++) {
      Xmin = min(Xmin, X[i]);
      Xmax = max(Xmax, X[i]);
      Ymin = min(Ymin, Y[i]);
      Ymax = max(Ymax, Y[i]);
   }
   dude[0] = make_pair(0, Xmin);
   dude[1] = make_pair(0, Xmax);
   dude[2] = make_pair(1, Ymin);
   dude[3] = make_pair(1, Ymax);
   int ans = 0;
   for(int mask = 1 ; mask < 16 ; mask++) {
      int sgn = __builtin_popcount(mask);
      vector<pair<int,int> > v;
      for(int i = 0 ; i < 4 ; i++) {
         if ((mask >> i) & 1) {
            v.push_back(dude[i]);
         }
      }
      if (sgn & 1) {
         ans = (ans + calc(v)) % MOD;
      }   else {
         ans = (ans - calc(v)) % MOD;
      }
   }
   ans = (ans + MOD) % MOD;
   ans = (ans + MOD) % MOD;
   printf("%dn", ans);
   return 0;
}

{“mode”:”full”,”isActive”:false}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>


int a[1005][2];
int edge[4];
int n, total;

void input() {
    int i, j, k;
	
    scanf("%d %d", &n, &total);
    edge[0] = edge[2] = 1005 * 1005;
	edge[1] = edge[3] = -1;
	
    for (i = 0; i < n; i++) {
        scanf("%d %d", &a[i][0], &a[i][1]);
        if (a[i][0] < edge[0])
			edge[0] = a[i][0];
		if (a[i][0] > edge[1])
			edge[1] = a[i][0];
		
		if (a[i][1] < edge[2])
			edge[2] = a[i][1];
		if (a[i][1] > edge[3])
			edge[3] = a[i][1];
    }
}

int b[1005][2];
const int mod = 1000000007;
typedef long long ll;
ll f[1005], invf[1005];
ll mypow(ll v, ll n) {
    if (n == 0)
        return 1ll;
    if (n == 1)
        return v;
    
    ll p = mypow(v, (n >> 1));
    p = (p * p) % mod;
    if (n & 1)
        return p * v % mod;
    else
        return p;
}

void prepare() {
    f[0] = f[1] = invf[0] = invf[1] = 1ll;
    
    for (int i = 2; i < 1005; i++) {
        f[i] = f[i - 1] * i % mod;
        invf[i] = mypow(f[i], mod - 2);
    }
}

int flag[1005];
int thearray[4][1005];
int num[4];
ll ans;

void solve(int c, int index, int sum) {
	int i, k, j;
	
	if (c >= total || index >= 4)
		return;
	sum++;
	for (i = index; i < 4; i++) {
		for (j = 0; j < num[i]; j++) {
			k = thearray[i][j];
			if (flag[k] == 0) {
				c++;
			}
			flag[k]++;
		}
		
		if (c <= total) {
			// cout<<"i =  "<<i<<"   count = "<<c<<"   sum = "<<sum<<"  ans = "<<ans<<endl;
			if (sum & 1) {
				ans = (ans + f[n - c] * invf[total - c] % mod * invf[n - total]) % mod;
			} else {
				ans = (ans + mod - f[n - c] * invf[total - c] % mod * invf[n - total] % mod) % mod;
			}
			solve(c, i + 1, sum);
		}
		
		for (j = 0; j < num[i]; j++) {
			k = thearray[i][j];
			if (flag[k] == 1) {
				c--;
			}
			flag[k]--;
		}
	}
}

void process() {
    int i, j, k, l, m, t;
    
	j = 0;
    for (i = 0; i < n; i++) {
		if (a[i][0] == edge[0] || a[i][0] == edge[1] || 
			a[i][1] == edge[2] || a[i][1] == edge[3]) {
			b[j][0] = a[i][0];
			b[j++][1] = a[i][1];
		}
    }
	
	prepare();
	m = j;
	k = total;
	if (0 == total) {
		ans = 0;
	} else if (n == total) {
		ans = 1;
	} else {
		if ((edge[0] == edge[1]) || (edge[2] == edge[3])) {
			ans = f[n - 2] * invf[k - 1] % mod * invf[n - k - 1] * 2 % mod;
			if (k >= 2) {
				ans = (ans + f[n - 2] * invf[k - 2] % mod * invf[n - k]) % mod;
			}
		} else {
			
			for (i = 0; i < m; i++) {
				
				for (j = 0; j < 4; j++) {
					k = (j < 2) ? 0 : 1;
					if (b[i][k] == edge[j]) {
						
						thearray[j][num[j]] = i;
						num[j]++;
					}
				}
			}
			
			solve(0, 0, 0);
		}
		
	}
    printf("%lldn", ans);
    
}

int main() {
    input();
    process();
    
    return 0;
}

{“mode”:”full”,”isActive”:false}

algorithm coding problems