If anybody know test cases which broke the program, please, share them.

Thanks in advance.

UPD: Below is the algorithm I used to solve this problem, but still got WA#10. Please suggest any test case which can break the algorithm.

Let's suppose we have two arrays (Collections) named e.g. Left and Right.
These collections are empty.
So, we iterate through the numbers from 1 to N.
If any of the collections contain the current number we do nothing.
Otherwise (this is the first occurrence of this number), we put current number into the Left collection and start iterating through his friends:
The logic here is almost the same. We check whether the current friend is present in any of the collections. If he's not, we put the friend into the Right collection.

For example, how this algorithm works on the input data from the problem statement:
1. Current number is 1. Left and Right are empty, so we put 1 into the Left collection and (it's obvious) put all his friends into the Right collection. So the state after the first step is:
Left = {1}; Right = {2, 3}
2. The next number is 2. It's present in the Right, so we skip it.
3. The next number is 3. It's also present in the Right, so we skip it.
4. Current number is 4. Neither Left nor Right contain this number, so we put it into the Left. So the current state became - Left = {1, 4}; Right = {2, 3}.
    4.1. We iterate through the friends list of the 4. There are the only number 3, which is already present in the Right, so we do nothing.
5. The next number is 5. Here we have the same situation as on the previous step, so the current state became:
Left = {1, 4, 5}; Right = {2, 3}
6. Current number is 6. It's not present in Left and Right, so we put it into the Left and the current state became - Left = {1, 4, 5, 6}; Right = {2, 3}. Now we iterate through the list of friends of the 6. There is the only friend 7, which is not present in Left and Right, so we put 7 into the Right collection.
7. Current number is 7, which is already present in the Right, so we do nothing.

And the result is:
Left = {1, 4, 5, 6}; Right = {2, 3, 7}
And the program output is:
4
1, 4, 5, 6

I tried lots of combinations, but they all work correctly.

Edited by author 12.02.2013 00:00

Please? can I see 19 test&

What is test #15??

import java.io.*;
import java.util.*;

class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /**
     * call this method to initialize reader for InputStream
     */
    static void init(InputStream input) {
        reader = new BufferedReader(new InputStreamReader(input));
        tokenizer = new StringTokenizer("");
    }

    /**
     * get next word
     */
    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}

public class _1106 {

    public static void main(String args[]) throws IOException {
        int a;
        Reader.init(System.in);

        int n = Reader.nextInt();
        int graph[][] = new int[n][n];
        ArrayList<ArrayList<Integer>> st = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> grp1 = new ArrayList<Integer>();
        ArrayList<Integer> grp2 = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            ArrayList<Integer> ar = new ArrayList<Integer>();
            do {
                a = Reader.nextInt();
                if (a != 0) {
                    graph[i][a - 1] = 1;
                    ar.add(a - 1);
                }

            }
            while (a != 0);
            st.add(ar);
        }


        if (n != 0) {
            grp1.add(0);
            for (int i = 1; i < n; i++) {
                if (graph[0][i] != 1) {
                    grp1.add(i);
                } else {
                    grp2.add(i);
                }
            }

            for (int i = 1; i < grp1.size(); i++) {
                int x = grp1.get(i);

                if (!st.get(x).isEmpty()) {
                    boolean frFlag = false;
                    Iterator it = st.get(x).iterator();
                    while (it.hasNext()) {
                        if (grp2.contains((Integer) it.next())) {
                            frFlag = true;
                            continue;
                        }
                    }

                    if (!frFlag) {
                        Integer rm = st.get(x).get(0);
                        //grp1.r
                        grp1.remove(rm);
                        grp2.add(rm);
                    }
                }

            }

            System.out.println(grp1.size());
            Iterator it1 = grp1.iterator();
            while (it1.hasNext()) {
                System.out.print(((Integer) it1.next() + 1) + " ");
            }
        } else {
            System.out.println(0);
        }

    }
}

Dear moderator or anybody else,
  Could you please give me testcase 10,I got WA on it,Thanks
so so much

Edited by author 03.11.2007 14:35

Edited by author 03.11.2007 14:35

I think following phrase should be changed:
"Every member of each team must have friends in another team."

Because firstly I thought that every member must have more than 1 friend, since it is "friends".

so something like
"Every member of each team must have at least one friend in another team"
should work

#include <iostream>
using namespace std;

void main()
{
    int flag[100][100];
    int flag1[100], N, j, flag2[100];
    do
    {
        cin >> N;
    }
    while (N < 0 || N > 100);

    for (int i = 1; i <= N; i++)
    {
        do
        {
            cin >> j;
            flag[i][j + 1] = 1;
        }
        while (j != 0);
    }
    flag1[1] = 1;
    for (int i = 1; i <= N; i++)
    {
        for (j = i + 1; j <= N; j++)
        {
            if (flag[i][j] == 1)
            {
                if (flag1[j] != 1 && flag1[j] != 2)
                {
                    flag1[j] = 3 - flag1[i];
                }
            }
        }
    }
    int i = 0;
    for (j = 1; j <= N; j++)
    {
        if (flag1[j] == 1)
        {
            flag2[i] = j;
            i++;
        }
    }
    for (j = 0; j < i; j++)
    {
        cout << flag1[i];
    }
}
I have debugged, but finally I can't find why my code gives wrong answers. Anyone help me, plz.

test case #7 fail. please give it for me!

it's not standard problem

5
3 4 5 0
4 0
1 4 0
1 2 3 0
1 0

It should be noted that problem statement doesn`t say that strings with numbers of friends for each friend is ordered - order of numbers can be random. And if algorithm wrong writed, it will be make problem (I have WA on test 9 many times, before i understood this)

 What is test 7?  here is my code. It is working on the available sample inputs. Please help.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.StringTokenizer;

/**
 *
 * @author proy
 */
class Reader
{
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input)
    {
        reader = new BufferedReader(new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }

    /** get next word */
    static String next() throws IOException
    {
        while ( ! tokenizer.hasMoreTokens() )
        {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(reader.readLine() );
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException
    {
        return Integer.parseInt( next() );
    }

    static double nextDouble() throws IOException
    {
        return Double.parseDouble( next() );
    }
}
public class p1106
{

    public static void main(String args[]) throws IOException
    {
        int a;
        Reader.init(System.in);

        int n = Reader.nextInt();
        int graph[][]= new int[n][n];
        ArrayList<ArrayList<Integer>> st = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> grp1 = new ArrayList<Integer>();
        ArrayList<Integer> grp2 = new ArrayList<Integer>();
        for (int i = 0; i<n;i++)
        {
            ArrayList<Integer> ar = new ArrayList<Integer>();
            do
            {
                a = Reader.nextInt();
                if(a !=0)
                {
                    graph[i][a-1] = 1;
                    ar.add(a-1);
                }

            }
            while(a!=0);
            st.add(ar);
        }



        if(n!=0)
        {
            grp1.add(0);
            for(int i = 1; i<n; i++)
            {
                if(graph[0][i]!= 1 )
                {
                    grp1.add(i);
                }

                else
                {
                    grp2.add(i);
                }
            }

            for(int i = 1; i<grp1.size();i++)
            {
                int x = grp1.get(i);

                if(!st.get(x).isEmpty())
                {
                   boolean frFlag = false;
                   Iterator it = st.get(x).iterator();
                   while(it.hasNext())
                   {
                       if(grp2.contains((Integer)it.next()))
                       {
                           frFlag = true;
                           continue;
                       }
                   }

                   if(!frFlag)
                   {
                       Integer rm = st.get(x).get(0);
                       //grp1.r
                       grp1.remove(rm);
                       grp2.add(rm);
                   }
                }

            }

            System.out.println(grp1.size());
            Iterator it1 = grp1.iterator();
            while(it1.hasNext())
            {
                System.out.print(((Integer)it1.next()+1)+ " ");
            }
        }

        else
        {
            System.out.println(0);
        }

    }

}

First  my code maxn=100 then WA on 8
Second my code maxn=105 then WA on 11
Third  my code maxn=200 then WA on 20
Fourth my code maxn=1000 then ......AC

Does the problem statement meant that each member should have all his friends in the other team OR each member should have at least 1 friend in the other team ?
If the first statement is correct the sample output does not hold.
Please clarify.
Thanks in advance

Edited by author 17.02.2013 01:32

i've got AC but i omitted the case "impossible" (ie print "0"). it has always solution?

Can somebody give test #16?
Getting TLE
Thnx

on test # 1......................
if i get it again, i'm gonna break something....
it runs perfectly on my compiler


#include <stdio.h>
#include <iostream>
#include <vector>
#define PB push_back

using namespace std;

int lev[110];

int main()
{
  int i,j,k,l,n,s,e,v;
  int q[10100];
  vector<int> a[110];
  scanf("%d",&n);
//  cin>>n;
  for (i=1; i<=n; i++)
   {
     while (1)
     {
      scanf("%d",&j);
//  cin>>j;
      if (j!=0) a[i].PB(j); else break;
     }
   }


  for (i=1; i<=n; i++)
  if (!lev[i])
{
  q[0]=i; e=0;
  for (s=0; s<=e; s++)
   {
      for (j=0; j<a[q[s]].size(); j++)
       {
        v=a[q[s]][j];
        lev[v]=lev[q[s]]+1;
        q[e++]=v;
       }
   }
}

  vector<int> ans;
  for (i=1; i<=n; i++)
   if (lev[i]%2) ans.PB(i);

  printf("%d\n",ans.size());
  for (i=0;i<ans.size()-1; i++)
   printf("%d ",ans[i]);
  printf("%d\n",ans[ans.size()-1]);

  return 0;
}

Input:
7
2 3 0
3 1 0
1 2 4 5 0
3 0
3 0
7 0
6 0

Output:
4
1 4 5 6
Is it true?
Please Give me some tests.

Edited by author 03.11.2009 15:17

Edited by author 03.11.2009 15:18

if input is sample input,can output be :
2
3 6?
And why?thx