често срещани грешки
В решението на задача 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] не участва в нулева тройка. Това, че външният цикъл терминира по два възможни начина е вярно, но е по-сложно и може да не се споменава.
Просто да се преразказва алгоритъмът няма смисъл.