Table of Contents
Covering the stains – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Covering the stains HackerRank Solution
#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;
}
Java Covering the stains HackerRank Solution
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
public class Solution {
private static Reader in;
private static PrintWriter out;
public static long mod = 1000000007;
public static long mod_exp(long b, long e) {
long r = 1;
while (e > 0) {
if ((e & 1) == 1) r = (r * b) % mod;
b = (b * b) % mod;
e >>= 1;
}
return r;
}
public static long[] fact, invfact;
public static void main(String[] args) throws IOException {
in = new Reader();
out = new PrintWriter(System.out, true);
fact = new long[1001];
invfact = new long[1001];
fact[0] = 1;
invfact[0] = 1;
for (int i = 1; i <= 1000; i++) {
fact[i] = (i * fact[i - 1]) % mod;
invfact[i] = mod_exp(fact[i], mod - 2);
}
int sx = 1 << 29, sy = 1 << 29, ex = -1, ey = -1;
int N = in.nextInt(), K = in.nextInt();
int[][] p = new int[N][2];
for (int i = 0; i < N; i++) {
p[i] = new int[2];
p[i][0] = in.nextInt();
p[i][1] = in.nextInt();
if (p[i][0] < sx) sx = p[i][0];
if (p[i][0] > ex) ex = p[i][0];
if (p[i][1] < sy) sy = p[i][1];
if (p[i][1] > ey) ey = p[i][1];
}
int[] b = new int[] {sx, ex, sy, ey};
int[] id = new int[] {0, 0, 1, 1};
long total = 0;
for (int mask = 1; mask < 1 << 4; mask++) {
int count = 0;
for (int i = 0; i < N; i++) {
boolean ok = false;
for (int j = 0; j < 4; j++) {
if (set(mask, j) && p[i][id[j]] == b[j])
ok = true;
}
if (ok) count++;
}
long sgn = Integer.bitCount(mask) % 2 == 1 ? 1 : (mod - 1);
total = (total + sgn * binom(N - count, K - count)) % mod;
}
out.println(total);
out.close();
System.exit(0);
}
public static boolean set(int m, int i) {
return ((m >> i) & 1) == 1;
}
public static long binom(int N, int K) {
if (K < 0 || K > N) return 0;
return fact[N] * invfact[K] % mod * invfact[N - K] % mod;
}
static class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader() {
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public Reader(String file_name) throws IOException {
din = new DataInputStream(new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public String readLine() throws IOException {
byte[] buf = new byte[1024];
int cnt = 0, c;
while ((c = read()) != -1) {
if (c == '\n')
break;
buf[cnt++] = (byte) c;
}
return new String(buf, 0, cnt);
}
public int nextInt() throws IOException {
int ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public long nextLong() throws IOException {
long ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public double nextDouble() throws IOException {
double ret = 0, div = 1;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (c == '.')
while ((c = read()) >= '0' && c <= '9')
ret += (c - '0') / (div *= 10);
if (neg)
return -ret;
return ret;
}
private void fillBuffer() throws IOException {
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException {
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException {
if (din == null)
return;
din.close();
}
}
}
Python 3 Covering the stains HackerRank 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)
Python 2 Covering the stains HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
mod = 1000000007
N, K = map(int, raw_input().split())
l = []
for i in xrange(N):
a,b = map(int, raw_input().split())
l.append((a,b))
limits = []
# xmin
xmin = min([x[0] for x in l])
limits.append(set([i for i in xrange(len(l)) if l[i][0] == xmin]))
#xmax
xmax = max([x[0] for x in l])
limits.append(set([i for i in xrange(len(l)) if l[i][0] == xmax]))
#ymin
ymin = min([x[1] for x in l])
limits.append(set([i for i in xrange(len(l)) if l[i][1] == ymin]))
#ymax
ymax = max([x[1] for x in l])
limits.append(set([i for i in xrange(len(l)) if l[i][1] == ymax]))
fact = [1]
for i in xrange(1,2000):
fact.append((i*fact[-1]) % mod)
def inv(x):
return pow(x, mod-2, mod)
def comb(a, b):
return (fact[a] * inv(fact[b]) * inv(fact[a-b])) % mod
ans = 0
for i in xrange(1, 16):
temp = set([])
cnt = 0
for j in xrange(4):
if (i / (2**j)) % 2 == 1:
cnt += 1
temp = temp.union(limits[j])
if len(temp) > K: continue
tmp = comb(N - len(temp), K - len(temp))
if cnt % 2 == 0: ans = (ans - tmp + mod) % mod
else: ans = (ans + tmp) % mod
print ans
C Covering the stains HackerRank 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,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;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
