HackerRank Covering the stains Problem Solution Yashwant Parihar, August 6, 2023August 1, 2024 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 FormatThe 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 5 2 0 1 3 3 2 0 0 3 2 3 Sample Output 8 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. HackerRank Covering the stains Problem Solution 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) c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython