|
|
back to boardSeems that the O(lgn) algorithm is slower than the O(n) algorithm for these test cases. For the classic Josephus problem, there exists two classic algorithms. The algorithm A has time complexity O(lgn) and comes from <discrete mathematics>. /* Algorithm A */ int solve(int N/*The magic number 1999*/, int m/*length of the text*/) { long long z = 1; while (z < (N - 1LL/*int may overflow here*/) * m + 1) { z = (z * N + N - 2) / (N - 1); } return m * N - z; } The algorithm B is the classic O(n) algorithm. int solve(int N/*The magic number 1999*/, int m/*length of the text*/) { int z = 0; for (int k = 2; k <= m; ++k) { z = (z + N) % k; } return z; } In my submissions, algorithm A costs 0.015s, and algorithm B costs 0.001s. Maybe arithmetic operations for "long long" is a little too slow? |
|
|