Page 1 of 2

11307 - Alternative Arborescence

Posted: Sat Oct 06, 2007 7:22 pm
by mmonish
can anyone give me some hint on how to solve this problem..

Posted: Sat Oct 06, 2007 7:53 pm
by sclo

let f(i,j) = minimum sum of subtree rooted at i, where i has color j

Further, the maximum color we need can be more than 2

Posted: Sat Oct 06, 2007 8:31 pm
by rushel
how stupid i am. i tried dp with 3 colors. thank sclo now i got ACCEPTED using 20 colors.

but how could i proof that how many colors are needed.

Posted: Sun Oct 07, 2007 3:40 am
by mmonish
I tried DP but i am getting WA. Anyone please give me some critical test case..

Posted: Sun Oct 07, 2007 7:30 am
by baodog
I believe number of colors can be bounded by C*log n or so.
In this case exactly 6 colors suffice.

Posted: Sun Oct 07, 2007 7:52 am
by mmonish
Can anyone tell me what i did wrong here..

Code: Select all

Remove After AC

Posted: Sun Oct 07, 2007 8:05 am
by baodog
Looks like you assume root is 0.
The root is in general not 0.

Posted: Sun Oct 07, 2007 9:02 am
by mmonish
Thx for ur quick reply. Now i get AC.

Posted: Sun Oct 07, 2007 12:05 pm
by goodwill
You may find this O(n) algorithm interesting (no need to know how many color there are).

Posted: Sun Oct 07, 2007 1:49 pm
by Darko
I found the way to build the minimum size trees that need k colors and the linear algorithm to calculate the chromatic sum of a tree in the paper referenced there:
'Introduction to chromatic sums' - Kubicka, Schwenk (1989)
Expanded version is the first section of Kubicka's PhD thesis.

I thought it was fun, just because it is not that obvious how many colors you need and some obvious greedy approaches don't work (like assigning 1's to a max independent set).

A tree needs more than 10000 nodes to use the 9th color. The sequence of minimum number of nodes that force kth color is in OEIS - I didn't find the chromatic sum mentioned there, but that is the sequence.

baodog is right, test cases go only up to 6 colors (I was doing them by hand - too lazy, I guess, but if you solve for 6 I think you solved it).

Posted: Sun Oct 07, 2007 2:53 pm
by Robert Gerbicz
goodwill wrote:You may find this O(n) algorithm interesting (no need to know how many color there are).
Today I've implemented that algorithm. Giving me the first position on this problem's ranklist by only 0.030 sec. of running time.

Posted: Mon Oct 08, 2007 12:11 am
by sclo
Actually, on the contest, I saw many people got WA the first try, so I guessed that greedy doesn't really work, and tried an solution for 10 colors, since it seems reasonable that the number of color is around O(log n)

Posted: Wed Nov 21, 2007 7:00 pm
by Donotalo
I tried with 10 colors but got WA. Here is my code:

Code: Select all

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

#define MAX 10004
#define NCOLOR 10
unsigned long INF = (1 << 29);

int degree[MAX], graph[MAX][MAX], cost[MAX][NCOLOR];

int main()
	register int m, p;
	int n, i, j, k, color;
	string line, first;

	while(cin >> n) {
		if (n == 0) break;

		memset(degree, 0, sizeof(degree));
		memset(graph, 0, sizeof(graph));

		for (i = 0; i < n; i++) {
			getline(cin, line);
			stringstream sstr;
			sstr << line;
			sstr >> first;
			first.erase(first.size()-1, 1);
			stringstream sstr2;
			sstr2 << first;
			sstr2 >> j;

			while(sstr >> k) {
				if (k > j)
					graph[j][degree[j]++] = k;
					graph[k][degree[k]++] = j;

/*		for (i = 0; i < n; i++) {
			cout << i << ": ";
			for (j = 0; j < degree[i]; j++)
				cout << graph[i][j] << ' ';
			cout << endl;
		cout << endl;*/

		for (i = n-1; i >= 0; i--) {
			if (degree[i] == 0) {
				for (j = 0; j < NCOLOR; j++)
					cost[i][j] = j + 1;
			else {
				for (color = 0; color < NCOLOR; color++) {
					k = 0;
					for (j = 0; j < degree[i]; j++) {
						m = INF;
						for (p = 0; p < NCOLOR; p++) {
							if (p == color) continue;
							if (cost[graph[i][j]][p] < m)
								m = cost[graph[i][j]][p];
						k += m;
					cost[i][color] = k + color + 1;

		m = cost[0][0];
		for (i = 1; i < degree[0]; i++)
			if (cost[0][i] < m)
				m = cost[0][i];
		cout << m << endl;

	return 0;
Can anyone help me to find my mistake?

Posted: Wed Dec 19, 2007 5:57 pm
by Sedefcho
Hello all,

I have implemented the algorithm described in the OCCP article
by Leo G. Kroon, Arunabha Sen, Haiyong Deng and Asim Roy.

Check this link (it's a PostScript file):

I have tested it with several test cases (simple ones)
and the answers seem OK.
I got RE from the judge though.

Could someone give any hint about special cases,
boundary conditions etc. I am stuck as the new system
provides no feedback at all about the error (not even
a simple email).

Thanks in advance.


Re: 11307 - Alternative Arborescence

Posted: Tue May 27, 2008 5:09 pm
by lonelyone
Why it got Runtime Error? Could someone explain this for me? Thanks a lot.

Code: Select all

for(i=0; i<n; ++i)
            p = line;
            sscanf(p, "%d%n", &from, &len);
            p += len;
                if(sscanf(p, "%d%n", &to, &len) == 1)
                p += len;