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


  • 1

    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


  • 0
    F
    #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;
    }

  • 0

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


  • 0

    @babhishek21 Perhaps similar but not the same.


  • 0

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


  • 0

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


  • 0
    G

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


  • 0

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


  • 0

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


  • 0
    U

    @LHearen It is a FREAKING HARD problem.

    It is called COUPON COLLECT PROBLEM WITH DIFFERENT PROBABILITIES.

    Check this article if you want:

    http://www.mat.uab.cat/matmat/PDFv2014/v2014n02.pdf


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.