Codeforces Round 102 Problem C

Virtually participated in Codeforces Round #102 last week, during which I could only solve problems A and B within the coding period. I did upsolve problems C to E, though, and will be posting the solutions to each soon as I am able to narrate the ideas to their solution and the implementation in sufficient detail.

Problem Statement

The problem statement can be found here. We are asked to place maximum amount of 'T' shaped objects with fixed size on an M x N board. An object may be placed in 4 different ways. (i.e. consider rotating the 'T' shaped object 0, 90, 180, or 270 degrees) M and N are given as input. We are asked to output not only the maximum amount of objects that can be placed on the board, but a sample placement of that many objects on the board.

The board size being less than 10 on each dimension clearly hints that the possibility of a brute-force solution (i.e. trying all possible placements in each possible direction) should be explored.

Solution

Let's briefly consider a completely brute-force approach. Suppose we use depth-first search(DFS) to traverse all possible cases and try to place in each cell the intersection of vertical and horizontal lines of 'T', in all 4 directions.

Complexity of Plain Brute-Force

A simple analysis of the recurrence relation this brute-force approach can reveal such complexity.

As we recursively go deeper with DFS, for each cell we investigate, we will explore the possibility of placing a 'T' shaped object to some particular set of cells. On the worst case, we can place the object in 4 different directions. Thus, we need to make 4 recursive calls to DFS. We may also choose to not place an object to that location as well, which accounts for another recursive call. Consequently, we end up with the recurrence relation below.

Let a be the remaining number of cells to investigate
f(1) = O(1)
f(a) = 4 * f(a-1) + f(a-1) + O(1)
     = 5 * f(a-1) + O(1)
     = 25 * f(a-2) + O(1)
     = ...
f(a) = (5k) * f(a-k) + O(1)

f(a) = 5a

Evidently the execution time of a brute force approach is exponential, indicated by the closed form of the recurrence relation given above. Thus we should either modify our approach to become more clever or figure out a completely new way to solve this problem. If the bound for input was larger, we would probably have to go with the latter option. But without any modification this solution seems to work okay for n,m ≤ 6. The bounds, I think, hint the possibility of getting a passing solution after some modification on the simplest brute-force solution.

A Heuristic

Depth-first search in a plain brute force solution checks all possible placements of all possible number of placements. We want to modify that traversal so that it ignores cases where it is impossible to get a maximal amount of placement of objects.

We can either limit the breadth, or the depth to achieve such a modification. Yet, knowing that we need to check for each of 4 possible placements of an object at a certain position, we know we need to make at least 4 calls, and it is obvious that we have one more case of not placing anything at that spot. Evidently we can not limit the breadth of the traversal, which means that we need to find a way to not go as deep.

The heuristic is derived from the observation that each 'T' shaped object takes up 5 cells. Thus, if we got K more cells to investigate and we place 'T'-pieces strictly beyond the point we are currently investigating, then we can not place more than (K / 5) objects as we go deeper within our depth-first search. Consequently, at our current position if we have placed E elements as a result of our previous inspections within this branch of the DFS and the maximum number of placements found so far is M, then we should go deeper with our traversal if only it can possibly yield a greater M. In other words, if M > (K / 5) + E, then there is no way we can find a new maximal amount of placements greater than M, simply because there is not enough cells in which one can place sufficient amount of tools.

Implementation Details

As highlighted in the previous paragraph, it is an important implementation detail to make sure that all points to be inspected are definitely clean, and not a single cell among them contains any piece of any of the previously placed objects. The correctness of your calculation of the condition(i.e.whether the remaining cells can contain a sufficient amount of 'T' pieces) presented above depends on it.

int a, b;  
a = ((i - 1) * m + j - 5 * numPlacements);  
b = (m * (n - i) + (m - j));  
if(b + (a>5 ? 5 : a) <= 5*(maxPlacements - numPlacements))  
    return;

Just for the sake of clarifying things let's go over my implementation of the condition. The condition check, which is shown above, is placed in the first 4 lines of dfs() function. My particular implementation of "placing" objects puts them to board in such a way that one part of the 'T' piece to be placed lies exactly on the point I am currently investigating, and the other four lie strictly in the already-inspected zone. "reaping" objects from board works similarly.

As you can see, variable b stores the remaining number of cells to investigate, while a stores the number of inspected cells that are still empty. There are a couple of things that I would like to note regarding the implementation of this check.

First is regarding the integer division. If, instead of multiplying the difference in number of placements like seen above, the value on the left is divided by 5, due to the integer division losing the remainder, we would end up with a wrong(i.e. not maximal) answer in several cases, caused by DFS not going as deep as we need it to.

Second thing to note here is the variable a. The particular method I used to place 'T' shaped objects requires placing them to already-explored cells as well as the one currently being investigated. So, value stored in a, the amount of empty cells among the ones we already investigated (and are currently investigating) is essential while checking the number of placements we can make on top of the current state of the board. For instance, if a < 5, we may deduce that it is not possible to place an element to the current spot we are investigating, as an object takes up 5 cells.

Last thing to notice in the implementation of the condition check is the ternary operator within the if statement. It clamps the value of a back to 5 if it exceeds it. The reason we need to limit a is the fact that, at each recursive level of DFS, we can place a single 'T' shaped object on the already inspected cells, regardless of how many empty ones we have among the already inspected cells. Ternary operator expression prevents DFS from going to deeper levels of recursion that would not actually yield a better value for maximum amount of placements. You may indeed notice the change in execution time by removing the ternary operator. I believe it would give a TLE(i.e. time limit exceeded) if you submitted it to Codeforces judge without the ternary operator.

Upper Bound for Complexity

It is important to note that this heuristic does not change the complexity of the solution. As the input size gets bigger, DFS will need to go deeper to find the correct result, and the execution time will exceed any time constraints imposed by practical requirements or by Codeforces judge. I believe the time limit set by Codeforces judge is exceeded if the upper bound N (i.e. the size of any dimension of the board) exceeds 14.

Obviously the problemsetters wanted this problem to be solvable with this brute-force approach, given the upper bound for N is 9.

Code

Here is my passing submission to the problem. Those who are interested in others' solutions may visit submissions to Round 102 on Codeforces

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

int n, m;  
char matrix[20][20];  
char maxMatrix[20][20];  
int numPlacements, maxPlacements;

bool canBePlaced(int i, int j, int dir)  
{
    if(dir == 1)
    {
        if(j - 1 <= 0 || i - 2  <= 0 || j + 1 > m)
        {
            return false;
        }
        return ((matrix[i][j] == '.') &&
                (matrix[i-1][j] == '.') &&
                (matrix[i-2][j] == '.') &&
                (matrix[i-2][j+1] == '.') &&
                (matrix[i-2][j-1] == '.'));
    }
    else if(dir == 2)
    {
        if(i - 2  <= 0 || j - 2 <= 0)
        {
            return false;
        }
        return ((matrix[i][j] == '.') &&
                (matrix[i-1][j] == '.') &&
                (matrix[i-2][j] == '.') &&
                (matrix[i-1][j-1] == '.') &&
                (matrix[i-1][j-2] == '.'));
    }
    else if(dir == 3)
    {
        if(j - 2 <= 0 || i - 2  <= 0)
        {
            return false;
        }
        return ((matrix[i][j] == '.') &&
                (matrix[i][j-1] == '.') &&
                (matrix[i][j-2] == '.') &&
                (matrix[i-1][j-1] == '.') &&
                (matrix[i-2][j-1] == '.'));
    }
    else if(dir == 4)
    {
        if(i - 2 <= 0 || j + 2 > m)
        {
            return false;
        }
        return ((matrix[i][j] == '.') &&
                (matrix[i-1][j] == '.') &&
                (matrix[i-2][j] == '.') &&
                (matrix[i-1][j+1] == '.') &&
                (matrix[i-1][j+2] == '.'));
    }

    return false;
}

void operateWithTool(int i, int j, int dir, char operation)  
{
    matrix[i][j] = operation;

    if(dir == 1)
    {
        matrix[i-1][j] = matrix[i][j];
        matrix[i-2][j] = matrix[i][j];
        matrix[i-2][j+1] = matrix[i][j];
        matrix[i-2][j-1] = matrix[i][j];
    }
    else if(dir == 2)
    {
        matrix[i-1][j] = matrix[i][j];
        matrix[i-2][j] = matrix[i][j];
        matrix[i-1][j-1] = matrix[i][j];
        matrix[i-1][j-2] = matrix[i][j];
    }
    else if(dir == 3)
    {
        matrix[i][j-1] = matrix[i][j];
        matrix[i][j-2] = matrix[i][j];
        matrix[i-1][j-1] = matrix[i][j];
        matrix[i-2][j-1] = matrix[i][j];
    }
    else if(dir == 4)
    {
        matrix[i-1][j] = matrix[i][j];
        matrix[i-2][j] = matrix[i][j];
        matrix[i-1][j+1] = matrix[i][j];
        matrix[i-1][j+2] =matrix[i][j];
    }
}

void place(int i, int j, int dir)  
{
    ++numPlacements;

    operateWithTool(i, j, dir, ('A' - 1) + numPlacements);

    if(numPlacements > maxPlacements)
    {
        for(int i=1; i <= n; ++i)
            for(int j=1; j <= m; ++j)
            {
                maxMatrix[i][j] = matrix[i][j];
            }
        maxPlacements = numPlacements;
    }
}

void reap(int i, int j, int dir)  
{
    operateWithTool(i, j, dir, '.');
    --numPlacements;
}

void dfs(int i, int j)  
{
    int a, b;
    a = ((i - 1) * m + j - 5 * numPlacements);    // empty slots left behind
    b = (m * (n - i) + (m - j));
    if( b + (a > 5 ? 5 : a) <= 5 * (maxPlacements - numPlacements))
        return;

    for(int k=1; k <= 4; ++k)
    {
        if(canBePlaced(i, j, k))
        {
            place(i, j, k);

            if(j < m)
            {
                dfs(i, j+1);
            }
            else if(i < n)
                dfs(i+1, 1);

            reap(i, j, k);
        }
    }

    if(j < m)
    {
        dfs(i, j+1);
    }
    else if(i < n)
        dfs(i+1, 1);
}

int main()  
{

    cin >> n >> m;
    for(int i=1; i <= n; ++i)
        for(int j=1; j <= m; ++j)
            matrix[i][j] = maxMatrix[i][j] = '.';

    numPlacements = maxPlacements = 0;

    dfs(1, 1);

    cout << maxPlacements << endl;
    for(int i=1; i <= n; ++i)
    {
        for(int j=1; j <= m; ++j)
        {
            cout <<  maxMatrix[i][j];
        }
        cout << endl;
    }

    return 0;
}