Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Take the naive n^2 algorithm, but test only the nodes whose distance from the start is a power of two.


This seems just as magical as the original algorithm. Do you have insight as to why it works and what though process is necessary to arrive to it?


> This seems just as magical as the original algorithm.

If you do a "change of coordinates" the original algorithm becomes trivial: If you know that any loop in the list doesn't begin after the node you're on, you can just mark where that is, run ahead, and check if you ever come back. In the general case, "change coordinates" so that with every step, the origin advances one step. Now you'll eventually be in the previous case.


It's an act of logification.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: