Topcoder SRM 595 DIV2 500

Problem Statement

We are given cells. Initially all cells are completely white. We are provided with two colors white and black. We are also given two arrays L[ ] and R[ ]. At each iteration i, paint all the cells from L[i-1] to R[i-1] with either black or white. We have to find total number of configurations possible. Two configurations are different if at least on cell in white in one configuration and black in another.

You can find a detailed problem description here.

Solution

Both arrays L and R are traversed sequentially. At each iteration, cells between L[i-1] and R[i-1] are repainted. The color of any cell depends on the final color chosen to repaint that.

Eg: M=4 , {1,2,1}, {3,5,5}

There are three intervals in this example. 1 – 3 , 2 – 5, 1 – 5.

Initially all balls are white,

0 0 0 0 0

Take the interval and paint with White or Black. This is represented by 1. Now, the configuration is.

1 1 1 0 0

Now take the next interval ( 2 – 5 ) and repaint that.

1 2 2 2 2. 

The color of the second and third cell depends on (2 – 5) not on ( 1-3). Hence, color of a cell depends on the latest interval

Now take the final interval ( 1 – 5 ) and repaint again.

3 3 3 3 3

So, the color of all cells depends on the 3 interval. All balls can be either white or black. So, the answer is two.


Now take another example , 4, {1, 1, 2}, {5,3,5}

Initially all balls are white,

0 0 0 0 0

Take the first interval (1 – 5) and paint with White or Black. This is represented by 1. Now, the configuration is.

1 1 1 1 1

Now take the next interval ( 1- 3 ) and repaint that.This is represented by 2.

2 2 2 1 1.

Now take the final interval ( 2 – 5 ) and repaint it. This is represented by 3.

2 3 3 3 3.

Tot. No. of Configurations = ( Colors possible for cells affected by 2md interval )  * (  Colors possible for cells affected by 3rd interval )

Tot. No. of Configurations = 2 * 2 = 4

Naive Solution

class LittleElephantAndIntervalsDiv1 {
public:
	long long getNumber(int M, vector <int> L, vector <int> R) {

	int sz = L.size(),i,j;
	long long result = 1LL;
	vector<bool> check(50,false);
	vector<int> m(1001,0);

	for(i=0;i<sz;i++)
	{
		for(j=L[i]-1;j<R[i];j++)
			m[j] = (i+1);
	}

	for(i=0;i<M;i++)
	{
		if( m[i] > 0 && !check[m[i]] )
		{
			check[m[i]] = true;
			result = result << 1LL;
		}
	}

	return result;
	}
};

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s