[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Messages posted by: petarsor
Forum Index » Profile for petarsor » Messages posted by petarsor
Author Message
BATIR wrote:Nekoja ideja za ovaa zadaca?
Vidov deka ima i druga tema za ovaa zadaca , no ne sakam da preminam direktno na resenieto.

Има само 8 карти.
BATIR wrote:Zdravo. Probuvam da iskucam dijkstra samo so priority_queue, bez koristenje niza dist[]. Kodot ne mi pecati nisto. Kje moze da mi se objasni kade mi e greskata?

Ако нешто не работи како што треба, можеш да пробаш со debug-ирање (види во IDE-то кое го користиш), а можеш и да пробаш да додадеш неколку наредби за печатење за да си ја најдеш грешката. Ќе ти користи и за време на натпревар.

Треба да смениш повеќе работи иначе, еве некои

Тука веројатно мислиш true наместо false.


Тука не мислиш graph[i].size() него веројатно graph[curr.idx].size()


Тука тргни го вториот услов (по &&)

Krenkov wrote:http://hsin.hr/coci/contest2_tasks.pdf

Може да ми помогнете која е математиката во втората задачата? Некоја идеја,насока?

Ви благодарам.


Можеш да ги прочиташ коментарите поврзани со натпреварот/задачите на Codeforces. Обично има дискусија веднаш по некој натпревар.
На пример https://codeforces.com/blog/entry/63165?#comment-471894 но има и други
Perez wrote:znaci imam slucaj ama skrien mi e greshen ... hidden e no po nekoi pretpostavki dojdov do zaklucok deka negoviot OUTPUT e UBAV ...

Поприлично сум сигурен дека ќе си го најдеш проблемот и сам ако ја пререшиш (прекуцаш) задачата. Бидејки не е многу долга, а сигурен сум дека ќе напишеш поубаво решение.

Зошто мислам така? Имаш некои делови од кодот кои се тешки за читање, бидејќи се повторуваш.
На пример, во вториот (вгнезден) for циклус викаш


а потоа имаш if наредби каде што проверуваш дали (gjerdan[j]!='G'), итн.
BATIR wrote:Smetam deka ovaa zadaca se resava so dijkstra , no sakam nekoj da mi dade podetalna ideja.
http://mendo.mk/Task.do?id=707


Пробај сам/а прво да ја решиш, види што е проблемот (дали е пребавно или нешто друго), па потоа може да ти помогнеме. Така најдобро ќе научиш.
За задачава, да, може да се искористи Dijkstra. Пробај и да го искористиш фактот што има само 10 типови на портали.

Еве ти и решение ако заглавиш, ама ти препорачувам да не го гледаш додека не пробаш сам/а.
BATIR wrote:Link do zadacata - http://mendo.mk/algoritmi/Task.do?competition=150&id=176
Ja resavam zadaca transport , od delot mendo.mk/algoritmi, zadacata ocigledno se resava so dijkstra, ja iskucav kod. Funkcionira za prviot odgovor, (minimalnata cena za transport na tovarot od pocetniot do krajniot grad), no za vtoriot odgovor ne funkcionira (brojot na gradovi niz koi se prevezuva tovarot vklucuvajki gi i prviot i poceetniot grad). Ako nekoj ,moze da go razgleda kodot, i da napravi popravka?


Не може со една променлива "passed". Dijkstra не работи на тој начин, ќе имаш многу други градови кои ќе бидат посетени.
Види ги промените во оваа програма (наместо passed да е од тип int, сега е низа - исто како dist)

VlatkoSh wrote: Veke mi se smaci od zadacava

Те разбирам, ама дрвава се многу важни во натпреварите по програмирање, така да не ти е џабе изгубеното време.
Еве ти поправен код.
Обрни внимание дека немаше (sum += *s1.rbegin()) на крајот од for циклусот за да ја ажурираш сумата.
Слично, не можеш да ги сортираш првите K елементи од v на тој начин (јас направив нов вектор vcopy - види долу), бидејќи ако тие ти се сортирани, подоцна во вториот for нема да бришеш точни елементи со erase_single(s1, v[i-k]), итн.


VlatkoSh wrote:A kako da znaeme kade da go insertneme noviot element (v[i])? I dali prvo da se brise stariot (v[i-k]) element pa da se insertne noviot, ili prvo da se insertne noviot pa da se izbrise stariot?

Не е тоа важно. Еве да кажеме, прво да се избрише стариот, па да се стави новиот. И дека новиот елемент секогаш ќе го ставаме во второто множество.

Но, од кога ќе ставиш нов елемент, треба да провериш неколку работи:
- дали во множествата има соодветен број на елементи (на пример, ако бараме медијана од 5 вредности, треба 3 во првото, и 2 во второто). ако има проблем, префрлувај како што опишав погоре (најголемиот од првото во второто, или најмалиот од второто во првото).
- да провериш дали најголемиот елемент од првото е помал/еднаков на најмалиот елемент од второто, бидејќи во првото треба да се помалите а во второто поголемите (ова може да не е како што треба бидејќи горе кажав дека "еве, секогаш ќе ставаме во второто"). ако е така, само направи замена (најголемиот од првото стави го во второто, и најмалиот од второто во првото). кај set/multiset ова вадење, ставање работи во logN време.
VlatkoSh wrote:Ne razbiram kako da se znae dali vo edniot ili vo drugiot heap da se stavi? I kako treba da se implementira heap?

Во едниот ќе ти бидат најмалите, а во другиот најголемите. Ова може да се имплементира со множества во C++ (set, multiset), бидејќи кај нив begin() покажува на најмалиот елемент, а end() - 1 на најголемиот. Ова го има и во предавањата на МЕНДО.
http://mendo.mk/Lecture.do?id=26

На пример, замисли дека во едното множество имаме [11, 12, 13], а во другото [14, 15]. Медијаната е најголемиот елемент во првото множество.
Ако во било кој момент се извади некој елемент од првото или второто множество, можеш да преместиш елемент од едното во другото за пак да има 3 (и тоа 3-те најмали) во едното, и 2 во другото. (тука гледаме пример со 5).
Кога преместуваш, или ќе го преместуваш најголемиот елемент од првото во второто, или најмалиот елемент од второто во првото.

Во set, multiset, можеш лесно да бараш, додаваш и бришеш елементи.
BATIR wrote:Ja resavam studentski prasanja. No ne znam zosto ne e dobar kodot. Ne mozam da si ja najdam greskata.
http://mendo.mk/algoritmi/Task.do?competition=150&id=120
Moze pomos?


Ако нешто не работи, можеш прво да пробаш да го прочиташ кодот така што ќе бараш некоја од "честите" грешки што се прават.
(Има предавање на МЕНДО со наслов "Грешки на кои треба да внимавате", така да можеш да го видиш тоа прво)

На пример, ако имаш низа arr[n], можеш да пристапуваш само до индекси од 0 до n-1. (Хинт: види линија каде што пристапуваш до arr[i+2], и дали е тоа добро).
Има и други проблеми, ама од кога ќе ги поправиш ваквите грешки, и имајќи предвид дека решаваш на МЕНДО каде што можеш да го видиш и примерот [инфо], ќе можеш да си го анализираш кодот дел по дел на твојот компјутер.
BATIR wrote:Fala. Za pomalo ednakvo ne mi tekna No, zosto ne raboti so nuli?

Кажав, поради споредбите.

На пример, разгледај го ова:

Ти проверуваш дали е нула само (dp[i][j+1] != 0). Но што ако е нула (dp[i+1][j])? Тогаш dp[i][j+1] нема да биде помало од dp[i+1][j].

Можеш и со нули, ама доста покомплицирано
BATIR wrote:Zdravo uste ednas. Go resiv problemot, no ispadna deka mi dava nadminat vremenski limit vo slucajot so baranjeto na odgovorot vo vtoriot red , indexite . Eve konecen kod:


Кај мене не работи последниот код (дава надминат временски лимит), па претпоставувам ти треба помош.

Во последниот дел од кодот, само користи помало и еднакво наместо помало при споредбите, и немој да користиш нула (0) туку некој голем број за означување специјални случаи (инаку споредбите нема да ти функционираат).
Вака:

jakov___mitrovski wrote:Ја решавам задачава со алгоритмот на крушкал, и на повеќето тест примери ми вади runtime error.
Ако може мала помош околу грешката во кодов?


Ај вака да те насочам кон проблемот.
Ако ја замениш претпоследната линија со:



Тогаш не дава runtime error, туку погрешен резултат. Значи пристапуваш до ...

Можеш на МЕНДО да симнеш и некој тест случај и да го извршиш локално.
VlatkoSh wrote:Не очекував да биде меморискиот лимит... инаку дали решението ми е на прав пат или треба нешто попаметно? Пробав да ги правам броевите мод 60000011 ама има колизии.

Можеш да пробаш со твојата идеја (MOD) и да ги додаваш елементите во низа, која потоа ќе ја сортираш и ќе гледаш колку еднакви последователни елементи има. Нешто вака.

VlatkoSh wrote:Link: http://mendo.mk/Task.do?id=200

Ne razbiram zosto kodov mi dava Runtime Error za 5/10 testovi? Duri i simnav eden od niv i nemase Runtime Error kaj mene, tuku tocen odgovor.


Во задачата (во сите задачи на МЕНДО и други натпревари) има и мемориски лимит.
Во случајов, имај предвид дека користиш мапа cnt и дека во нејзе додаваш милиони елементи.

Притоа, кај мапа всушност се користи бинарно дрво во позадина, па за секоја клуч всушност се троши меморија за: клучот (во случајов long long 8 бајти), вредноста (4 бајти), два покажувачи лево/десно (за бинарното дрво), итн.
Скоро па сигурно е до тоа. Значи, memory limit. На твојот компјутер немаш таков лимит, па затоа работи, но можеш да отвориш Task Manager на пример (ако користиш Windows) додека работи програмата па и таму да се увериш.
 
Forum Index » Profile for petarsor » Messages posted by petarsor
Go to:   
Powered by JForum 2.1.8 © JForum Team