ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

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

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.