×

# FATCHEF-Editorial

Author: Ishani Parekh
Tester: Jingbo Shang
Editorialist: Ajay K. Verma

Easy

# 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.

O (N)

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution will be put up soon.
Tester's solution will be put up soon.

This question is marked "community wiki".

6★djdolls
2.2k518484
accept rate: 0%

19.7k350498541

It's a good question on combinatorics ^_^

(13 Oct '14, 15:56)

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

(13 Oct '14, 16:11) 3★
(13 Oct '14, 16:21)

For java , time limit was too strict. I submitted the same code in C and it was accepted. Why so?

(13 Oct '14, 16:40)

I took the same approach and got TLE. http://www.codechef.com/viewsolution/5143632

(13 Oct '14, 18:05)
1

@ 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.

(15 Oct '14, 11:58)

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

(02 Nov '14, 20:55)
showing 5 of 7 show all

 5 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 237●2●7●17 accept rate: 7% Can you help me with error in this code http://www.codechef.com/viewsolution/5155169 Thanks. (16 Oct '14, 03:44)
 1 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 answered 13 Oct '14, 18:49 3★goltu 26●2●4 accept rate: 0% This question needs faster input/output methods. 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:17)
 1 For those using C++, this might help for TLE - my answer answered 14 Oct '14, 02:43 186●1●3●11 accept rate: 0%
 0 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 1●1 accept rate: 0% 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)
 0 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 3★vidudaya 1●2 accept rate: 0% Yes you have to use fast read. see http://discuss.codechef.com/questions/7394/help-on-fast-inputoutput 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) beroul5★
 0 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. http://www.codechef.com/viewsolution/5131646 answered 14 Oct '14, 04:05 24●1 accept rate: 0%
 0 All those getting a TLE, please use fast I/O. Use this implementation of fast I/O or any other that you would like. answered 14 Oct '14, 07:47 4★roman28 1.6k●7●14●29 accept rate: 19%

## Edit:- beroul has pointed out my mistake. There is no flaw in the answer.

I think this answer has a flaw.
If you consider 1000200030004 as input(as used in the editorial).
If some point between first and fifth is coloured 2, it means it can only be start or end.
Space between bucket is used in following lines, for 1 and 2 it refers to the zeros at positions 2nd,3rd,4th
It means that there can only be 2 gaps between buckets, which are coloured with colours on either side buckets.
But, this answer assumes that 1111223333444 is possible, which is having 3 spaces between buckets.

4★varun1
290124
accept rate: 0%

2

start at the most left point ("bucket 1"), go to the most right point (bucket "4") go from bucket "4" to bucket bucket "3" then 1 step to the right then back to bucket 3 then go to bucket "2" then 1 step to the right then go to bucket "1" then 3 step to the right

(15 Oct '14, 02:07) 5★

Thanks for the explanation! :)

(15 Oct '14, 13:31) 4★
 0 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 2★nirvit 1 accept rate: 0%
 0 what is the answer to above example.?i.e the total number of combinations after modulo.? answered 15 Oct '14, 18:23 2★nirvit 1 accept rate: 0%
 0 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 1●1●2 accept rate: 0%
 0 prob with code , gives WA . please point out : https://code.hackerearth.com/12ad60I answered 05 Jan '17, 12:15 1 accept rate: 0%
 0 I didn't use Fast I/O being a java user.Instead I did an optimization i.e start from the minimum position(which is painted) and go till Max Position(which is painted). Hope that helps. Here is my code for reference. answered 16 Oct '17, 20:33 0●1 accept rate: 0%
 -1 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 223●6 accept rate: 0%
 -7 Answer is hidden because of too many downvotes. Click here to view. answered 13 Oct '14, 16:01 24●1 accept rate: 0% 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)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,490
×3,706
×867
×319

question asked: 13 Oct '14, 15:00

question was seen: 4,259 times

last updated: 16 Oct '17, 20:33