Hello all who reading this blog entry. Let me present my solution of task "1394 Ships. Version 2" on Ural Online Judge. When I started to solve this task I didn't read anything about the problem and to the moment I don't know if this approach novel or not.

Let me describe the task first. This problem is a variation of multiknapsack problem. There are some ships with size 1xN (where N is between 1 and 100, max 99 ships) and rows for this ships: each row is a line 1xM (max 9 rows). It is needed to place all the ships inside the rows, ships can touch each other by side but can not intersect. (original description is https://acm.timus.ru/problem.aspx?space=1&num=1394)

So le me start with my algorithm. Actually I combined two different algorithms.

First algorithm is a simple brute force consists of a recursion of two functions.

1. Sort all ships in descending order and sort all rows in ascending order.
2. Invoke recursive function rec(index of row) where index of row is a index of row to fill with ships (all the rows with less index are already filled).

Description of function rec(index of row)

1. Calculate the count of different solution for a row with index of row using simple knapsack DP. Let r[i] be the count of different combination for length i.
2. if index of row > index of last row — we found the solution and output it.
3. Invoke recursive function recKnapsack(rowLength)

Description of function recKnapsack(length)

1. if length > 0 do step 5. else do step 7.
2. Sort all available ships in order of decreasing value r[length — ships.length]
3. For all available ships in order from step 2.3. try to invoke recKnapsack(length — current ship length).
4. Invoke recursive function rec(index of row + 1)

And that is all with first algorithm. Use this I was able to pass test from 1 to 47. And on test 48 I got TLE. Then I've found the test which fail above algorithm:

Ships: 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 86, 86, 86, 86, 86, 86, 86, 86, 86, 86, 83, 83, 83, 83, 73, 73, 73, 73, 73, 72, 72, 72, 62, 62, 57, 57, 57, 57, 57, 57, 57, 53, 53, 50, 50, 50, 50, 46, 46, 46, 42, 42, 42, 42, 42, 42, 42, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 24, 24, 24, 22, 22, 22, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 14, 14, 14, 14, 10, 10, 10, 10, 10, 10, 10, 10

Rows: 159, 516, 57, 724, 146, 1014, 688, 507, 1039

I designed another approach described further:

1. Generate solutions for all the rows independently using brute force.
2. For each row: sort the solutions in order of decreasing ships count
3. Invoke recursive function rec(index of row)

Here is the description of the rec(index of row) function:

1. If index of the row = index of last row — 2 then use simple knapsack DP
2. For each solution of the row with index of row:
3. If all the ships of the solution are available
4. Mark all the used ships as unavailable
5. if rec(index of row) is true : output the solution, return true;

Also I stored all failed solution in cache: if some solution (available ships and index of row) already was processed — don't process it.

I have to note some another details: on step 1 for each row I try to generate not similar solutions. For example if I have 100 solution for a row like: 99 72 ..., 99 70 ..., ... 99 68 ... I just stop the generation and go further to next ship: 91 86 ..., 91 83 ...

In the rec(index of row) I put another parameter: count of suitable solutions: between steps 5. and 6. I increase the counter. If value of the counter more then some threshold — break from the for and return false;

These two approaches are combined in simple way: if algorithm 1 works more than 100ms then halt it and try algorithm 2. If algorithm 2 works more than 400ms then halt it and try to reorder row and run it again.

That is all. Accepted in 0.9 with Java.

P.S. If you want I can share link to github with the solution.