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

Обсуждение задачи 1115. Корабли

My AC solution
Послано Denis Koshman 30 июл 2008 14:40
I write it here because there exist data sets which will TL it out.

1. Sort rows ascendingly
2. Sort ships descendingly
3. Recurse row-by-row, ship-by-ship
4. Keep ships in the linked list, so you don't have to skip them over and over once they are taken.
5. For each row try only next ships (1+2+3 is same as 1+3+2).
6. Once you reach the last row, don't recurse over it, just pick remaining ships.

This yields AC in 0.015 sec

More optimizations can be done:
1. For each row store index of the first ship which fits in it
(don't forget to skip this ship(s) if it's already taken by the time you reach the row)
2. Store amounts of same-size ships, so that 2+2 is processed only once with 6 ships of size 2, but not C(2,6) times.

Edited by author 30.07.2008 14:41
Try to solve problem 1394 (-)
Послано Sandro (USU) 30 июл 2008 15:50
Re: My AC solution
Послано Pavel Khaustov [Tomsk PU] 1 фев 2009 22:10
Tests in this problem are quite stupid. I've got AC with BF in 0.015! When I stored amounts of same-size ships, I've got TLE #7 many times with all kinds of optimization. Really bad problem, surely must be replaced.