Category Archives: algorithm

ZOJ 3725 Painting Storages

This problem can be found here


ZOJ Problem Set - 3725
Painting Storages
Time Limit: 2 Seconds
Memory Limit: 65536 KB

There is a straight highway with N storages alongside it labeled by 1,2,3,...,N. Bob asks you to paint all storages with two colors: red and blue. Each storage will be painted with exactly one color.

Bob has a requirement: there are at least M continuous storages (e.g. "2,3,4" are 3 continuous storages) to be painted with red. How many ways can you paint all storages under Bob's requirement?

Input

There are multiple test cases.

Each test case consists a single line with two integers: N and M (0<N, M<=100,000).

Process to the end of input.

Output

One line for each case. Output the number of ways module 1000000007.

Sample Input

4 3

Sample Output

3

It is not hard to find that this is another dynamic programming problem. An O(n^2) solution is not acceptable, it should be done better.

Notation: we use f[i] to keep the number of ways for i storages.
(1) if m continuous red storages are found before i, we definitely have f[i] = f[i-1] * 2
(2) if the (i-1)th, (i-2)th … (i-m+1)th storage is red and the (i-m)th one is blue, then we can make the ith one red, regardless of the combination of the first i-m-1 storages. f[i] += 2^(i-m-1). But in this situation, we must make sure that there are no m continuous red ones in the first (i-m-1) storages, otherwise it is duplicate as case(1). f[i] -= f[i-m-1].

So finally the function is:
f[i] = (f[i-1]*2) + 2^(i-m-1) - f[i-m-1]
Be careful about the boundary cases and we will reach the solution.

//ZOJ 3725
//LANG C++

#include <iostream>

#define MOD 1000000007
#define MAX 100001

using namespace std;

//Using long long makes life much easier
long long p[MAX];	//p[i] = (2^i)%MOD
long long f[MAX];
int main()
{
	
	p[0] = 1;
	for(int i=1; i<MAX; i++)
		p[i] = (p[i-1]*2)%MOD;
	
	
	int n, m;
	while((cin>>n>>m))
	{
		//Boundary cases
		for(int i=0; i<m; i++)
			f[i] = 0;
		f[m] = 1;
		f[m+1] = 3;

		//DP
		for(int i=m+2; i<=n; i++)
		{
			f[i] = ((f[i-1]*2) + p[i-m-1] - f[i-m-1])%MOD;
			if(f[i]<0)
				f[i]+=MOD;
		}
		cout<<f[n]<<endl;
	}
	return 0;
}

System of Difference Constraints and ZOJ 2770 Burn the Linked Camp

A system of difference constraints has n variables and m inequations. Each inequation is like:
x_i - x_j <= b_k
where i, j ∈[1, n]

Here is an example of a system of difference constraints:

x_2 - x_5 <= 1
x_1 - x_2 <= 0
x_1 - x_5 <= -1
x_3 - x_1 <= 5
x_4 - x_1 <= 4
x_4 - x_3 <= -1
x_5 - x_3 <= -3
x_5 - x_4 <= -3

The goal is to find an X = [x_1, x_2, x_3, x_4, x_5] which satisfies the above-referenced inequations.

To solve such a problem, we usually convert these inequations to a graph, as in a graph there is:

d[v] <= d[u] + w(u, v)

where d(v) is the distance between v and a certain node, and w(u, v) is the weight of the edge connecting u and v.
It can be easily transformed into

d[v] - d[u] <= w(u, v)

For a given inequation

x_i - x_j <= b_k

we can construct two nodes i and j, and an edge from j to i whose weight is b_k.

we also need to make up a source node so that d[x] represents the distance from source to x. The initial weight from source to any node is usually zero, or an arbitrary number.

After we constructed this graph, solving these ineqations becomes as easy as calculating the shortest path from source to each node. Since weight can be negative value, Bellman-Ford (BF) Algorithm or Shortest Path Faster Algorithm (SPFA) is usually used.

If any of these inequations are conflicting, for example:

x_1 - x_2 <= -1
x_2 - x_1 <= -1

Then they will become a negative cycle. Fortunately BF or SPFA algorithm can detect it, so we do know if these inequations have no solution.

Let’s see a real problem, which can be found here.


ZOJ Problem Set - 2770
Burn the Linked Camp
Time Limit: 2 Seconds
Memory Limit: 65536 KB

It is well known that, in the period of The Three Empires, Liu Bei, the emperor of the Shu Empire, was defeated by Lu Xun, a general of the Wu Empire. The defeat was due to Liu Bei's wrong decision that he divided his large troops into a number of camps, each of which had a group of armies, and located them in a line. This was the so-called "Linked Camps".

Let's go back to that time. Lu Xun had sent many scouts to obtain the information about his enemy. From his scouts, he knew that Liu Bei had divided his troops into n camps, all of which located in a line, labeled by 1..n from left to right. The ith camp had a maximum capacity of Ci soldiers. Furthermore, by observing the activities Liu Bei's troops had been doing those days, Lu Xun could estimate the least total number of soldiers that were lived in from the ith to the jth camp. Finally, Lu Xun must estimate at least how many soldiers did Liu Bei had, so that he could decide how many troops he should send to burn Liu Bei's Linked Camps.

Input:

There are multiple test cases! On the first line of each test case, there are two integers n (0<n<=1,000) and m (0<=m<=10,000). On the second line, there are n integers C1 ... Cn. Then m lines follow, each line has three integers i, j, k (0<i<=j<=n, 0<=k<2^31), meaning that the total number of soldiers from the ith camp to the jth camp is at least k.

Output:

For each test case, output one integer in a single line: the least number of all soldiers in Liu Bei's army from Lu Xun's observation. However, Lu Xun's estimations given in the input data may be very unprecise. If his estimations cannot be true, output "Bad Estimations" in a single line instead.

Sample Input:

3 2
1000 2000 1000
1 2 1100
2 3 1300
3 1
100 200 300
2 3 600

Sample Output:

1300
Bad Estimations

For the first sample, we are given:

x_1 <= 1000
x_2 <= 2000
x_3 <= 1000
x_1 + x_2 >= 1100
x_2 + x_3 >= 1300

And the solution is:

x_1 = 0
x_2 = 1100
x_3 = 200

so the output is x_1 + x_2 + x_3 = 1300

To convert this problem into a system of difference constraints problem, we need to define that:
y_i = x_1 + x+2 + ... + x_i

Then this sample becomes:

y_1 - y_0 <= 1000
y_2 - y_1 <= 2000
y_3 - y_2 <= 1000
y_2 - y_0 >= 1100 then y_0 - y_2 <= -1100
y_3 - y_1 >= 1300 then y_1 - y_3 <= -1300

and we also know these by default:

x_1 >= 0
x_2 >= 0
x_3 >= 0

so we have:

y_1 - y_0 >= 0 then y_0 - y_1 <= 0
y_2 - y_1 >= 0 then y_1 - y_2 <= 0
y_3 - y_2 >= 0 then y_2 - y_3 <= 0

Then we can easily build a graph to solve this problem.

//ZOJ 2770
//LANG: C++

#include <stdio.h>
#include <stdlib.h>

int edge_u[20000];
int edge_v[20000];
int edge_w[20000];
int dist[2000];
int null[2000];

int main(int argc, char* argv[])
{
 	int n, m;
	int t1,t2,t3;
	int eid;
	while(fscanf(stdin, "%d %d", &n, &m)!=EOF)
	{
		eid = 0;
		for(int i=1; i<n+2; i++)
		{
			edge_u[eid] = 0;
			edge_v[eid] = i;
			edge_w[eid] = 0;
			eid++;
		}
		for(int i=2; i<n+2; i++)
		{
			edge_u[eid] = i;
			edge_v[eid] = i-1;
			edge_w[eid] = 0;
			eid++;
		}
		for(int i=0; i<n; i++)
		{
			fscanf(stdin, "%d", &t1);
			edge_u[eid] = i+1;
			edge_v[eid] = i+2;
			edge_w[eid] = t1;
			eid++;
		}

		for(int i=0; i<m; i++)
		{
			fscanf(stdin, "%d %d %d", &t1, &t2, &t3);
			edge_u[eid] = t2+1;
			edge_v[eid] = t1;
			edge_w[eid] = -t3;
			eid++;
		}

		//BF
		//init
		for(int i=0; i<n+2; i++)
		{
			null[i] = 1;
		}
		null[0]	= 0;
		dist[0] = 0;

		//relax
		for(int i=0; i<n+1; i++)
		{
			for(int j=0; j<eid; j++)
			{
				int u = edge_u[j];
				int v = edge_v[j];
				int w = edge_w[j];
				if((null[v] == 1 && null[u] == 0))
				{
					null[v] = 0;
					dist[v] = dist[u]+w;
				}
				else if(null[v]==0 && null[u] == 0)
				{
					if(dist[v]>dist[u]+w)
					{
						dist[v] = dist[u]+w;
					}
				}

			}
		}

		//check negative
		int flag = 0;
		for(int i=0; i<eid; i++)
		{
			int u = edge_u[i];
			int v = edge_v[i];
			int w = edge_w[i];
			if((null[v] == 1 && null[u] == 0))
			{
				flag = 1;
				break;
			}
			else if(null[v]==0 && null[u] == 0)
			{
				if(dist[v]>dist[u]+w)
				{
					flag = 1;
					break;
				}
			}
		}

		if(flag == 1)
			fprintf(stdout, "Bad Estimations\n");
		else
		{
			fprintf(stdout, "%d\n", dist[n+1]-dist[1]);
		}
	}
}