RandomColoring
SRM 540 · 2011-11-22 · by nV
Problem Statement
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
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).
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
Submissions are judged against all 109 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RandomColoring with a public method double getProbability(int N, int maxR, int maxG, int maxB, int startR, int startG, int startB, int d1, int d2) · 109 test cases · 2 s / 256 MB per case