42

У меня получилось 42.

Предлагается тоже сначала найти эту задачу, а только потом отписаться? :)

Это первая часть задачи.

я знаю пароль, я вижу результат - это 22555

Задача-макгаффин?

Добавил в тему ссылку на задачу.

http://wunderfund.io/dev_job

Буду попробывать

Возможно усилю стремление к увеличению намерения попробовать эту задачку попоздее.

SPOILER ALERT

Братiе, только не вкидывайте в тред выигрышные стратегии! Только ваш максимальный результат.

Задача старая, мелькала уже.

А время дискретно меняется или непрерывно?

Время дискретно

А время дискретно меняется или непрерывно?

Вы пробовали условие прочитать? Время дискретно. На каждом шаге дискретизации есть конкретная цена, можно либо продать 1 акцию, либо купить 1 акцию, либо не делать ничего.

Dicsrete Time optimal control.

Так как пространство управления не выпукло, то будет

relaxed discrete time optimal control.

Можно конечно и как TSP сформулировать - но это есессно тупняк.

9220 Сначала получалось на десятку больше, пока не учел, эммм, упущенную прибль.

И да, мне написало, что я выиграл автомобиль.

набор данных каждый раз разный — зайди в анонимной вкладке

У кого сколько получится?

Куча денег, но OlympTrade © лень устанавливать :)

http://pastebin.com/EyUdBj9b Как-то так. Задача слишком сферически-вакуумная.

Я пытался заново скачать файл, он мне тот же подсовывает, даже из приватной вкладки тот же

Я придумал стратегию: нужно покупать подешевле, продавать подороже :) я не шучу.

Учитывая сообщение:

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

Меняться задача может просто по времени.

Да я перезагружал страницу ж и заново качал файл

У меня на текущих данных получается 2000, но тоже говорит что неверно.

у меня 15 555 получалось и ошибок я не видел. Странно. Вроде бы данные не изменились.

Действительно, с другого компьютера - другие данные.

Для воспроизводимости результатов предлагаю пользоваться вот этим файлом. Писать сюда сумму прибыли по этому файлу после того, как на сайте вам сообщат, что ваше решение верное.

http://pastebin.com/S2WWu4b3

Решение то я придумал и мне кажется, что быстрее я его смогу реализовать на питоне для произвольных данных, как только снова прочитаю о том, как удалять элементы из массива/списка. Всё равно практики нет никакой и не умел.

В main уже полный треш, а не код, голова не варит что-то совсем

import Data.Array

inf = 1000000000

fAr :: [Int] -> Array (Int, Int) Int
fAr p = fAr'
    where l = ((-1, 0), (length p-1, length p))
          fAr' = array l (zip (range l) $ map (uncurry f) (range l))
          f :: Int -> Int -> Int
          f (-1) 0 = 0
          f (-1) _ = -inf
          f t n = let a | n>0 = fAr'!(t-1, n-1) - (p!!t)
                        | otherwise = -inf
                      b = fAr'!(t-1, n)
                      c | n<=t = fAr'!(t-1, n+1) + (p!!t)
                        | otherwise = -inf
                   in maximum [a, b, c]




main = do
    f <- readFile "wf.csv"
    let p = map (read . tail . dropWhile (/=',')) $ tail (lines f)
        n = length p
        lastPrice = head $ reverse p
        moneys = map (\x -> (fAr p)!x + (snd x)*lastPrice) (range ((n-1, 0), (n-1, n)))
    print $ maximum moneys

Для воспроизводимости результатов предлагаю пользоваться вот этим файлом.

Ну у меня получилось 4810, хотя не факт, что у меня правильный алгоритм. А у вас сколько?

Подозреваю, что у него 15 555. Мой ответ приняло и на этих данных получается 10750.

Мой ответ приняло и на этих данных получается 10750.

А кинь на пастебин или куда-либо еще список пар покупка-продажа для этого файла. Инетересно понять, как такое число получается вообще.

Добавил back-tracking, на их мелком примере отработал правильно: тут.

Вроде, правильно находит путь (на последнем шаге нечего продавать):

-10000 -10160 -9960 -10080 -10100 -10110 -10080 -10100 -10220 -10320 -10210 -10360 -10440 +10660 -10450 +10540 +10660 -10470 -10460 -10450 +10510 +10670 +10610 +10500 +10640 +10570 +10530 +10690 +10780 +10890 +10730 +10850 +10690 +10510 -10360 +10420 -10320 -10170 +10370 +10490 -10310 +10410 -10210 -10300 +10410 +10310 -10120 -9950 -10030 -10180 -10020 -10030 +10190 +10350 +10370 +10190 +10260 +10230 -10090 +10240 -9890 -9910 +10070 -9880 +10030 +10000 -9840 -9920 -9880 -9920 -9860 +9960 +10020 +10010 +10060 +10040 -9870 +10000 -9870 +9900 -9690 +9790 -9650 +9740 -9310 +9410 +9240*0 = 10750

что у них там за вакансии, что оценивают по таскам уровня второй на регионе для школьников?

слишком много умных слов для таски такого уровня

Они не оценивают, они отфильтровывают тех, кто не решит.

логично в общем-то

эх, опять глупость сгенерировал

а расскажите, пожалуйста, алгоритм решения

Не знаю какой у него, но я хотел бы реализовать поиск максимального на всём диапазоне (продажа) и минимального левее этого значения (покупка). Их разница будет максимальной выгодой из всех пар. Потом исключить эти два значения из диапазона и повторить процедуру.

Уже ведь привели код на python и haskell. Код на последнем понять сама по себе задача, а на python понять можно. Это динамическое программирование, но, что может немного сбить с толку, это итерирование не по новому состоянию на каждом шаге, а по старому.

У меня и код и мой исходный набор данных остались на работе. Но смысл был такой:

1. Выбирался шаг с минимальной стоимостью
2. находился шаг с максимальной стоимостью позже первого.
3. Они считались парой купил-продал, сохранялись и исключались из исходного набора. Их прибыль плюсовалась в прибыль общую.
4. Возвращался к п. 1

   Завтра проверю результат на тестовой выборке. Но я даже знаю, где в моем алгоритме ошибка. Причем она будет проявляться не всегда. Завтра поправлю и проверю.

Выбирался шаг с минимальной стоимостью

Но минимальная стоимость во всём диапазоне может быть предпоследним шагом, а на последнем стоимость может быть ещё меньше, а последний шаг предполагает только продажу. Тогда разница получится отрицательная. Разве не так?

Напоминает задачу из недавнего BlackBox Challenge

мой ответ не приняло, а получается 11250 (по этим данным Задача в вакансии (комментарий)).

а что если их решение не правильное? о_О http://risovach.ru/upload/2012/11/templ_1352053367_orig_A-chto-esli.jpg

python 2.7:

price = [10000,10160,9960,10080,10100,10110,10080,10100,10220,10320,10210,10360,10490,10440,10490,10660,10450,10540,10660,10470,10460,10450,10510,10670,10610,10500,10640,10570,10530,10690,10780,10890,10730,10850,10690,10510,10460,10360,10420,10320,10170,10370,10490,10310,10360,10410,10210,10300,10410,10310,10120,9950,10030,10180,10020,10030,10190,10350,10370,10190,10260,10190,10230,10150,10090,10240,10040,9890,9910,10070,9880,10030,10000,9840,9920,9880,9920,9860,9960,10020,10010,9930,10060,10040,9870,10000,9910,9870,9900,9860,9700,9690,9790,9650,9740,9680,9500,9500,9310,9410,9240]

print price
sum = 0

while len(price) > 1:
    print "LEN = ", len(price)
    
    pmax = price[0]
    nmax = 0
    
    for i in range(len(price) - 1):
        if pmax  <= price[i+1]:
            pmax = price[i+1]
            nmax = i+1
        
    print pmax,"[",nmax,"]"

    pmin = price[0]
    nmin = 0
    
    for i in range(nmax):
        if pmin  > price[i+1]:
            pmin = price[i+1]
            nmin = i+1
        
    print pmin,"[",nmin,"]"
    
    sum = sum + pmax - pmin
    price.remove(pmax)
    if nmax > nmin:
        price.remove(pmin)

    print "ssum = ",sum  
    print '------------'    
    print price

print "SUM:",sum

Я так понял, им нужны специалисты по экселю?

http://imgur.com/D0aEniA

Что в Excel, что в Calc есть линейные решатели. Описываешь задачу, жмёшь кнопку, получаешь результат.

(Я гифку раз в пять дольше делал, чем задачу решал.)

А принятие решения (третий столбец) -1, 1, 0 не понял откуда бралось и running total :(

В LO Calc просто задаёшь диапазон ячеек, в которых можно значения менять, и целевую ячейку, в которой нужно максимизировать. Я искал одно из чисел: -1, 0, 1 (купить, ничего не делать, продать), причём в 100 ячейках. Оптимизировался итоговый баланс. Условия были: больше -1, меньше 1, целое. Running total — это running total по числу акций. Оно не может быть отрицательным, поэтому использовалось как ещё одно ограничение.

Другими словами, LO Calc сам ищет решение. Ты ему — входные данные и ограничения на них. Он тебе — результат.

или правильнее так, но ответ тот же и не совпадает :(

    for i in range(len(price)):
        if pmax  <= price[i]:
            pmax = price[i]
            nmax = i

...

    for i in range(nmax):
        if pmin  > price[i]:
            pmin = price[i]
            nmin = i

Про решатель я знаю, что он сам ищет, просто не совсем понял почему заранее проставлены числа в decision, от предыдущего запуска осталось?

И наверное не все условия поместились отображаясь в окошке выбора параметров решателя.

от предыдущего запуска осталось?

Ага.

не все условия поместились отображаясь в окошке выбора параметров решателя

Вроде, их 4 было. Я думаю, это все.

А что интересного то в задаче? Она же тривиальна. Единственное, что из условия не совсем ясно, можно ли купить часть акции, или они продаются только целиком? Возможно, из-за этого и не сходится решение.

значит для предпоследнего шага не будет пары на продажу и он будет пропущен.

По моему в таком способе не учитывается условие, что на момент продажи надо иметь хотя бы 1 акции. Не увидел этого в таблице. И что на последнем шаге можно продать несколько акций за раз. То есть Excel не на всех входных данных даст верный ответ.