[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: VlatkoSh
Forum Index » Profile for VlatkoSh » Messages posted by VlatkoSh
Author Message
Runtime error cesto se dobiva koga:
1) alociras premnogu memorija odednas
pr.
2) imas Out Of Bounds error
pr.

Ti go pravis 2). Imas ama podole pravis za i = 0, 1, 2, ..., 29 sto dava Runtime Error.
Link: http://mendo.mk/Task.do?id=801
Moj kod:




Ne razbiram zosto prosto BFS e presporo za zadacava. BFS ima O(V + E) kompleksnost, vo zadacava najlos slucaj e O(N + N*(N-1)/2) = O(N^2), ama ova nema smisla, bidekji odgovorot (najkratok pat od S do T) ke se najde relativno brzo. Ili gresam?
Ok, ja razbrav i ja resiv. Fala mn! Inaku, prv pat srekjavam zadaca vo koja treba da se /izgradi/ graf, mnogu interesno
petarsor wrote:Kakvi editoriali ima na Codeforces, ova i ne e tolku loso.
Inaku, toj e najgolemiot paragraf, pa neznam za shto konkretno treba pomosh.


Vo pravo si, trebase podobro da objasnam. Ne razbiram sto saka da kaze vo boldiranoto:


Also let's keep all free vertices forming the diameter in some data structure which allows us to take the vertex with the minimum maximal distance to any other vertex and remove such vertices. It can be done by, for example, set of pairs (distv,v), where distv is a maximum distance from the vertex v to any other vertex. Now let's add all vertices from starting from the vertex d+1(0-indexed) to the vertex n−1, let the current vertex be u. We get the vertex with the minimum maximal distance to any other vertex, let it be v. Now we increase the degree of vertices u and v, add the edge between they, and if v still be free, return it to the data structure, otherwise remove it. The same with the vertex u (it is obvious that its maximal distance to any other vertex will be equals distv+1).


Minimum maximal distance? Od kade go dobiva ova? Prespostavuvam deka so ova se obiduva da go napravi drvoto taka sto nema pateka megu koi bilo 2 teminja podolga od d, ama ne razbiram kako.
Линк за задачата

Задачата бара да се направи дрво со n темиња, со дијаметар од d и секое теме може да има најмногу k степен. 1 <= n, d, k <= 400000
Сам успеав само дијаметарот да го направам. Меѓутоа, не разбирам како да ги поврзам останатите темиња. Ова е едиториалот. Во едиториалот, не можам да го разбирам третиот параграф, односно делот после правењето на првите d+1 темиња (дијаметарот). Идеи?
Бидеќи никој не ми одговори повеќе од еден ден, одлучив да поразмислам уште малку. Одговорот е дека цената и вредноста на вино е преголема.
Задача: http://mendo.mk/Task.do?id=57

После читајќи го ова, не разбирам зошто не е спомнато динамичко за решавање за задачава? Дали не е можно или е преспоро? Јас пробав ама добивам Runtime Error.

Eве псевдокод

Бидејќи money_spent и gained_value можат да стигнат до 32*30000000, користам vector<map<int, map<int, int>>> за dp за да има доволно меморија.
Ова ми дава WA на еден кејс и Runtime Error на повеќе.
Razbiram, fala!
Link - http://mendo.mk/Task.do?id=290

Ne ja razbiram slednava situacija



Ako treba da napravi 3 cekori na nekoja strana, dali ako otide nadesno ke vleze vo izlezot?
MOI wrote:
VlatkoSh wrote:Каде е грешката?

Не ти е баш точно ова:     Бројот на парови е: (X над 2)/2 (секој пар ќе се одбере 2 пати)
https://en.wikipedia.org/wiki/Combination


Ah fala, amaterska greska
http://mendo.mk/Task.do?id=137

Мојот обид:

Нека бројот на прегледувачи е Х
За К >= N, Х=1 е најбрзо.
При договорањето, секој пар од прегледувачи треба да зборува за К минути. Бројот на парови е: (X над 2)/2 (секој пар ќе се одбере 2 пати). Според тоа бројот на минути на прегледување е:

При прегледувањето, ги делиме задачите за секој прегледувач да има ист број; Ако има остаток, тој е помал од Х и со нив прегледувачите завршуваат за 1 минута. Времето е:

Вкупното време е збирот на двата израза горе.

Проверуваме за Х од 1 до N. Oчигледно Х <= N (на пр. за 100 задачи, 100 и 9999 прегледувачи ќе ги прегледаат за 1 минута, а (Х над 2) се зголемува)

Каде е грешката?

Kod:
fala
http://mendo.mk/Task.do?id=792

Заглавив на делот како да го одредам Х-тиот по ред збор. Се разбира, не може да се генерираат сите можни зборови и да се подредат. Значи мора да има некоја финта за да се одреди пермутацијата брзо.
Имам vector од string-ови, каде i-тиот стринг ги има сите можности за i-тиот # во оригиналниот збор. Според мојата идеја, ги подредив сите стрингови лексикографски. Сега само некако треба да се одредат index-ите во секој стринг за која буква ќе биде на крај, користејќи го само X...

Еве пример инпут

Првиот # е a, b, или c, вториот # е d, e, или f, третиот е # g, h, или i.
Сите можности за #те, лексикографски подредени се:
adg adh adi aeg aeh aei afg afh afi bdg bdg bdi beg beh bei bfg bfh bfi cdg cdh cdi ceg ceh cei cfg cfh cfi

Еве ми го кодот...


Се разбира, можеби има друго решение кое не го гледам (делов на којшто заглавив ми изгледа претежок за задача на регионален). Ако може помош???
Не е сложено решението воопшто; како што кажав, само динамичко програмирање.

Динамичко програмирање не е лесно.
despotovski01 wrote:
Сега добива runtime error бидејќи не проверуваш дали векторите имаат должина поголема од 0 пред индексирање кај овој дел од кодот:

Справи се со ова и не би требало веќе да добиваш runtime грешки. Имаш уште еден пропуст во решението, но тоа ќе го оставам на тебе да го увидиш.

Problem fixed, thanks
 
Forum Index » Profile for VlatkoSh » Messages posted by VlatkoSh
Go to:   
Powered by JForum 2.1.8 © JForum Team