11307 - Alternative Arborescence

Moderator: Board moderators

11307 - Alternative Arborescence

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

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

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
sclo
Guru

Posts: 519
Joined: Mon Jan 23, 2006 10:45 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.
rushel
Learning poster

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

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

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

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

Posts: 197
Joined: Wed Jul 04, 2007 6:53 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.
mmonish
Experienced poster

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

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

Posts: 197
Joined: Wed Jul 04, 2007 6:53 am

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

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

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

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

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

Posts: 572
Joined: Fri Nov 11, 2005 9:34 am

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.
Robert Gerbicz
Experienced poster

Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek

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)
sclo
Guru

Posts: 519
Joined: Mon Jan 23, 2006 10:45 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 10unsigned 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?

Donotalo
Learning poster

Posts: 56
Joined: Sat Aug 20, 2005 11:05 am

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

Sedefcho

Sedefcho
A great helper

Posts: 375
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

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;            }        }`
lonelyone
Learning poster

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

Next