10811 - Up the Ante

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

Moderator: Board moderators

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

10811 - Up the Ante

Post by Destination Goa » Fri Feb 18, 2005 1:17 am

Gordon,

My DP solution can't solve sample input (WA), but if I do not limit it to positive profit, summary probability is 1.0. So at least state graph traversal is correct. I think I just make wrong transitions.

The problem statement claims:
The patterns are designed so that each symbol appears once, twice, and three times in an equal number of wheel positions.
But on the picture I see 2 positions with 3 crowns and 6 positions with 1 crown. Though it seems to work for other symbols. Anyway, how is this related to the quote above?

Also, if the picture is correct, but the problem statement is wrong, there are 2 issues:
1) Will Stan choose the best symbol (i.e. the best winning strategy) since they seem to be unequal if the picture is correct.
2) A better picture because some characters are hardly distinguishable with this one.
To be the best you must become the best!

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Re: 10811 - Up the Ante

Post by gvcormac » Fri Feb 18, 2005 2:34 am

Destination Goa wrote:Gordon,

My DP solution can't solve sample input (WA), but if I do not limit it to positive profit, summary probability is 1.0. So at least state graph traversal is correct. I think I just make wrong transitions.

The problem statement claims:
The patterns are designed so that each symbol appears once, twice, and three times in an equal number of wheel positions.
But on the picture I see 2 positions with 3 crowns and 6 positions with 1 crown. Though it seems to work for other symbols. Anyway, how is this related to the quote above?

Also, if the picture is correct, but the problem statement is wrong, there are 2 issues:
1) Will Stan choose the best symbol (i.e. the best winning strategy) since they seem to be unequal if the picture is correct.
2) A better picture because some characters are hardly distinguishable with this one.
The wheel is symmetric, so there are only 14 distinct patterns, each of which appears
twice:

6 - three-of-a-kind
6 - two-of-a-kind + one-of-a-kind
2 - three-different-symbols

So there is one pattern with 3 crowns (i.e. 2 wheel positions)

And one pattern with 2 crowns and something else (i.e. 2 wheel positions)

And one pattern with 1 crown and 2 equal other symbols (2 wheel positions)

And one pattern with 1 crown and 2 distinct other symbols (2 wheel positions)

I think maybe you've misread the 2 positions with 2 crowns. They appear just
before 9:00 and 3:00 on the picture.

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Fri Feb 18, 2005 3:17 am

Thank you for prompt reply. But alas it does not clarify my question.
And one pattern with 1 crown and 2 distinct other symbols (2 wheel positions)
There are two such patterns: 1st and 3rd if we start at 12:00 clockwise.

Also, I was asking about 1-crown patterns. There are 6 wheel positions, not 4. After all, how is the quote "... same number of times" from the problem description related with your recent reply?

To keep things simple, please clarify:
1) How many wheel positions are there with 1 crown and 2 non-crown symbols (not necessarily distinct)?
2) How many wheel positions are there with 2 crowns and 1 non-crown symbol?
3) How many wheel positions are there with 3 crowns?
4) Will the answers 1,2,3 be the same for some other symbol, not a crown?
5) If the answer to 4 is "No", how does Sten choose a symbol for his bet?

Currently I am 99% sure that the answer for question 3 is 2, but all others still keep me frustrating. Hearts, for example, have another distribution. Anchors - yet another.

Thanks in advance.
To be the best you must become the best!

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Fri Feb 18, 2005 3:51 am

OK, now I see your point. The illustration is indeed hard to read, and appears to be an unfair board. It was my intent that the game be completely fair so that it doesn't matter what symbol Stan plays.

It is surprisingly difficult to find a decent photo of Crown & Anchor considering how common it is at fairs and exhibitions in North America. I am now intriuged to know if all C&A games
have this bias, or this is just a rogue board.

Anyway, the problem means you to assume that every symbol appears 14 times in total:

6 times as a three-of-a-kind (i.e. 2 positions)
4 times as a two-of-a-kind (i.e. 2 positions)
4 times as a one-of-a-kind (twice with another pair, twice as member of 3 distinct symbols)
Last edited by gvcormac on Fri Feb 18, 2005 4:47 am, edited 2 times in total.

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Fri Feb 18, 2005 4:06 am

Here's a crown & anchor wheel that appears to be fair:

http://www.njsdesign.on.ca/images/produ ... wheel1.gif

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Fri Feb 18, 2005 4:29 am

Ok, thank you!

Just one more thing:
4 times as a three-of-a-kind
I guess you mean "4 times as a two-of-a-kind", right? And by this you mean that there are 4 cells belonging to 2-of-a-kind-of-that-symbol positions, right? I.e. 2 wheel positions, each of which contains exactly 2 symbols of this kind.
To be the best you must become the best!

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Fri Feb 18, 2005 4:46 am

Destination Goa wrote:Ok, thank you!

Just one more thing:
4 times as a three-of-a-kind
I guess you mean "4 times as a two-of-a-kind", right? And by this you mean that there are 4 cells belonging to 2-of-a-kind-of-that-symbol positions, right? I.e. 2 wheel positions, each of which contains exactly 2 symbols of this kind.
Right. I'll edit the post just to confuse people who read this.

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Fri Feb 18, 2005 5:30 am

(your last sentence will confuse them the most, just read it carefully :lol:)

Now I can't get the right sample output... 0.3180 all the time. I will try to do it without optimizations and see if I get same value.

Just a question (perhaps you made this mistake, perhaps not). It is possible to use 3D DP (round, num_seq_losses, profit) or 2D (round, profit) and try loss sequence length in transition loop. In the latter case it is possible to forget checking if the profit goes non-positive inside that num_seq_losses loop. P.S: I use 3D DP.

(If I try to limit profit to -5 instead of +1, I get the right answer on that case).
To be the best you must become the best!

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Fri Feb 18, 2005 5:48 am

Same thing... Here is unoptimized code for small cases. But it returns 0.3180 instead of 0.5835. What's wrong? BTW, this is the first time I ask for help with own code on hands :)

Code: Select all

// @JUDGE_ID: 4153NK 10811 C++ ""
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <time.h>
#include <limits.h>

const double _1_28 = 1.0 / 28;

int v[32];

#define BASE	(128)

double f[8][16][256]; // [rounds][loss_sequence % nv][BASE+profit]

int main()
{
//	freopen("input.txt", "rt", stdin);

	int N;
	scanf("%d", &N);

	for(;N;N--)
	{
		int kk, mm, ll;
		scanf("%d %d %d", &kk, &mm, &ll);

		int i, j, k;

		v[0] = 1;

		int nv = 1;

		for(i=1;i<mm;i++)
		{
			v[nv] = v[i-1] * 2;

			if(v[nv] > ll)
				break;

			nv++;
		}

		int a = 4;
		int b = 2;
		int c = 2;

		memset(f, 0, sizeof(f));

		f[0][0][BASE] = 1;

		for(i=0;i<mm;i++)
		{
			for(j=0;j<nv;j++)
			{
				for(k = i<kk ? -BASE : 1 ; k<BASE ; k++)
				{
					double cf = f[i][j][BASE+k];

					if(cf==0)
						continue; // also prevents from index out of bound

					cf *= _1_28;

					f[i+1][(j+1)%nv][BASE+k-v[j]] += cf * (28-a-b-c);

					f[i+1][0][BASE+k+v[j]]   += cf * a;
					f[i+1][0][BASE+k+v[j]*2] += cf * b;
					f[i+1][0][BASE+k+v[j]*3] += cf * c;
				}
			}
		}

		double tf = 0;

		for(j=0;j<nv;j++)
		{
			for(k=1;k<BASE;k++)
				tf += f[mm][j][BASE+k];
		}

		printf("%.4lf\n", tf);
	}

	return 0;
}
To be the best you must become the best!

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Feb 18, 2005 6:25 am

In the latter case it is possible to forget checking if the profit goes non-positive inside that num_seq_losses loop.
It seems you have the same wrong interpretation of the problem statement that I had first. "Stan wins the bet if, following this strategy, his net winnings are positive at any time after playing k and before playing the m+1st round."
This doesn't mean the winnings have to be positive at every time step. We only care if it becomes positive once inside that time interval.

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Fri Feb 18, 2005 10:19 am

Adrian,

No, it's correct. If so, I would get the answer of 0.0 because even the very first step would be made from net profit >=1, but at the start we have only net profit of 0 available.

Ok, here is the math formula behind that code. I will use "i, j, k" for indices and "mm, kk, ll" for input values to stay synched with code variables.

a, b, c - number of wheel positions ( out of 28 ) where each symbol appears once, twice and three times respectively (this was discussed above). a=4, b=2, c=2.

v(i) - power of bet amount, i=0..nv-1
v(i) = 2^i.
2^(nv-1) <= ll, nv -> max

f(i, j, k) - probability of the state
i - number of rounds played (0 - played nothing, 1 - after 1st round)
j - bet index at this step (0..nv-1), actually Sten will bet for 2^j.
k - his overall profit. That is, what would be his ballance delta since the game begining if he leaves Ex at this point.

Now transitions:
For i<kk (i.e. for rounds when we don't care what is our profit), all states are propagated to 4 possible further states:

To f(i+1, (j+1)%nv, k-v[j]) with probability of f(i, j, k) * (28-a-b-c) / 28 // loss
To f(i+1, 0, k+v[j]) with probability of f(i, j, k) * a / 28 // win bet
To f(i+1, 0, k+v[j]*2) with probability of f(i, j, k) * b / 28. // win bet x 2
To f(i+1, 0, k+v[j]*3) with probability of f(i, j, k) * c / 28. // win bet x 3

So, as you may see, nothing is lost during processing i=0..kk-1. Sum(j=0..nv-1, k=-100..100) == 1.0 for any 0 <= i < kk.

Once i >= kk, we can propagate only states with positive net profit, i.e. states with k >= 1. You may see this in code as:

for(k = i<kk ? -BASE : 1 ; k<BASE ; k++)

Take a look at the initialization expression. If current 'i' (number of rounds was played) is less then 'kk', then we start at -INF, otherwise we start at 1. For sample input BASE is large enough to work as INF for us.

Also, in the end we amass only values >= 1.

The only difference in code from this statement is that array 'f' is shifted BASE elements on its 3rd argument to keep that index positive.
To be the best you must become the best!

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Fri Feb 18, 2005 10:37 am

Adrian,

I think I've got what you mean. That way I finally got sample output working. Just considered propagation of states -INF <= k < 1 for i >= kk and all terminal states (k>=1, i>=kk) went to the output, that is:

answer = sum(f(i, j, k); i=kk..mm, j=0..nv-1, k=1..INF)
To be the best you must become the best!

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Fri Feb 18, 2005 10:50 am

Finally AC. Thank you guys! 0.482 sec (2-row array, and zeroing only what indeed needs zeroing).

Gordon,

I think that this phrase:
Stan wins the bet if, following this strategy, his net winnings are positive at any time after playing k and before playing the m+1st round.
should be changed to this
Stan wins the bet if, following this strategy, his net winnings become positive at any time after playing k and before playing the m+1st round.
Or replace it with "turn positive". Also, better replace "any" with "some" (the latter will directly point to singular form instead of plural form which is correct). When I try to read the original phrase backtracking my mind, I see that the word "any" does the most damage to desired understanding.

AFAIK, English is your native language (as opposed to my case), but the latter seems to be much closer to what Adrian told to help me out.

Thanks again!
To be the best you must become the best!

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Fri Feb 18, 2005 2:15 pm

Destination Goa wrote:Finally AC. Thank you guys! 0.482 sec (2-row array, and zeroing only what indeed needs zeroing).

Gordon,

I think that this phrase:
Stan wins the bet if, following this strategy, his net winnings are positive at any time after playing k and before playing the m+1st round.
should be changed to this
Stan wins the bet if, following this strategy, his net winnings become positive at any time after playing k and before playing the m+1st round.
Or replace it with "turn positive". Also, better replace "any" with "some" (the latter will directly point to singular form instead of plural form which is correct). When I try to read the original phrase backtracking my mind, I see that the word "any" does the most damage to desired understanding.

AFAIK, English is your native language (as opposed to my case), but the latter seems to be much closer to what Adrian told to help me out.

Thanks again!
I don't really have any editorial control once uva takes the problem. As far as the Waterloo
site is concerned, the problem statement is part of the historical record, so I don't
want to tinker with it.

While Waterloo participants are the principal audience, I do try to be sensitive to
internationalization. It is sometimes a challenge for me to guess what wordings
will be difficult to interpret. I never try to be obscure, but obviously I'm not
always successful, especially in communicating to non-English speakers.

That said, I don't think "turn positive" would be an improvement. That would imply that if
Stan's winnings were positive after k-1 rounds and continued to be positive after k
rounds, Stan would not win because his winnings did not "turn positive after k rounds."

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Fri Feb 18, 2005 6:52 pm

Ok, that was just an offer. You are right about turn/become - it would actually make k-- . "any" -> "some" is a better conversion (to my taste), but as long as the problem is frozen, so be it.
To be the best you must become the best!

Post Reply

Return to “Volume 108 (10800-10899)”