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

Discussion of Problem 1512. Zinium

I have one question!!
Posted by PSV 2 Apr 2007 01:15
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...
Re: I have one question!!
Posted by Ilya Grebnov[Ivanovo SPU] 3 Apr 2007 00:33
Random solution combined with a local collision minimization is acceptable.

Re: I have one question!!
Posted by PSV 3 Apr 2007 01:39
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.
Re: I have one question!!
Posted by Ilya Grebnov[Ivanovo SPU] 4 Apr 2007 23:22
Yes, the solution has the O(n) complexity. This solution is the the first approach with linear complexity for this problem.