RandomColoring | Topcoder Archive

Problem Statement

Little Arthur has built a new fence around his house and now it is time to color it.

The fence consists of N planks numbered 0 to N-1 such that i-th plank is adjacent to planks i-1 and i+1 (modulo N) for all i between 0 and N-1, inclusive.

Each of the planks in the fence has to be colored using a single color. Different planks may have different colors. Each color is defined by three integer components: R, G, and B (meaning red, green, and blue, respectively), where 0 <= R < maxR, 0 <= G < maxG, and 0 <= B < maxB. Arthur can use any of the maxR*maxG*maxB possible colors.

Arthur likes random patterns. Therefore he has devised the following randomized method of coloring the fence:

In the first step he colors plank 0 using the color with components startR, startG, startB.
Next, for each i from 1 to N-1, in this order, he does the following: He looks at the (already determined) color C of the plank (i-1). The color for plank i is chosen uniformly at random among all colors that make a good transition from the color C. (Good transitions are defined below.)

A transition from color (R, G, B) to color (R', G', B') is called good if all components differ by at most d2 units (formally, |R - R'| <= d2, |G - G'| <= d2, |B - B'| <= d2) and at least one component differs by at least d1 units (formally, at least one of the conditions |R - R'| >= d1, |G - G'| >= d1, |B - B'| >= d1 holds). Intuitively, a transition between two colors is called good if they are neither too similar, nor too different.

Unfortunately, Arthur hasn't realized that after coloring all planks the transition from plank (N-1) to plank 0 does not have to be good. (Note that the fence is cyclic and thus these two planks are adjacent.) If that happens, the fence will look ugly.

Given ints N, maxR, maxG, maxB, startR, startG, startB, d1, and d2, return the probability that the fence will be ugly. (I.e., the probability that the transition from the color of plank (N-1) to the color of plank 0 is not good.)

Definition

Class:: RandomColoring
Method:: getProbability
Parameters:: int, int, int, int, int, int, int, int, int
Returns:: double
Method signature:: double getProbability(int N, int maxR, int maxG, int maxB, int startR, int startG, int startB, int d1, int d2)
(be sure your method is public)

Notes

Your return value must have an absolute or relative error less than 1e-9.
It is given that there exists at least one color that makes a good transition from the color (startR, startG, startB). Using this fact it can be proven that during the coloring process it is impossible to reach a state where there is no color that makes a good transition from the current plank's color. I.e. the coloring process cannot stop before coloring all the planks.

Constraints

N will be between 2 and 40, inclusive.
maxR, maxG, maxB, will be between 1 and 50, inclusive.
startR will be between 0 and maxR-1, inclusive.
startG will be between 0 and maxG-1, inclusive.
startB will be between 0 and maxB-1, inclusive.
d1 and d2 will be between 0 and 50, inclusive.
d1 will be less than or equal to d2.
It is guaranteed that there will exist at least one valid color that makes a good transition from color (startR, startG, startB).

Examples

```
2
```
```
5
```
```
1
```
```
1
```
```
2
```
```
0
```
```
0
```
```
0
```
```
1
```
```
Returns: 0.0
```
In this test case there are only two planks. Plank 1 will surely be colored using a color that makes a good transition from the color of plank 0. By symmetry, the transition from plank 1 color to plank 0 color has to be good as well. The fence will never be ugly.
```
3
```
```
5
```
```
1
```
```
1
```
```
2
```
```
0
```
```
0
```
```
0
```
```
1
```
```
Returns: 0.22222222222222227
```
Only the R component can change here. There are nine ways how to color the planks 0, 1, and 2: (2, 0, 0) - (1, 0, 0) - (0, 0, 0) (2, 0, 0) - (1, 0, 0) - (1, 0, 0) (2, 0, 0) - (1, 0, 0) - (2, 0, 0) (2, 0, 0) - (2, 0, 0) - (1, 0, 0) (2, 0, 0) - (2, 0, 0) - (2, 0, 0) (2, 0, 0) - (2, 0, 0) - (3, 0, 0) (2, 0, 0) - (3, 0, 0) - (2, 0, 0) (2, 0, 0) - (3, 0, 0) - (3, 0, 0) (2, 0, 0) - (3, 0, 0) - (4, 0, 0) All of these ways are equally likely. In two of them the transition from the color of plank 2 to the color of plank 0 is not good. Thus the probability of having an ugly fence is 2/9.
```
7
```
```
4
```
```
2
```
```
2
```
```
0
```
```
0
```
```
0
```
```
3
```
```
3
```
```
Returns: 1.0
```
As the number of planks is odd, Arthur will certainly have an ugly fence.
```
10
```
```
7
```
```
8
```
```
9
```
```
1
```
```
2
```
```
3
```
```
0
```
```
10
```
```
Returns: 0.0
```
For any pair of colors the transition between them is good. The fence cannot be ugly.
```
10
```
```
7
```
```
8
```
```
9
```
```
1
```
```
2
```
```
3
```
```
4
```
```
10
```
```
Returns: 0.37826245943967396
```
```
3
```
```
3
```
```
2
```
```
2
```
```
1
```
```
0
```
```
0
```
```
1
```
```
2
```
```
Returns: 0.09090909090909148
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.