HackerRank Covering the stains Problem Solution

In this post, we will solve 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 as 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).
Assume that each stain is a point and that the rectangle is aligned parallel to the axes.
Input Format
The first line contains two integers N (1=N<=1000) and K (0K<=N). Next follow N lines. one for each stain. Each line contains two integers in the form ‘X Y’, (0<=XY<100000), the coordinates of each stain into the blanket. Each pair of coordinates is unique.

Output Format

Output a single integer. The remainder of the division by 1000000007 of the answer.

Sample Input

Sample Output

Explanation

We can clean two spots. So removing any of the following set of stains will lead us to a conbination that will need less amount of silk.(The numbers refer to the indices of the stains in the input and they begin from 1).

1, 4
2, 1
2, 3
2, 4
2, 5
3, 1
3, 4
3, 5

So there are 8 ways.

Table of Contents

Covering the stains C Solution

#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
long long modPow(long long a,int x);
long long modInverse(long long a);
long long C(int n,int k);
long long fac[1001];
long long ifac[1001];

int main(){
  int N,K,maxx=-1,maxy=-1,minx=-1,miny=-1,u=0;
  int d=0,l=0,r=0,ul=0,ur=0,dl=0,dr=0,i,t;
  int *x,*y;
  long long ans=0;
  fac[0]=fac[1]=ifac[0]=ifac[1]=1;
  for(i=2;i<1001;i++){
    fac[i]=i*fac[i-1]%MOD;
    ifac[i]=modInverse(fac[i]);
  }
  scanf("%d%d",&N,&K);
  x=(int*)malloc(N*sizeof(int));
  y=(int*)malloc(N*sizeof(int));
  for(i=0;i<N;i++){
    scanf("%d%d",x+i,y+i);
    if(minx==-1 || x[i]<minx)
      minx=x[i];
    if(miny==-1 || y[i]<miny)
      miny=y[i];
    if(maxx==-1 || x[i]>maxx)
      maxx=x[i];
    if(maxy==-1 || y[i]>maxy)
      maxy=y[i];
  }
  for(i=0;i<N;i++){
    if(x[i]==minx)
      l++;
    if(x[i]==maxx)
      r++;
    if(y[i]==miny)
      d++;
    if(y[i]==maxy)
      u++;
    if(x[i]==minx && y[i]==miny)
      dl++;
    if(x[i]==minx && y[i]==maxy)
      ul++;
    if(x[i]==maxx && y[i]==miny)
      dr++;
    if(x[i]==maxx && y[i]==maxy)
      ur++;
  }
  if(N==1){
    if(K==0)
      printf("0");
    else
      printf("1");
  }
  else if(minx==maxx || miny==maxy){
    if(K>=1)
      ans=(ans+C(N-1,K-1)*2%MOD)%MOD;
    if(K>=2)
      ans=(ans-C(N-2,K-2)+MOD)%MOD;
    printf("%lld",ans);
  }
  else{
    if(K>=u)
      ans=(ans+C(N-u,K-u))%MOD;
    if(K>=d)
      ans=(ans+C(N-d,K-d))%MOD;
    if(K>=l)
      ans=(ans+C(N-l,K-l))%MOD;
    if(K>=r)
      ans=(ans+C(N-r,K-r))%MOD;
    t=u+d;
    if(K>=t)
      ans=(ans-C(N-t,K-t)+MOD)%MOD;
    t=u+l-ul;
    if(K>=t)
      ans=(ans-C(N-t,K-t)+MOD)%MOD;
    t=u+r-ur;
    if(K>=t)
      ans=(ans-C(N-t,K-t)+MOD)%MOD;
    t=d+l-dl;
    if(K>=t)
      ans=(ans-C(N-t,K-t)+MOD)%MOD;
    t=d+r-dr;
    if(K>=t)
      ans=(ans-C(N-t,K-t)+MOD)%MOD;
    t=l+r;
    if(K>=t)
      ans=(ans-C(N-t,K-t)+MOD)%MOD;
    t=u+d+l-ul-dl;
    if(K>=t)
      ans=(ans+C(N-t,K-t))%MOD;
    t=u+d+r-ur-dr;
    if(K>=t)
      ans=(ans+C(N-t,K-t))%MOD;
    t=u+r+l-ul-ur;
    if(K>=t)
      ans=(ans+C(N-t,K-t))%MOD;
    t=r+d+l-dl-dr;
    if(K>=t)
      ans=(ans+C(N-t,K-t))%MOD;
    t=u+d+l+r-ul-ur-dl-dr;
    if(K>=t)
      ans=(ans-C(N-t,K-t)+MOD)%MOD;
    printf("%lld",ans);
  }
  return 0;
}
long long modPow(long long a,int x){
  long long res = 1;
  while(x>0){
    if(x%2)
      res=res*a%MOD;
    a=a*a%MOD;
    x>>=1;
  }
  return res;
}
long long modInverse(long long a){
  return modPow(a,MOD-2);
}
long long C(int n,int k){
  return fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;
}

Covering the stains C++ Solution

#include <cassert>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
typedef unsigned int uint;
typedef unsigned long long int ull;
uint const mod=1e9+7;
uint const max_N=1000;

int main()
{
    uint N=0,K=0;
    scanf("%u%u",&N,&K);
    assert(1<=N && N<=max_N);
    assert(0<=K && K<=N);
    struct pos { int x=0,y=0; };
    std::vector<pos> P(N);
    int min_x=0,min_y=0,max_x=0,max_y=0;
    for(uint i=0; i<N; ++i)
    {
        pos &p=P[i];
        scanf("%d%d",&p.x,&p.y);
        if(0<i)
        {
            min_x=std::min(min_x,p.x);
            min_y=std::min(min_y,p.y);
            max_x=std::max(max_x,p.x);
            max_y=std::max(max_y,p.y);
        }
        else
        {
            min_x=(max_x=p.x);
            min_y=(max_y=p.y);
        }
    }

    uint A[16][max_N+1]={};
    A[0][0]=1;
    for(uint n=0; n<N; ++n)
    {
        pos p=P[n];
        uint pm=0;
        if(p.y==max_y)
            pm|=1;
        if(p.x==max_x)
            pm|=2;
        if(p.y==min_y)
            pm|=4;
        if(p.x==min_x)
            pm|=8;

        uint A2[16][max_N+1]={};
        for(uint m=0; m<16; ++m)
        {
            uint m2=m|pm;
            for(uint i=0; i<=N; ++i)
            {
                A2[m][i]=(A2[m][i]+A[m][i])%mod;
                A2[m2][i+1]=(A2[m2][i+1]+A[m][i])%mod;
            }
        }
        for(uint m=0; m<16; ++m)
            for(uint i=0; i<=N; ++i)
                A[m][i]=A2[m][i];
    }

    uint r=0;
    if(min_x<max_x && min_y<max_y)
        for(uint m=0; m<15; ++m)
            r=(r+A[m][N-K])%mod;
    printf("%u\n",r);
    return 0;
}

Covering the stains C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
    static void Main(String[] args) {
        /* Enter your code here. Read input from STDIN. Prlong output to STDOUT. Your class should be named Solution */
        string[] no=Console.ReadLine().Split(' ');
        long N=Convert.ToInt64(no[0]);
        long K=Convert.ToInt64(no[1]);
        List<long> longlistx=new  List<long>();
        List<long> longlisty=new  List<long>();
        long way_count=0;
        //long[ , ] arr=new long[N,N];
        List<string> longersect=new List<string>();
        for(long i=0;i<N;i++)
        {
            string[] no1=Console.ReadLine().Split(' ');
            //arr[i,0]=Convert.ToInt32(no1[0]);
            //arr[i,1]=Convert.ToInt32(no1[1]);  
            longlistx.Add(Convert.ToInt64(no1[0]));
            longlisty.Add(Convert.ToInt64(no1[1])); 
            longersect.Add(string.Format("{0},{1}",no1[0],no1[1])); 
        }
        if(N==K)
        {
           way_count=1; 
        }
        else
        {
            long xmax=longlistx.Max();
            long xmin=longlistx.Min();
            long ymax=longlisty.Max();
            long ymin=longlisty.Min();
            long p3=longlistx.Where(x=>x==xmax).Count();//p3xmax_count
            long p1=longlistx.Where(x=>x==xmin).Count();//p1xmin_count
            long p2=longlisty.Where(x=>x==ymax).Count();//p2ymax_count
            long p4=longlisty.Where(x=>x==ymin).Count();//p4ymin_count
            long p3p4=longersect.Any(x=>x.Equals(string.Format("{0},{1}",xmax,ymin))) ? 1 :0;//p1p4
            long p2p3=longersect.Any(x=>x.Equals(string.Format("{0},{1}",xmax,ymax)))? 1 :0;//p1p3
            long p1p4=longersect.Any(x=>x.Equals(string.Format("{0},{1}",xmin,ymin)))? 1 :0;//p2p4
            long p1p2=longersect.Any(x=>x.Equals(string.Format("{0},{1}",xmin,ymax)))? 1 :0;//p2p3
 
            long[] way1_arr={p1,p2,p3,p4};
            long way1=Way(N,K,way1_arr.ToList());
            long[] way2_arr={p1+p2-p1p2,p1+p3,p1+p4-p1p4,p2+p3-p2p3,p2+p4,p3+p4-p3p4};
            long way2=Way(N,K,way2_arr.ToList());
            long[] way3_arr={p1+p2+p3-p1p2-p2p3,p1+p2+p4-p1p4-p1p2,p1+p3+p4-p1p4-p3p4,p2+p3+p4-p2p3-p3p4};
            long way3=Way(N,K,way3_arr.ToList());
            long[] way4_arr={p1+p2+p3+p4-p1p2-p1p4-p2p3-p3p4};
            long way4=Way(N,K,way4_arr.ToList());
            way_count=(way1-way2+way3-way4) % 1000000007;
            if(way_count<0)
                way_count = way_count + 1000000007;
            
        }        
       Console.WriteLine(way_count % 1000000007);
    }
    public static long factorial(long numberInt)
    {
       long result=1;
       //Console.WriteLine(numberInt);
       for (long i = 2; i <=numberInt; i++)
        {
            result = result * i;
        }
        //Console.WriteLine(result);
        return result;
    }
    public  static long Way(long N,long K,List<long> xList)//long xmax_count,long xmin_count,long ymax_count,long ymin_count)
    {
        long way_count=0;
        foreach(long x in xList)
        {
            if(K==x)
            {
                way_count++;
            }
            else if(x<K)
            {
                //n-xmax_countCK-xmax_count
                
                long a=N-x;
                long b=K-x;
                way_count=(way_count+fuc(a,b)) % 1000000007;
              
            }
        }
        //Console.WriteLine("r:"+way_count);
        return way_count;
    }
   public static long fuc(long n, long k)
{
   // This function gets the total number of unique combinations based upon N and K.
   // N is the total number of items.
   // K is the size of the group.
   // Total number of unique combinations = N! / ( K! (N - K)! ).
   // This function is less efficient, but is more likely to not overflow when N and K are large.
   // Taken from:  http://blog.plover.com/math/choose.html
   //
   long [,] C = new long [n+1,k+1];
//C[n+1][k+1];
    long i, j;
 
    // Caculate value of Binomial Coefficient in bottom up manner
    for (i = 0; i <= n; i++)
    {
        for (j = 0; j <= min(i, k); j++)
        {
            // Base Cases
            if (j == 0 || j == i)
                C[i,j] = 1;
 
            // Calculate value using previosly stored values
            else
                C[i,j] = (C[i-1,j-1] + C[i-1,j]) % 1000000007;
            //Console.WriteLine("r:"+C[i,j]);
        }
    }
    // Console.WriteLine("r:"+C[n,k]);
    return C[n,k] % 1000000007;

   
}
    
    public static long min(long a, long b)
{
    return (a<b)? a: b;
}

}

Covering the stains Java Solution

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;

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


}

Covering the stains Python Solution

def stain_combos(n, k):
    p = 1000000007
    if k < 0:
        return 0
    out = 1
    for i in range(n-k+1, n+1):
        out = (out * i) % p 
    denom = 1
    for i in range(1, k+1):
        denom = (denom * i) % p
    denom = pow(denom, p-2, p)
    return (out*denom)%p


def solve(n, k, stains):
    print(size_decrease(stains, k))

from itertools import combinations
from functools import reduce

def size_decrease(stains, k):
    min_x = min([p.x for p in stains])
    max_x = max([p.x for p in stains])
    min_y = min([p.y for p in stains])
    max_y = max([p.y for p in stains])
    top = {p for p in stains if p.x==min_x}
    bot = {p for p in stains if p.x==max_x}
    left = {p for p in stains if p.y==min_y}
    right = {p for p in stains if p.y==max_y}

    out = 0
    for i in range(1, 5):
        for sides in combinations([top, bot, left, right], i):
            removed = reduce(lambda x,y: x.union(y), sides)
            length = len(removed)
            out += ((-1)**(i+1)) * stain_combos(len(stains)-length, k-length)
    return out%1000000007 

from collections import namedtuple

point = namedtuple('point', ['x','y'])

n, k = [int(x) for x in input().split(" ")]

stains = []

for _ in range(n):
    stains.append(point(*[int(number) for number in input().split(" ")]))

solve(n, k, stains)

Covering the stains C Solution

Covering the stains C++ Solution

Covering the stains C Sharp Solution

Covering the stains Java Solution

Covering the stains Python Solution

Related Posts