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

Vladimir Yakovlev (USU) Problem 1115 "Ships" now has 2 versions. [12] // Problem 1394. Ships. Version 2 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.
Sandro (USU) Re: Problem 1115 "Ships" now has 2 versions. [11] // Problem 1394. Ships. Version 2 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.
Jurassic Park I think the time limit is too strict. [10] // Problem 1394. Ships. Version 2 24 Nov 2005 19:34
Vladimir Yakovlev (USU) Re: I think the time limit is too strict. [9] // Problem 1394. Ships. Version 2 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.
Safe Bird You must come up with a nice algorithm. [4] // Problem 1394. Ships. Version 2 28 Nov 2005 11:35
Wouldn't you like to share with us?
Safe Bird up // Problem 1394. Ships. Version 2 3 Dec 2005 12:45
Vladimir Yakovlev (USU) Re: You must come up with a nice algorithm. [2] // Problem 1394. Ships. Version 2 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!
Safe Bird Oh, my // Problem 1394. Ships. Version 2 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.
molphys fti UFU (Ekaterinburg) Re: You must come up with a nice algorithm. // Problem 1394. Ships. Version 2 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.
Manciu Ion Re: I think the time limit is too strict. [3] // Problem 1394. Ships. Version 2 17 Nov 2020 12:29
It will be reasonable to increase the TL to 3s.
Anatoliy V Tomilov Re: I think the time limit is too strict. [2] // Problem 1394. Ships. Version 2 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.
Manciu Ion Re: I think the time limit is too strict. [1] // Problem 1394. Ships. Version 2 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
Anatoliy V Tomilov Re: I think the time limit is too strict. // Problem 1394. Ships. Version 2 22 Nov 2020 03:40
I sort input before use. What do you mean?

Edited by author 16.12.2020 00:35