Обсуждение @ 1040. Авиакомпания @ Timus Online Judge

Показать все сообщения Спрятать все сообщения

2Admins (!) tests are incorrect Burunduk1 24 дек 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 Yaroslavtsev Grigory (SpbSPU) 24 дек 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 KingPin 25 дек 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! Burunduk1 28 дек 2005 20:07

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

Fixed (+) Vladimir Yakovlev (USU) 19 фев 2006 23:41

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

Обсуждение задачи 1040. Авиакомпания