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

How to solve this problem? Is it a NP problem?
Posted by Saturn 5 Jul 2004 15:22
How to solve this problem? Is it a NP problem?
Thanks
Re: How to solve this problem? Is it a NP problem?
Posted by Saturn 5 Jul 2004 23:54
I used full search and got TLE#5
Read the problem carefully.You must be missing some important describe.By the way,DP+DFS will work...good luck!
Posted by Yu YuanMing 7 Jul 2004 09:22
I think the problem is NP (+)
Posted by Dmitry 'Diman_YES' Kovalioff 7 Jul 2004 17:31
It is one of knapsack-problem's variations, which is obviously NP. I used brute force with some optimizations and got AC within very short time. Of course, DP will work because of weak restrictions, but brute force is a classical way to solve this problem.

Edited by author 07.07.2004 17:33
Re: Read the problem carefully.You must be missing some important describe.By the way,DP+DFS will work...good luck!
Posted by Saturn 8 Jul 2004 00:08
Can you give me more details?