Discussion @ 1098. Questions @ Timus Online Judge

It is a Joseph problem.If you have read Concrete Mathematics,you can solve it easily in O(N),

Posted by Andrew 14 Jul 2004 19:28

Re: It is a Joseph problem.If you have read Concrete Mathematics,you can solve it easily in O(N),

Posted by Igor E. Tuphanov 10 Jul 2006 14:18

How's that? FE, it seems to me, my solution works for O(logn), where n is the length of text and the base of logarithm is 1999/1998.

Re: It is a Joseph problem.If you have read Concrete Mathematics,you can solve it easily in O(N),

Posted by Anisimov Dmitry 6 Oct 2008 21:12

Igor, it seems wrong because your solution has exactly same asymptotical order.
O(ln X/ln(N/(N-1)) = O(ln X/(ln(1+1/N))= O(N*ln X)

Discussion of Problem 1098. Questions