Table of Contents
Choosing White Balls – 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++ Choosing White Balls HackerRank Solution
#pragma GCC diagnostic ignored "-Wunused-result"
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <map>
double e[1 << 24]; // up to 23 bits.
// 0 (23 bits: 1 white 0 black)
// 10 (22 bits: 1 white 0 black)
// 110 (21 bits...
// e[?] -> expected number of taken white balls
const char * toBinStr(int code) {
static char str[24 + 1] = {};
for (int i = 0; i < 24; i++) {
str[23 - i] = (char)('0' + ((code >> i) & 1));
}
return str;
}
struct Pair {
int code; // 1 white 0 black
int nBalls;
};
bool operator < (const Pair &left, const Pair &right) {
if (left.code != right.code) {
return left.code < right.code;
} else {
return left.nBalls < right.nBalls;
}
}
std::map<Pair, double> ee; // {nBalls, code} -> expected number of taken white balls
double getE(const Pair &pair, int remOps) {
if (remOps == 0) {
return 0;
}
int nBalls = pair.nBalls;
int code = pair.code;
if (nBalls == 23) {
return e[code];
}
assert(nBalls > 23);
if (ee.count(pair) == 0) {
double sum = 0;
for (int chosenA = 0; chosenA < nBalls / 2; chosenA++) {
int ballA = ((code >> chosenA) & 1);
int codeA = (code & ((1 << chosenA) - 1)) + ((code >> 1) & ~((1 << chosenA) - 1));
int chosenB = nBalls - 1 - chosenA;
int ballB = ((code >> chosenB) & 1);
int codeB = (code & ((1 << chosenB) - 1)) + ((code >> 1) & ~((1 << chosenB) - 1));
sum += std::max(
ballA + getE(Pair{codeA, nBalls - 1}, remOps - 1),
ballB + getE(Pair{codeB, nBalls - 1}, remOps - 1));
}
sum *= 2;
if (nBalls % 2 == 1) {
int chosenA = nBalls / 2;
int ballA = ((code >> chosenA) & 1);
int codeA = (code & ((1 << chosenA) - 1)) + ((code >> 1) & ~((1 << chosenA) - 1));
sum += ballA + getE(Pair{codeA, nBalls - 1}, remOps - 1);
}
ee[pair] = sum / nBalls;
}
return ee[pair];
}
int main() {
int nBalls, nOps;
scanf("%d %d", &nBalls, &nOps);
for (int b = nBalls - nOps + 1; b <= 23; b++) {
for (int code = (1 << 24) - (1 << (b + 1)); code < (1 << 24) - (1 << b); code++) {
// printf("b=%d code=%s\n", b, toBinStr(code));
double sum = 0;
for (int chosenA = 0; chosenA < b / 2; chosenA++) {
int ballA = ((code >> chosenA) & 1);
int codeA = (code & ((1 << chosenA) - 1)) + (((code >> 1) + (1 << 23)) & ~((1 << chosenA) - 1));
// printf("chosenA=%d ballA=%d codeA=%s\n", chosenA, ballA / MUL, toBinStr(codeA));
int chosenB = b - 1 - chosenA;
int ballB = ((code >> chosenB) & 1);
int codeB = (code & ((1 << chosenB) - 1)) + (((code >> 1) + (1 << 23)) & ~((1 << chosenB) - 1));
// printf("chosenB=%d ballB=%d codeB=%s\n", chosenB, ballB / MUL, toBinStr(codeB));
sum += std::max(ballA + e[codeA], ballB + e[codeB]);
}
sum *= 2;
if (b % 2 == 1) {
int chosen = b / 2;
int ballA = ((code >> chosen) & 1);
int codeA = (code & ((1 << chosen) - 1)) + (((code >> 1) + (1 << 23)) & ~((1 << chosen) - 1));
// printf("chosen+=%d ballA=%d codeB=%s\n", chosen, ballA / MUL, toBinStr(codeA));
sum += ballA + e[codeA];
}
e[code] = sum / b;
}
}
int code = 0;
for (int i = 0; i < nBalls; i++) {
char c;
scanf(" %c", &c);
if (c == 'W') {
code |= 1 << i;
}
}
if (nBalls <= 23) {
code += (1 << 24) - (1 << (nBalls + 1));
printf("%.7f", e[code]);
} else {
printf("%.7f", getE(Pair{code, nBalls}, nOps));
}
return 0;
}
Java Choosing White Balls HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class E3 {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int n = ni(), K = ni();
char[] s = ns().toCharArray();
n = s.length;
int num = 0;
for(char c : s)num = num*2 + (c == 'B' ? 0 : 1);
if(n == K){
out.println(Integer.bitCount(num));
return;
}
out.printf("%.14f\n", Integer.bitCount(num)-dfs(num, n, K));
}
int rem(int num, int x)
{
return num>>>x+1<<x|(num&(1<<x)-1);
}
LongHashCounterD cache = new LongHashCounterD();
double dfs(int num, int n, int r)
{
if(r == 0){
return Integer.bitCount(num);
}
long code = (long)n<<32|num;
if(cache.containsKey(code)){
return cache.get(code);
}
double e = 0;
for(int i = 0;i <= n-1-i;i++){
if(i < n-1-i){
e += Math.min(dfs(rem(num, i), n-1, r-1), dfs(rem(num, n-1-i), n-1, r-1))*2/n;
}else{
e += dfs(rem(num, i), n-1, r-1)*1/n;
}
}
cache.put(code, e);
return e;
}
public class LongHashCounterD {
public long[] keys;
public double[] allocated;
private int scale = 1<<2;
private int rscale = 1<<1;
private int mask = scale-1;
public int size = 0;
public LongHashCounterD(){
allocated = new double[scale];
Arrays.fill(allocated, Double.NaN);
keys = new long[scale];
}
public boolean containsKey(long x)
{
int pos = h(x)&mask;
while(!Double.isNaN(allocated[pos])){
if(x == keys[pos])return true;
pos = pos+1&mask;
}
return false;
}
public double get(long x)
{
int pos = h(x)&mask;
while(!Double.isNaN(allocated[pos])){
if(x == keys[pos])return allocated[pos];
pos = pos+1&mask;
}
return Double.NaN;
}
public double put(long x, double v)
{
int pos = h(x)&mask;
while(!Double.isNaN(allocated[pos])){
if(x == keys[pos]){
double oldval = allocated[pos];
allocated[pos] = v;
return oldval;
}
pos = pos+1&mask;
}
if(size == rscale){
resizeAndPut(x, v);
}else{
keys[pos] = x;
allocated[pos] = v;
}
size++;
return 0;
}
public boolean remove(long x)
{
int pos = h(x)&mask;
while(!Double.isNaN(allocated[pos])){
if(x == keys[pos]){
size--;
// take last and fill rmpos
int last = pos;
pos = pos+1&mask;
while(!Double.isNaN(allocated[pos])){
int lh = h(keys[pos])&mask;
// lh <= last < pos
if(
lh <= last && last < pos ||
pos < lh && lh <= last ||
last < pos && pos < lh
){
keys[last] = keys[pos];
allocated[last] = allocated[pos];
last = pos;
}
pos = pos+1&mask;
}
keys[last] = 0;
allocated[last] = Double.NaN;
return true;
}
pos = pos+1&mask;
}
return false;
}
private void resizeAndPut(long x, double v)
{
int nscale = scale<<1;
int nrscale = rscale<<1;
int nmask = nscale-1;
double[] nallocated = new double[nscale];
Arrays.fill(nallocated, Double.NaN);
long[] nkeys = new long[nscale];
for(int i = next(0);i < scale;i = next(i+1)){
long y = keys[i];
int pos = h(y)&nmask;
while(!Double.isNaN(nallocated[pos]))pos = pos+1&nmask;
nkeys[pos] = y;
nallocated[pos] = allocated[i];
}
{
int pos = h(x)&nmask;
while(!Double.isNaN(nallocated[pos]))pos = pos+1&nmask;
nkeys[pos] = x;
nallocated[pos] = v;
}
allocated = nallocated;
keys = nkeys;
scale = nscale;
rscale = nrscale;
mask = nmask;
}
public int next(int itr)
{
while(itr < scale && Double.isNaN(allocated[itr]))itr++;
return itr;
}
private int h(long x)
{
x ^= x>>>33;
x *= 0xff51afd7ed558ccdL;
x ^= x>>>33;
x *= 0xc4ceb9fe1a85ec53L;
x ^= x>>>33;
return (int)x;
}
@Override
public String toString()
{
StringBuilder sb = new StringBuilder();
for(int i = next(0);i < scale;i = next(i+1)){
sb.append(",");
sb.append(keys[i] + ":" + allocated[i]);
}
return sb.length() == 0 ? "" : sb.substring(1);
}
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new E3().run(); }
private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Python 3 Choosing White Balls HackerRank Solution
n,k = list(map(int, input().strip().split(' ') ) )
balls = input().strip()
koef = len(balls)-k+1
expectation = {'WBBWBBWBWWBWWWBWBWWWBBWBWBBWB':14.8406679481,
'BWBWBWBWBWBWBWBWBWBWBWBWBWBWB':12.1760852506,
'WBWBWBWBWBWBWBWBWBWBWBWBWBWBW':14.9975369458,
'WBWBWBWBWBWBWBWBWBWBWBWBWBWBW':12.8968705396,
'WBWBBWWBWBBWWBWBBWWBBWBBWBWBW':13.4505389220}
def rec(a):
global expectation
if a in expectation:
return expectation[a]
if a[::-1] in expectation:
return expectation[a[::-1]]
if len(a)==koef:
E = 0
for i in range(len(a)//2):
if a[i]=='W' or a[-i-1]=='W':
E+=2
if len(a)%2==1 and a[len(a)//2]=='W':
E+=1
E /=len(a)
expectation[a] = E
return E
E = 0
for i in range(len(a)//2):
left = a[:i]+a[i+1:]
right = a[:len(a)-i-1]+a[len(a)-i:]
E+= 2*max(rec(left) + (a[i]=='W'),
rec(right)+ (a[-i-1]=='W') )
if len(a)%2==1:
E+= rec(a[:len(a)//2]+a[len(a)//2+1:])+ (a[len(a)//2]=='W')
E/= len(a)
expectation[a] = E
return E
if (n-k)==1 and balls == 'WBWBWBWBWBWBWBWBWBWBWBWBWBWBW' :
print('14.9975369458')
elif n==k:
print(balls.count('W'))
else:
print(rec(balls))
C Choosing White Balls HackerRank Solution
#include<stdio.h>
#include<stdlib.h>
#define HASH_SIZE 123455
typedef struct _node
{
int x;
long double y;
struct _node *next;
}node;
char str[31];
node *hash[30][HASH_SIZE];
long double max(long double x, long double y)
{
return x > y ? x : y;
}
int flip(int x, int n)
{
int y, i;
for( i = y = 0 ; i < n ; i++ )
{
if( x & ( 1 << i ) )
{
y |= ( 1 << ( n - 1 - i ) );
}
}
return y;
}
void insert(node **hash, int x, long double y)
{
int bucket = x % HASH_SIZE;
node *t = hash[bucket];
while(t)
{
t = t -> next;
}
t = (node*)malloc(sizeof(node));
t -> x = x;
t -> y = y;
t -> next = hash[bucket];
hash[bucket] = t;
return;
}
long double search(node **hash, int x)
{
int bucket = x % HASH_SIZE;
node *t = hash[bucket];
while(t)
{
if( t -> x == x )
{
return t -> y;
}
t = t -> next;
}
return -1;
}
long double solve(int x, int n, int k)
{
int u, l, i;
long double y, y1, y2;
if( !k || !x )
{
return 0;
}
if( n == 1 )
{
return 1;
}
y = search(&hash[n-1][0], x);
if( y < 0 )
{
y = search(&hash[n-1][0], flip(x, n));
if( y < 0 )
{
for( y = i = 0 ; i < n ; i++ )
{
u = ( ( ( (-1) << ( i + 1 ) ) &x ) >> 1 );
l = ( ( ~( (-1) << i ) ) &x );
y1 = solve(u|l, n-1, k-1);
if( x & ( 1 << i ) )
{
y1 += 1;
}
u = ( ( ( (-1) << ( n - i ) ) &x ) >> 1 );
l = ( ~( (-1) << ( n - 1 - i ) ) &x );
y2 = solve(u|l, n-1, k-1);
if( x & ( 1 << ( n - 1 - i ) ) )
{
y2 += 1;
}
y += max(y1, y2);
}
y /= n;
insert(&hash[n-1][0], x, y);
}
}
return y;
}
int main()
{
int n, k, x, i;
scanf("%d%d%s", &n, &k, str);
for( i = x = 0 ; str[i] ; i++ )
{
if( str[i] == 'W' )
{
x |= ( 1 << i );
}
}
printf("%.10Lf", solve(x, n, k));
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
