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 1115. Ships

My AC solution
Posted by Denis Koshman 30 Jul 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 (-)
Posted by Sandro (USU) 30 Jul 2008 15:50
Re: My AC solution
Posted by Pavel Khaustov [Tomsk PU] 1 Feb 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.