Didn't know will it be useful for someone and is it on the right path to solve the problem, but I wish to publish this code for SSP solver. To invent good heuristics for MSSP is utmost harder.

using I = short;

template<typename T = I, typename S = I>
struct DDP // dynamic dynamic programming solver for subset sum problem O(n^3 * 2^sqrt(n)) (n is number of input bits)
{
    T terms[2][10001];
    S sums[2][10001];

    template<typename Term, typename Sum>
    std::pair<Term, Sum> solve(const Term termsBeg, const Term termsEnd, const Sum sumsBeg, const Sum sumsEnd)
    {
        static_assert(std::is_same<typename std::iterator_traits<Term>::value_type, T>::value, "!");
        static_assert(std::is_same<typename std::iterator_traits<Sum>::value_type, S>::value, "!");

        auto sumMax = std::max_element(sumsBeg, sumsEnd);

        auto termsSrc = terms[0];
        auto termsDst = terms[1];

        auto sumsSrc = sums[0];
        auto sumsDst = sums[1];

        *termsSrc = {};
        *sumsSrc = {};

        auto sumsSrcEnd = std::next(sumsSrc);
        for (auto t = termsBeg; t != termsEnd; ++t) {
            auto termsSrcBeg = termsSrc;
            auto termsDstBeg = termsDst;

            auto sumsSrcBeg = sumsSrc;
            auto sumsShiftedBeg = sumsSrc;
            auto sumsDstBeg = sumsDst;

            // merge unique
            assert(std::size_t(std::distance(sumsSrcBeg, sumsSrcEnd)) <= std::extent<std::remove_reference_t<decltype(sums[0])>>::value);
            while (sumsSrcBeg != sumsSrcEnd) {
                if (sumsShiftedBeg == sumsSrcEnd) {
                    break;
                }
                I shiftedSum = *sumsShiftedBeg + *t;
                if (shiftedSum < *sumsSrcBeg) {
                    *sumsDstBeg++ = shiftedSum;
                    ++sumsShiftedBeg;
                    *termsDstBeg++ = *t;
                } else {
                    if (shiftedSum == *sumsSrcBeg) {
                        ++sumsShiftedBeg;
                        assert(*sumsShiftedBeg + *t != *sumsSrcBeg);
                    }
                    *sumsDstBeg++ = *sumsSrcBeg++;
                    *termsDstBeg++ = *termsSrcBeg++;
                }
                assert(std::size_t(std::distance(sumsDst, sumsDstBeg)) <= std::extent<std::remove_reference_t<decltype(sums[0])>>::value);
            }
            if (sumsShiftedBeg == sumsSrcEnd) {
                sumsSrcEnd = std::copy(sumsSrcBeg, sumsSrcEnd, sumsDstBeg);
                termsDstBeg = std::copy_n(termsSrcBeg, std::distance(sumsDstBeg, sumsSrcEnd), termsDstBeg);
            } else {
                assert(sumsSrcBeg == sumsSrcEnd);
                sumsSrcEnd = std::transform(sumsShiftedBeg, sumsSrcEnd, sumsDstBeg, [t] (S s) { return s + *t; });
                termsDstBeg = std::fill_n(termsDstBeg, std::distance(sumsDstBeg, sumsSrcEnd), *t);
            }

            std::swap(termsSrc, termsDst);
            std::swap(sumsSrc, sumsDst);

            for (auto sum = sumsBeg; sum != sumsEnd; ++sum) {
                sumsSrcBeg = std::lower_bound(sumsSrc, sumsSrcEnd, *sum);
                if ((sumsSrcBeg != sumsSrcEnd) && (*sumsSrcBeg == *sum)) {
                    sumsSrcEnd = sumsSrcBeg;
                    assert((*std::next(termsSrc, std::distance(sumsSrc, sumsSrcEnd)) == *t));
                    auto termsDstEnd = termsDst;
                    do {
                        auto term = *std::next(termsSrc, std::distance(sumsSrc, sumsSrcEnd));
                        *termsDstEnd++ = term;
                        sumsSrcEnd = std::lower_bound(sumsSrc, sumsSrcEnd, *sumsSrcEnd - term);
                    } while (sumsSrcEnd != sumsSrc);
                    assert((std::accumulate(termsDst, termsDstEnd, S{}) == *sum));
                    termsDstBeg = termsDst;
                    auto termsSrcEnd = t;
                    assert(*termsSrcEnd == *termsDstBeg);
                    auto termsTail = termsSrcEnd;
                    while (++termsDstBeg != termsDstEnd) {
                        while (*--termsSrcEnd != *termsDstBeg) {
                            *termsTail-- = *termsSrcEnd;
                        }
                    }
                    while (termsBeg != termsSrcEnd) {
                        *termsTail-- = *--termsSrcEnd;
                    }
                    assert(std::distance(termsBeg, termsTail) + 1 == std::distance(termsDst, termsDstEnd));
                    auto term = termsTail;
                    termsDstBeg = termsDst;
                    assert(termsDstBeg != termsDstEnd);
                    do {
                        *termsTail-- = *termsDstBeg++;
                    } while (termsDstBeg != termsDstEnd);
                    assert(termsTail == std::prev(termsBeg));
                    return {term, sum}; // not past the end element for found range but exactly last element
                }
            }
            sumsSrcEnd = std::lower_bound(sumsSrc, sumsSrcEnd, *sumMax); // crop
        }
        return {termsEnd, sumsEnd};
    }
};

auto x = solve(std::begin(ships), std::end(ships), std::cbegin(rows), std::cend(rows)) if succeeded, it gives rearranged ships range such, that range [std::begin(ships), x.first] is a solution and sum of all ships is *x.second. [std::begin(ships), std::end(ships)) still consists of exactly the same ships. If not succeeded then it return a pair of std::end(ships) and std::cend(rows)

Edited by author 11.06.2020 12:53

What algorithm do you use to pass 68 tests ?

Edited by author 15.06.2020 21:48

I use bactracking and dynamic programming, it runs 30 seconds for the test 67th, the hardest one for my solution.


Edited by author 17.06.2020 15:02

it's too hard to figure out what's going on here!

Not specific kind of algorithm but just a good seed. I have no backtracking. No dp or dfs over that primitive above. Free search by combining of ships from one of found rows with pool of ships that cannot form some of the rows. Here used stability of the algorithm above to rearrange ships for better mixing of them. 67 is also hardest test for mine. 8 solutions per minute on E5-2667 v2 when running 16 threads (I use -fopenmp to parallelize). 70 gives about 220 solutions for that configuration.

Edited by author 17.06.2020 03:36

Edited by author 17.06.2020 15:37

Mind elaborating? Cannot see the linkage between this code and an O(n^3 * 2^sqrt(n)) algorithm.

My email sunzheng.david[at]gmail.com.

This is implementaton of third algorithm from "An Empirical Study of Algorithms for the Subset Sum Problem" O'Neil. It is not the code of solution of the whole problem (which is "multiple subset sum problem"), but a trivial part of it ("subset sum problem").

Hello, Orient, could you tell us more about your idea by email facttacf@gmail.com?

What algorithm do you use to pass 82 tests?

is it the same one you described above?

The same, but with small improvements, which detect a situation when heuristics goes to infinite loop then reshuffles a part of partial solution.
Strictly speaking above algorithm is only a part of the whole algorithm. Anyways that algorithm is just a heuristics. Although it is the only "beautiful" heuristics I can imagine, it is still a heuristics.

(!!!) Just now I found, that full brute force for tests like 67, 70 and 80, which enumerates all the possible solutions (literally ALL (+ simple b&b of course)), finishes in 3 seconds max. Even if I don't exit when first solution is found. It is incredible after all that research in heuristics field. I think I'll publish the algorithm. Not too soon. After solving the problem.

Congratulations!

Thx. It seems it is mistake of OJ, because I cannot reproduce.

jury must add a test in which several inputs are verified with single verdict: passed or failed to protect them from collecting information :)


Edited by author 25.10.2020 06:23

I bet you have a number of 70+ tests))

only one, and realized that it would be faster to solve it by changing the heuristic parameter (every 3-5 works) than to spend 100+ submissions to determine it.

You heuristics is fast. Mine is not. Can you give us a hint?

test 80 has 11881161 solutions! Your algorithm generate all of them in just 3 seconds!?