DjangoBB LoFi version

Начало » Центр помощи » Задачка для всех

1 2 3

Frog-king

Янв. 21, 2013 21:01:19

Вообщем, судя по недавнему топику про Комбинаторику я подумал что всем будет интересно (в том числе и мне) решить одну задачку на питоне.
Эту задачку я получил когда проходил второй этап поступления в Школу программистов HH (собственно я так и не прошел). Мне удалось решить задачу частично т.к. одно из условий было

Ни одна из задач не должна считаться больше 5 секунд на валидных входных данных

, в которое я ну не как не мог уложиться.
Вообщем сама задача:

№10. Пилообразные последовательности
Назовем последовательность пилообразной, если каждый ее элемент либо строго больше, либо строго меньше своих соседей. По данными числам n и k определите число пилообразных последовательностей длины n , составленных из чисел 1.. k .
Программа получает на вход два натуральных числа n и k , не превосходящих 10**6. Гарантируется, что ответ не превосходит 2**31-1.
Пример
Ввод - “3 3” Вывод - “10”

P.S. потоки - можно, процессы - нельзя,
** - степень

P.P.S. Если нужно то могу выложить свой неудачный код

Frog-king

Янв. 21, 2013 22:25:42

Самый быстрый код который у меня получился ( но он настолько уродский что стыдно) решал эту задачу с входными данными n = 8, k = 8 чуть больше 12 секунд ( ответ выдает 691550).
У кого получается быстрее, тот очень крут ( IMHO).
Пожалуйста, мне очень интересно как сделать ещё быстрее ( желательно без сторонних библиотек и всяких PyPy)

Soteric

Янв. 21, 2013 22:32:14

Решение принималось только на питоне? На скольки ядрах подразумевался запуск кода?

Я вижу, что можно распараллелить на k потоков. Каждый из потоков делает допущение, что последовательность начинается с числа 1..k и просчитывает соответствующие комбинации.

Выложите код, хуже не будет.

Frog-king

Янв. 21, 2013 23:19:37

Принималось и на java Но это не равный бой. Я её не знаю. )) и знать пока не хочу.
По поводу ядер нечего не писалось.
Такой вариант с потоками пробовал, но получилось медленней, возможно я не умею их готовить ( делал через класс threading.Thread) к сожалению сорцов этой попытки не осталось.
Я выложу пока более маленькое и лаконичное решение (но пи“”" медленное).

import itertools
import time
def is_pill(ch_list):
    for index, num in enumerate(ch_list[1:]):
        try:
            if not (ch_list[index] < num > ch_list[index + 2]
                 or ch_list[index] > num < ch_list[index + 2]):
                return False
        except:
            pass
    return True
def testsupper3(k, n):
    res = 0
    for args in itertools.product(*[range(1, k + 1)] * n): # обратите внимание на * перед range - удивительный оператор
        if is_pill(args):
            res += 1
    return res
n, k = 8, 8
t1 = time.time()
ans = testsupper3(k, n)
t2 = time.time()
print ans, t2 - t1

Более длинное решение но быстрое пока не буду выкладывать ( там все равно нечего не понять).
Я его 3 месяца назад писал. Сейчас смотрю и думаю как я так мог - Руки оторвать.

Lexander

Янв. 21, 2013 23:23:43

Условие ведь неполное.
Может быть, в правиле построения последовательности должна быть степень?

Soteric
В задании сказано, что нельзя потоки использовать ;)

Soteric

Янв. 21, 2013 23:23:50

Если я правильно понимаю проблему с GIL, то многопоточность в питоне не даст прироста производительности на задачах интенсивно использующих процессор.

В задании сказано потоки - можно, процессы - нельзя.

Frog-king

Янв. 21, 2013 23:29:35

Потоки можно. (если помогут )
А по поводу степени не понял, но задание написал правильно (точно)

Lexander

Янв. 21, 2013 23:47:30

Frog-king
задание написал правильно (точно)

Возможно, просто последовательности бывают разными, связаны с какой-либо прикладной дисциплиной и отличаются правилами формирования.
Честно, я не помню уже какие последовательности бывают в комбинаторике :)

Плюс неточность в формулировке относительно соседей.
Например, становится ясно, что при входных данных “3 3” последовательности ~~123 и 321 считаются пилообразными только по косвенному признаку - результат = 10, иначе было бы 8~~.
Думаю, здесь я ошибся в формировании последовательности и, соответственно, в подсчете.
Впрочем, неточность с соседями остается :)

Опять же, по косвенным признакам, я предполагаю, что речь идет о последовательностях вида:
1 1 1
1 1 2
1 1 3
1 2 1
1 2 3
… и т.д. до
3 3 3

Frog-king

Янв. 22, 2013 00:16:39

нет.
Ваши последовательности не пилообразные. Либо оба соседа больше элемента либо оба меньше
Вот все варианты 3 на 3:
1) 1 2 1
2) 1 3 1
3) 1 3 2
4) 2 1 2
5) 2 1 3
6) 2 3 2
7) 2 3 1
8) 3 1 2
9) 3 1 3
10)3 2 3

Вот и все
P.S 4 на 4 писать не буду))

Lexander

Янв. 22, 2013 01:40:24

У меня получились именно такие последовательности, к которым добавил, 123 и 321.

Frog-king
Либо оба соседа больше элемента либо оба меньше

В задаче не сказано “оба соседа”, что однозначно указывало бы только на средний элемент последовательности длиной три.
Сказано

каждый ее элемент либо строго больше, либо строго меньше своих соседей

В последовательности 123 для элемента 3 это правило выполняется тоже, хотя у него только 1 сосед слева.
Понимаете в чем неточность формулировки? ;)