ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1394. Ships. Version 2

Pages: 1 2 3 Next
SSP solver
Posted by Orient 11 Jun 2020 01:19
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) {
                I shiftedSum = *sumsShiftedBeg + *t;
                if (shiftedSum < *sumsSrcBeg) {
                    *sumsDstBeg++ = shiftedSum;
                    *termsDstBeg++ = *t;
                } else {
                    if (shiftedSum == *sumsSrcBeg) {
                        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
Re: SSP solver
Posted by Manciu Ion 14 Jun 2020 11:18
What algorithm do you use to pass 68 tests ?

Edited by author 15.06.2020 21:48
Re: SSP solver
Posted by Manciu Ion 14 Jun 2020 12:29
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
Re: SSP solver
Posted by Manciu Ion 14 Jun 2020 22:08
Re: SSP solver
Posted by Manciu Ion 15 Jun 2020 21:44
it's too hard to figure out what's going on here!
Re: SSP solver
Posted by Orient 17 Jun 2020 03:25
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
Re: SSP solver
Posted by Manciu Ion 17 Jun 2020 15:00

Edited by author 17.06.2020 15:37
Re: SSP solver
Posted by David Sun 4 Jul 2020 22:52
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.
Re: SSP solver
Posted by Orient 6 Jul 2020 01:34
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").
Re: SSP solver
Posted by Obmen 6 Jul 2020 12:26
Hello, Orient, could you tell us more about your idea by email facttacf@gmail.com?
Re: SSP solver
Posted by Manciu Ion 20 Oct 2020 21:15
What algorithm do you use to pass 82 tests?
Re: SSP solver
Posted by Manciu Ion 21 Oct 2020 14:42
is it the same one you described above?
Re: SSP solver
Posted by Orient 23 Oct 2020 00:56
Manciu Ion wrote 21 October 2020 14:42
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.
Re: SSP solver
Posted by Manciu Ion 25 Oct 2020 00:32
Re: SSP solver
Posted by Orient 25 Oct 2020 01:14
Thx. It seems it is mistake of OJ, because I cannot reproduce.
Re: SSP solver
Posted by rip&pvs 25 Oct 2020 05:55
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
Re: SSP solver
Posted by Orient 25 Oct 2020 07:24
I bet you have a number of 70+ tests))
Re: SSP solver
Posted by rip&pvs 25 Oct 2020 09:28
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.
Re: SSP solver
Posted by Orient 25 Oct 2020 14:11
You heuristics is fast. Mine is not. Can you give us a hint?
Re: SSP solver
Posted by Manciu Ion 26 Oct 2020 16:55
test 80 has 11881161 solutions! Your algorithm generate all of them in just 3 seconds!?
Pages: 1 2 3 Next