ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1394. Корабли. Версия 2

Страницы: 1 2 3 Следующая
SSP solver
Послано Orient 11 июн 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) {
                    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
Re: SSP solver
Послано Manciu Ion 14 июн 2020 11:18
What algorithm do you use to pass 68 tests ?

Edited by author 15.06.2020 21:48
Re: SSP solver
Послано Manciu Ion 14 июн 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
Послано Manciu Ion 14 июн 2020 22:08
Re: SSP solver
Послано Manciu Ion 15 июн 2020 21:44
it's too hard to figure out what's going on here!
Re: SSP solver
Послано Orient 17 июн 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
Послано Manciu Ion 17 июн 2020 15:00


Edited by author 17.06.2020 15:37
Re: SSP solver
Послано David Sun 4 июл 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
Послано Orient 6 июл 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
Послано Obmen 6 июл 2020 12:26
Hello, Orient, could you tell us more about your idea by email facttacf@gmail.com?
Re: SSP solver
Послано Manciu Ion 20 окт 2020 21:15
What algorithm do you use to pass 82 tests?
Re: SSP solver
Послано Manciu Ion 21 окт 2020 14:42
is it the same one you described above?
Re: SSP solver
Послано Orient 23 окт 2020 00:56
Manciu Ion писал(a) 21 октября 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
Послано Manciu Ion 25 окт 2020 00:32
Congratulations!
Re: SSP solver
Послано Orient 25 окт 2020 01:14
Thx. It seems it is mistake of OJ, because I cannot reproduce.
Re: SSP solver
Послано rip&pvs 25 окт 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
Послано Orient 25 окт 2020 07:24
I bet you have a number of 70+ tests))
Re: SSP solver
Послано rip&pvs 25 окт 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
Послано Orient 25 окт 2020 14:11
You heuristics is fast. Mine is not. Can you give us a hint?
Re: SSP solver
Послано Manciu Ion 26 окт 2020 16:55
test 80 has 11881161 solutions! Your algorithm generate all of them in just 3 seconds!?
Страницы: 1 2 3 Следующая