May 2007
1 / 5
May 2007
Jun 2007
TripleM_sof
May '07

I'm just wondering.. is there actually an official solution that runs in time for this problem? I find that pretty unlikely.. or if so, then it was extremely lucky to run in time.

The problem is quite famous (I studied it quite a bit when at university), and a brute force solution is, of course, hopeless. The only known way of solving it is to use approximation algorithms, genetic algorithms etc (starting with a randomly coloring, then trying to move towards a solution).

There have been many research papers written about this that I've found online, including one that solved all trees of size up to 28 or so - taking well over 10 seconds average to solve each one.

So no doubt if there is an official solution, the heuristics involved must only luckily work on the small sample of trees from the test data.. and I could come up with a tree on which it failed.

So, could we have some hints at what the test data alone is like, or what the lucky heuristics are, or change the bounds on the problem?

(I am, of course, talking about the small tree one, not the other trivial part).

  • created

    May '07

  • last reply

    Jun '07
  • 4

    replies

  • 1.2k

    views

  • 3

    users

thanhvy_sof
May '07

The big tree is easy in this problem since it has a special shape
The small one: yes, I used the popular heuristic like some papers said: chose a random colors, then used Hill Climbing and Tabu search to optimize it until we get the correct answer. Size of tree is up to 27, i.e. it always exists solutions. I think it's small enough to pass Time Limit
Our implementation, which used to get running time is in Pascal.

p/s: We're writing a booklet (analysis) for all problems, will publish soon smile

1 month later
quirk_sof
Jun '07

To thanhvy,
Is the book published? I keen to read the book because i love TREE though didn't participate the contest. smile