|
|
back to boardShow all messages Hide all messagesHi 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 |
|
|
