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.

- Sort all ships in descending order and sort all rows in ascending order.
- 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)**

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

Description of function **recKnapsack(length)**

- if length > 0 do step 5. else do step 7.
- Sort all available ships in order of decreasing value r[length — ships.length]
- For all available ships in order from step 2.3. try to invoke recKnapsack(length — current ship length).
- 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:

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

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

- If index of the row = index of last row — 2 then use simple knapsack DP
- For each solution of the row with
:**index of row** - If all the ships of the solution are available
- Mark all the used ships as unavailable
- 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.

it would be interesting to see your solution of the TLE 70+ itself