[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: OP Magic Potato
Forum Index » Profile for OP Magic Potato » Messages posted by OP Magic Potato
Author Message
@ovlasten za mendo
stavi kopce za da mozam da gi gledam site prateni reshenija za odredena zadaca na samiot link na zadacata, ne da moram da go baram reshenieto vo "reshenija" !!!
ima nekolku nacini.

>dinamicno
>matematicki brute force
>BIT

glavnata ideja na site 3 e da go iskoristish slednovo:
za bilo koi dve mnozestva A i B, mozesh da stignesh od A do B vo najvekje |A|+|B|-2 cekori, kade shto zbir_na_elementi(A)==zbir_na_elementi(B) && |A| oznacuva brojot na elementi vo A
Segment tree ili binary index tree, ama prvo treba da gi kompresirash broevite bidejki se mnogu golemi.

posle za sekoe brojce od nizata (i) so pomosh na BIT ili segment tree ke odredish kolku od broevite pred nego se pogolemi od nego(k) i kolku od broevite posle nego se pomali od nego(l) i brojot na trojki kade sto "i" e sredno ke bide k*l. rezultatot e zbirot na k*l za sekoe i
fala mnogu D
eve mi go kodot:

mi pagja na 13tiot test primer, probuvam racno da gi stavam brojcinjata i pak mi ispagja pogolem rezultat od tocniot izlez
13 test primer:
input:
??????-(??-?????)+(???-(?+????-(?+???+(????+??????)-?+?????)-??+????))+(????+???+??????)+??????+(???+(???+???))+(?+???)
4134559295420993590475024322731223116069607037733078291231138059667870621692737
output:
4197600

mojata programa pecati:
4204380
si ja najdov greskata
linija 40 treba da bide:
seg[i]+=k;
mi treba pomosh so zadacava: http://www.spoj.pl/problems/DCEPC206/

eve mi go reshenieto:

prvpat kucam segment tree pa ne mozam da si ja najdam greskata.
p.s. pagja na wrong answer >
xD
filip_bujaroski wrote:
OP Magic Potato wrote:@site, da failnete sto e mozno povekje utre, da vi se blokiraaat mozocite, nisto da ne mozete da reshite xDD


Haters gonna hate...
Potatoes gonna potate


tocno taka
da ne ke treba da donesam utre printer na PMF? da ne ispadne kako minatata godina da ne mozete diplomite da gi isprintate DDDDDDDDDDDDDDDDD
@site, da failnete sto e mozno povekje utre, da vi se blokiraaat mozocite, nisto da ne mozete da reshite xDD
Ne sum siguren, ama bi trebalo da moze da te piknime vo internatot vo yahya kemal.

p.s. cura 18+ moze da se desi, a sigurno e deka ke bide mnogu interesno
Sakam da naznacam deka nacinot na odbiranje na pokanetite ucenici na drzavniot natprevar e prilicno legitimen

GJ
bedzo wrote:А пробај со вакво динамичко. Гледаш во која кутија можеш најмногу предмети да ставиш, па ги вадиш предметите што си ги искористил и продолжуваш за сите кутии, ако ти останале елементи испечати 0, ако не испечати 1. Ова е knapsack проблем како што гледам..

ne te razbiram so sakash da pravish, a inache site kutii imaat ist kapacitet.

obi1kenobi wrote:Ова е integer multi-knapsack проблем и по дефиниција нема никакво друго решение освен брутфорс. Користи дфс и ќе биде во ред.

EDIT: Дури сега видов дека сите кутии се со иста големина. Со тоа ограничување, постои динамичко решение.


go razmisliv ova reshenie, ama nema da mi pomogne deka DFS-to ke treba da go povtoruvam 2^N pati (najlosh slucaj N=20,slozenosta O((2^20)*DFS))
obi1kenobi wrote:Зошто не поминува greedy? Или не сфаќам што прашуваш, или нема никаков проблем со greedy-то.


**ne go opishav inputot dobro, vo prviot red se dadeni 3 integers N(brojot na predmeti), M(brojot na kutii) i G(volumenot na site kutii posebno), a vo vtoriot red se dadeni N integers, broevi koi gi opishuvaat volumenite na predmetite.

jas mislam na vakvo greedy: gi sortirash predmetite po rastecki redosled, i polnish edna kutija se dodeka sobira(prvo go stavsh prviot element, pa vtoriot, pa tretiot se dodeka moze kutijata da sobere). koga ke go nadminesh kapacitetot na prvata kutija, probuvash da ja napolnish vtorata kutija itn. Ova go povtoruvash se dodeka ima mesto vo kutiite za sledniot predmet, ili go povtoruvash se dodeka ima predmeti za stavanje. Na kraj, ako si gi iskoristil site elementi pecatish 1(moze elementite da se smestat vo kutiite), vo sprotivno pecatish 0.

ova reshenie ne e tocno, kontra primer e
N: 8 // dadeni se 8 predmeti
M: 4 // dadeni se 4 kutii
G: 15 // prvata kutija ima volumen 15, vtorata 15, tretata 15 i cetvrtata kutija ima volumen 15.
N-te predmeti: 7 8 6 9 5 10 4 11 // predmetite se so vloumen: 7, 8, 6, 9, 5, 10, 11;

greedyto vaka ke raboti:
ja sortira nizata: 4 5 6 7 8 9 10 11
i gi stava predmetite:
vo prvata kutija ke gi stavi predmetite so V = 4 5 6
vo vtorata kutija ke gi stavi predmetite so V = 7 8
vo tretata kutija ke gi stavi predmetie so V=9 (samo eden predmet, bidejki sledniot e so V=10 i nema da go sobere vo preostanatiot prostor)
vo cetvrtata kutija ke go stavi predmetite so V=10
ke ostane predmetot so V=11, odnosno programa ke vrati 0 bidejki ne usteala da gi smesti site predmeti vo kutiite

tocniot rezultat e 1
vo prvata kutija da vlezat predmetite so V=7 8
vo vtorata kutija da vlezat predmetite so V=6 9
vo tretata kutija da vlezat predmetite so V=5 10
vo cetvrtata kutija da vlezat predmetite so V=4 11
bidejki site predmeti se iskoristeni tocnoto reshenie e 1(predmetite mozat da se smestat vo kutiite)
 
Forum Index » Profile for OP Magic Potato » Messages posted by OP Magic Potato
Go to:   
Powered by JForum 2.1.8 © JForum Team