Discussion @ 1040. Airline Company @ Timus Online Judge

2Admins (!) tests are incorrect

Posted by Burunduk1 24 Dec 2005 10:58

Please, explain me why answer is always YES?
It's right only for connected graphs!

For example:
6 6
1 2 2 3 3 1
4 5 5 6 6 4
Answer is NO.

Re: 2Admins (!) tests are incorrect

Posted by Yaroslavtsev Grigory (SpbSPU) 24 Dec 2005 22:35

Oh, what a trick! I was very much confused seeing > 400 people who solved this problem. I'm really annoyed beacuse in this case the problem is O(n + m) using a simple idea gcd(n,n + 1) = 1. But if the graph can be disconnected everything is much worse!!!

Re: 2Admins (!) tests are incorrect

Posted by KingPin 25 Dec 2005 03:43

Graph can be disonnected.
Sample is.
But testset is weak... Why am I not surprised :)
My always "YES" program
got AC.

2Admins: Please, fix this problem!

Posted by Burunduk1 28 Dec 2005 20:07

With such tests the problem is much easier than it is.
Please, change tests or statements!

Fixed (+)

Posted by Vladimir Yakovlev (USU) 19 Feb 2006 23:41

Graph is always connected now.
Statements and tests are updated. So, the solution always exists.

Discussion of Problem 1040. Airline Company