[UVa.10911] Forming Quiz Teams

알고리즘 트레이닝 - 스티븐 할림/펠릭스 할림의 첫 문제입니다.
각자의 수준을 알아보라는 목적으로 낸 문제인데, 생각보다 수월하게 풀려서 확실히 10년대 초반에 비해 실력의 하한이 올라갔다는 생각이 듭니다. 그런 점에서 할림 형제는 목적을 이룬 것 같네요 ㅋㅋ

Problem

문제 본문
요약: 주어진 $2N$개의 점들을 $N$개의 그룹으로 나눕니다. 이 때, $N$개의 각 그룹에서 두 점 사이의 거리가 나올텐데, 그 거리의 총합이 최소가 되게 하고 싶습니다. 이 때, 총합을 구해주세요.

Basic approach

수식이 오히려 불편하기 때문에 직접 연산량을 구하도록 하겠습니다.
$X=\binom {16}{2}\times\binom {14}{2}\times\cdots \times\binom {2}{2}$라고 합시다.
naive하게 $X=16!/2^8\approx 16\cdot 15\cdot 14\cdot 13\cdot 12\cdot 11\times 3628800/2^8\ge 10^6\times 3\cdot 10^6/3\cdot 10^2= 10^{10}$번의 연산을 하면 TLE가 명백합니다.
그러면, 중복을 해결했을때 어떻게 될까요?
$X/8!$가 됩니다. $X/8!=16\cdot 15\cdot 14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9/2^8\approx 2\cdot 10^6$이므로 충분히 돌아갈 것입니다.

뒤이어 나올 두 가지 솔루션은 모두 중복을 제거하는 풀이이기 때문에 확신을 갖고 임하면 됩니다.
상세한 시간 복잡도 분석은 뒤에서 하겠습니다.

First Solution

/*

Code by hgmhc.
* 20분 컷.
* 1 WA 후 AC. 변명을 하자면 책에 요약된 문제 내용이 실제 description과 달라서 다른 형태로 제출함.
* 28번째 줄을 쓰지 않은걸 디버깅 함.

*/
#include <bits/stdc++.h>
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define debug(x) cout << #x << " is " << x << el
#define el '\n'
using namespace std; using ll = long long;

const int N = 17;
const double INF = 1e9;
int n;
complex<double> point[N];
bool checked[N];

double f(int k = 1) {
    if (k == n+1) return 0;
    int x = -1;
    REP(i,1,2*n) if (not checked[i]) {x = i; break;}
    double best = INF;
    checked[x] = true;
    REP(y,x+1,2*n) {
        if (checked[y]) continue;
        checked[y] = true;
        best = min(best,abs(point[x]-point[y])+f(k+1));
        checked[y] = false;
    }
    checked[x] = false;
    return best;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc = 0;
    cout << fixed;
    cout.precision(2);
    while (++tc) {
        cin >> n;
        if (n == 0) return 0;
        REP(i,1,2*n) {
            string s; cin >> s;
            double x, y; cin >> x >> y;
            point[i] = {x,y};
        }
        cout << "Case " << tc << ": " << f() << el;
    }
}

$T(n)$이 제 코드 속 알고리즘 수행 시간입니다.
$T(m)=2n+2n+(2n-2m)\cdot T(m-1)=4n+2(n-m)\cdot T(m-1)\le 2n\cdot T(m-1)+\mathcal O(n);\, T(1)=\mathcal O(1).$
$T'(m)=2n\cdot T'(m-1)+\mathcal O(n);\, T'(1)=\mathcal O(1).$
$T'(m)\ge T(m)\forall m\ge 1.$
따라서 $T'(m)$의 시간 복잡도가 통과한다는 것을 확인하면 충분하다.
믿음의 치환법으로, $T'(m)=\mathcal O(2^m n^2)$라 하면, $(RHS)=2n\cdot 2^{m-1} n^2+\mathcal O(n)$ 옳지 않다.
$T'(m)=\mathcal O(2^m n^{m-1})$라 하면, $(RHS)=2n\cdot 2^{m-1} n^{m-2}+\mathcal O(n),$
$T'(1)=\mathcal O(2^1\cdot n^0)=\mathcal O(1)$이므로 만족한다.
$T'(8)=2^8\cdot 8^7=2^{8+21}\approx 5\times 10^8$이므로 1초에는 안 돌아가되, 기도했을 시 제한 시간 3초 내에 돌아갈 수 있습니다. 또한, $T'$이 naive 버전이란 것을 감안하면 좀 더 빠를 것입니다.
사실 저도 이렇게까지는 안 재보고 넣었는데 실전이였으면 큰일 날 번 했군요...
역시 백트래킹 시간 복잡도 분석은 어렵습니다...
오늘 마스터 정리와 치환법 알아가는 것은 상당히 기분이 좋군요...

Second Solution

$\mathcal O(2n+2^{2n}+2^{2n}\cdot \binom{2n}2)=\mathcal O(4^nn^2).$
$4^8\times 8^2=2^22=4\times 1048576\approx 4\times 10^6$이므로 통과합니다.

#include <bits/stdc++.h>
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define debug(x) cout << #x << " is " << x << el
#define el '\n'
using namespace std; using ll = long long;

const int N = 16;
const double INF = 1e9;
int n;
complex<double> point[N];
double dp[1<<N];

double solve() {
    fill_n(dp,1<<(2*n),INF);
    dp[0] = 0;
    REP(mask,0,1<<(2*n)) {
        REP(i,0,2*n-1) if (mask&(1<<i)) {
            REP(j,i+1,2*n-1) if (mask&(1<<j)) {
                dp[mask] = min(dp[mask],dp[mask^(1<<i)^(1<<j)]+abs(point[i]-point[j]));
            }
        }
    }
    return dp[(1<<(2*n))-1];
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc;
    cout << fixed;
    cout.precision(2);
    while (++tc) {
        cin >> n;
        if (n == 0) return 0;
        REP(i,0,2*n-1) {
            string s; cin >> s;
            double x, y; cin >> x >> y;
            point[i] = {x,y};
        }
        cout << "Case " << tc << ": " << solve() << el;
    }
}