Problem solving techniques (Cont.) Example problems

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.