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 payoff (I think, that this step should I do faster, but I don't know how)
3. Display result.
Best regards
DM
561  Jackpot
Moderator: Board moderators

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
561  Jackpot
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)
Born from ashes  restarting counter of problems (800+ solved problems)

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm

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

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

 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.
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.

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Thanks little yoey for entlightning me
I never think about this problem in this way
Now I try to accepted it
Best regards
DM
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)
Born from ashes  restarting counter of problems (800+ solved problems)

 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
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)
Born from ashes  restarting counter of problems (800+ solved problems)

 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;
}
metaphysis: http://uhunt.onlinejudge.org/id/95895
My solutions for UVa problems: https://github.com/metaphysis/Code.
My solutions for UVa problems: https://github.com/metaphysis/Code.