2
votes
Rank in a Convex Combination
By duality, this problem is equivalent to the halfplane range query problem.
For the worst-case complexity, there is a known space-time tradeoff of [1]:
$O(n^2/\log^2 n)$ data structure size and $O(\...
- 1,416
1
vote
Floyd's Cycle Detection Algorithm Proof In Laymen
Assume there is a cycle of length r, which is entered after m steps. Once you enter the cycle, you stay in the cycle. After either m steps, or after 1 step if m = r, both tortoise and hare are in the ...
- 25.6k
1
vote
Floyd's Cycle Detection Algorithm Proof In Laymen
1. Detecting cycle using Floyd's cycle detection algorithm - for this we need answer to the question: what's the guarantee that the hare and the tortoise will meet?
2. Detecting the starting point of ...
Only top scored, non community-wiki answers of a minimum length are eligible