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

## Обсуждение задачи 1394. Корабли. Версия 2

Problem 1115 "Ships" now has 2 versions.
Послано Vladimir Yakovlev (USU) 23 ноя 2005 21:43
Problem 1394 "Ships. Version 2" is the same problem as 1115 but has full testset. Problem 1115 has only first 10 tests.

All latest submissions on 1115 were moved to new problem. You can resubmit you solutions to 1115 also if you want.

Problem 1115 was rejudged with 10 tests. But some submissions got WA.
Re: Problem 1115 "Ships" now has 2 versions.
Послано Sandro (USU) 24 ноя 2005 16:30
So change the text 1115, because two problems now have the same limits for N, M and interval length. Or just delete the problem 1115.
I think the time limit is too strict.
Послано Jurassic Park 24 ноя 2005 19:34
Re: I think the time limit is too strict.
Послано Vladimir Yakovlev (USU) 26 ноя 2005 23:32
If you can write a solution that works within 5-10 seconds for any test I make, I wolud increase TL.
You must come up with a nice algorithm.
Послано Safe Bird 28 ноя 2005 11:35
Wouldn't you like to share with us?
up
Послано Safe Bird 3 дек 2005 12:45
Re: You must come up with a nice algorithm.
Послано Vladimir Yakovlev (USU) 6 дек 2005 02:51
I use two algorithms inside one program:
First I try to arrange ships using heuristics with randomization.
If it fails for many times (say, 1000 times) I use bruteforce with optimizations (just like many people)

I found a big numbers of different bruteforces and heuristics for this problem. I have tests for all that methods. You need just one good combination! My program works well on all tests, I've already checked more than 30 billions random tests.

A little hint: my bruteforce gets TLE 22, heuristics gets TLE 17.
Good luck!
Oh, my
Послано Safe Bird 26 янв 2006 08:35
the idea is great! I have thought for too many strange ideas like netflow.....but not this one!

i gonna try to solve it right now.
Re: You must come up with a nice algorithm.
Послано molphys fti UFU (Ekaterinburg) 17 июн 2011 18:12
Where is your good solution at now? The present-day test is too tough for your algorithm?
If this the edge, it may be worth keeping the time limit so that one top solution has always been AC.
Re: I think the time limit is too strict.
Послано Manciu Ion 17 ноя 2020 12:29
It will be reasonable to increase the TL to 3s.
Re: I think the time limit is too strict.
Послано Anatoliy V Tomilov 20 ноя 2020 23:23
It is required to inspect all the current solutions thoroughly to decide whether all of them have some "tweaking" for specific tests or not. If any of them is universal (i.e. actually not depends on any seed or magic number), then time limit can be even capped on that. If not, then it is reasonable to increase TL somehow.
Re: I think the time limit is too strict.
Послано Manciu Ion 21 ноя 2020 11:49
I can bet that some of accepted solutions will not pass for some permutation of actual tests and that is not ok when them will require to be adjusted in order to pass!

Edited by author 21.11.2020 11:53
Re: I think the time limit is too strict.
Послано Anatoliy V Tomilov 22 ноя 2020 03:40
I sort input before use. What do you mean?

Edited by author 16.12.2020 00:35