Solution UVA: 10911 - Forming Quiz Teams

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10911 - Forming Quiz Teams	Accepted	C++11	0.010	0.000	735	18 secs ago

We must "dynamic programming with bitmask" to solve problem if not want use another algorithm harder. (CP Book 4 Part 2 have tutorial detail)

If you not know dp bitmask before, i think we need go to from:

/1/ basic dp with state use vector<bool> 

/2/ upgrade dp with state use bitset

/3/ And final use dp bitmask !

Version /3/ use bitmask (Accepted -  Code from CP Book 4 Part 2): //version 1 and 2 in bottom

// Forming Quiz Teams

#include <algorithm>            // if you have problems with this C++ code,

#include <cmath>            // consult your programming text books first...

#include <cstdio>

#include <cstring>

using namespace std;

        /* Forming Quiz Teams, the solution for UVa 10911 above */

          // using global variables is a bad software engineering practice,

int N, target;                  // but it is OK for competitive programming

double dist[20][20], memo[1 << 16];  // 1 << 16 = 2^16, note that max N = 8

double matching(int bitmask) {                        // DP state = bitmask

                       // we initialize `memo' with -1 in the main function

  if (memo[bitmask] > -0.5)          // this state has been computed before

    return memo[bitmask];                   // simply lookup the memo table

  if (bitmask == target)                // all students are already matched

    return memo[bitmask] = 0;                              // the cost is 0

  double ans = 2000000000.0;               // initialize with a large value

  int p1, p2;

  for (p1 = 0; p1 < 2 * N; p1++)

    if (!(bitmask & (1 << p1)))

      break;                              // find the first bit that is off

  for (p2 = p1 + 1; p2 < 2 * N; p2++)              // then, try to match p1

    if (!(bitmask & (1 << p2)))     // with another bit p2 that is also off

      ans = min(ans,                                    // pick the minimum

                dist[p1][p2] + matching(bitmask | (1 << p1) | (1 << p2)));

  return memo[bitmask] = ans;    // store result in a memo table and return

}

int main() {

  int i, j, caseNo = 1, x[20], y[20];

  // freopen("10911.txt", "r", stdin);      // redirect input file to stdin

  while (scanf("%d", &N), N) {                    // yes, we can do this :)

    for (i = 0; i < 2 * N; i++)

      scanf("%*s %d %d", &x[i], &y[i]);                // '%*s' skips names

    for (i = 0; i < 2 * N - 1; i++)        // build pairwise distance table

      for (j = i + 1; j < 2 * N; j++)      // have you used `hypot' before?

        dist[i][j] = dist[j][i] = hypot(x[i] - x[j], y[i] - y[j]);

    // use DP to solve min weighted perfect matching on small general graph

    for (i = 0; i < (1 << 16); i++) memo[i] = -1.0;  // set -1 to all cells

    target = (1 << (2 * N)) - 1;

    printf("Case %d: %.2lf\n", caseNo++, matching(0));

} } // return 0;

Verison /1/ basic dp use vector<bool> (Only apply N <= 4, my code)

#include<bits/stdc++.h>

using namespace std;

const int N= 9;

int x[N], y[N];

double d[N][N];

int n;  

string s;

map<vector<bool>, double> F;

double f(vector<bool> state){

    if (F.count(state)) return F[state];

   

    int i= 0;

    for(i; i<state.size(); i++)

        if (state[i] == false) break;

    if (i == state.size()) return 0;

   

    double ans = 1000111000;

    int p1, p2;

   

    for(p1 = 0; p1 < 2*n; p1++)

        if (state[p1] == false) break;

   

    for(p2 = p1 + 1; p2 < 2*n; p2++)

        if (state[p2] == false){

           

            state[p1]= true;

            state[p2]= true;

           

            ans = min(ans, d[p1][p2] + f(state));

           

            state[p1]= false;

            state[p2]= false;

        }

   

    return F[state] = ans;

   

}

int main(){

    while(cin >> n && n){

        for(int i=0; i<2*n; i++)

            cin >> s >> x[i] >> y[i];

           

        for(int i=0; i<2*n; i++)

            for(int j=0; j<2*n; j++)

                d[i][j] = hypot(x[i]-x[j], y[i]-y[j]);

       

        vector<bool> state(2*n, false);            

        F.clear();

        cout << f(state) <<"\n";

    }

}

Verison /2/ dp use bitset (Only apply N <= 4, memory smaller than vector<bool> and deploy near bitmask,  my code)

#include<bits/stdc++.h>

using namespace std;

const int N= 8;

int x[N], y[N];

double d[N][N];

int n;  

string s;

unordered_map<bitset<16>, double> F;

double f(bitset<16> state){

    if (F.count(state)) return F[state];

   

    int i= 0;

    for(i; i<2*n; i++)

        if (state.test(i) == false) break;

    if (i == 2*n) return 0;

   

    double ans = 1000111000;

    size_t p1, p2;

   

    for(p1 = 0; p1 < 2*n; p1++)

        if (state.test(p1) == false) break;

       

    for(p2 = p1 + 1; p2 < 2*n; p2++)

        if (state.test(p2) == false){

           

            state.flip(p1);

            state.flip(p2);

           

            ans = min(ans, d[2*n-1-p1][2*n-1-p2] + f(state));

           

            state.flip(p1);

            state.flip(p2);

        }

   

    return F[state] = ans;

   

}

int main(){

    while(cin >> n && n){

        for(int i=0; i<2*n; i++)

            cin >> s >> x[i] >> y[i];

           

        for(int i=0; i<2*n; i++)

            for(int j=0; j<2*n; j++)    

                d[i][j] = hypot(x[i]-x[j], y[i]-y[j]);

       

        bitset<16> state; //00...000(16)                

        F.clear();

        cout << fixed << setprecision(3) << f(state) <<"\n";

    }

}