ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1098. Questions

Seems that the O(lgn) algorithm is slower than the O(n) algorithm for these test cases.
Послано some_programming_novice 17 ноя 2018 17:57
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?