오랜만의 에디토리얼이네요..

상위 10명, 300등 안에 든 한국인들과 일부 타겟들의 리스트를 섞어보았습니다.
Hard (Level 3) 문제에 대한 에디토리얼은 추후에 누군가가 써 주시리라 믿고 전 패스하겠습니다.

Easy (250 pts)

• Problem Statement 페이스북 엔지니어들은 체스를 너무 좋아한답니다. 또한 그들은 체스판에서 할 수 있는 모든 게임들을 즐겨합니다. 오늘은 주어진 규칙에 따라 Knight가 이동한다면 몇 개의 칸을 지나가는지 구하고 있었습니다. 8x8의 체스 보드가 있습니다. 보드는 '*', '.', 'K'로 이루어져 있습니다. K는 나이트의 위치이며, 는 갈 수 없는 곳을 나타내고 있습니다. "." 는 나이트가 갈 수 있는 위치를 나타냅니다. 나이트는 한 방향으로 두 칸, 그에 수직한 방향으로 한 칸 이동합니다. (장기의 마와 비슷합니다.) 현재 위치에서 이동할 수 있으면, 그 칸을 "Accessible" 하다고 합니다. 또한 시작점을 포함해서, 한 번 지나간 장소는 두 번 다시 돌아올 수 없습니다. 나이트는 현재 위치에서 다음 위치로 이동했을 때, 다음 위치에서 갈 수 있는 칸이 제일 많은 칸으로 이동합니다. 만약 이러한 칸이 여럿 존재하는 경우에는, row number가 작은 곳으로, row number가 같다면 col number가 작은 곳으로 이동합니다. 만약 나이트가 더 이상 이동할 수 없으면 멈춥니다. 시작위치를 포함해서, 나이트가 몇 칸이나 방문할 수 있는지를 구하세요. [spoiler="풀이 보기..."] Solution Easy 문제는 알고리즘을 주고, 그대로 코딩하라는 문제기 때문에 따로 적을 내용이 없네요 [...] ~~~ cpp

int dx[8] = {-2,-2,-1,-1,1,1,2,2};
int dy[8] = {-1,1,-2,2,-2,2,-1,1};
vector board;
int getpos(int x, int y)
{
int ret = -1;
int lo = 999;
for (int i = 0; i < 8; ++i)
{
int tmp = 0;
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= 8 || ny >= 8) continue;
if (board[nx][ny] == '*') continue;
for (int j = 0; j < 8; ++j)
{
int nnx = nx + dx[j], nny = ny + dy[j];
if (nnx < 0 || nny < 0 || nnx >= 8 || nny >= 8) continue;
if (board[nnx][nny] == '*') continue;
tmp++;
}
if (lo > tmp) { lo = tmp; ret = i; }
}
return ret;
}
int go(int x, int y)
{
int ret = 1;
while (true)
{
int g = getpos(x, y);
if (g == -1) break;
x += dx[g], y += dy[g];
ret++;
board[x][y] = '*';
}
return ret;
}
struct KnightsTour {
int visitedPositions(vector _board)
{
board = _board;
const int n = 8;
int x, y;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (board[i][j] == 'K') { x = i, y = j; board[i][j] = '*'; }
return go(x, y);
}
};

[/spoiler]

Medium (500 pts)
* Problem Statement (원본 문제를 의역했습니다.)
 친구관계는 Symmetric하지만 Transitive 하지는 않습니다. A가 B의 친구라면 B는 A의 친구입니다. 하지만 A가 B의 친구리고, B가 C의 친구라고 하더라도, A와 C는 친구가 아닐 수도 있습니다.
 둘이 서로 친구라면 이는 1-friend 라고 부릅니다. 1보다 큰 n에 대해서, {A와 B가 n-friend}이거나, {A와 n-friend인 C가 있고, C와 B가 1-friend}인 경우, A와 B는 (n+1)-friend 라고 부릅니다. 
 A와 B가 3-friend가 되지 않도록 만들고 싶습니다. 최소한의 사람을 제외시킨다고 할 때, 몇 명의 사람이 없어져야 A와 B가 3-friend가 될 수 없을까요?
[spoiler="풀이 보기..."]
* Solution
 A와 B가 3-friend라면 A의 친구 P, B의 친구 Q, 그리고 P와 Q는 서로 친구인 경우가 존재하는 셈입니다. 이러면 P와 Q는 한 명 이상일 수가 있게 되지요. 또한 P이면서 Q인 사람이 존재할 수 있는데 이러한 사람은 무조건 제외시켜야 합니다.
 <img alt="srm447med.png" src="/files/attach/images/53443/261/060/srm447med.png" editor_component="image_link">
P = Q인 경우를 제외하면 위와 같이 되겠지요. 서로 1-friend인 경우를 연결시켜 보았습니다. 이제 여기서 최소의 사람을 제외시켜 그래프를 끊으면 되겠습니다. 그려놓고 보니 min-cut 문제가 되어버렸네요...
 따라서 그래프를 만들고 Maximum matching을 구하면 됩니다. (min-cut과 동치니까요... 자세한 설명은 댓글로 달아 주실꺼에요)
~~~ cpp

int n;
int N, M;
vector  graph[50];
vector  a, b;
int match1[50];
int match2[50];
char check[50];
bool extendMatch(int a) {
  for (int i = 0 ; i < graph[a].size() ; i++) {
    int b = graph[a][i];
    if (check[b]) continue;
    if (match2[b] == -1) {
      match1[a] = b;
      match2[b] = a;
      return true;
    }
  }
  for (int i = 0 ; i < graph[a].size() ; i++) {
    int b = graph[a][i];
    if (check[b]) continue;
    check[b] = 1;
    if (extendMatch(match2[b])) {
      match1[a] = b;
      match2[b] = a;
      return true;
    }
  }
  return false;
}
int maxMatch() {
  memset(match1, -1, N*sizeof(int));
  memset(match2, -1, M*sizeof(int));
  int cnt = 0;
  for (int i = 0 ; i < N ; i++) {
    memset(check, 0, M);
    if (extendMatch(i))
      cnt++;
  }
  return cnt;
}
struct PeopleYouMayKnow {
  int maximalScore(vector  friends, int personA, int personB) {
    n = friends.size();
    int ret = 0;
    for (int i = 0; i < n; ++i)
    {
      if (i == personA || i == personB) continue;
      if (friends[personA][i] == 'Y' && friends[personB][i] == 'Y') 
      {
        ret++;
        continue;
      }
      if (friends[personA][i] == 'Y') a.push_back( i );
      if (friends[personB][i] == 'Y') b.push_back( i );
    }
    for (int i = 0; i < a.size(); ++i)
    {
      for (int j = 0; j < b.size(); ++j)
      {
        if (friends[a[i]][b[j]] == 'Y') graph[i].push_back( j );
      }
    }
    N = a.size();
    M = b.size();
    return ret + maxMatch();
  }
};

[/spoiler]