561 - Jackpot

[Dominik Michniewski]

I try to solve this problem, but I got TLE many times. Could anyone help me and give any hint, how can I speed up my program ?

I use following algorithm:
1. Count different patterns for all three wheels
2. for every state on every wheel (O(N^3)) compute pay-off (I think, that this step should I do faster, but I don't know how)
3. Display result.

Best regards
DM

[little joey]

Try a probabilistic approach... counting all combinations is too slow, as you've experienced.

[Dominik Michniewski]

Could you explain me it deeper ? I cannot imagine myself this method ...

Best regards
DM

[junjieliang]

Instead of running through everything in O(n^3) time, consider using some maths to do the calculations.

[little joey]

It's a bit of a spoiler, but consider this example:

Left wheel: 20 symbols, 7 of which are 'A';
Middle wheel: 10 symbols, 3 of whitch are 'A';
Right wheel: 5 symbols, 2 of which are 'A'.

Now the chance of getting three 'A's on the middle row is (7/20)*(3/10)*(2/5) = 42/1000. The payoff from this winning combination is 10 coins, so the relative payoff is 10*42/1000 = 0.42.

Similarly we can calculate the chances and relative payoffs of all the other winning combinations (a maximum of 26*5=130) and calculate the total relative payoff.

To gain speed and avoid rounding errors you might like to reorder the calculations, but this is the basic idea.

[Dominik Michniewski]

Thanks little yoey for entlightning me
I never think about this problem in this way
Now I try to accepted it

Best regards
DM

[Dominik Michniewski]

Little yoey - if you want, remove your hint from board - I got Accepted on this problem ...

Best regards
DM

[metaphysis]

Test data generator.

Code: Select all

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, char *argv[])
{
    srand(time(NULL));
    
    int cases = 100;
    cout << cases << '\n';
    
    for (int c = 1; c <= cases; c++)
    {
        int x = rand() % 198 + 3;
        int y = rand() % 198 + 3;
        int z = rand() % 198 + 3;
        
        cout << x << ' ' << y << ' ' << z << '\n';
        
        for (int i = 1; i <= x; i++)
        {
            int k = rand() % 26;
            cout << (char)('A' + k);
        }
        cout << '\n';
        for (int i = 1; i <= y; i++)
        {
            int k = rand() % 26;
            cout << (char)('A' + k);
        }
        cout << '\n';
        for (int i = 1; i <= z; i++)
        {
            int k = rand() % 26;
            cout << (char)('A' + k);
        }
        cout << '\n';        
    }
    
    return 0;
}