# The expected times to get all colours, no one knows how to hack this?

• There are k different colors balls in a box, and each colour can have different number of balls like a1, a2, ... ak;

now you are required to pick up a ball at a time and record its colour and then put it back and again pick up a ball from the box and record its colour and then put it back...

the question here is what's the `expected times` you need to pick up balls from the box that all different k colours are recorded.

For example:
k = 2
arr = [5, 10],
return 3.500000

• ``````#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <map>
#include <unordered_set>
#include <algorithm>
#include <queue>
using namespace std;

int cnt[10];
double prob[10];
bool visit[10];
double ans_color;
int g_level;

double dfs(int level, double sum_prob) {
if (level == g_level-1) {
for (int i = 0; i < g_level; i++) {
if (!visit[i])
return 1 / prob[i];
}
}
double result = 0;
for (int i = 0; i < g_level; i++) {
if (!visit[i]) {
visit[i] = true;
result += prob[i] / (1 - sum_prob) * (1 / (1 - sum_prob) + dfs(level + 1, sum_prob + prob[i]));
visit[i] = false;
}
}
return result;
}

double solver_color() {
cin >> g_level;
memset(cnt, 0, 10);
memset(visit, false, 10);
double sum = 0;
ans_color = 0;
for (int i = 0; i < 10; i++) {
cin >> cnt[i];
sum += cnt[i];
}
for (int i = 0; i < 10; i++) prob[i] = cnt[i] / sum;
return dfs(0, 0);
}

int main_color() {
int test_large = 0;
if (test_large) {
freopen("D-large.in", "r", stdin);
freopen("D-large-practice.out", "w", stdout);
}
else {
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
}

int T = 0;
cin >> T;
for (int i = 0; i < T; i++) {
cout << "Case #" << i + 1 << ":" << endl;
cout << solver_color() << endl;
}
return 1;
}``````

• Is this a Google codejam question? Also, this looks similar to the coupon collector problem.

• @babhishek21 Perhaps similar but not the same.

• @LHearen Actually, it is the coupon collector problem with unequal probabilities.

• @babhishek21 I am really happy that my tought process was similar some weeks ago.

• Dynamic Programming with binary representation set can be used to solve this problem directly.

• @gmcather DP with bitmasking? Hmm. Can you perhaps provide some code? I would be really interested in this approach.

• @babhishek21 maybe you have to encode in a bitmask the colours you have selected. It is bitmask of K bits

• @LHearen It is a FREAKING HARD problem.

It is called COUPON COLLECT PROBLEM WITH DIFFERENT PROBABILITIES.