|
|
вернуться в форум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 |
|
|
