Problem D

I was really close to get the right idea for this problem. In the contest, I thought the algorithm should be something like this:

First, assign each vertex v with different potential p[v], and the weight of each edge {v,w} is p[v] – p[w]. Then, I spent a lot of time to try figuring out a set of numbers for being the potentials until the end of the contest.

After the contest, I found that  I misread the problem statement. The weight of an edge {v, w} should be the same as the weight of {w, v}. Oh, damn. It *seems* that my algorithm doesn’t work since p[v] – p[w] != p[w] – p[v]. Then, after reading some solutions in the practice room, I found that I was really closed to the solution. Actually, we can use addition instead of subtraction. Damn… Unbelievable… I missed something as simple as this XD. So, change my previous algorithm for p[v] – p[w] to p[v] + p[w] and we get the right answer. Here is my code, got it accepted in the practice room.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>

#define REP(i,n) for (int i = 0, _n = (n); i < _n; i++)
#define FOR(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define SIZE(c) (c).size()
#define PB push_back

using namespace std;

vector <int> v;
set <int> S;

int M[22][22];

int main () {
    v.PB (1);

    REP (i, 19) {
        FOR (j, v[i] + 1, 1000) {
            bool flag = true;
            REP (k, SIZE (v)) {
                if (S.find (j + v[k]) != S.end()) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                REP (k, SIZE (v)) S.insert (j + v[k]);
                v.PB (j);
                break;
            }
        }
    }

    REP (i, 20) {
        REP (j, 20) {
            M[i][j] = v[i] + v[j];
        }
    }

    REP (i, 20) M[i][i] = 0;

    int N;

    scanf ("%d", &N);

    REP (i, N) {
        REP (j, N) {
            if (j) printf (" ");
            printf ("%d", M[i][j]);
        }
        puts ("");
    }

    return 0;
}
Advertisements