**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;
}

### Like this:

Like Loading...

*Related*

Pingback: E – Baldman and the military (Codeforces Beta Round #41) « Risan