ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1394. Ships. Version 2

Problem 1115 "Ships" now has 2 versions.
Posted by Vladimir Yakovlev (USU) 23 Nov 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.
Posted by Sandro (USU) 24 Nov 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.
Posted by Jurassic Park 24 Nov 2005 19:34
Re: I think the time limit is too strict.
Posted by Vladimir Yakovlev (USU) 26 Nov 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.
Posted by Safe Bird 28 Nov 2005 11:35
Wouldn't you like to share with us?
up
Posted by Safe Bird 3 Dec 2005 12:45
Re: You must come up with a nice algorithm.
Posted by Vladimir Yakovlev (USU) 6 Dec 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
Posted by Safe Bird 26 Jan 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.
Posted by molphys fti UFU (Ekaterinburg) 17 Jun 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.
Posted by Manciu Ion 17 Nov 2020 12:29
It will be reasonable to increase the TL to 3s.
Re: I think the time limit is too strict.
Posted by Anatoliy V Tomilov 20 Nov 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.
Posted by Manciu Ion 21 Nov 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.
Posted by Anatoliy V Tomilov 22 Nov 2020 03:40
Dura lex, sed lex. There are rules.