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

Обсуждение задачи 1514. Национальный парк

WA16 What is special in this test? i can't find the bug in my prog
Послано Alias (Alexander Prudaev) 17 фев 2007 20:52
please help me!
Послано Alias (Alexander Prudaev) 17 фев 2007 21:49
i have write brute-force procedure solve()
and test my program on random tests.
my program always gives correct answer.
I have not so twisted imagination, which
have autors this tests, so i can't think up such test.

My congratulations to  autors:
your imagination is more twisted than rand() :)
Re: please help me!
Послано svr 17 фев 2007 22:04
Your should be greatful to authors who
keep in secret speeding up methods and
give you(and us) chance to create them.
Now I can't see how avoid O(n^3)
For example may be 16000 smal identical triangles and so on.
I think 15-test is last with small N.
So not-top-coders may move to solution by
exchanging with ideas on forum.

Edited by author 17.02.2007 22:04
to SVR
Послано Alias (Alexander Prudaev) 17 фев 2007 22:09
there is NlogN solution
Re: to SVR
Послано svr 17 фев 2007 22:17
Why in this case you use use brute force and random?
Re: to SVR
Послано Alias (Alexander Prudaev) 17 фев 2007 23:11
because my NlogN solution gives wrong answer on 16th test
and i tryed to find such test, that BruteForce answer differs
with MyNlogNSolution answer
Re: to SVR
Послано svr 18 фев 2007 00:26
Try to prove your algorithm.
If proof right and authors is'n mistaken you
will pass test 16 without difficulties.