The graph is not oriented graph. It makes solution easier.

Edited by author 19.08.2023 12:29

9
3 9 8 2
3 7 3 1
2 4 2
2 5 3
3 7 6 4
3 9 8 5
2 5 2
2 6 1
2 6 1
Please try this data,please
My progame can't pass this,but I got AC

my first attempt based on partitions
//        1 2
//          3
//          7
//        6 4
//          8
//          5
gave WA1, is there any kind of tricks in computing smallest group? or Don`t they use sample as a test 1?

The next 2^N worst-case algo gets AC.

searchSolution(i) {
   if (i==N+1) {
       throw new FoundException();
   }
   group[i] = 1;
   if (checkThisAndAdvsHasNotMoreThan1Adv(i)) {
      searchSolution(i+1);
   }
   group[i] = 2;
   if (checkThisAndAdvsHasNotMoreThan1Adv(i)) {
       searchSolution(i+1);
   }
   group[i] = 0;
}

............

try {
   searchSolution(1);
} catch (FoundException e) {
   outputResult();
}
output("NO SOLUTION");


Judges, please do something with it :)
This is cool graph problem, i think in order to get AC one should write O(N) solution :)
But this obvious brute-force gets AC
SAD :(

My AC solution gets wrong answer on this test:

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

I think it should be added to testset.

Only DFS? Or exist fast solution? Please help me

here is code, it use O(nlogn)
if problem has O(n) algo,please write your code.
sorry for my bad english.


#include <iostream>
#include <set>
#include <vector>

using namespace std;

const int MAXN= 7163+ 5;

bool group[MAXN];
int n, Size[2];
int d[MAXN];
vector <int> adj[MAXN];

struct node{
    int num;

    node (int _num= -1) : num(_num) {}

    inline bool operator < (const node &second) const{
        if (d[second.num]!= d[num])
            return d[num] > d[second.num];
        return num > second.num;
    }
};
set <node> sit;
/***********************************************************/
inline void partition (){
    while (true){
        node v= *sit.begin();
        if (d[v.num] < 2)
            return;
        for (int i= 0;i< (int)adj[v.num].size();i ++){
            int tmp= adj[v.num][i];
            node k(tmp);
            if (group[tmp]== group[v.num]){
                sit.erase (tmp);
                d[tmp] --;
                sit.insert (tmp);
            }
            else{
                sit.erase (tmp);
                d[tmp] ++;
                sit.insert (tmp);
            }
        }
        Size[group[v.num]] --;
        group[v.num]= !group[v.num];
        Size[group[v.num]] ++;
        sit.erase (v);
        d[v.num]= adj[v.num].size()- d[v.num];
        sit.insert (v);
    }
}
/*********************************************/
int main (){
    scanf ("%d", &n);
    for (int i= 1;i<= n;i ++){
        scanf ("%d", &d[i]);
        for (int j= 1;j<= d[i];j ++){
            int tmp;
            scanf ("%d", &tmp);
            adj[i].push_back (tmp);
        }
        group[i]= false;
        node tmp (i);
        sit.insert (tmp);
        Size[0] ++;
    }
    partition ();
    int cur= 0;
    if (Size[0] < Size[1])
        cur= 0;
    else if (Size[1] < Size[0])
        cur= 1;
    else
        cur= group[1];
    printf ("%d\n", min (Size[0], Size[1]));
    for (int i= 1;i<= n;i ++)
        if (group[i]== cur)
            printf ("%d ", i);

    return 0;
}

8
3 2 3 7
3 1 3 7
3 1 2 7
1 6
0
2 4 8
3 1 2 3
1 6

why i can't make group like this:
1: 1 2 6
2: 3 4 5 7 8
???

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n,i,j,p,x;
vector<int> a[10000];
vector<int> b,c;
int d[10000];

void dfs(int i,int k)
{
    d[i] = 1;
    int j;
    for (j = 0;j<a[i].size();j++)
        if (d[a[i][j]] == 0)
    {
        if (k == 1)
        {
            c.push_back(a[i][j]);
            dfs(a[i][j],0);
        }
        else
        {
            b.push_back(a[i][j]);
            dfs(a[i][j],1);
        }
    }
}

int main()
{
    cin >> n;
    for (i = 1;i<=n;i++)
    {
        cin >> p;
        for (j = 1;j<=p;j++)
        {
            cin >> x;
            a[i].push_back(x);
        }
    }
    for (i = 1;i<=n;i++)
        if (d[i] == 0)
        {
            b.push_back(i);
            dfs(i,1);
        }
    if (b.size()<=c.size())
    {
        cout << b.size() << endl;
        if (b.size()>0)
        for (i = 0;i<b.size();i++)
            cout << b[i] << " ";
    }
    else
    {
        cout << c.size() << endl;
        if (c.size()>0)
        for (i = 0;i<c.size();i++)
            cout << c[i] << " ";
    }
    return 0;
}

As description of question mentioned, we need to output the smaller group of children, which fits the restrictions. However, for sample output, we can also put 5 [without any adversary] into abitrary group, so, the smallest group should not be 1,2,5,6, that's 1,2,6. Am I right? and my program could produce another seemingly meanful answer: 3,6,7[1,2,4,8,5 another group]. yeah, a little bit lost! could someone help me out?
Thank a lot in advance! ^_^

What I must write for this test?
6
5 2 3 4 5 6
5 1 3 4 5 6
5 1 2 4 5 6
5 1 2 3 5 6
5 1 2 3 4 6
5 1 2 3 4 5
No solution?

please give me some useful tests.

In  subject statement,  "5" have not a adversary, but the "5" is in output result...
  if i output:
   3
   1 2 6
   the result is right?
  if wrong , why ?

why I got wa in test 3?
var f,num:array[1..10000]of longint;
    a:array[1..10000,1..3]of longint;
    w,i,n,j:longint;
procedure print(a:longint);
  var i,w:longint;
      b:array[1..10000]of longint;
 begin
  w:=0;
  fillchar(b,sizeof(b),0);
  for i:=1 to n do
   if f[i]=a then
    begin
     inc(w);
     b[w]:=i;
    end;
  writeln(w);
  if w<>0 then
  begin
  for i:=1 to w-1 do
   write(b[i],' ');
  writeln(b[w]);
  end;
 end;
begin
 assign(input,'a.in');
 reset(input);
 assign(output,'a.out');
 rewrite(output);
 readln(n);
 for i:=1 to n do
  begin
   read(num[i]);
   for j:=1 to num[i] do
    read(a[i,j]);
  end;
 fillchar(f,sizeof(f),0);
 for i:=1 to n do
  if f[i]=0 then
  begin
   w:=0;
   for j:=1 to num[i] do
    if f[a[i,j]]=0 then
     inc(w);
   if w>1 then f[i]:=1;
  end;
 for i:=1 to n do
  begin
   w:=0;
   for j:=1 to num[i] do
    if f[i]=f[a[i,j]] then
     inc(w);
   if w>1 then
    begin
     writeln('NO SOLUTION');
     close(input);
     close(output);
     halt;
    end;
  end;
 w:=0;
 for i:=1 to n do
  w:=w+f[i];
 if w>n/2 then print(0)
  else if w<n/2 then print(1)
   else
    print(f[1]);
 close(input);
 close(output);
end.

Edited by author 08.12.2008 17:26

#include<iostream.h>
int main()
{
    int n,i,j,k[7165],l,**a,b[7165],kol=0;
    cin>>n;
        a=new int *[n+1];
for(i=1;i<=n;i++)
a[i]=new int[n+1];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=0;
for(i=1;i<=n;i++)
{
    cin>>k[i];
    for(j=0;j<k[i];j++)
    {
        cin>>l;
        a[i][l]=1;
    }
}
for(i=1;i<=n;i++)
{
    if(k[i]>1)
    {
    b[kol++]=i;
        for(j=i+1;j<=n;j++)
            if(a[j][i]==1)
            {
                a[j][i]=0;
                k[j]--;
            }
    }
}

cout<<kol<<endl;
if(kol!=0){
for(i=0;i<kol;i++)
cout<<b[i]<<" ";}
return 0;
}
Thank in advance!!!!!!

My program got WA#2. Who have more tricky tests?
Can the answer of sample test be
3
1 2 6
?

In what case answer is NO SOLUTION ?

Edited by author 08.01.2008 03:20

Edited by author 08.01.2008 03:20

Edited by author 14.08.2007 17:15

If anyone can tell me what then sample stands for? It requires that you should print then smaller group,but in the sample No.5 can be put in the larger group so the anser should be 3?

When n is negative - what to output??
And most intersting what output when N = 0, I think it's one test when NO SOLUTION? because it says that that when two teams are equal by size - output where 1? but there both teams have 0 members - so what out? coz 1 appears nowhere