HackerRank Choosing White Balls Solution

In this post, we will solve HackerRank Choosing White Balls Problem Solution.

There are n balls in a row, and each ball is either black (B) or white (w). Perform & removal operations with the goal of maximizing the number of white balls picked. For each operation & (where 1≤i≤k:

Choose an integer, x, uniformly and independently from 1 ton – i + 1 (inclusive).
Remove the x, th ball from either the left end or right end of the row, which decrements the number of available balls in the row by 1. You can choose to remove the ball from whichever end in each step maximizing the expected total number of white balls picked at the end.
Given a string describing the initial row of balls as a sequence of n w’s and B’s, find and print the expected number of white balls providing that you make all choices optimally. A correct answer has an absolute error of at most 10-6
Input Format
The first line contains two space-separated integers describing the respective values of n (the number of balls) and k (the number of operations).
The second line describes the initial sequence balls as a single string of n characters; each character is either B or w and describes a black or white ball, respectively.

Output Format

Print a single floating-point number denoting the expected number of white balls picked. Your answer is considered to be correct if it has an absolute error of at most 10 power -6.

Sample Input 0

3 1
BWW

Sample Output 0

1.0000000000

HackerRank Choosing White Balls Problem Solution

Choosing White Balls C Solution

#include <stdio.h>
#include <stdlib.h>
#define HASH_SIZE 123455
typedef struct _node{
  int x;
  long double y;
  struct _node *next;
} node;
long double solve(int x,int n,int k);
void insert(node **hash,int x,long double y);
long double search(node **hash,int x);
char str[31];
node *hash[30][HASH_SIZE];

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;
}
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;
}
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-1-i)+1))&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;
}
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;
}

Choosing White Balls C++ Solution

#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <unordered_map>
#include <bitset>
using namespace std;

unordered_map<unsigned int, double>* calculatedScores;
double getMaxExpectedScore(int n, int k, unsigned int bitRow);
unsigned int stripSingleBit(unsigned int bitRow, int bitIndex);
unsigned int getSingleBit(unsigned int bitRow, int bitIndex);
unsigned int reverseBits(unsigned int bitRow, int numBits);

unsigned int powersOf2[32];
unsigned int msbSet[32];
unsigned int lsbSet[32];
double reciprocal[32];

int main() {
    
    int n, k;
    string balls;
//    in >> n >> k >> balls;
    cin >> n >> k >> balls;
    
    calculatedScores = new unordered_map<unsigned int, double>[n];
    
    unsigned int bitRow = 0;
    for (int i = 0; i < n; i++) {
        bitRow <<= 1;
        if (balls[i] == 'B') bitRow = bitRow | 1;
    }
    
    powersOf2[0] = 1;
    msbSet[31] = 0;
    lsbSet[0] = 0;
    for (int i = 1; i < 32; i++) {
        powersOf2[i] = powersOf2[i - 1] << 1;
        lsbSet[i] = lsbSet[i - 1] | powersOf2[i - 1];
    }
    for (int i = 30; i >= 0; i--) {
        msbSet[i] = msbSet[i + 1] | powersOf2[i + 1];
    }
    reciprocal[0] = 0;
    for (int i = 1; i < 32; i++) { reciprocal[i] = 1.0 / i; }
    
//    char ch = 255;
//    unsigned char ch = 255;
//    cout << ch << " " << (ch >> 1) << endl;
//    cout << bitset<8>(ch) << " " << bitset<8>(ch >> 1) << endl;

    cout << setiosflags(ios::fixed) << setprecision(10) << getMaxExpectedScore(n, k, bitRow);
    
    return 0;
}

double getMaxExpectedScore(int n, int k, unsigned int bitRow) {
    if (k == 0) return 0;
    if (calculatedScores[n - 1].count(bitRow) == 1) return calculatedScores[n - 1][bitRow]; // Can be optimised to one look-up.
    double result = 0;
    for (int i = 0; i < (n >> 1); i++) {
        double play1 = getMaxExpectedScore(n - 1, k - 1, stripSingleBit(bitRow, i)) + getSingleBit(bitRow, i);
        double play2 = getMaxExpectedScore(n - 1, k - 1, stripSingleBit(bitRow, n - i - 1)) + getSingleBit(bitRow, n - i - 1);
        result += 2.0 * max(play1, play2);
    }
    if ((n & 1) == 1) result +=
            (getMaxExpectedScore(n - 1, k - 1, stripSingleBit(bitRow, (n >> 1))) + getSingleBit(bitRow, (n >> 1)));
    result *= reciprocal[n];
    calculatedScores[n - 1].emplace(bitRow, result);
    calculatedScores[n - 1].emplace(reverseBits(bitRow, n), result);
    return result;
}

unsigned int stripSingleBit(unsigned int bitRow, int bitIndex) {
    return ((msbSet[bitIndex] & bitRow) >> 1) | (lsbSet[bitIndex] & bitRow);
}

unsigned int getSingleBit(unsigned int bitRow, int bitIndex) {
    if ((bitRow & powersOf2[bitIndex]) == 0) return 1;
    return 0;
}

unsigned char BitReverseTable256[] = {
    0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
    0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
    0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
    0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
    0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
    0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
    0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
    0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
    0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
    0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
    0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
    0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
    0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
    0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
    0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
    0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
};
    
unsigned int reverseBits(unsigned int bitRow, int numBits) {
    unsigned int result = (BitReverseTable256[bitRow & 0xff] << 24) |
            (BitReverseTable256[(bitRow >> 8) & 0xff] << 16) |
            (BitReverseTable256[(bitRow >> 16) & 0xff] << 8) |
            (BitReverseTable256[(bitRow >> 24) & 0xff]);
    result >>= (32 - numBits);
    return result;
}

Choosing White Balls C Sharp Solution

using System;
using System.Globalization;
using System.Collections.Generic;

public class Solution
{
    static Dictionary<int, double> memoization;

    static double GiveProbability(int balls, int n, int k)
    {
        if (k == 0)
        {
            return 0;
        }

        int key = balls | (1 << n);
        if (memoization.ContainsKey(key))
        {
            return memoization[key];
        }

        double prob = 0;
        for (int i = 0; i < n / 2; i++)
        {
            int matchL = (balls & (1 << i)) != 0 ? 1 : 0;
            int matchR = (balls & (1 << (n - i - 1))) != 0 ? 1 : 0;
            double probL = GiveProbability(Sub(balls, i), n - 1, k - 1);
            double probR = GiveProbability(Sub(balls, n - i - 1), n - 1, k - 1);
            double maxProb = Math.Max(matchL + probL, probR + matchR);
            prob += 2 * maxProb / n;
        }

        if (n % 2 == 1)
        {
            int i = (n - 1) / 2;
            int matchM = (balls & (1 << i)) != 0 ? 1 : 0;
            double probM = GiveProbability(Sub(balls, i), n - 1, k - 1);
            prob += (matchM + probM) / n;
        }

        memoization[key] = prob;
        balls = ReverseBits(balls, n);
        memoization[balls | (1 << n)] = prob;

        return prob;
    }

    static int Sub(int word, int bitIndex)
    {
        if (bitIndex == 0)
        {
            word >>= 1;
            return word;
        }

        int m = word & ((1 << bitIndex) - 1);
        word -= word & ((1 << (bitIndex + 1)) - 1);
        word >>= 1;
        word |= m;
        return word;
    }

    static int ReverseBits(int n, int nBits)
    {
        int rev = 0;

        while (nBits > 0)
        {
            rev <<= 1;

            if ((n & 1) == 1)
            {
                rev ^= 1;
            }
            n >>= 1;
            nBits--;
        }
        return rev;
    }

    public static void Main(string[] args)
    {
        var input = Console.ReadLine().Split(' ');
        int n = int.Parse(input[0]);
        int k = int.Parse(input[1]);
        char[] arr = Console.ReadLine().ToCharArray();

        int balls = 0;
        for (int i = 0; i < arr.Length; i++)
        {
            if (arr[i] == 'W')
            {
                balls |= (1 << i);
            }
        }

        memoization = new Dictionary<int, double>();

        NumberFormatInfo nfi = new NumberFormatInfo();
        nfi.NumberDecimalDigits = 10;
        double result = GiveProbability(balls, arr.Length, k);
        Console.WriteLine(result.ToString("N", nfi));
    }
}

Choosing White Balls Java Solution

import java.io.*;
import java.text.NumberFormat;
import java.util.*;

public class Solution {

  static class IntDoubleHashMap {

    private static final int MAX_LOAD = 90;

    int mask;
    int len;
    int size;
    int deletedCount;
    int level;
    boolean zeroKey;

    int maxSize, minSize, maxDeleted;

    public IntDoubleHashMap(int n) {
      reset(n);
    }

    void checkSizePut() {
      if (deletedCount > size) {
        rehash(level);
      }
      if (size + deletedCount >= maxSize) {
        rehash(level + 1);
      }
    }

    void resetInt(int newLevel) {
      minSize = size * 3 / 4;
      size = 0;
      level = newLevel;
      len = 2 << level;
      mask = len - 1;
      maxSize = (int) (len * MAX_LOAD / 100L);
      deletedCount = 0;
      maxDeleted = 20 + len / 2;
    }

    int getIndex(int hash) {
      return hash & mask;
    }

    public static final double NOT_FOUND = -1;

    static final int DELETED = 1;
    int[] keys;
    double[] values;
    double zeroValue;

    protected void reset(int newLevel) {
      resetInt(newLevel);
      keys = new int[len];
      values = new double[len];
    }

    public void put(int key, double value) {
      if (key == 0) {
        zeroKey = true;
        zeroValue = value;
        return;
      }
      try {
        checkSizePut();
      } catch (Exception e) {

      }
      int index = getIndex(key);
      int plus = 1;
      int deleted = -1;
      do {
        int k = keys[index];
        if (k == 0) {
          if (values[index] != DELETED) {
            if (deleted >= 0) {
              index = deleted;
              deletedCount--;
            }
            size++;
            keys[index] = key;
            values[index] = value;
            return;
          }
          if (deleted < 0) {
            deleted = index;
          }
        } else if (k == key) {
          values[index] = value;
          return;
        }
        index = (index + plus++) & mask;
      } while (plus <= len);
    }

    void rehash(int newLevel) {
      int[] oldKeys = keys;
      double[] oldValues = values;
      reset(newLevel);
      for (int i = 0; i < oldKeys.length; i++) {
        int k = oldKeys[i];
        if (k != 0) {
          put(k, oldValues[i]);
        }
      }
    }

    public double get(int key) {
      if (key == 0) {
        return zeroKey ? zeroValue : NOT_FOUND;
      }
      int index = getIndex(key);
      int plus = 1;
      do {
        int k = keys[index];
        if (k == 0 && values[index] == 0) {
          return NOT_FOUND;
        } else if (k == key) {
          return values[index];
        }
        index = (index + plus++) & mask;
      } while (plus <= len);
      return NOT_FOUND;
    }

  }

  static int sub(int word, int bitIndex) {
    if (bitIndex == 0) {
      word >>>= 1;
      return word;
    }

    long m = word & ((1 << bitIndex) - 1);
    word -= word & ((1 << (bitIndex + 1)) - 1);
    word >>>= 1;
    word |= m;
    return word;
  }

  static IntDoubleHashMap map;

  static double giveProbability(int balls, int n, int k) {
    if (k == 0) {
      return 0;
    }
    int key = balls | (1 << n);
    double v = map.get(key);
    if (v >= 0) {
      return v;
    }
    double prob = 0;
    for (int i = 0; i < n / 2; i++) {
      int matchL = (balls & (1 << i)) != 0 ? 1 : 0;
      int matchR = (balls & (1 << (n - i - 1))) != 0 ? 1 : 0;
      double probL = giveProbability(sub(balls, i), n - 1, k - 1);
      double probR = giveProbability(sub(balls, n - i - 1), n - 1, k - 1);
      prob += 2 * Math.max(matchL + probL, probR + matchR) / n;
    }
    if (n % 2 == 1) {
      int i = (n - 1) / 2;
      int matchM = (balls & (1 << i)) != 0 ? 1 : 0;
      double probM = giveProbability(sub(balls, i), n - 1, k - 1);
      prob += (matchM + probM) / n;
    }
    map.put(key, prob);
    balls = reverseBits(balls, n);
    map.put(balls | (1 << n), prob);

    return prob;
  }

  public static int reverseBits(int n, int nBits) {
    int rev = 0;

    while (nBits > 0) {
      rev <<= 1;

      if ((n & 1) == 1) {
        rev ^= 1;
      }
      n >>= 1;
      nBits--;
    }
    return rev;
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int k = Integer.parseInt(st.nextToken());
    char[] arr = br.readLine().toCharArray();

    int balls = 0;
    for (int i = 0; i < arr.length; i++) {
      if (arr[i] == 'W') {
        balls |= (1L << i);
      }
    }

    if (n >= 29) {
      map = new IntDoubleHashMap(853);
    } else if (n > 5) {
      map = new IntDoubleHashMap(n * n);
    } else {
      map = new IntDoubleHashMap(2);
    }

    NumberFormat nf = NumberFormat.getInstance();
    nf.setMaximumFractionDigits(10);
    double result = giveProbability(balls, arr.length, k);
    bw.write(nf.format(result));

    bw.newLine();
    bw.close();
    br.close();
  }

}

Choosing White Balls Python 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 C# C++ HackerRank Solutions java javascript C cpp CSharp Hackerrank Solutions java javascript