MUFFINS - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

HARD

EXPLANATION

The problem is simply to find a large independent set in a large graph. The standard backtracking method will probably time out on this instance. It might be possible to optimize this approach to get it accepted, but the time spent getting this to work may eat up much of the 2.5 hours of the contest.

Recall that if I is an independent set of a graph G(V,E), then V-I is a vertex cover: a collection of nodes such that at least one endpoint of each edge is in the collection. So, the problem was essentially to determine if there is a vertex cover of size k <= 15 (recall n-g <= 15 in the problem description).

There is actually a simple algorithm for deciding if there is a vertex cover of size k that runs in time O(m*2^k) where m is the number of edges. For a fixed constant k, this is linear time! Note that the standard algorithm “enumerate over subsets of V of size k” takes at least Omega(n^k) time (when n is the number of nodes) which is certainly not linear time for k > 1. Consider the following recursive routine that tries to cover the edges with j nodes (initially called with j = k).

bool cover(G,j)

if G has no edges then return true
else if j == 0 then return false
else let e = (u,v) be an edge
return cover(G-{u},j-1) OR cover(G-{v},j-1)

where G-{x} means remove vertex x and all of its incident edges from G. The depth of the recursion is k+1 and each call makes at most two recursive calls. It can be implemented so that only O(m) work is done each time the function is called (disregarding the work done in recursive calls). Thus, the total work is O(2^k*m). Of course, it really won’t take this long in practice if implemented properly as O(m) was a coarse upper bound on the amount of work done at each step.

Now let’s argue correctness. If there is no such vertex cover then clearly the algorithm fails to find one. Otherwise, consider a vertex cover C of size <= k. When the algorithm is trying to cover an uncovered edge, consider the recursive call that correctly guessed the node x in C that covered e (if both endpoints of e are in C, then any will do). Then C-{x} is clearly a feasible vertex cover of G-{v} of size <= k-1. Unroll this argument to the base case of C being empty. Then G has no edges in this case so the recursive algorithm will find a vertex cover.

2

#include <stdio.h>
#include <stdlib.h>
#define DEBUG 1
#ifdef ONLINE_JUDGE
#define DEBUG 0
#endif

struct pt {
int i, j;
};

int grid[15];

char line[111];

int fig_counts[7] = {2,4,4,1,2,4,2};
int fig_heights[7][4] = {
{1,4},
{2,3,3,2},
{2,3,2,3},
{2},
{2,3},
{2,3,2,3},
{2,3},
};
int figs[7][4][4] = {
{ // I
{(1<<0)|(1<<1)|(1<<2)|(1<<3)},
{(1<<0),(1<<0),(1<<0),(1<<0)},
},
{ // J
{(1<<0)|(1<<1)|(1<<2),(1<<0)},
{(1<<0)|(1<<1),(1<<1),(1<<1)},
{(1<<0),(1<<0),(1<<0)|(1<<1)},
{(1<<2),(1<<0)|(1<<1)|(1<<2)},
},
{ // L
{(1<<0)|(1<<1)|(1<<2),(1<<2)},
{(1<<0)|(1<<1),(1<<0),(1<<0)},
{(1<<0),(1<<0)|(1<<1)|(1<<2)},
{(1<<1),(1<<1),(1<<0)|(1<<1)},
},
{ // O
{(1<<0)|(1<<1),(1<<0)|(1<<1)},
},
{ // S
{(1<<0)|(1<<1),(1<<1)|(1<<2)},
{(1<<1),(1<<0)|(1<<1),(1<<0)},
},
{ // T
{(1<<0)|(1<<1)|(1<<2),(1<<1)},
{(1<<0),(1<<0)|(1<<1),(1<<0)},
{(1<<1),(1<<0)|(1<<1)|(1<<2)},
{(1<<1),(1<<0)|(1<<1),(1<<1)},
},
{ // Z
{(1<<1)|(1<<2),(1<<0)|(1<<1)},
{(1<<0),(1<<0)|(1<<1),(1<<1)},
},
};

void print() {
for (int i = 14; i >= 0; i–) {
for (int j = 0; j < 15; j++) {
printf(“%c “, grid[i] & (1<<j) ? ‘#’ : ‘.’);
}
printf(”\n”);
}
}

/////////////////////////////////////////////////////////
/*

*/
int type;
int move;
bool cvis[15][15];
int cdi[4] = {0, 1, 0, -1};
int cdj[4] = {1, 0, -1, 0};
int visit(int i, int j) {
int size = 1;
cvis[i][j] = true;
for (int d = 0; d < 4; d++) {
int ni = i + cdi[d];
int nj = j + cdj[d];
if (0 <= ni && ni < 15 && 0 <= nj && nj < 15) {
if (!cvis[ni][nj]) {
size += visit(ni, nj);
}
}
}
return size;
}
double compute_score(int rot, int i, int j, int clears) {
int holes = 0;
for (int I = 0; I < 15; I++) {
for (int J = 0; J < 15; J++) {
cvis[I][J] = (grid[I] & (1<<J)) != 0;
}
}
for (int J = 0; J < 15; J++) {
if (!cvis[14][J]) {
visit(14, J);
}
}
for (int I = 0; I < 15; I++) {
for (int J = 0; J < 15; J++) {
if (!cvis[I][J]) {
holes += visit(I, J);
}
}
}
int height = 0;
int bump = 0;
int prev = 0;
for (int J = 0; J < 15; J++) {
int I = 14;
while (I >= 0 && !(grid[I] & (1<<J))) I–;
height += ++I;
if (J) {
bump += abs(prev - I);
prev = I;
}
}
#define aa -0.510066
#define bb 0.760666
#define cc -0.35663
#define dd -0.184483
return aa * height + bb * clears + cc * holes + dd * bump + ((double)rand() / RAND_MAX) * 0.001;
}
/////////////////////////////////////////////////////////

int rrot;
int ri, rj;
double rscore;
int do_move(int rot, int i, int j) {
for (int I = 0; I < fig_heights[type][rot]; I++) {
grid[i + I] |= figs[type][rot][I] << j;
}
// clear lines
int curr = 0;
for (int i = 0; i < 15; i++) {
if (grid[i] != (1<<15)-1) grid[curr++] = grid[i];
}
int clears = 0;
while (curr < 15) clears++, grid[curr++] = 0;
return clears;
}
int _grid[15];
void compute_move_pos(int rot, int i, int j) {
for (int i = 0; i < 15; i++) _grid[i] = grid[i];
int clears = do_move(rot, i, j);
double score = compute_score(rot, i, j, clears);
if (rscore < score) {
rscore = score;
rrot = rot;
ri = i;
rj = j;
}
for (int i = 0; i < 15; i++) grid[i] = _grid[i];
}
bool vis[16][15];
int good[16][15];
pt queue[16*15];
int di[3] = {-1, 0, 0};
int dj[3] = {0, 1, -1};
void compute_move_rot(int rot) {
for (int i = 0; i <= 15; i++) {
for (int j = 0; j < 15; j++) {
vis[i][j] = false;
good[i][j] = 0;
}
}
int q = 1;
queue[0].i = 15;
queue[0].j = 0;
vis[15][0] = true;
for (int f = 0; f < q; f++) {
int i = queue[f].i;
int j = queue[f].j;
if (i + fig_heights[type][rot] <= 15) {
bool good = false;
for (int h = 0; h < fig_heights[type][rot]; h++) {
int I = i + h;
if (!I || (grid[I-1] & (figs[type][rot][h] << j))) {
good = true;
break;
}
}
if (good) {
compute_move_pos(rot, i, j);
}
}
for (int d = 0; d < 3; d++) {
int ni = i + di[d];
int nj = j + dj[d];
if (0 <= ni && ni <= 15 && 0 <= nj && nj < 15 && !vis[ni][nj]) {
if (!good[ni][nj]) {
// compute_good
good[ni][nj] = 2;
for (int h = 0; h < fig_heights[type][rot]; h++) {
if (ni + h >= 15) break;
if (((figs[type][rot][h] << nj) >= 1<<15) || (grid[ni + h] & (figs[type][rot][h] << nj))) {
good[ni][nj] = 1;
break;
}
}
}
if (good[ni][nj] == 2) {
queue[q].i = ni;
queue[q].j = nj;
vis[ni][nj] = true;
q++;
}
}
}
}
}
void compute_move(int fix) {
rscore = -1e111;
if (fix >= 0) {
compute_move_rot(fix);
} else {
// compute valid positions
for (int rot = 0; rot < fig_counts[type]; rot++) {
compute_move_rot(rot);
}
}
}

int main() {
srand(11);
for (move = 0;; move++) {
scanf(“%s”, line);
char ptype = *line;
if (ptype == ‘1’ || ptype == ‘2’) {
scanf(“%d”, &type);
type–;
int fix = -1;
if (ptype == ‘2’) {
scanf(“%s”, line);
fix = *line - ‘a’;
}

        if (DEBUG) {
            printf("new piece\n");
            for (int i = fig_heights[type][0] - 1; i >= 0; i--) {
                for (int j = 0; j < 4; j++) {
                    printf("%c ", figs[type][0][i] & (1<<j) ? '#' : '.');
                }
                printf("\n");
            }
        }

        compute_move(fix);
        printf("%c %d %d\n", 'a' + rrot, 15 - ri, rj + 1);
        fflush(stdout);
        do_move(rrot, ri, rj);

        if (DEBUG) print();

    } else break;
}
if (DEBUG) printf("DONE. moves=%d\n", move);

}