## 561 - Jackpot

Moderator: Board moderators

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

### 561 - Jackpot

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)

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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:
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
Instead of running through everything in O(n^3) time, consider using some maths to do the calculations.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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:
Thanks little yoey for entlightning me
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:
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

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