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 1092. Transversal

You can Feel the Power of 'Random'.
Posted by 198808xc 20 Mar 2005 11:45
I used Greedy(Hungary Algorithm) and Randomization in my Program and Got ACed.

First Time, ACed at 1.000s;
While Second, Failed because TLE.
Third Time, ACed again at 0.015s!!!
Forth Time to Ninth Time, Either OLE or TLE...
Tenth Time, ACed at 0.564s......

What a 'Strange' Program I've Created!
Don't use Randomization, just in increasing order!
Posted by Fu Dong 10 May 2005 14:46
After you do max_match, when you change the un-matched rows' state, there maybe many orders, but some of them are wrong, and will get OLE, so you can use randomization (I think this method is very good! ^_^). But in this problem, you just change the un-matched rows' state in increasing order, then you will get AC. (At the first time, I used decreasing order, but I got OLE :( ,then I used increasing order and got AC with 0.015s :) ).

I'm sorry my English is so poor... :(

Edited by author 10.05.2005 14:46