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
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 ![:)](./images/smilies/icon_smile.gif)
I never think about this problem in this way![:)](./images/smilies/icon_smile.gif)
Now I try to accepted it![:)](./images/smilies/icon_smile.gif)
Best regards
DM
![:)](./images/smilies/icon_smile.gif)
I never think about this problem in this way
![:)](./images/smilies/icon_smile.gif)
Now I try to accepted it
![:)](./images/smilies/icon_smile.gif)
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.