There is always a solution and it is always only one --

you have n linear independent vectors (that is the determinant of the
linear system is <> 0) and using Cramer's rule you have a single
solution.

Ok
I understand that but i decided that there are bugs in my proof
so ...

3
1 -1
1 2 -1
2 -1

No, consider the following case:
3
1 -1
1 -1
1 2 3 -1
both 3 and 1 2 3 are correct answer but 3 is the shortest.

There is no any test for "No solution" :) I forgot about this case, but had AC :)

this test is incorrect, because 1 combine 3 = 2

>

http://acm.timus.ru/status.aspx?space=1&num=1042&author=13392

Lier!!!

I also tried this method and got TLE. Can you give me your code?  My e-mail is   barssimfi@mail.ru

Could you paste your code here?

What is "bad" in your opinion?

Please anybody help me........
This is my code:
const maxn=2510;


var n,i,j:longint;
sol,a:array[0..maxn,0..maxn] of longint;
lines:array[0..maxn] of longint;


function aor(a:longint):boolean;
begin
  if a<>0 then result:=true else result:=false;
end;

procedure ReadInput;
var i,j:longint;
begin
  readln(n);
  for i:=1 to n do
  begin
    while true do
    begin
      read(j);
      if j=-1 then
      begin
        readln;
        break;
      end;
      a[j,i]:=1;
    end;
    a[i,0]:=1;
  end;
end;

procedure Solve;
var i,j,k,ok:longint;
begin
  for i:=1 to n-1 do
  begin
    ok:=1;
    for j:=1 to n do
      if (not(aor(Lines[j]))) and (aor(A[j][i])) then
      begin
        ok:=0;
        break;
      end;
    Lines[j]:=1;
    for k:=0 to n do
    begin
      if k=i then sol[i,k]:=0 else sol[i,k]:=a[j,k];
    end;
    for k:=1 to n do
    begin
      if (not(aor(Lines[k]))) and (aor(A[k][i])) then
      begin
        a[k,i]:=0;
        for j:=0 to n do
          a[k,j]:=a[k,j] xor sol[i,j];
      end;
    end;
  end;
  sol[n,0]:=a[n,0];

  for i:=n downto 0 do
    for j:=i-1 downto 0 do
      if aor(sol[j,i]) then
      begin
        sol[j,i]:=0;
        sol[j,0]:=sol[j,0] xor sol[i,0];
      end;
  for i:=1 to n do
    if aor(sol[i,0]) then write(i,' ');
end;


begin
  {$IFNDEF ONLINE_JUDGE}
    reset(input,'input.txt');
    rewrite(output,'output.txt');
  {$ENDIF}

  ReadInput;

  Solve;

  {$IFNDEF ONLINE_JUDGE}
    close(output);
  {$ENDIF}
end.

Edited by author 24.06.2007 19:25

4
2 3 4 -1
2 -1
4 -1
1 2 -1

Edited by author 30.01.2005 20:15

Certainly NOT!

You can fire the last technician (-:
The first three working altogether will do his work.

Of course NO solution.

No.1 and No.2 can make combination to No.3. So this input is incorrect.