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).
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()
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);
}
}
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("%d\n", ans);
return 0;
}
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("%lld\n", ans);
}
int main() {
input();
process();
return 0;
}
0 Comments