6 6
1 2 1
2 3 2
3 1 3
4 5 1
5 6 2
6 4 3

Proof that a system of linear equation has a unique solution if the corresponding cycle is of an odd length.

system of LE
x1 + x2 = y1
x2 + x3 = y2
...
x_{n-1} + x_n = y_{n - 1}
x1 + x_n = y_n

Is written in matrix form (i'll skip the last column)

1 1 0     ... 0
0 1 1 0   ... 0
0 0 1 1 0 ... 0
      .
      .
      .
0     ... 0 1 1
1 0    ...  0 1

It's determinant can be computed as follows
det(
  1 1   .. 0
  0 1 1 .. 0
      .
  0 0 .0 1 1
  0 ...  0 1
)
 +-(!!!)
det (
  1 0   .. 0
  1 1 0 .. 0
      .
      .   1 0
  0 ... 0 1 1
)


I took entries (1, 1) and (n, 1) to form these two. The sign (+-) depends on dimention and is equal to (-1)^(n + 1).

The two determinans are equal as the first one is equal to
1 1
0 1
which can be seen if you keep choosing entry (n, n) to form determinant

and the second one is equal to
1 0
1 1
keep choosing (1, 1)

So, the determinant of initial matrix is equal to 2 if the number of variables odd which means the system has a unique solution. The system can't have one in the case of zero determinant which is when the number of variables is even.

Edited by author 01.09.2018 17:02

You have to keep only the lineary independet ones, I think.
What I did is I kept only the first 5 ones, which contain certain number (so the matrix in the end was at most 5000 rows long, containing at least 5 rows, containing a digit at each position) and it passed system test (otherwise the solution was right, but too slow)

5  6
5 4 9
4 2 6
5 1 6
1 2 3
5 3 8
3 2 5

Edited by author 21.10.2007 22:20

Edited by author 21.10.2007 22:20

0.031 :)

I need a hint ( or test case ) aswell. I was looking for an TLE error but instead I got WA.

Try this test:
4 4
1 2 2
1 3 2
3 4 2
1 4 2

Answer:
1.00
1.00
1.00
1.00

Edited by author 10.04.2010 16:20

Edited by author 10.04.2010 16:20

DFS on graph (0.062)
http://acm.timus.ru/rating.aspx?space=1&num=1580
Good luck...

My AC program, output IMPOSSIBLE.

M<N - It's IMPOSSIBLE!