среда, 3 апреля 2013 г.

Для прокачивания навыка решения алгоритмических задач зарегистрировалась на spoj. Этот сайт удобен тем, что на нем выложено много задачек, в том числе и "классических". После удачного решения очередной задачи рейтинг пользователя повышается, что очень круто, хочется решать еще и еще(кажется, такой прием стимулирования пользователей называется геймификацией).

На сайте spoj можно решать задачки на разных языках программирования. Я пробовала решить задачу бинарного поиска. Но, к сожалению, обычный способ не подходит - выдается time limit error, а с оптимизацией - выдается wrong answer. Некоторое время пыталась найти ошибку в алгоритме с оптимизацией, но не смогла. Организовала дискуссию по этому вопросу, но никто ничего внятного не ответил, так что забила на эту задачу. Пробовала делать другую задачу (нахождение квадратного корня). Даже нашла итерационный алгоритм быстрого нахождения корня. Его реализация отрабатывала очень быстро. Но потом почитала комментарии к задаче и увидела, что автор задачи отключил прием решений на Python после жалоб про time limit exceeded. Общее впечатление осталось такое: если хочется без проблем прокачать навыки на этом сайте, то это лучше всего делать на каком-нибудь C++. А с Python все будет намного сложнее. 

Потом мы с Дмитрием пробовали участвовать в одном из чемпионатов Codechef. Задачка была такова: для заданного целого N > 0 найти количество палиндромов из букв английского алфавита, длины не превосходящей N.  Загвоздка была в том, что N могло быть очень большим, поэтому ответ нужно было вывести как остаток от деления (результат / 10^9 + 7). Были и другие задачки, но захотелось начать с чего-то полегче. На все про все давалось 3 часа. Сначала получился такой код:

def get_PNum(N):
    if (N==1):
        return 26
    elif (N % 2 == 0):
        return get_PNum(N-1) + pow(26,N/2)
    else:
        return get_PNum(N-1) + pow(26,N/2)*26

(26 - потому что 26 букв в алфавите, N/2 - потому что уникальность палиндрома определяется сочетанием букв из его половины).

При попытке отправить решение выдавалась time limit error. Тогда я видоизменила код так:


def get_PNum(N):
    if (N == 1): 
        return 26
    result = 26.0
    for i in range(2, N+1):
        if (i % 2 == 0):
            result = result + pow(26,i/2)
        else:
            result = result + pow(26,int(i/2))*26
    return result

Опять time limit error. Тогда я увидела, что можно еще свернуть формулу, использовав формулы для суммы членов и количеств членов геометрических прогрессий (тут как бы получаются две прогрессии, с одинаковым множителем, просто первый член разный, ну и количество членов разное):


def get_PNum(N):
    if (N == 1): 
        return 26
    n = 0.0
    m = 0.0
    if (N % 2 == 0):
        n = (N-2)/2 + 1
    else:
        n = (N-1)/2 + 1
    m = N - n    
    return 26*(pow(26,n) - 1)/25 + 26*(pow(26,m)-1)/25

Опять time limit error! Но тут пришла догадка, что нужно попробовать решить задачу для числа N = 1000000000. Eclipse просто стал вываливаться на этом числе. Оказалось, что функция возведения в степень просто сходит с ума на таких больших числах. Нашелся алгоритм "быстрого возведения в степень", но как раз к этому моменту, к сожалению, 3 часа соревнования подошли к концу. А еще, оказывается (это уже просмотр удачных решений других пользователей) надо было сразу делить (как только можется) оперируемые числа на 10^7 (а не делить после того, как функция вернет результат).
Ну в общем, можно сказать, что опыт был успешный, мозги в процессе поупражнялись :)