PROBLEM LINK:
Author: Ishani Parekh
Tester: Jingbo Shang
Editorialist: Ajay K. Verma
DIFFICULTY:
Easy
PREREQUISITES:
ad-hoc, basic math
PROBLEM:
We are given a line of length N, where M lattice points (points with integer co-ordinates) have pre-defined color. Chef makes a walk along the line starting from any point and finishing at any point such that all points on the line are visited at least once. He can switch his traversal direction at any of the lattice points. After the traversal a point p in the line has the same color as that of the point with pre-defined color which was visited just before the last visit to p. The task is to find the number of coloring arrangements that can be achieved by different traversals.
EXPLANATION:
If a point has a pre-defined color x, then its final color will be x, no matter which traversal is chosen. If a point does not have a pre-defined color, and the first point of the left of it with pre-defined color has color x, and the first point on the right with pre-define color has color y (note that in some cases x or y may not exist, if there is no point to the left/right of this point with pre-defined color), then the final color of this point will be either x or y.
Let us see an example: In the following string zero represents un-colored points, while all other entries represent points with pre-defined color.
00010000020003000100
After the final traversal, some of the points will have the fixed color: the points with pre-defined color, and the points for which one of the x or y is not defined (i.e., the un-colored points towards the line end). Hence, any traversal will have the following configuration:
1111xxxxx2xxx3xxx111
Now consider any interval of consecutive x’s, e.g.,
1xxxxx2
Each of the x’s will be either 1 or 2. Moreover, all the 1’s will be on the left of 2’s because the traversal is continuous. Hence, the following configurations are possible for this interval:
1111112
1111122
1111222
1112222
1122222
1222222
Similarly, we can find the possible configuration of other intervals of x’s. The important observation is that all possible configurations of two intervals are compatible with each other, i.e., for a given configuration c1 of first interval, c2 of second interval, and c3 of the third interval, we can always find a traversal which leaves the three intervals in the chosen configurations.
For example, we if want to achieve the following final configuration:
111 1 11122 2 233 3 333 1 11
Then we start with the 4th point (with color 1), go to left and color all points with 1, come back to 4th point, then move right all the way to 10th point (with color 2).
At this point the partial configuration will look like:
111 1 11111 2…
Since we want the two rightmost points of the interval to be of color 2, after visiting the 10th point, we go back to left and color these two points 2, then come back to 10th point, and go all the way right to the 14th point (with color 3). The configuration at this point will look like:
111 1 11122 2 222 3…
In the second interval, we want the two rightmost points to be of color 3, hence after visiting the 14th point, we go back left and color these two point 3, come back to 14th point and continue to right all the way up to 18th point (with color 1), and so on.
This means, we can achieve any possible configuration of the intervals independently of one another. Hence, in order to find the number of color arrangements of the line, we need to find the number of configurations of each interval and multiply them together. If for an interval both x and y are the same, then this interval has exactly one configuration, otherwise the interval will have (1 + n) configurations, where n is the length of the interval.
Time Complexity:
O (N)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution will be put up soon.
Tester’s solution will be put up soon.
