ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1810. Antiequations

any hint ?
Posted by Phạm Quang Vũ - ConanKudo \(^(oo)^)/ 19 Mar 2011 12:28
Could anyone give me the hint to solve this problem ?
Re: any hint ?
Posted by me 27 Mar 2011 22:07
Tools of linear algebra work with any field ( https://secure.wikimedia.org/wikipedia/en/wiki/Field_(mathematics) ), including finite ones like integers mod 3. The problem is effectively Gaussian Elimination.
Re: any hint ?
Posted by sklyack 29 Mar 2011 00:50
But we can't do transformations with antiequations such as with equations. For example, let we have a system:
x1    != 0 (mod 3)
   x2 != 2 (mod 3).
It has a solution (2; 0)
If we add the antiequations, we'll get this one:
x1+x2 != 2 (mod 3), but it's wrong for solution (2; 0) of the system!
Am I right?

Edited by author 29.03.2011 00:53
Re: any hint ?
Posted by me 29 Mar 2011 13:45
Uhm, sorry. I was wrong.
Re: any hint ?
Posted by svr 29 Mar 2011 20:13
I think that your advice is absolutely right!
Let for example det(Aij)<>0.
Then Answer is 2^k,because (A*X)i in {0,1,2}\{bi}
If det(Aij)==0
we can use gauss method to make standard worm of the matrix A.