ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1758. Bald Spot Revisited 2

Request for helpful optimizations :-)
Posted by Artem Khyzha 9 Jul 2012 20:25
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
Re: Request for helpful optimizations :-)
Posted by bsu.mmf.team 10 Jul 2012 14:32
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.
Re: Request for helpful optimizations :-)
Posted by Shen Yang 8 Oct 2018 13:06
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