Про частичное решение на олимпиаде
Вы не подписаны на эту тему. Подписаться
|
На городской олимпиаде в задаче D сколько бы баллов набрало решение, обрабатывающее только добавление пилонов?
Редактировано 2011-12-17 23:51:06. |
|
[не правильно понял, протупил, ок]
|
|
Ну если бы моя программа игнорировала все удаления пилонов и учитывала только их добавление, тогда на многих тестах она бы выдала правильный ответ?
|
|
|
Сомневаюсь. Если даже в первом тесте было удаление пилонов, то в следующих наверняка встречалось бы оно и не раз. Да и если программа работает на добавление пилонов, в чём собственно говоря проблема дописать пару строк на удаление и изменение ситуации?
|
|
Может быть были тесты (например некий max-тест), где ответ бы неким случайным образом совпал с правильным даже если игнорить удаление, или были специально сделаны тесты для решения с одним добавлением (как частичного решения). На олимпиаде я стал писать это так: заводил две кучи, одна для левой половины пилонов, другая для правой (в левой мы знали где пилон с максимальной координатой, в правой с минимальной). Когда состояние менялось, надо было просто добавить или удалить пилон из кучи, а затем уравнять их количество в кучах, перенеся один слева направо или справа налево. После того как я написал добавление пилона, стал думать над удалением и понял что за бред написал. Тут парой строк кода было не обойтись. Тогда я не подумал отправить написанное. Мне просто интересно, дало ли мне бы такое решение хоть какие-нибудь 10-15 баллов
|
|
Насколько я помню, мы не сделали специфичных тестов на только добавление, потому не думаю, что это решение набрало бы много. Вопрос в другом: что мешает написать кучу с возможностью удаления и перебалансировать её так же, как ты и написал. В результате получим как раз полное решение и 100 баллов :-)
|
|
Чтобы написать удаление, нужно знать местоположение каждого элемента в куче, а значит пришлось бы перелопатить весь код дописывая обработку местоположений элементов, что я и попытался сделать, да вот не успел. Выходит, всё-таки не было смысла посылать то незавершённое решение, значит я буду спокоен :)
|
|
trueNikita | 2011-12-21 21:45:03 А что мешало вместо двух куч использовать два multiset'a? Более того, первое решение жюри было именно таким :) |
|
Пфф, и вправду. Так было бы куда проще
|