FATCHEF-Editorial

PROBLEM LINK:

Practice
Contest

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.

3 Likes

What is wrong in this solution? Help…!!

static int mod = (int)(1E9 + 9);

static void solve()
{
for(int T=nextInt();T>=1;T–)
{
int n=nextInt(), m=nextInt();
int x,y;
int color[] = new int[n];
for(int i=0;i<m;i++)
{
String s[] = nextLine().split(" ");
x = (int)(s[0].toCharArray()[0]);
y = Integer.parseInt(s[1]);
color[y-1]= x;
}
int flag=0,prevI=0,total=1;
for(int i=0;i<n;i++)
{
if(color[i]!=0)
{
flag++;
if(flag==1)
{
prevI=i;
}
else
{
if(color[i]==color[prevI])
{
prevI=i;
total = total%mod;
}
else
{
total = ((total%mod)*((i-prevI)%mod))%mod;
prevI=i;
}
}
}
}
out.println(total);
}

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.

5 Likes

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.

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

1 Like

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

the same algorithm steps are done in Java and got TLE. anyone know a way to speed up the input read ?

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

1 Like

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

All those getting a TLE, please use fast I/O. Use this implementation of fast I/O or any other that you would like.

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.

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

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

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

prob with code , gives WA . please point out :

https://code.hackerearth.com/12ad60I

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


[1] for reference.


  [1]: https://www.codechef.com/viewsolution/15878434

It’s a good question on combinatorics :slight_smile:

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?