PROBLEM LINK:Author: Ishani Parekh DIFFICULTY:Easy PREREQUISITES:adhoc, basic math PROBLEM:We are given a line of length N, where M lattice points (points with integer coordinates) have predefined 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 predefined 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 predefined color x, then its final color will be x, no matter which traversal is chosen. If a point does not have a predefined color, and the first point of the left of it with predefined color has color x, and the first point on the right with predefine 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 predefined 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 uncolored points, while all other entries represent points with predefined color. After the final traversal, some of the points will have the fixed color: the points with predefined color, and the points for which one of the x or y is not defined (i.e., the uncolored points towards the line end). Hence, any traversal will have the following configuration: Now consider any interval of consecutive x's, e.g., 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: 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: 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: 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: 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.
This question is marked "community wiki".
asked 13 Oct '14, 15:00
showing 5 of 7
show all

Also worth mentioning is the use of the property (axb)%val=((a%val)x(b%val))%val!! As this would not let the integer overflow happen. answered 13 Oct '14, 17:43
Can you help me with error in this code http://www.codechef.com/viewsolution/5155169 Thanks.
(16 Oct '14, 03:44)

Why is my solution giving TLE even if i have solved in O(n)... Please help me .Here's the code: http://www.codechef.com/viewsolution/5095572 answered 13 Oct '14, 19:06
Even you need a faster input output method. This question has many inputs. cin and cout are slow. Use scanf/printf or else if u want to continue using cin and cout add this line std::ios::sync_with_stdio(false); under the int main line
(15 Oct '14, 02:19)

the same algorithm steps are done in Java and got TLE. anyone know a way to speed up the input read ? answered 14 Oct '14, 01:25
Yes you have to use fast read. see http://discuss.codechef.com/questions/7394/helponfastinputoutput Also see here (my solution including some code NOT FROM ME for fast intput): http://www.codechef.com/viewsolution/4972765
(14 Oct '14, 02:10)

What is wrong with my solution? I have used the same approach in JAVA. Here is link to my solution. Please see to it and HELP..!! Thanks in advance. answered 14 Oct '14, 04:05

I did exactly the same as mentioned.But still getting the WA . anyone could tell me why.? here is the link to my solution http://www.codechef.com/viewsolution/5152710 answered 15 Oct '14, 18:18

what is the answer to above example.?i.e the total number of combinations after modulo.? answered 15 Oct '14, 18:23

anyone could please point out the mistake in my code ? I am getting wrong answer again n again. link to my solution > http://www.codechef.com/viewsolution/5261675 answered 02 Nov '14, 20:54

prob with code , gives WA . please point out : answered 05 Jan '17, 12:15

I think that the problem was not tested properly. Solutions of similar complexity in Java are getting different verdicts. One is AC and other is TLE. For example, here is AC solution and a similar solution but TLE. answered 13 Oct '14, 18:27

Answer is hidden because of too many downvotes. Click here to view.
answered 13 Oct '14, 16:01
1
Please refrain from posting your code here. Either link to your submission or explain how you approached the problem. If you do need to post a code snippet, format it properly.
(13 Oct '14, 23:41)

It's a good question on combinatorics ^_^
I did the same thing as mentioned here . Still I was getting TLE . It would be great if someone points out the mistake in the given code.
http://www.codechef.com/viewsolution/5123371
why wrong answer??? http://www.codechef.com/viewsolution/5064542
For java , time limit was too strict. I submitted the same code in C and it was accepted. Why so?
I took the same approach and got TLE. http://www.codechef.com/viewsolution/5143632
@ bhanuagrawal
I just checked your code and find the following things wrong with your code . 1. first of all read the problem statement carefully. you need to output the answer mod 10^9+9 because number of arrangements may be very large. you have not used mod any where in your code.
Second thing your array size is exactly 10^5 and you are using 1 based indexing. In c and c++ 0 based indexing is used. so your array actual index is from 0 to 99999 and you are trying to access 1 to 10^5.
anyone could please point out the mistake in my code ? I am getting wrong answer again n again. link to my solution > http://www.codechef.com/viewsolution/5261675