В решението на задача 2 във варианта, в който зад. 2 е за въпроси, които прескачаме или не прескачаме, често се среща следният опит за решение.  Да моделираме задачата с ориентиран граф, в който върховете са въпросите, а ребрата са възможните преходи от всеки въпрос (те са най-много два -- към следващия или към някой нататък).  Графът очевидно е тегловен dag, който дори е, удобно за нас, топо-сортиран от наредбата на въпросите; ние просто търсим най-дълъг път, което знаем как се прави оптимално от лекции.

Това не става.  Първо, в този граф теглата са по върховете, а не по ребрата.  Дори да се измисли начин да се трансформира dag-ът в друг dag, при който теглата са върху ребрата, пак не става.  Правилната посока е отзад напред, а не като при намиране на най-къс или най-дълъг път в dag отпред назад.  Вижте следния пример с ASCII графика


1 ----> 100 ----> 5

  \----------------/


Въпрос 1 струва 1 точка, вторият е 100 точки, третият е 5, ако отговорим на първия, то прескачаме втория и отиваме на третия.  Очевидно оптималното решение е да прескочим първия, да отговорим на втория и третия и да съберем 105 точки.  Ако не прескочим първия, максимум 6 точки ще имаме.  Как обаче да накараме алгоритъм за най-дълъг път да прескочи първия въпрос?  Най-дългият претеглен (с тегла на върховете) път очевидно е през всички върхове и той има тегло 106, но всъщност решение със стойност 106 няма.  Не мисля, че можем да оправим нещата със слагане на фиктивен връх в началото -- ако от фиктивния можем да стигнем до въпрос 1, все едно нищо не правим, а откъде да знаем да не правим това...



----------------------------------



Среща се и още една идея, която не работи.  За даден q[i] гледаме сумата p[i+1] + .. + p[i + ti] и я сравняваме с p[i]; ако p[i] е по-голяма, то правим скока напред, в противен случай не.  Ако p[i] е по-голяма, наистина няма как да сбъркаме, пропускайки въпроси q[i+1] .. q[i + ti], но в обратния случай никой не е казал, че непременно можем да реализираме p[i+1] + .. + p[i + ti] точки от въпроси q[i+1], ..., q[i + ti].  Това зависи от t-тата на q[i+1], ... , q[i + ti]. 



--------------------------------------



В другия вариант на изпита се намира задачата, известна като 3SUM.  Има верни решения със сложност  n^2, но без смислена аргументация за коректност.   Дори да не бъде доказва подробно поради липса на време (това е ОК), поне трябва да се спомене някакво твърдение, наподобяващо инварианта.  Говорим за външния цикъл.  Твърдението е, че на всяка итерация, която не е последната, нито един елемент A[1], ..., A[i-1] не участва в нулева тройка.  Това, че външният цикъл терминира по два възможни начина е вярно, но е по-сложно и може да не се споменава. 

Просто да се преразказва алгоритъмът няма смисъл.

Last modified: Wednesday, 5 September 2018, 6:26 PM