Strange Town

This is problem D from Codeforces Round 41. You can find the analysis of the whole problemset here.

The problem in short -

Given a graph with N nodes and bidirectional edges between all pair of nodes, you have to assign distinct prices to the edges of the graph in a way such that all the Hamiltonian cycles cost the same. Price of an edge cannot exceed 1000.

Now there are some key observations here -

1. Instead of assigning prices to edges, if we assign them to nodes, then all the Hamiltonian cycles will cost the same and that will be double the sum of prices of the nodes.
2. Lets say, there are 2 edges - (i,j) and (k,l). Now a[i] + a[j] != a[k] + a[l] where a[x] is the price of node x. So, a[i] != a[k] + a[l] - a[j].

We can use observation 2 to employ a greedy strategy to solve the problem. We are going to assign prices one by one. For a node i, we have to assign it a price a[i] such that for any tuple (j,k,l) of already assigned nodes, a[i] != a[k] + a[l] - a[j].

We could have just assigned Fibonacci numbers to the nodes as

F(n) > F(n-1) + F(n-2) - F(1)

that is every new number in Fibonacci sequence is greater than sum of 2 largest number minus the lowest number. So, naturally a[i] != a[k] + a[l] - a[j] will always hold. But 20-th number of Fibonacci sequence is way larger than 1000, so we can't use it.

Btw, you can check this new (going-to-be-awesome) blog by Moshiur-
http://problem-solving-notes.blogspot.com/

C++ Source code -

#include<stdio.h>
#include<string.h>

#define rep(i,n) for(i = 0; i < (n); i++)

#define MAXN 20

bool flag[1024];

int main() {
 int N;
 int i,j,k,l;
 int a[MAXN+2];
 while(scanf(" %d",&N)==1) {
  a[0] = 1, a[1] = 2, a[2] = 3;
  for(i = 3; i < N; i++) {
   memset(flag,0,sizeof(flag));
   rep(j,i) flag[a[j]] = 1;
   rep(j,i) rep(k,i) rep(l,i) {
    if(j == k || k == l || l == j) continue;
    if(a[k] + a[l] - a[j] > 0) flag[a[k]+a[l]-a[j]] = 1;
   }
   for(j=1;j<=1000;j++) if(!flag[j]) break;
   a[i] = j;
  }
  rep(i,N) {
   rep(j,N) {
    if(j > 0) printf(" ");
    if(i == j) printf("0");
    else printf("%d",a[i]+a[j]);
   }
   printf("\n");
  }
 }
 return 0;
}