|
|
50
39
1 33 11 22 44 4 28 14 42 21 7 35 5 25 50 10 20 40 8 32 16 48 24 12 36 18 6 30 15 45 9 27 3 39 13 26 2 34 17
21
17
1 16 8 4 20 10 5 15 3 9 18 6 12 2 14 7 21 Hi guys,
Could you please share any hint on how to optimize backtracking?
I've been trying to solve this problem, but it seems that I haven't got the idea good enough: my precalculation has been working for an hour and there's still N>45 cases to solve. :-)
Edited by author 10.07.2012 10:14 Try to set maximum border of the answer for every big N (for example, you can exclude all primes > N/2 etc.)
After that think whether this maximum value can be achieved (as I remember, it is possible only if numbers with less count of divisors should apeear first in resulting sequence - it's not hard to prove).
Such thinking allows you to set some numbers in the beginning of the sequence. Other 40-45 values can be found by backtrack. I use random search in this problem ,and it is fine. when dfs and we can't find a number to add it to the last, then we perform reverse,reverse [id,end], and continue dfs search..
then we can get correct answer very fast.
then we can use if(times>1e4) return prunning. it can AC...
it is a bit similar as LKH algo
Edited by author 08.10.2018 13:09
Edited by author 18.11.2017 07:25 |
|
|
