11307 - Alternative Arborescence

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

11307 - Alternative Arborescence

Post by mmonish » Sat Oct 06, 2007 7:22 pm

can anyone give me some hint on how to solve this problem..

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sat Oct 06, 2007 7:53 pm

DP:

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

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Post by rushel » Sat Oct 06, 2007 8:31 pm

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.

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Sun Oct 07, 2007 3:40 am

I tried DP but i am getting WA. Anyone please give me some critical test case..

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Post by baodog » Sun Oct 07, 2007 7:30 am

I believe number of colors can be bounded by C*log n or so.
In this case exactly 6 colors suffice.

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Sun Oct 07, 2007 7:52 am

Can anyone tell me what i did wrong here..

Code: Select all

Remove After AC
Last edited by mmonish on Sun Oct 07, 2007 9:00 am, edited 1 time in total.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Post by baodog » Sun Oct 07, 2007 8:05 am

Looks like you assume root is 0.
The root is in general not 0.

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Sun Oct 07, 2007 9:02 am

>>baodog
Thx for ur quick reply. Now i get AC.

goodwill
New poster
Posts: 25
Joined: Mon Sep 03, 2007 10:54 am

Post by goodwill » Sun Oct 07, 2007 12:05 pm

You may find this O(n) algorithm interesting (no need to know how many color there are).
http://citeseer.ist.psu.edu/494676.html

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Sun Oct 07, 2007 1:49 pm

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).

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by Robert Gerbicz » Sun Oct 07, 2007 2:53 pm

goodwill wrote:You may find this O(n) algorithm interesting (no need to know how many color there are).
http://citeseer.ist.psu.edu/494676.html
Today I've implemented that algorithm. Giving me the first position on this problem's ranklist by only 0.030 sec. of running time.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Oct 08, 2007 12:11 am

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)

User avatar
Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
Location: Bangladesh

Post by Donotalo » Wed Nov 21, 2007 7:00 pm

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;

		cin.ignore();
		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;
				else
					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?
Image

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Wed Dec 19, 2007 5:57 pm

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):
http://www.public.asu.edu/~halla/papers/OCCPWG96.ps

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.

Sedefcho

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

Re: 11307 - Alternative Arborescence

Post by lonelyone » Tue May 27, 2008 5:09 pm

Why it got Runtime Error? Could someone explain this for me? Thanks a lot.

Code: Select all

for(i=0; i<n; ++i)
        {
            gets(line);
            p = line;
            sscanf(p, "%d%n", &from, &len);
            p += len;
            while(*p)
            {
                if(sscanf(p, "%d%n", &to, &len) == 1)
                {
                     v[from].push_back(to);
                }
                p += len;
            }
        }

Post Reply

Return to “Volume 113 (11300-11399)”