First Post / Top Coder Open 2014 Round 2A

Hi everyone! First things first, a short introduction.

I challenged myself to become RED on topcoder and to have a high rating on codeforces, codechef and maybe more. I'm going to post solutions to problems and I want to improve my skills everyday.

TCO 2014 Round 2A


Couple weeks ago I advanced to TCO 2014 Round 2. Match A from that round took place on May 17th. Only top 50 from each of 3 matches in Round 2 advances to the next Round.

I finished 431th, solving 250 problem in 30 minutes (should've done that much faster) and earned 124 rating points, which is quite surprising. 

250 Problem


The 250 Problem Statement is pretty clear.

You have a 4x4 grid consisting of 16 1x1 spots and 16 three dimensional blocks each of size 1 x 1 x h[i], where h[i] is the height of i-th block.

You have to assign an unique spot for each block in a way which maximize a visible surface formed by the blocks - we don't take the bottom sides of the blocks into account, because the grid lays on the table. The task is to return this maximum visible surface.

Since there are only 16 blocks, I thought that something like a brute force would work and the first idea that came to my mind is the following:

  1. Sort blocks by height in non-decreasing order.
  2. Put 8 blocks with greatest heights in spots marked red in the drawing below. We can do that, because within these blocks, there is no block which covers any part of any other top 8 bricks.
  3. Since there are only 8 blocks remaining to put, we can try every permutation of these, because 8! = 40320
  4. For each such permutation, we have to compute the visible surface and check if it's greater that maximum computed so far.


The total complexity of that method is less than 10^7 so we can afford that.


My solution from the contest is so messed up that I decided to write a better structured version:

int di[] = {-1, 0, 1, 0};
int dj[] = {0, 1, 0, -1};
int order1[] = {1, 3, 4, 6, 9, 11, 12, 14}; 
int order2[] = {0, 2, 5, 7, 8, 10, 13, 15}; 

class SixteenBricks {
public:
    int sol[16];
    vector<int> h;
    int init;
    int res;
    bool visited[8];

    void solve(int cnt)
    {
        if(cnt == 8)
        {            
            int ans = init;
            FOR(i, 4)
            {
                FOR(j, 4)
                {
                    FOR(z, 4)
                    {
                        int ni = i + di[z];
                        int nj = j + dj[z];
                        if(ni >= 0 && ni < 4 && nj >= 0 && nj < 4)
                        {
                            int l = 4 * ni + nj;
                            ans -= min(sol[4 * i + j], sol[l]);
                        }
                    }
                }
            }
            REMAX(res, ans);
        } 
        else
        {
            FOR(i, 8)
            {
                if(!visited[i])
                {
                    visited[i] = 1;
                    sol[order2[cnt]] = h[i];
                    solve(cnt + 1);
                    visited[i] = 0;
                }
            }
        }
    }
    int maximumSurface(vector<int> height) {
        h = height;
        sort(ALL(h));
        FOR(i, 8)
        {
            sol[order1[i]] = h[8 + i];
        }
        FOR(i, 16)
        {
            init += 4 * h[i] + 1;
        }
        FOR(i, 8)
        {
            visited[i] = 1;
            sol[order2[0]] = h[i];
            solve(1);
            visited[i] = 0;
        }
        return res;
    }
};


During the challenge phase, I saw that there are a way clearer solutions, I'll try to think about it later.


500 Problem


I had enough time for 500 problem, but I couldn't come up with any efficient solution.