Messages posted by: petarsor

VlatkoSh wrote:http://mendo.mk/Task.do?id=197
Ne razbiram zosto greedy delot e sekogas tocen? (oficijalno resenie, kako sto znam i edinstveno)

Претпоставувам мислиш на делот со коментарот "//greedy"? Другото е бинарно пребарување.

Ако да, тогаш најлесно е да пробаш со неколку примери, и да се обидеш да најдеш контра примери зошто не би работело.
Кодот за тој дел е поприлично мал. На пример, ќе разбереш дека првиот if услов е да се открие случај кога збирот на сите елементи досега не се доволни да се создадат потребните вредности пред тековниот елемент - што е логично, бидејќи ако збирот е помал тоа значи дека и ако ги искористиме сите монети нема да можеме да вратиме вредност - а новиот елемент е поголем, па тој не може да се искористи.

Би сакал само да споменам дека може да се реши и со испробување на "сите можни решенија", т.е. вредности за "максималниот број на задачи за кои е задолжен еден од членовите на комисијата при оптимална поделба на нивната работа.".
Имено, може да пробаме да видиме дали резултатот може да е 1, па 2, па 3, ..., па 170, и запираме кога ќе најдеме валидна вредност.

VlatkoSh wrote:Link: http://mendo.mk/Task.do?id=801
Moj kod (dobiva TLE, malku optimiziran): http://mendo.mk/User_SubmissionSourceCode.do?id=274277

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?

Gresis. Ne mozhe da ti go vidime kodot bidejki ne mozhe da se gledaat kodovi od drugi lugje preku link (mozhesh da go iskopirash na forumov), ama problemot e shto nekoi polinja kje gi pominuvash po povekje pati (ne znaesh koi ti se vekje poseteni).
Ako ti e klasicno BFS, znachi deka imash vnatre nekoj for koj gi izminuva site edgevi, pa mozhesh vnatre vo forot da stavish eden brojac i da ispechatish kolku operacii ti ima reshenieto (ako simnesh nekoj pogolem test primer od MENDO). Kje vidish deka e pogolem broj od N. So mapa mozhesh i da izbroish po kolku pati doagjash do sekoe pole.

Perez wrote:еве вака јас го напишав и немав проблеми , А нешто по побрз начин ?

Povekje mislev vaka.

Perez wrote:Da toa ako ima 3ka vo nizata ... ami sho ako nema i da sakam da vidam kolku broevi ima pomalku od 3...

EDIT
moja greska bez razlika dali ima 3ka ili nema ...

Da, rabotat lower_bound i upper_bound bez razlika dali taa vrednost postoi ili ne.

Perez wrote:Sakam da znam kako so binary search ... potocno so lower_bound i upper_bound ili ...

Pa da, na primer so niv. Ima dobri tutoriali na MENDO za ova vo delot za Algoritmi.

Eve uste eden hint.

Hint: shto ako imash eden for koj gi izminuva elementite od vtorata (srednata) niza, eden po eden? Da kazheme deka si vo momentov kaj element so vrednost "5" od vtorata niza. Dali mozhesh sega polesno da izbrois kolku ima soodvetni elementi od prvata i tretata niza?
(Ushte eden hint: mozhe, so soodvetna struktura ili ako ti se odnapred sortirani prvata i tretata niza so binary search)

VlatkoSh wrote: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.

Da go minimizirame maksimalnoto rastojanie - koristejki greedy algoritam - za da pravime pateki, a da ne napravime pateku podolga od "d". Koga imame greedy, za da ne pishuvame komplicirani dokazi, najednostavno e da se ubedime vo tocnosta na algoritamot preku kontradikcija ("Zoshto da ne dodademe vrska od najmaliot element, a da se dodade od nekoj drug element ... itn?", dali ima kontra sluchaj, ...)
Barem mene mi e taka najlesno i najbrzo.

Kakvi editoriali ima na Codeforces, ova i ne e tolku loso.

Inaku, toj e najgolemiot paragraf, pa neznam za shto konkretno treba pomosh. Ona shto ne e bash najdobro objasneto e dobro i ednostavno implementirano vo dadenoto reshenie (vednash do tutorialot).
Mozhebi samo ne objasnile deka strukturata za shto zboruvaat e implementirana so set<pair<int, int>> q; (vo reshenieto)
bidejki set e binarno drvo, pa ona shto se dobiva so q.begin() e najmaliot element (koga imame parovi, prvo se gleda par->first pa par->second)

Ако имаме 5 елементи (пр вина) и вредности (пр цени) од 1, 2, 4, 8, 16, тогаш има 2^5 = 32 различни збирови.
1, 2, 1+2, 4, 1+4, 2+4, 1+2+4, 8, 1+8, ...
Со 32 вина, има премногу различни вредности. Да беа цените/вредностите помали, можеби ќе можеше вака.

Дали е подобро да се користи scanf/printf или cin/cout?

Кај повеќето решенија се користи cin/cout, така да претпоставувам дека тоа е полесно, ама па scanf треба да е побрзо.

зошто во делот за интернационални натпревари нема задачи од ЈБОИ 2017?
има од сите други години