You are not logged in. Please login at to post your questions!





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




ad-hoc, basic math


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.


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.

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:

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:
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 solution will be put up soon.
Tester's solution will be put up soon.

This question is marked "community wiki".

asked 13 Oct '14, 15:00

djdolls's gravatar image

accept rate: 0%

edited 10 Nov '14, 01:41

admin's gravatar image

0★admin ♦♦

It's a good question on combinatorics ^_^

(13 Oct '14, 15:56) abcdexter242★

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.

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

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) rohanagarwal5★

I took the same approach and got TLE.

(13 Oct '14, 18:05) code_overlord3★

@ 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) ma5termind3★

anyone could please point out the mistake in my code ? I am getting wrong answer again n again. link to my solution ->

(02 Nov '14, 20:55) praveen184★
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

sidgupta234's gravatar image

accept rate: 7%

Can you help me with error in this code Thanks.

(16 Oct '14, 03:44) coding_kumar102★

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.


answered 13 Oct '14, 18:49

goltu's gravatar image

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) pranjalranjan4★

For those using C++, this might help for TLE - my answer


answered 14 Oct '14, 02:43

chefkaushik94's gravatar image

accept rate: 0%

Why is my solution giving TLE even if i have solved in O(n)... Please help me .Here's the code:


answered 13 Oct '14, 19:06

rkm_coder's gravatar image

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) pranjalranjan4★

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

vidudaya's gravatar image

accept rate: 0%

Yes you have to use fast read. see Also see here (my solution including some code NOT FROM ME for fast intput):

(14 Oct '14, 02:10) beroul5★

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

piyush4793's gravatar image

accept rate: 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

roman28's gravatar image

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.

I tried to ask about this via comment but there was no reply from admin.


answered 15 Oct '14, 01:18

varun1's gravatar image

accept rate: 0%

edited 15 Oct '14, 13:32


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) beroul5★

Thanks for the explanation! :)

(15 Oct '14, 13:31) varun14★

I did exactly the same as mentioned.But still getting the WA . anyone could tell me why.? here is the link to my solution


answered 15 Oct '14, 18:18

nirvit's gravatar image

accept rate: 0%

what is the answer to above example.?i.e the total number of combinations after modulo.?


answered 15 Oct '14, 18:23

nirvit's gravatar image

accept rate: 0%

anyone could please point out the mistake in my code ? I am getting wrong answer again n again. link to my solution ->


answered 02 Nov '14, 20:54

praveen18's gravatar image

accept rate: 0%

prob with code , gives WA . please point out :


answered 05 Jan '17, 12:15

dreamin_fool's gravatar image

accept rate: 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

bhagirathi08's gravatar image

accept rate: 0%


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

code_overlord's gravatar image

accept rate: 0%

edited 13 Oct '14, 19:10

Answer is hidden because of too many downvotes. Click here to view.

answered 13 Oct '14, 16:01

piyush4793's gravatar image

accept rate: 0%


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) nisargshah953★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 13 Oct '14, 15:00

question was seen: 4,259 times

last updated: 16 Oct '17, 20:33