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