Discussion @ 1098. Questions @ Timus Online Judge

Timus Online Judge

Online Judge	Problems	Authors	Online contests
About Online Judge Frequently asked questions Site news Webboard Links	Problem set Submit solution Judge status Guide	Register Update your info Authors ranklist	Current contest Scheduled contests Past contests Rules

Discussion of Problem 1098. Questions

Show all messages Hide all messages

It is a Joseph problem.If you have read Concrete Mathematics,you can solve it easily in O(N), 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), 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), 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)