ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1394. Ships. Version 2

Pages: Previous 1 2 3 Next
Re: SSP solver
Posted by Orient 26 Oct 2020 21:18
> 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
Re: SSP solver
Posted by Orient 26 Oct 2020 23:44
> 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
Re: SSP solver
Posted by Orient 26 Oct 2020 23:44

Edited by author 26.10.2020 23:45
Re: SSP solver
Posted by rip&pvs 27 Oct 2020 23:14
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.
Re: SSP solver
Posted by Orient 28 Oct 2020 00:18
Спасибо и на этом.
Re: SSP solver
Posted by Manciu Ion 28 Oct 2020 14:22
Do you use one algorithm or you mix them ?

Edited by author 29.10.2020 11:56
Re: SSP solver
Posted by Orient 29 Oct 2020 16:29
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.
Re: SSP solver
Posted by Manciu Ion 29 Oct 2020 18:03
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.
Re: SSP solver
Posted by Orient 29 Oct 2020 18:15
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?
Re: SSP solver
Posted by Manciu Ion 29 Oct 2020 18:28
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!
Re: SSP solver
Posted by Orient 29 Oct 2020 18:29
What is the constraint? Is it a secret for now?
Re: SSP solver
Posted by Manciu Ion 29 Oct 2020 18:35
It's no secret, but it won't be fair to post it here
Re: SSP solver
Posted by Orient 29 Oct 2020 18:38
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
Re: SSP solver
Posted by Orient 31 Oct 2020 01:36
> 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?
Re: SSP solver
Posted by Manciu Ion 31 Oct 2020 10:52
Yes, It can, but I don't think it will improve more than 0.1 second!

Edited by author 31.10.2020 12:56
Re: SSP solver
Posted by Manciu Ion 31 Oct 2020 13:32
It is not critic recovering and saving solution!
Re: SSP solver
Posted by Anatoliy V Tomilov 31 Oct 2020 18:29
Anyways it is interesting to implement next-bit-set-iterator.
Re: SSP solver
Posted by Manciu Ion 5 Nov 2020 14:05
Do you use parallel programing ?
Re: SSP solver
Posted by Anatoliy V Tomilov 5 Nov 2020 23:25
No. Because it have no sense. User time of all the threads are summed up.
Re: SSP solver
Posted by Manciu Ion 6 Nov 2020 14:33

Edited by author 20.11.2020 22:00
Pages: Previous 1 2 3 Next