JMK no matter what

A match sponsored by Facebook. Simple simulation 250, Graph + Bipartite Matching 500. I wasn't sure about whether bipartite matching could be the right solution for 500 (I'm so rusty.. of course, this is a classic example of Konig's theorem.) About 1000, so far no idea.

250 KnightsTour

I had some classic mistakes; like, writing x instead of jx and such. This kind of mistakes happen because the code was not decomposed properly into functions, and every line has a lot of context. Factoring out the part where we are looking for accessibility numbers would have been more neat.

lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;

const int dx[8] = { 2, 2, 1, 1, -2, -2, -1, -1 };
const int dy[8] = { 1, -1, 2, -2, 1, -1, 2, -2 };

struct KnightsTour 
{
    int visitedPositions( vector <string> board ) 
    {
        int kx, ky;
        int h = board.sz, w = board[0].sz;
        REP(i,h) REP(j,w) if(board[i][j] == 'K') { ky = i; kx = j; }
        int ret = 1;
        while(true)
        {
            board[ky][kx] = '*';
            int ny = -1, nx = -1, minAcc = 999;
            REP(k,8)
            {
                int y = ky + dy[k], x = kx + dx[k];
                if(0 <= y && y < h && 0 <= x && x < w && board[y][x] == '.')
                {
                    int acc = 0;
                    REP(k2,8)
                    {
                        int jy = y + dy[k2], jx = x + dx[k2];
                        if(0 <= jy && jy < h && 0 <= jx && jx < w && board[jy][jx] == '.')
                            ++acc;
                    }
                    if(acc < minAcc ||
                            (acc == minAcc && y < ny) ||
                            (acc == minAcc && y == ny && x < nx))
                    {
                        minAcc = acc;
                        ny = y;
                        nx = x;
                    }
                }
            }
            if(ny == -1) break;
            ky = ny;
            kx = nx;
            ++ret;
        }
        return ret;
    }
};

500 PeopleYouMayKnow

A nice problem statement. Start from the obvious: if they share a friend, all the friends should be removed. Otherwise, there are two friends between them. There's a choice - remove which? Classify them into two classes - ones who are friends with A and ones who are friends with B. Then we have a bipartite graph and a min vertex cover problem.

lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;

struct BipartiteMatch
{
    int A, B;
    vector<vector<int> > adj;
    vector<int> bmatch;
    vector<bool> seen;
    BipartiteMatch(int A_, int B_) : A(A_), B(B_), adj(A), bmatch(B, -1), seen(A) { }
    void addEdge(int a, int b) { adj[a].push_back(b); }
    int go() {
        int ret = 0;
        for(int i = 0; i < A; ++i) { fill(seen.begin(), seen.end(), false); if(improve(i)) ++ret; }
        return ret;
    }
    bool improve(int here)
    {
        if(seen[here]) return false; seen[here] = true;
        for(int i = 0; i < adj[here].size(); ++i)
        {
            int there = adj[here][i];
            if(bmatch[there] == -1 || improve(bmatch[there])) { bmatch[there] = here; return true; }
        }
        return false;
    }
};

struct PeopleYouMayKnow 
{
    int maximalScore( vector <string> friends, int person1, int person2 ) 
    {
        int n = friends.sz;
        VVI c(n, VI(n));
        REP(i,n) REP(j,n) { if(i == j) c[i][j] = 0; else if(friends[i][j] == 'Y') c[i][j] = 1; else c[i][j] = 999; }
        REP(k,n) REP(i,n) REP(j,n) c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
        int ret = 0;
        VI a1, a2;
        REP(i,n) if(c[i][person1] == 1 && c[i][person2] == 1) ++ret;
        REP(i,n) if(c[i][person1] == 1 && c[i][person2] == 2) a1.pb(i);
        REP(i,n) if(c[i][person1] == 2 && c[i][person2] == 1) a2.pb(i);
        BipartiteMatch bm(a1.sz, a2.sz);
        REP(i,a1.sz) REP(j,a2.sz) if(friends[a1[i]][a2[j]] == 'Y') 
            bm.addEdge(i, j);
        return ret + bm.go();
    }
};