GILGAMESH's blog

SPOJ MFISH
By GILGAMESH, 11 years ago, In English

Hi. I was working on a DP problem (SPOJ MFISH) but I couldn't understand how the DP works. I've seen a few codes online but couldn't comprehend them either. Could someone explain it to me?

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
11 years ago, hide # |
← Rev. 2  
Vote: I like it +9 Vote: I do not like it

Consider the ships sorted by their anchor index. For every ship you can find a range of indexes where it can start. Just try every possible placement for each ship. The complexity is O(n) because you visit every index at most twice.

P.S.: Thanks to SPOJ, I just found out that there is a programming language called "chicken" :D

→ Reply
  • »
    »
    11 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    OK, got AC. I was using the end location of ships to do my DP, but I think I calculated them wrong. Thanks!

    → Reply