When I tried the brute force algorithm, I TLE at #15 How to solve this problem? Please send the solution to 13588731339@163.com 1) When bruteforcing, random shuffle both m rows and n ships 2) When solving one subset sum problem inside bruteforcing, use bitset (array of bitsets) instead of bool array (2d-array). Instead of max() in subset sum problem, use operator OR and operator "right bit shift". Just search "subset sum problem bitset" and you'll find out. This will speed up your dynamic programming in 32 or 64 times (if you are using both 64-bit compiler and 64-bit processor) It will not totally solve problem, but you will get TLE#67 which is better and giving more hope :) Edited by author 12.04.2024 01:08 Edited by author 12.04.2024 01:09 Edited by author 12.04.2024 01:11 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 Now I know what's been wrong with my solution (TLE30), but now TLE46 If you read SPb-MaxBuzz's article about test generation for the problem, then you can see tests rearranged intentionally for top of solutions at some time point in the past. You can think your solution is very special. Hello :) Could someone please give me test 48 or similar to let me understand what is wrong with my program ? :) My program works fast on this test case :) (about 0.5 seconds) but still have TLE 48 ) What is the best way to collect information for particular test? Time/100ms (if there is window for that), memory/100kB, WA, TLE, RE... what else? What maximum number of bits per try? Let's call it `bitrate`. Serious enough term for further discussion =), isn't it? How to match particular test? Binary search for hash value of the input? Please, reveal your super-duper technology with your fancy-nancy metrics. Edited by author 18.12.2017 22:11 Re: test case 70: Posted by Shen Yang 19 Dec 2017 05:08 I just use stupid bianry search every veriable and submit many many many times I don't have better ideas and I have only test case 70... Edited by author 19.12.2017 05:09 Thank you for prompt :) But I guess I found one which helped me: 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 You mean without even single magic number for single test? Yes. Formally I can write code, that handle particular cases (e.g. patalogical cases having a bunch of repeating ships and rows), but is it somehow better then to find a single seed for the only case, which my solution cannot pass? 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 I have to say ,I'm toooooooo stupid..... wa haha Accpeted congratulations , looking forward another rejudgement hahaha Thanks for the good test ! Are the any other inputs you mined here bit by bit? :) Please share them with us, don't hesitate. What is the best way to collect information for particular test? Time/100ms (if there is window for that), memory/100kB, WA, TLE, RE... what else? What maximum number of bits per try? Let's call it `bitrate`. Serious enough term for further discussion =), isn't it? How to match particular test? Binary search for hash value of the input? Please, reveal your super-duper technology with your fancy-nancy metrics. Edited by author 18.12.2017 22:11 I just use stupid bianry search every veriable and submit many many many times I don't have better ideas and I have only test case 70... Edited by author 19.12.2017 05:09 //6 min 32.43 sec 4 100 71 42 14 4 97 57 47 34 5 100 71 42 42 9 5 100 100 74 9 9 5 100 74 66 49 9 5 100 100 71 42 9 5 100 100 71 42 14 5 100 71 68 68 34 11 97 97 97 97 97 97 68 68 34 34 34 The 83-rd test is almost the same. 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. So change the text 1115, because two problems now have the same limits for N, M and interval length. Or just delete the problem 1115. If you can write a solution that works within 5-10 seconds for any test I make, I wolud increase TL. Wouldn't you like to share with us? I use two algorithms inside one program: First I try to arrange ships using heuristics with randomization. If it fails for many times (say, 1000 times) I use bruteforce with optimizations (just like many people) I found a big numbers of different bruteforces and heuristics for this problem. I have tests for all that methods. You need just one good combination! My program works well on all tests, I've already checked more than 30 billions random tests. A little hint: my bruteforce gets TLE 22, heuristics gets TLE 17. Good luck! the idea is great! I have thought for too many strange ideas like netflow.....but not this one! i gonna try to solve it right now. Where is your good solution at now? The present-day test is too tough for your algorithm? If this the edge, it may be worth keeping the time limit so that one top solution has always been AC. It will be reasonable to increase the TL to 3s. It is required to inspect all the current solutions thoroughly to decide whether all of them have some "tweaking" for specific tests or not. If any of them is universal (i.e. actually not depends on any seed or magic number), then time limit can be even capped on that. If not, then it is reasonable to increase TL somehow. I can bet that some of accepted solutions will not pass for some permutation of actual tests and that is not ok when them will require to be adjusted in order to pass! Edited by author 21.11.2020 11:53 I sort input before use. What do you mean? Edited by author 16.12.2020 00:35 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 Edited by author 17.06.2020 15:37 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 What algorithm do you use to pass 82 tests? is it the same one you described above? 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? > solve it by changing the heuristic parameter (every 3-5 works) Your heuristics is highly effective, if I understand correctly. Is it true, that you can select a parameter ("seed") for the heuristics by just 3-5 tries? For each hard test case. Then you write `for (int seed : {seed_test70, seed_test67, seed_test80, seed_test69, seed_test77, seed_test79}) heuristics(seed);` and even for test79 (e.g., here "last" one) all iterations run in less then 1 second? I.e. less then a small number of milliseconds per every seed value, you collect? Edited by author 26.10.2020 23:46 nothing like this, my solution is common for all test and direct randomization is minimal. Actually I have kind of deterministic one (stuck on test#67 and can't pass #82 too, but not critical) and ideas for improving it, but don't have motivation and time to do this. I'm not going to share an idea or give hints. Do you use one algorithm or you mix them ? Edited by author 29.10.2020 11:56 I use two algorithms. Heuristics and branch and bounded brute force. They called in the next order: 1 try of heuristics (I think 90% of tests are covered by this first one) (it take about 1-2ms), then highly clipped b&b brute force (I think it get about a couple of hundreds of milliseconds in worst case - on test 77 or 79 it fails and made complete (unsuccessful) enumeration through all clipped DoD), then infinite number of tries of the same heuristics (it get about first tens or mb one hundred of milliseconds average, but for some good seed (in fact I enumerate first 20 of them - two was good enough) it get mb less than ten milliseconds or so). A vast majority of test are covered by heuristics. It works well on those tests, that have big actual number of unique solutions. For these brute force produces too big number of solutions, that results in MLE. Heuristics is simple and have regular structure. Actually it can find solutions for any test, but for some of them (test67) the probability per try is too low to reliable fit in 1 seconds of time limit. On the contrary brute force is highly effective on those tests, which have one or two unique solutions (or maybe thousands -- don't even know, because I have only test67 and test70, which have such a property). Branch and bounding works highly effective on these. The only "cheating" to get solution for me was to find right seed for test79 (I don't know its structure and I want to collect it maybe). Don't even know how rare it -- I find it from the first try. Another cheating -- is to optimize. I made holes in DoD of brute force. So enumeration was reduced a lot for minor number of tests. Optimization is not valuable at all from algorithmic point of view. It is a bullshit full of magic numbers. My backtracking algorithm runs in 4.0 sec on Java and 8.0 sec on C++ for test 78, 0.178 sec on Java and 0.165 sec on C++ for test 67. I can conclude, that your backtracking algorithm is (exactly) as optimal as mine. I bet you use something like `std::vector<std::bitset<99>>` to store solutions per every row and something like `std::unordered_map<std::bitset<9>, std::unordered_set<std::bitset<99>>>` for branch and bounding, isn't it? Yes, you are right, but I use my bit set implementation. I have found another constraint but I don't know for now how to implement optimal! What is the constraint? Is it a secret for now? It's no secret, but it won't be fair to post it here OK, I think I'll come up with one too. Knowing that there is something besides `std::unordered_map<std::bitset<9>, std::unordered_set<std::bitset<99>>>` is enough. Edited by author 29.10.2020 18:39 > I use my bit set implementation Do you use _bit_scan_forward/_bit_scan_reverse when recover solution? Can it be an improvement over std::bitset? Yes, It can, but I don't think it will improve more than 0.1 second! Edited by author 31.10.2020 12:56 It is not critic recovering and saving solution! Anyways it is interesting to implement next-bit-set-iterator. Do you use parallel programing ? No. Because it have no sense. User time of all the threads are summed up. Edited by author 20.11.2020 22:00 Good to know. Do you want to trade our solutions when you solve?) Edited by author 26.10.2020 23:45 test 80 has 11881161 solutions! Your algorithm generate all of them in just 3 seconds!? > test 80 has 11881161 solutions! Your algorithm generate all of them in just 3 seconds!? I was wrong. The algorithm (backtracking) generates all the (15741649, "all the" contains a large amount of convention, because of branch and bounding) solutions for test80 in ~72 seconds. First solution found in 3.223853s for standard random seed and 0.563442s for search in lexicographical order. But my heuristics finds solution for test80 in 0.000041s and it goes before the backtracking, so test80 is not the problem at all. test67 (first solution): 0.290 (lexicographical order) test67 (complete enumeration, 1 solution): 0.373 (lexicographical order) test70 (first solution): 0.179 (lexicographical order) test70 (complete enumeration, 2 solutions): 0.187 (lexicographical order) Number of solutions for each separate line for test80 (lines sorted): 109 115 209 3981 4442 10091 38691 0 // this one is not even calculated, because not needed Hardware: Intel Intel(R) Xeon(R) CPU E5-2667 v2 @ 3.30GHz (3.90GHz Trubo Boost per single core, vs 2.40GHz (same arch) on OJ system). Specially bought for this problem). BTW test5 is a tough nut to crack for the algorithm. Edited by author 26.10.2020 22:38 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? 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 Are you sure? It get 0 nanoseconds for mine TLE67 version (for any random permutation of input). Edited by author 06.03.2020 00:50 Yes, I am sure. The tests are a bit peculiar for this problem. Some group of tests target specific solutions, so it's entirely possible your solution deals with some of the last tests easily (there should be 81 of them), but fails on earlier ones. Edited by author 05.03.2020 18:15 Thank you for the information. 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 I think this problem is different with usual acm problems. for other problems writer give test cases to test code,this problem is reverse, using code to test the test cases. I think the final result is test cases AC all participant's codes, because it is NP hard problems.. Edited by author 12.10.2014 14:48 RT At least, it can be written as linear programming problem. However, it is INTEGER linear programming problem, which still remains to be NP-hard. can we use simplex() to solve floating version of lp, then use it as heuristics: brute force to search in descending order of veriable x.. I will try this approach to test case 70(toooooooooooooo hard....) 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.... can anyone give me some hint on this case? 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 hope nobody will put. Forum is not good place to post right solutions ;) You can write your email here... Btw, and did you try to solve|submit it yourself? Money? Put here... +7 926 153 72 30 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 |
|