11307 - Alternative Arborescence
Moderator: Board moderators
11307 - Alternative Arborescence
can anyone give me some hint on how to solve this problem..
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.
You may find this O(n) algorithm interesting (no need to know how many color there are).
http://citeseer.ist.psu.edu/494676.html
http://citeseer.ist.psu.edu/494676.html
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).
'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).
-
- Experienced poster
- Posts: 196
- Joined: Wed May 02, 2007 10:12 pm
- Location: Hungary, Pest county, Halasztelek
- Contact:
Today I've implemented that algorithm. Giving me the first position on this problem's ranklist by only 0.030 sec. of running time.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
I tried with 10 colors but got WA. Here is my code:
Can anyone help me to find my mistake?
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;
}
![Image](http://img157.imageshack.us/img157/295/donotalo2251522537ss3.png)
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
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
Re: 11307 - Alternative Arborescence
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;
}
}