Messages posted by: despotovski01

Задачата е наменета да се реши со динамичко програмирање, само што твоето решение го надминува меморискиот лимит (пресметај ги димензиите на dp матрицата и лесно ќе се увериш во тоа).
За да се надмине овој проблем, клучно е да се увиди кои податоци не треба да ги чуваме. За да пресметаме произволен елемент од матрицата dp[i][j], нас ни требаат само вредностите од редот i-1, сите останати редици не ни играат улога, од што може да се заклучи дека во еден момент нам ни е потребно да чуваме само 2 редици од матрицата (претходната редица и таа што во сегашниот момент ја пресметуваме), што многу ни ја намалува меморијата.

Perez wrote:Дали се вршат последователно инструкциите или уште првиот рекурзивен повик се враќаме k+1 ?

Прво целосно се извршува првата рекурзија, па потоа втората.

Помош за рекурзивни функции можеш да најдеш тука (или од било кој друг релевантен извор): https://www.hackerearth.com/practice/notes/working-of-recursive-function

Нека моментално го разгледуваме k-тиот елемент од множеството. Имаме две опции за него, или тој влегува во тековните подмножества што ги генерираме, или не го земаме во нив. Во првиот рекурзивен повик, ги разгледуваме сите подмножества кои не го содржат тековниот елемент, а во вториот, сите кои го содржат.

Може да има повеќе причини зошто не напредуваш. Можеби решаваш само задачи кои се лесни за тебе, можеби не решаваш доволно задачи, можеби премногу лесно се откажуваш кога ќе заглавиш со задача, или пак немаш доволно познавање од основите на алгоритми и податочни структури и дискретна математика. Можно е твојот проблем да е комбинација од горенаведените причини.

Доколку ти фалат основите на алгоритми и податочни структури, на интернет има безброј книги и курсеви кои би ти помогнале во тоа, многу од нив се и бесплатни. Со нивна помош ќе научиш повеќе за основните податочни структури, како листи, редици, стекови, дрва, и за основните алгоритми од разни категории. Ова се моите препораки:

Algorithms, Part 1 by Princeton University
Algorithms, Part 2 by Princeton University
Algorithms by Stanford University
Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne
Introduction to Algorithms, 3rd edition (CLRS) by Thomas Cormen
Competitive Programmer's Handbook

Како што кажав претходно, можеби имаш погрешна стратегија за вежбање. Иако тоа е субјективна работа, можно е да грешиш со изборот на задачи за вежбање. Би ти препорачал секогаш да пробуваш да решаваш малку потешки задачи од тие што се лесни за тебе, бидејќи тоа е најприродниот начин да напредуваш. Ако одбереш прелесни задачи, нема да научиш ништо ново, додека претешките задачи немаш реалистична шанса да ги решиш.

Не знам колку време посветуваш дневно/неделно на решавање задачи и на учење, но ако си сериозен за подобрување, според мене добар план е секој ден да решиш барем по една задача и да научиш нешто ново. Секако, ќе има и денови кога нема да можеш да решаваш, но ја разбираш поентата, треба континуирано да вежбаш и да учиш.
Мендо не е единствен извор на задачи. Можеш да најдеш интересни задачи на многу други страници, како на пример CodeForces, HackerRank, TopCoder, CodeChef и многу други. На повеќето од нив има и објаснувања за повеќето од задачите, па ако заглавиш некаде, можеш да го прочиташ тоа што ти фали и да ја решиш задачата.

Можеби имам нешто пропуштено, но мислам дека овој предлог би ти помогнал да се подобриш во решавањето. Have fun

Не е погрешен случајот. Можеш 6 пати да го притиснеш + копчето и да стигнеш до 106. Имаш грешка во алгоритмот, пробај да ја најдеш.

Можеме барокните згради да ги замислиме како правоаголници кои се шират секој месец во сите четири правци, горе, доле, лево и десно. Според тоа, ако барокната зграда на почетокот се наоѓа на позиција (x, y), тогаш за N месеци таа ќе го зафаќа правоаголникот со горна-лева координата (max(1, x - N), max(1, y - N)) и долна-десна координата (min(WIDTH, x + N), min(HEIGHT, y + N)). Притоа, сметаме дека горното-лево поле има координати (0, 0), а координатниот систем има ширина WIDTH и висина HEIGHT.

Проблемот успешно го сведовме на познатиот геометриски проблем на наоѓање на плоштина на поклопувачи правоаголници, кој можеме да го решиме со помош на line-sweep техниката.

Бидејќи кодот е обемен, го ставив на Pastebin, и може да се најде на следниов линк: https://pastebin.com/unpBwXzs

Повеќе за line-sweep можеш да прочиташ тука: https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/

Можеме да искориситме бинарно пребарување. Нека a[x] изнесува сумата на траењата на сите епизоди од првата до x-тата. Лесно може да се увиди дека ова е строго растечка низа, бидејќи секоја епизода трае позитивен број минути. Тогаш, за секоја почетна епиода x, со бинарно пребарување можеме да најдеме колку последователни епизоди можеме да изгледаме:

HoulaHulaHoop wrote:Но како тоа? Зар 'оптималниот' палиндром не е оној кој се избира во оптималното решение?

За 'оптимален' мислев тој што делува дека е најдобро да се одбере во еден чекор со некој алчен критериум, пример најголемиот, најмалиот, итн. Не мора да значи ако еден палиндром делува дека е најдобар во еден момент, дека тој спаѓа во оптималното решение.

HoulaHulaHoop wrote:А како заклучивте дека 'Greedy' не поминува на оваа задача?

Проблемов го нема алчното својство, односно не мора да значи дека ако при секој чекор го земеме 'оптималниот' палиндром, дека тој мора да биде земен и во оптималното решение.

За темава се има дискутирано и порано: http://mendo.mk/jforum/posts/list/388.page

Greedy не проаѓа за оваа задача, ќе треба со динамичко програмирање да ја решиш.

stoki97 wrote:Probav so matrica ama na dump pagja neznam zosto eve go kodot.

Грешката ти е во оваа линија код:

Проверката дали координатите влегуваат во границите ја правиш откако пробуваш да го прочиташ полето од матрицата, па затоа добиваш и runtime error. Оваа линија се јавува во bfs и во bfs2 процедурата. Стави ги проверките за координатите на почеток и би требало да работи.

stoki97 wrote: Moze pokonkretno da ponudite nekoj hint za Љубов zosto napisav algoritam sto pominuva 16/20 a za ostanatite 4 test slucai pagja na limit.. Gi probav tie test slucai i tocen resultat davaat ama pagjaat na limit.

Inace toa sto pravam vo kratki crti e pustam bfs od Saso i ako najde pat do Elena toas go pecati najkratkiot pat do krajot , ako ne prebaruva bari koi mozi da se pomini niz niv i gi cuva vo mapa .

so Vtoriot BFS pocnuva od krajot odnosno od Elena i bara od tie barite koj bea zacuvani vo mapata , ako najde togas go sporeduva maximumPatot so patot do pronajdenata bara. Vo slucaj ako e pogolg patot do barata od maximumot togas go setira patot do pronajdenata bara na maximalenPat.

Mala optimizacija napraviv so toa sto gi brojam vo prviot BFS brojot na bari a potoa gi odzemam vo vtoriot i ako se potrosi brojot na bari koj bea markirani kako proodni vo prviot BFS togas prekinuva programata i pecati (-1). PAtot za (i, j) tata bara koja e pronajdena so vtoriot BFS i markirana od prviot se presmetuva taka sto patot do barata koj bese presmetan se sobira so izminatiot pat od vtoriot BFS + 1 i taka se dobiva patot od Elena do Sase preku barata.

Kodot mi fati okolu 151 red

Најверојатно користењето на map ти е проблемот. Map структурата во C++ е имплементирана како бинарно пребарувачко дрво, па секое запишување/пребарување го извршува во O(logN) време во најдобар случај. Ако ја смениш map структурата со обична матрица многу ќе ги убрзаш овие операции, односно ќе станат O(1).

https://www.e-olymp.com/en/problems/1064
https://www.e-olymp.com/en/problems/1060

Еве многу едноставни примери што се решаваат без некои потешкотии. На CodeFu имаш десетици вакви задачи, можеш да ги побараш и таму.

Вакви задачи се сведуваат на пребарување низ графови и обично се решаваат со BFS (Breadth-First Search) или DFS (Depth-first Search). Сите задачи што ги посочи се решаваат со овој алгоритам, но секако со мали модификации за дадениот проблем.
Задачата Градинар се сведува на откривање на она поле кое може да биде достигнато од најголем број на цвеќиња.
Љубов е многу слична како Градинар, се сведува на наоѓање на ѕидот P за кого збирот од должината на најкраткиот пат од Сашо до P и најкраткиот пат од Елена до P е најголем.
За Чоколадна коцка, проблемот го сведуваме на наоѓање на максималната длабочина на пребарување до која можеме да стигнеме, и колку елементи (коцки) имаме на таа длабочина.

Помош за точка за рамотежа: не мора постојано да ги пресметувате сумите на интервалите. Нека s[k] е сумата на првите k броеви. Тогаш за било кое i < k, сумата на интервалот [i,k] може да се пресмета како s[k] - s[i-1]: