Discussion @ 1040. Airline Company @ Timus Online Judge

Burunduk1 2Admins (!) tests are incorrect [4] // Problem 1040. Airline Company 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.

Yaroslavtsev Grigory (SpbSPU) Re: 2Admins (!) tests are incorrect [1] // Problem 1040. Airline Company 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!!!

KingPin Re: 2Admins (!) tests are incorrect // Problem 1040. Airline Company 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.

Burunduk1 2Admins: Please, fix this problem! [1] // Problem 1040. Airline Company 28 Dec 2005 20:07

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

Vladimir Yakovlev (USU) Fixed (+) // Problem 1040. Airline Company 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