561 - Jackpot

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

561 - Jackpot

Post by Dominik Michniewski » Sun Apr 18, 2004 12:12 pm

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
Last edited by Dominik Michniewski on Mon Apr 19, 2004 1:38 pm, edited 1 time in total.
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Apr 18, 2004 1:16 pm

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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Sun Apr 18, 2004 2:17 pm

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

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Sun Apr 18, 2004 2:20 pm

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Apr 18, 2004 2:32 pm

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Sun Apr 18, 2004 10:09 pm

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

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Apr 19, 2004 1:38 pm

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

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 561 - Jackpot

Post by metaphysis » Fri May 12, 2017 4:19 pm

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;
}

Post Reply

Return to “Volume 5 (500-599)”