In this post and the up coming future posts i will show how to use the techniques discussed in my earlier posts problem solving techniques (
part 1 and
part 2) to solve problems.
Complete search (brute force) examples
Problem 1 (Building a House)
Code jam (Qualification Round Africa and Arabia 2011
)
You have just bought land and want to plant the largest rectangular
field possible. In surveying your land, you find a number of obstacles
and decide to draw a map. You indicate in each square of the map whether
it contains grass (
G), rock (
R), water (
W), shrubs (
S), or trees (
T). While the grass can be mowed and the shrubs dug from the ground, the water, rocks, and trees
cannot be removed. Given these obstacles, determine the area of the largest rectangular field.
Input
The first line of input gives the number of cases,
N.
N test cases follow. For each test case there will be:
- One line containing two space-separated integers indicating the length (L) and width (W) of your land.
- Followed by, W lines, each containing L characters where each indicates the conditions for that square of land (one of
G, R, W, S, or T).
Output
For each test case, output one line containing "Case #
x: "
followed by the maximum area of the largest rectangle that can be cleared.
Limits:
1 ≤
L ≤ 50
1 ≤
W ≤ 50
N ≤ 30
Fewer than 20 obstacles in each test case.
Discussion
From the constraints above we can check that a brute-force solution could survive. With the mathematical fact that we can represent a rectangle with only two points, we can iterate all possible combination's of two points and check if the rectangle represented with those two points include an obstacle or not. O(L^2*W^2*C) where c is the number of obstacles in the grid.
Code
vector<point>
obstacles;
int res = -1;
for (i = 0; i < l; i++)
for (j = 0; j < w; j++)
if(grid[i][j] != 'G' || grid[i][j] != 'S') obstacles.push_back(point(i, j));
for(i = 0; i < l; i++)
for(j = 0; j < w; j++)
for(a = i; a < l; a++)
for(b = j; b < w; b++)
{
for(c = 0; c < obstacles.size(); c++)
if(obstacles[c].x >= i && obstacles[c].x <= a && obstacles[c].y >= j && obstacles[c].y <= b) break;
if(c >= obstacles.size()) res = max(res, (a-i+1)*(b-j+1));
}
cout << res << endl;
Problem 2 (SRMCodingPhase)
Topcoder (SRM 520 Div 2 level 2, Div 1 level 1)
Mr. Dengklek introduced you to an online programming contest called SRM (Special Round Match)!
You are now in the coding phase of the contest. There are 3 problems in
the contest. You have practiced a lot before in practice rooms, so you
are sure that you can solve the first problem in
skills[0] minutes, the second problem in
skills[1] minutes and the third problem is
skills[2] minutes.
You have exactly 75 minutes to solve the problems. Before submitting a
solution to a problem, you must first open the problem. If you submit a
solution to a problem t minutes after you open the problem, you will
receive:
- (points[0] - 2t) points for the first problem, or
- (points[1] - 4t) points for the second problem, or
- (points[2] - 8t) points for the third problem.
In your strategy, you only submit a solution to a problem after you
solve the problem. If you don't submit a solution to a problem, you will
receive zero points for the problem.
It is well-known that luck plays an important role in a contest. A fortune-teller told you that you have
luck
points of luck. You may use these points to decrease the amount of time
you need to solve the problems, in minutes. Of course, you don't have
to use all the points. Each point is worth one minute per problem. So,
if you initially can solve a problem in t minutes, by using x points of
luck (where x is a positive integer and 0 < x < t), you can solve
the problem in (t - x) minutes (it is impossible to use t or more points
of luck on the problem).
Arrange your strategy in this coding phase. Return the maximum total score you can achieve in this coding phase.
Constraints
|
| - | points will contain exactly 3 elements. |
| - | points[0] will be between 250 and 300, inclusive. |
| - | points[1] will be between 450 and 600, inclusive. |
| - | points[2] will be between 900 and 1100, inclusive. |
| - | skills will contain exactly 3 elements. |
| - | Each element of skills will be between 1 and 100, inclusive. |
| - | luck will be between 0 and 100, inclusive. |
Discussion
From the problem constraints we can loop through all possible combination's of solved problems and compute the maximum points gained each time, caution about the tricky luck part, we can use greedy to pass it.
Code
int countScore(vector <int> points, vector <int> skills, int luck) {
int res = 0;
for(int i = 0; i < 2; i++) // 1 solve, 0 not solve
for(int j = 0; j < 2; j++) // 1 solve, 0 not solve
for(int s = 0; s < 2; s++) // 1 solve, 0 not solve
{
vector<int> lucky(3, 0);
int minutes = 0, tmp = 0;
if(s == 1) { // Solving problem 3
lucky[2] = min(skills[2]-1, luck); // Compute the lucky for prob 3
minutes += skills[2]; // Add the time for solving prob 3
tmp += points[2]-8*(skills[2]-lucky[2]); // Add the points gained from solving prob 3
}
if(j == 1) { // solving problem 2
lucky[1] = min(skills[1]-1, luck-lucky[2]); // Compute the lucky of solving prob 2
minutes += skills[1]; // Add the time for solving prob 2
tmp += points[1]-4*(skills[1]-lucky[1]); // Add the points gained from solving prob 2
}
if(i == 1) {
lucky[0] = min(skills[0]-1, luck-lucky[2]-lucky[1]); // Compute the lucky for prob 1
minutes += skills[0]; // Add the time for solving prob 1
tmp += points[0]-2*(skills[0]-lucky[0]); // Add the points gained from solving prob 1
}
if(minutes-luck <= 75) { // Check that we can solve the probs within time
res = max(res, tmp); // Check the max num of points
}
}
return res;
}
The next
post show how to solve specific types of problems using Divide and Conquer technique.
