remy paints the fence OCT 14

Our chef Remy ate all the delicious food he made. As a result, he has become really fat :). Chef’s assistant Linguini has taken up the herculean task of bringing back chef Remy to shape.

Linguini has built a fence which has N planks in a straight line. The planks are numbered 1 to N from left to right. In front of M of these N planks, he has put a bucket of paint. The paints may be of different colors. Each color is represented by any uppercase letter (A-Z). Chef Remy needs to paint the fence. He uses his painting brush to paint the fence.

Chef Remy starts the task by choosing a plank which has a bucket of paint in front of it and dips his brush in the bucket. He starts walking randomly along the straight fence passing the planks. He never moves out of the fence. Note that walking randomly along a fence means that Remy keeps walking all the time along his current direction. He can change his direction any time he wishes. Moving along a straight fence has just two directions, forward and backward.

Linguini has devised the following recipe for painting the fence.

Each bucket has an infinite supply of paint.
The brush can carry paint of a single color at any time.
When Remy passes a paint bucket, the brush acquires the color in the bucket first.
Every plank that Remy passes in his random walk must be colored with the color in the brush. A plank will be colored completely.
A plank can be colored multiple times. A plank's color is the latest color it is painted with.

A fence coloring is complete when each plank is painted with some color. Linguini is watching Remy dance around with colors. He wonders how many different complete fence colorings will he be able to see. Two fence colorings are different if there is atleast one plank numbered x whose color differs in both the colorings. Find out the number of different complete fence colorings modulo 1000000009.

can someone explain me the last four lines in simple way,that what i have to do and what is asking here to find.thanks in advace


If you paid more attention reading the question rather than getting ready to ask question on forum you woulf have got the answer yourself . Quoting from the question :“Chef Remy starts the task by choosing a plank which has a bucket of paint in front of it and dips his brush in the bucket”


how the input is done ?? in increasing order of the plank number or randomly?

Can anyone please help me find fault with my code?

the question is simple:
given some k colours in front of some N planks (colors may be same), Find total no. of different fence colorings (following the rules specified)

PS: Input is not sorted.
I think u have not considered the above fact in ur code…

where should i post the solution?

what will be the starting it extreme left or right

You Are assuming while taking input of plank with color that plank are given in increasing order but it is not the case as it is not given in problem

if you mean where to submit it, you can submit it in the practice section of the main page. the problems are already there.