When I tried the brute force algorithm, I TLE at #15


How to solve this problem? Please send the solution to 13588731339@163.com

Interesting that test48, test70 (with reservations) and test80 do not look so hard to my solution. At least if the commenters in previous threads were right with examples of these tests. But mysterious test30 and test31 - I don't even imagine what structure they got.

Test70 is "randomly" solvable: with time distributed between 0.3 and 2.9 seconds (with avg = 1.1 sec) on my Intel i5-9400 (by "randomly" - I mean, of course, that could be 2.9 seconds which is TLE and would not pass)

And my suggestion: It would be nice to have a separate section on the site with parallel running of tests for such hard computational tasks. I mean: maybe someone also passes test 70, but fails test 30, for example. And the total percentage: passed N tests, failed tests with numbers K, L, M

Hello :) Could someone please give me test 48 or similar to let me understand what is wrong with my program ? :)

49 9
9 9 9 9 9 14 14 34 34 34 34 34 42 42 42 42 42 47 49 57 66 68 68 68 68 71 71 71 71 71 74 74 97 97 97 97 97 97 97 100 100 100 100 100 100 100 100 100 100
227 235 264 292 298 322 327 341 820

Problem 1394 "Ships. Version 2" is the same problem as 1115 but has full testset. Problem 1115 has only first 10 tests.

All latest submissions on 1115 were moved to new problem. You can resubmit you solutions to 1115 also if you want.

Problem 1115 was rejudged with 10 tests. But some submissions got WA.

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

42 8
2 4 6 13 14 14 19 26 26 30 60 89 89 89 89 90 90 90 90 90 91 91 93 94 94 94 94 94 94 94 95 95 95 96 96 97 98 98 98 99 100 100
184 186 209 402 408 488 621 622

now I have came up with a new optimization of this problems...but I don't want to rewrite my code...

#include <stdio.h>
#include <algorithm>
#include <stack>
using namespace std;
#define MAXN 100
#define MAXM 10
int ship[MAXN];
int row[MAXM];
int exi[MAXN];
int N, M;

int cmp(const void* a, const void* b);
void divid(int m);
int main()
{
    scanf("%d%d", &N, &M);
    for(int i=0; i<N; i++)
        scanf("%d", &(ship[i]));
    for(int i=0; i<M; i++)
        scanf("%d", &(row[i]));

    for(int i=0; i<N; i++)
        exi[i] = 1;

    qsort(ship, N, sizeof(int), cmp);
    divid(M);

    return 0;
}

int cmp(const void* a, const void* b)
{
    int* x = (int*)a;
    int* y = (int*)b;
    return *y - *x;
}

void divid(int m)
{
    if(m > 1)
        divid(m-1);

    stack<int> s;
    int tot = row[m-1];
    int hav = 0;
    int i = 0;
    for(;;){
        while(i<N && (!exi[i] || ship[i]>(tot-hav))) i++;
        if(i >= N){
            for(;;){
                i = s.top();
                s.pop();
                hav -= ship[i];
                exi[i] = 1;
                i++;
                if(i < N)
                    break;
            }
            continue;
        }
        s.push(i);
        hav +=  ship[i];
        exi[i] = 0;
        i++;
        if(hav == tot){
            int sh_ind;
            int siz = s.size();
            printf("%d\n", siz);
            while(!s.empty()){
                sh_ind = s.top();
                s.pop();
                printf("%d ", ship[sh_ind]);
            }
            printf("\n");
            return;
        }
    }
}

####################################################
I used recursion alg. And I know there is error in this code because I didn't deal with the situation I called "data confliction" such as "5 = 2+3".But how to IMPROVE it ???

email:1813484947@qq.com



Edited by author 15.07.2017 20:00

Edited by author 16.07.2017 15:23

All of the test cases invented by myself pass however I have got TLE on test #14. I would like some of these difficult tests to see. Thank you.

Since there can be more than one acceptable solution, I think, it could give a more unambiguous result.

Maxim Buzdalov have added a new bunch of tests. Progbeat, showjim and [NRU ITMO] WiNGeR have lost their AC.

Edited by author 07.10.2014 13:20

RT

I think 1s is resonable,but 64M is too tight(unsigned long long hash table is too hard to fit in 64M),1s in ural oj can run many operations

Edited by author 31.03.2014 14:08

I think this is a very hard case,and I don't know how to pass it....

How to solve this problem?

Edited by author 29.09.2013 08:45

Edited by author 29.09.2013 08:45

HA




Edited by author 09.07.2013 17:16

Edited by author 09.07.2013 17:16

Edited by author 09.07.2013 17:17

Edited by author 09.07.2013 17:19

AC code?
Put here..

I send my solution to timus but it give me WA#1. I can not understand, I think my programm is working true. please give me the test 1