As I understand by random selecting I cannt solve this problem, so I have searching a bit in internet some info to find algo of it - AC. But how could ACM participants check this problem? What another approach? Random --> while (true) subbmiting or what? Please tell me...

Random solution combined with a local collision minimization is acceptable.

Are you sure? It's only for good luck - my random prog quikly works only for n = 200 at max. Maybe one more hint...
I use approach as in standart full search by verticals and O(1) - checking diagonals and horisontals and on every step use random.

Yes, the solution has the O(n) complexity. This solution is the the first approach with linear complexity for this problem.