Prev: ANN: Seed7 Release 2010-04-04
Next: repeating elements in an array
From: Richard Heathfield on 5 Apr 2010 07:00
news.telesweet.net wrote:
> On 4/5/2010 5:49 AM, Richard Heathfield wrote:
>> CVS wrote:
>>> In a game of cricket,
>>>
>>> 1. Assume you can score exactly as you want on each ball.
>>>
>>> 2. Single/Double/Triple/Four/Six are the options available to you on
>>> each ball.(no extras)
>>>
>>> 3. RISK is defined as the square of the score on each ball.
>>>
>>> * * * *
>>> Write a program that accepts:-
>>> a. Target runs to score (N)
>>> b. No. of balls to score it in (x)
>>>
>>> and prints the runs to score on each ball.
>>>
>>> Remember U have to ACHIEVE the target with MINIMUM RISK possible.
>>
>> Hypothesis: for scoring N, the minimum risk is achieved when you hit N
>> singles.
>>
>> To score N + 1, we can do one of these things:
>>
>> * reduce N to N-5, then add a six. The effect on the risk is that R[N+1]
>> is (R[N] - 5) + 36 = R[N] + 31, which is greater than R[N];
>> * reduce N to N-3, then add a four. This gives a risk greater than R[N]
>> by 4*4-3 = 13;
>> * reduce N to N-2, then add a three. This gives a risk greater than R[N]
>> by 3*3-2 = 7;
>> * reduce N to N-1, then add a two. This gives a risk greater than R[N]
>> by 2*2-1 = 3;
>> * simply add a single. This increases the risk by 1, the minimum.
>>
>> Now the base cases. To score 0, the least risky score is 0. To score 1,
>> the least risky score is a single. To score 2, the least risky score is
>> two singles. To score 3, the least risky score is three singles. To
>> score 4, the least risky score is four singles. To score 5, the least
>> risky score is five singles. And just to be sure, to score 6 the least
>> risky score is six singles.
>>
>> Induction has shown us that singles are always the safest way. Since the
>> overriding requirement is minimum risk, x is irrelevant and can be
>> ignored.
>
> You have implicitly assumed that x >= N in this argument. If x < N then
> it is simply impossible to score N on x balls by only scoring singles.

If x < N, you haven't minimised the risk, which is a requirement - in
fact, it's the only requirement, and it's spelled out in CAPITAL
LETTERS, so it's obviously vital. Therefore, x must be >= N.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within
From: news.telesweet.net on 5 Apr 2010 07:14
On 4/5/2010 7:00 AM, Richard Heathfield wrote:
> news.telesweet.net wrote:
>> On 4/5/2010 5:49 AM, Richard Heathfield wrote:
>>> CVS wrote:
>>>> In a game of cricket,
>>>>
>>>> 1. Assume you can score exactly as you want on each ball.
>>>>
>>>> 2. Single/Double/Triple/Four/Six are the options available to you on
>>>> each ball.(no extras)
>>>>
>>>> 3. RISK is defined as the square of the score on each ball.
>>>>
>>>> * * * *
>>>> Write a program that accepts:-
>>>> a. Target runs to score (N)
>>>> b. No. of balls to score it in (x)
>>>>
>>>> and prints the runs to score on each ball.
>>>>
>>>> Remember U have to ACHIEVE the target with MINIMUM RISK possible.
>>>
>>> Hypothesis: for scoring N, the minimum risk is achieved when you hit N
>>> singles.
>>>
>>> To score N + 1, we can do one of these things:
>>>
>>> * reduce N to N-5, then add a six. The effect on the risk is that R[N+1]
>>> is (R[N] - 5) + 36 = R[N] + 31, which is greater than R[N];
>>> * reduce N to N-3, then add a four. This gives a risk greater than R[N]
>>> by 4*4-3 = 13;
>>> * reduce N to N-2, then add a three. This gives a risk greater than R[N]
>>> by 3*3-2 = 7;
>>> * reduce N to N-1, then add a two. This gives a risk greater than R[N]
>>> by 2*2-1 = 3;
>>> * simply add a single. This increases the risk by 1, the minimum.
>>>
>>> Now the base cases. To score 0, the least risky score is 0. To score 1,
>>> the least risky score is a single. To score 2, the least risky score is
>>> two singles. To score 3, the least risky score is three singles. To
>>> score 4, the least risky score is four singles. To score 5, the least
>>> risky score is five singles. And just to be sure, to score 6 the least
>>> risky score is six singles.
>>>
>>> Induction has shown us that singles are always the safest way. Since the
>>> overriding requirement is minimum risk, x is irrelevant and can be
>>> ignored.
>>
>> You have implicitly assumed that x >= N in this argument. If x < N
>> then it is simply impossible to score N on x balls by only scoring
>> singles.
>
> If x < N, you haven't minimised the risk, which is a requirement - in
> fact, it's the only requirement, and it's spelled out in CAPITAL
> LETTERS, so it's obviously vital. Therefore, x must be >= N.
>

You have no control over x. From my reading of the problem statement
you must minimize the risk given x and N. For example, if N is 4 and x
is 2 then the risk is minimized by getting 2 doubles.

--
Dan G

From: Moi on 5 Apr 2010 07:27
On Mon, 05 Apr 2010 07:14:40 -0400, news.telesweet.net wrote:

> On 4/5/2010 7:00 AM, Richard Heathfield wrote:
>> news.telesweet.net wrote:
>>> On 4/5/2010 5:49 AM, Richard Heathfield wrote:
>>>> CVS wrote:

>> If x < N, you haven't minimised the risk, which is a requirement - in
>> fact, it's the only requirement, and it's spelled out in CAPITAL
>> LETTERS, so it's obviously vital. Therefore, x must be >= N.
>>
>>
> You have no control over x. From my reading of the problem statement
> you must minimize the risk given x and N. For example, if N is 4 and x
> is 2 then the risk is minimized by getting 2 doubles.

As I read it, you *must* realise the score. I cannot tel if this
should be an _exact_ match, or that you must realize _at least_ this
amount of points. If there are more than one methods to realise the
score, the one with the lowest risk should be chosen.

Looks like dynamic programming to me.

AvK
From: Willem on 5 Apr 2010 07:48
)> For the current run, take N/x, round down to the nearest possible score,
)> and score that. ?Then, you know what score you have to get with x-1 balls.

James Harris wrote:
) That seems almost right but what if the penultimate N/x results in 5?

ITYM the ultimate N/x. (That is, if you're left with 5 runs and 1 ball).
In that case, you're right, that is a special case to be considered.
If you round up and not down, this cannot happen unless you have an
impossible score to begin with. Also, you avoid the possibility of
getting a remaining score ratio above 6.

SO:

For the current run, take N/x, round *up* to the nearest possible score,
and score that. Then, you know what score you have to get with x-1 balls.

If, at x=1, N is not a possible score, the start score was impossible
to begin with.


ObPuzzle: Now do it in O(1) time. That is, use a fixed/bounded number
of mathematical operators on N and x to get the result.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
From: Willem on 5 Apr 2010 08:09
Moi wrote:
) On Mon, 05 Apr 2010 07:14:40 -0400, news.telesweet.net wrote:
)
)> On 4/5/2010 7:00 AM, Richard Heathfield wrote:
)>> news.telesweet.net wrote:
)>>> On 4/5/2010 5:49 AM, Richard Heathfield wrote:
)>>>> CVS wrote:
)
)>> If x < N, you haven't minimised the risk, which is a requirement - in
)>> fact, it's the only requirement, and it's spelled out in CAPITAL
)>> LETTERS, so it's obviously vital. Therefore, x must be >= N.
)>>
)>>
)> You have no control over x. From my reading of the problem statement
)> you must minimize the risk given x and N. For example, if N is 4 and x
)> is 2 then the risk is minimized by getting 2 doubles.
)
) As I read it, you *must* realise the score. I cannot tel if this
) should be an _exact_ match, or that you must realize _at least_ this
) amount of points. If there are more than one methods to realise the
) score, the one with the lowest risk should be chosen.
)
) Looks like dynamic programming to me.

Except that it isn't.

Because the risk/score ratio increases monotonically with the score, it
is obvious that you want all the scores to be as close as possible to
the average score.

This is easily achieved by always taking the lowest score that is above
the desired average, and then updating the average for the remaining runs.

I posted this solution crossthread already.
Formal proof is left as an exercise for the reader ;-)


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: ANN: Seed7 Release 2010-04-04
Next: repeating elements in an array