Sorry, the test is not small. Now I will give a description of the test. There 5 groups with sizes: (6 1) (5 1) (4 1) (4 1) (4 1). The right answer for this test is 14:14. But the greedy program gives 15:13. I think moderators shall add this test to the test data and many solutions will be rejected.

28
21 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 0
26 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 0
26 2 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 0
26 2 3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 0
26 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 0
26 2 3 4 5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 0
26 2 3 4 5 6 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 0
22 1 2 3 4 5 6 7 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 0
26 1 2 3 4 5 6 7 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 0
26 1 2 3 4 5 6 7 9 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 0
26 1 2 3 4 5 6 7 9 10 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 0
26 1 2 3 4 5 6 7 9 10 11 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 0
26 1 2 3 4 5 6 7 9 10 11 12 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 0
23 1 2 3 4 5 6 7 8 9 10 11 12 13 19 20 21 22 23 24 25 26 27 28 0
26 1 2 3 4 5 6 7 8 9 10 11 12 13 16 17 18 19 20 21 22 23 24 25 26 27 28 0
26 1 2 3 4 5 6 7 8 9 10 11 12 13 15 17 18 19 20 21 22 23 24 25 26 27 28 0
26 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 18 19 20 21 22 23 24 25 26 27 28 0
26 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17 19 20 21 22 23 24 25 26 27 28 0
23 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 24 25 26 27 28 0
26 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 21 22 23 24 25 26 27 28 0
26 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 22 23 24 25 26 27 28 0
26 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 23 24 25 26 27 28 0
26 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 24 25 26 27 28 0
23 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 0
26 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 26 27 28 0
26 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 25 27 28 0
26 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 25 26 28 0
26 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 25 26 27 0

can anyone send me a test please?
 semenanufriev@gmail.com

do anyone knows the 25th test?
I think my alg is correct but I can't acc it...
help pls!
Do a dfs on G complement to make it a set of bipartite graphs (remove one way edges) then brute force on set of components after some optimization to avoid TLE and find the best dividing...
any idea?!

Edited by author 20.08.2015 17:30

Hi all.
I use dfs to find the number of connected components.
If there are 2 components,then i output each of them as a single team.If there is only 1 CC,then i output numbers from 1 to n/2  and from n/2+1 to n.
Otherwise "No solution".
It seems to me correct,but....
Or tell me some tests that prove my idea's fail)

Can somebody share test case #5?

And,shouldn't this problem have a special judge?There may be many situations.
__
var col:array[1..100] of longint;
    c,c1,map:array[0..100,0..100] of boolean;
    t:array[1..3,1..100] of boolean;
    a,a1:array[0..100] of boolean;
    sum:array[0..3] of longint;
    n,i,j,k,l,x,ans:longint;

procedure dfs(x,v:longint);
var i:longint;
begin
 if col[x]<>0 then exit;
 if col[x]+v=3 then begin writeln('No solution');halt;end;
 col[x]:=v;inc(sum[v]);t[v,x]:=true;
 for i:=1 to n do if x<>i then
  if map[x,i] and map[i,x] then dfs(i,3-v);
end;

begin                assign(input,'1.txt');reset(input);
  readln(n);fillchar(col,sizeof(col),0);a[0]:=true;
  for i:=1 to n do begin read(x);while x<>0 do begin map[i,x]:=true;read(x);end;end;
  for i:=1 to n do if col[i]=0 then begin
   fillchar(t,sizeof(t),0);sum[1]:=0;sum[2]:=0;dfs(i,1);
   fillchar(a1,sizeof(a1),0);
   for k:=1 to 2 do
    for j:=0 to n-sum[k] do
     if a[j] and not a1[j+sum[k]] then begin
      a1[j+sum[k]]:=true;
      for l:=1 to n do c1[j+sum[k],l]:=c[j,l] or t[k,l];
     end;a:=a1;c:=c1;
  end;ans:=n;while(not a[ans])and(ans>=1) do dec(ans);
  write(ans);for i:=1 to n do if c[ans,i] then write(' ',i);writeln;
  write(n-ans);for i:=1 to n do if not c[ans,i] then write(' ',i);writeln;
end.

sim_pet3@hotmail.com
Thank you very much ^^

I have WA on the test 25. Who can help me?

My Email:sxcyd@126.com
Thank you!

Edited by author 23.10.2010 08:26

OX-OX-OX

The Judge's Server is powerful..
i uses DFS and DP to kill it.
But a simple wrong let me not 1Y this prolem..

Edited by author 07.02.2009 22:02

Logic & DP & Theory graphs & Attentiviness = AC

Thanks huge to authors of this problem!

WA On Test #16

#include <stdio.h>
#include <memory.h>
#include <stdlib.h>

#define max(a, b) (a) > (b) ? (a) : (b)

bool link[101][101];
int n;

int main(void){
    memset(link, false, sizeof(link));

    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        int next; scanf("%d", &next);
        while (next != 0){
              link[i][next] = true;
              scanf("%d", &next);
        }
    }

    for (int i = 1; i <= n; i++){
        for (int j = i + 1; j <= n; j++){
            if (!link[i][j] || !link[j][i]){
               link[i][j] = link[j][i] = true;
            }  else {
               link[i][j] = link[j][i] = false;
            }
        }
    }

    bool vis[101]; memset(vis, false, sizeof(vis));
    int blocks[101][101][2], blocks_size[101][2], blocks_count = -1;
    for (int i = 1; i <= n; i++){
        for (int j = i + 1; j <= n; j++){  //???????????
            if (link[i][j] && !vis[i]){
               int queue[2][101], queue_size[2], head[2];
               queue_size[0] = queue_size[1] = 0;
               head[0] = head[1] = 0;
               queue[1][0] = i; vis[i] = true;
               queue[0][0] = j; vis[j] = true;
               while (head[0] <= queue_size[0] || head[1] <= queue_size[1]){
                     if (head[0] <= queue_size[0]){
                        int point = queue[0][head[0]];
                        for (int k = 1; k <= n; k++){
                            if (link[point][k] && !vis[k]){
                               queue[1][++queue_size[1]] = k;
                               vis[k] = true;
                            }
                        }
                        head[0]++;
                     }

                     if (head[1] <= queue_size[1]){
                        int point = queue[1][head[1]];
                        for (int k = 1; k <= n; k++){
                            if (link[point][k] && !vis[k]){
                               queue[0][++queue_size[0]] = k;
                               vis[k] = true;
                            }
                        }
                        head[1]++;
                     }
               }

               for (int k = 0; k <= queue_size[0]; k++){
                   for (int l = k + 1; l <= queue_size[0]; l++){
                       if (link[queue[0][k]][queue[0][l]]){
                          printf("No solution\n");
                          getchar(); getchar(); getchar(); getchar();
                          return 0;
                       }
                   }
               }

               for (int k = 0; k <= queue_size[1]; k++){
                   for (int l = k + 1; l <= queue_size[1]; l++){
                       if (link[queue[1][k]][queue[1][l]]){
                          printf("No solution\n");
                          getchar(); getchar(); getchar(); getchar();
                          return 0;
                       }
                   }
               }

               blocks_count++;
               blocks_size[blocks_count][0] = queue_size[0];
               blocks_size[blocks_count][1] = queue_size[1];
               for (int k = 0; k <= queue_size[0]; k++) blocks[blocks_count][k][0] = queue[0][k];
               for (int k = 0; k <= queue_size[1]; k++) blocks[blocks_count][k][1] = queue[1][k];
            }
        }
    }

    for (int i = 1; i <= n; i++){
        if (!vis[i]){
           blocks_count++;
           blocks_size[blocks_count][0] = 0;
           blocks_size[blocks_count][1] = -1;
           blocks[blocks_count][0][0] = i;
           vis[i] = true;
        }
    }

    bool status[101], status_x[101];
    bool way[101][101], way_x[101][101];
    memset(way, false, sizeof(way));
    memset(status, false, sizeof(status));
    status[0] = true;
    for (int i = 0; i <= blocks_count; i++){
        memset(way_x, false, sizeof(way_x));
        memset(status_x, false, sizeof(status_x));
        for (int j = 0; j <= n / 2; j++){
            if (status[j]){
               if (!status_x[j + blocks_size[i][0] + 1] && j + blocks_size[i][0] + 1 <= n / 2){
                     status_x[j + blocks_size[i][0] + 1] = true;
                  memcpy(way_x[j + blocks_size[i][0] + 1], way[j], sizeof(way_x[j + blocks_size[i][0] + 1]));
                     for (int k = 0; k <= blocks_size[i][0]; k++){
                            way_x[j + blocks_size[i][0] + 1][blocks[i][k][0]] = true;
                  }
               }

               if (!status_x[j + blocks_size[i][1] + 1] && j + blocks_size[i][1] + 1 <= n / 2){
                     status_x[j + blocks_size[i][1] + 1] = true;
                  memcpy(way_x[j + blocks_size[i][1] + 1], way[j], sizeof(way_x[j + blocks_size[i][1] + 1]));
                     for (int k = 0; k <= blocks_size[k][1]; k++){
                            way_x[j + blocks_size[i][1] + 1][blocks[i][k][1]] = true;
                     }
               }
            }
        }
        memcpy(way, way_x, sizeof(way_x));
        memcpy(status, status_x, sizeof(status_x));
    }

    for (int i = n / 2; i >= 1; i--){
        if (status[i]){
           printf("%d", i);
           for (int j = 1; j <= n; j++){
                  if (way[i][j]) printf(" %d", j);
           }

           printf("\n%d", n - i);
           for (int j = 1; j <= n; j++){
                  if (!way[i][j]) printf(" %d", j);
           }
        }

        break;
    }

    getchar(); getchar(); getchar(); getchar();
}

i got wrong ans #25 .Please send me tests.
thanks.
my ym : linhduong55@yahoo.com

  type
        anstype  = array[0..100] of longint;

  var
        l    : longint;
        n    : longint;
        f    : array[1..100, -100..200] of boolean;
        ans  : array[1..2] of anstype;
        go   : array[1..100, 0..100] of longint;
        save : array[1..100, 0..100] of longint;
        g    : array[1..100, 0..100] of longint;
        done : array[1..100] of boolean;
        list : array[1..100, 1..2] of anstype;
        que  : array[1..100] of longint;
        edge : array[1..100, 1..100] of boolean;

  procedure init;
    var
        have       : boolean;
        i, j, a, k : longint;
        hash        : array[0..100] of boolean;
    begin
          readln(n);
          fillchar(g, sizeof(g), 0);
          for i := 1 to n do
            begin
              fillchar(hash, sizeof(hash), false);
              repeat
                read(a);
                hash[a] := true;
              until a = 0;
              for j := 1 to n do
                if (not hash[j]) and (i <> j)
                  then begin
                    have := false;
                    for k := 1 to g[i, 0] do
                      if g[i, k] = j
                        then begin
                          have := true;
                          break;
                        end;
                    if not have
                      then begin
                        inc(g[i, 0]);
                        g[i, g[i, 0]] := j;
                      end;
                    have := false;
                    for k := 1 to g[j, 0] do
                      if g[j, k] = i
                        then begin
                          have := true;
                          break;
                        end;
                    if not have
                      then begin
                        inc(g[j, 0]);
                        g[j, g[j, 0]] := i;
                      end;
                  end;
            end;
          fillchar(edge, sizeof(edge), false);
          for i := 1 to n do
            for j := 1 to g[i, 0] do
              edge[i, g[i, j]] := true;
    end;

  procedure get_tree(start : longint);
    var
        now           : array[1..100] of longint;
        get_in        : array[1..100] of boolean;
        level         : longint;
        i, h, t, k, j : longint;
    begin
          que[1] := start;
          h := 1;
          t := 1;
          now[1] := 1;
          fillchar(get_in, sizeof(get_in), false);
          get_in[start] := true;
          while true do
            begin
              k := que[h];
              level := now[h];
              done[k] := true;
              for i := 1 to g[k, 0] do
                begin
                  if get_in[g[k, i]]
                    then continue;
                  inc(t);
                  que[t] := g[k, i];
                  get_in[g[k, i]] := true;
                  now[t] := level + 1;
                end;
              inc(list[l, level mod 2 + 1, 0]);
              k := list[l, level mod 2 + 1, 0];
              list[l, level mod 2 + 1, k] := que[h];
              inc(h);
              if h > t then break;
            end;
          for k := 1 to 2 do
            for i := 1 to list[l, k, 0] do
              for j := i + 1 to list[l, k, 0] do
                if edge[list[l, k, i], list[l, k, j]]
                  then begin
                    writeln('No solution');
                    halt;
                  end;
    end;

  procedure make;
    var
        i : longint;
    begin
          l := 0;
          fillchar(done, sizeof(done), false);
          for i := 1 to n do
            if not done[i]
              then begin
                inc(l);
                get_tree(i);
              end;
    end;

  procedure dp;
    var
        tmp     : anstype;
        i, t, j : longint;
    begin
          fillchar(f, sizeof(f), false);
          f[1, abs(list[1, 1, 0] - list[1, 2, 0])] := true;
          for i := 2 to l do
            begin
              t := abs(list[i, 1, 0] - list[i, 2, 0]);
              for j := 0 to 100 do
                begin
                  f[i, j] := f[i - 1, j - t] or f[i - 1, j + t];
                  if not f[i, j]
                    then continue;
                  if (f[i - 1, j - t])
                    then begin
                      save[i, j] := j - t;
                      go[i, j] := 2
                    end
                    else begin
                      save[i, j] := j + t;
                      go[i, j] := 1;
                    end
                end;
            end;
          for i := 1 to l do
            if list[i, 1, 0] < list[i, 2, 0]
              then begin
                tmp := list[i, 1];
                list[i, 1] := list[i, 2];
                list[i, 2] := tmp;
              end;
    end;

  procedure add(a, b, c : longint);
    var
        tmp : anstype;
        i   : longint;
    begin
          for i := 1 to list[b, c, 0] do
            ans[a, ans[a, 0] + i] := list[b, c, i];
          inc(ans[a, 0], list[b, c, 0]);
          if ans[1, 0] < ans[2, 0]
            then begin
              tmp := ans[1];
              ans[1] := ans[2];
              ans[2] := tmp;
            end;
    end;

  procedure out(x, y : longint);
    var
        tmp  : anstype;
        i, t : longint;
    begin
          if x = 1
            then begin
              add(1, x, 1);
              add(2, x, 2);
              exit;
            end;
          out(x - 1, save[x, y]);
          if go[x, y] = 1
            then begin
              add(1, x, 2);
              add(2, x, 1);
            end
            else begin
              add(1, x, 1);
              add(2, x, 2);
            end;
    end;

  procedure print;
    var
        i, j, t : longint;
    begin
          fillchar(ans, sizeof(ans), 0);
          for i := 0 to 100 do
            if f[l, i]
              then break;
          out(l, i);
          for t := 1 to 2 do
            begin
              write(ans[t, 0]);
              for i := 1 to ans[t, 0] do
                write(' ', ans[t, i]);
              writeln;
            end;
    end;

  begin
        init;
        make;
        dp;
        print;
  end.

Edited by author 15.08.2005 10:50

I can't get accepted. I found tests from ACM contest for this problem
and my program works good on them. I think 56 tests is enough to
confirm corectness of my solution, but I still get Wrong Answer!
Can anyone help me?

const maxn=200;
var g:array[1..maxn,1..maxn] of byte;
    d,t,l:array[0..maxn] of integer;
    f,f1:array[0..maxn] of boolean;
    a:array[1..maxn,1..2] of integer;
    i,j,k,n,now,gr:integer;
procedure sub(p,gr:integer);
  var i:integer;
  begin
    for i:=1 to n do begin
      if (g[p,i]=1)and(t[i]<>gr)and(t[i]<>0) then begin
        writeln('No solution');
        halt;
      end;
      if (g[p,i]=1)and f[i] then begin
        t[i]:=gr; f[i]:=false;
        if odd(gr) then sub(i,gr+1)
          else sub(i,gr-1);
      end;
    end;
  end;
begin
  assign(input,'teams.in');
  reset(input);
  assign(output,'teams.out');
  rewrite(output);
  readln(n);
  for i:=1 to n do
    for j:=1 to n do
      if i<>j then g[i,j]:=1;
  fillchar(d,sizeof(d),0);
  for i:=1 to n do begin
    read(j);
    while j<>0 do begin
      g[i,j]:=0;
      read(j);
    end;
  end;
  for i:=1 to n do
    for j:=1 to n do if g[i,j]=1 then g[j,i]:=1;
  for i:=1 to n do
    for j:=1 to n do
      if g[i,j]=1 then inc(d[i]);
  fillchar(f,sizeof(f),true);
  now:=1;
  repeat
    i:=1;
    while i<=n do
      if f[i] then break
        else inc(i);
    if i>n then break;
    t[i]:=now;
    f[i]:=false;
    sub(i,now+1);
    now:=now+2;
  until false;
  fillchar(a,sizeof(a),0);
  gr:=now-2;
  for i:=1 to n do
    if odd(t[i]) then
      inc(a[t[i],1])
    else inc(a[t[i]-1,2]);
  fillchar(f,sizeof(f),false);
  f[0]:=true;
  for i:=1 to gr do
    if odd(i) then begin
      f1:=f;
      fillchar(f,sizeof(f),false);
      for j:=n downto 0 do
        if f1[j] then begin
          if (not f[j+a[i,1]])and(a[i,1]>0) then begin
            f[j+a[i,1]]:=true;
            l[j+a[i,1]]:=i;
          end;
          if (not f[j+a[i,2]])and(a[i,2]>0) then begin
            f[j+a[i,2]]:=true;
            l[j+a[i,2]]:=-i;
          end;
        end;
    end;
  i:=(n+1) div 2;
  while l[i]=0 do dec(i);
  write(i);
  now:=i;
  fillchar(f,sizeof(f),true);
  while (l[i]<>0)and(i>0) do begin
    for j:=1 to n do
      if ((l[i]>0)and(t[j]=l[i]))or((l[i]<0)and(t[j]=abs(l[i])+1))
then begin
        write(' ',j);
        f[j]:=false;
      end;
    if l[i]>0 then i:=i-a[l[i],1]
      else i:=i-a[-l[i],2];
  end;
  writeln;
  write(n-now);
  for i:=1 to n do
    if f[i] then write(' ',i);
  writeln;
  close(input);
  close(output);
end.