Hi all.

I tried to solve this problem many years ago and now returned to it with new knowledge and forces. Then i used pascal and now use Java.

For others, who would try to solve this problem in java i has two hints.

1) Do not use long. Use int instead - or you get TL9. Prime number about 5-6k is ok since 6000^2*50<MAX_INTEGER

2) It is very strange, but creators of tests thought that it is smart enough to give you a 0-vector in 10-th test. It is totally incorrect to do so,... But it is proved that you can throw this vector away.

... Oh - one, more hint - 6000 is small enough to precalculate all reverse values and put them to source - about 40kb.

Good luck. Questions to kluchnikovs on mail server mail.ru

Edited by author 22.07.2008 00:50

You've described very scary way of solving this problem (with 0-vectors and reverse values) =)
All you need to do in this problem is Gaussian elimination. Well-realized by some large modulo, it'll give you right answers with high probability and without any precalculations and 0-vectors checkings (by the way, I don't understand why giving 0-vectors is incorrect if not forbidden by the problem statement?)

Indeed I used Gaussian elimination but with small modulo.
But on first phase of solution, when i need to gather some basis I used "half-Gaussian" which considered permutation matrix -> so when I was looking for first non-zero vector element I got OutOfBoundsException. Reverse precalculation I used to reduce chances of second TLE (Java is times slow than c++/pascal).

By the way. I've did some more thoughts experiments and found that my solution is incorrect, but tests are too weak to find that.

For example for input:

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

My solution responds:
11
1
3
6

It is all because I throw away "bad" vectors on first stage which could get be in use in right solution.

I suspect it can be not only in my solution, so TESTS MUST BE STRENGTHENED!

Edited by author 22.07.2008 14:37

Edited by author 22.07.2008 14:37

Just a moment ago had rewritten my algo - now it doesn't use gaussian elimination at all, only Sherman-Morrison formula. So it need no permutation matrix, etc =)