Zadacha

Eto zadacata za koqto govorih. Ochakvam da vidq ideite vi za podhod kum resenieto. Ne publikuvaite kod!!!
I nedejte da pisete gluposti, pls!
---------------------------
Dunio Gorski poluchil malka gorichka ot restituciqta na zamite. Vupreki che zemqta e

mnogo skupa, istinskoto bogatstvo na g-n Gorski sa durvetata v gorata. Povecheto ot tqh sa

izkliuchitelno redki i skupi, poradi koeto g-n Gorski iska da gi ogradi, za da gi predpazi ot

nezelani nabezi. Za sazalenie, edinstveniqt material, ot koito moze da se napravi ograda, sa

samite darveta.
Da si predstavim, che gorskiqt uchastak e pravougalna mreza s N reda i M stulba, v koqto

ima K durveta, vsqko ot tqh razpolozeno v nqkoq ot kletkite na mrezata, kato vav vsqka kletka

moze da ima nai-mnogo edno darvo. Redovete sa nomerirani ot 1 do N, a stulbovete ot 1 do M, i

vsqka ot kletkite e kvadrat sas strana 1 metar. Za vsqko darvo e izvestna cenata mu, i kolko

metra ograda moze da se napravi, ako to se otseche. Ogradata, koqto trqbva da se postroi ste

predstavlqva pravougalnik sas strani, usporedni na stranite na gorskiq uchastak i trqbva da

zagrazda vsichki ne otsecheni darveta. Tq trqbva da minava po liniite na mrezata, taka che vsqka

kletka ili izcqlo se sadarza v ogradenata oblast, ili e izcqlo izvan ogradata. Dopuska se

ogradata da minava po strani na kletki, w koito ima ne otsecheni darveta.
Napisete zadacha, koqto izbira koi darveta da budat otsecheni, taka che s poliuchenata

darvesina da moze da se napravi ograda za ostanalite darveta. Estestveno, zelanieto na g-n Gorski

e sumarnata cena na durvetata koito ste se otrezat, da e vazmozno nai-malka. Ako ima nqkolko

vazmoznosti, udovletvorqvasti uslovieto za minimalna sumarna cena, se iziskva broqt na otrqzanite

darveta da e nai-maluk. Ako i pri tezi usloviq sa dopustimi nqkolko reseniq, da se izvede edno ot

tqh.
Vhodnite danni se sadarzat vav fail s ime OGRADA.INP. V purviq red sa zadadeni celite

chisla N,M i K, razdeleni s po 1 interval (1<=N<=200,1<=M<=200,1<=K<=50). Vseki ot sledvastite K

reda, sadarza opisanieto na edni darvo- 4 celi chisla- I,J,C,L

(1<=I<=N,1<=J<=M,1<=C<=10000,0<=L<=1000),razdeleni s po edin interval. Chisloto I e nomer na

reda, a chisloto J e nomer na stalbata, v koito se namira darvoto; C e cenata mu, a L e kolko

metra ograda moze da se napravi ot tova darvo.
Vasata programa trqbva da izvede namerenoto resenie v tekstov fail s ime OGRADA.OUT.

Purviqt red na faila trqbva da sadarza dve chisla- X i Y, razdeleni s 1 interval. Chisloto X e

sumarnata cena na otrqzanite darveta, a Y- tehniq broi. Vseki ot ostanalite Y reda trqbva da

sadarza po 1 chislo- nomer na otrqzanoto durvo. Nomerata sa v interval [1,k], kato saotvetstvat

na posledovatelnostta po koqto sa zadadeni dannite za darvetata vav vhodniq fail.

Primer:
OGRADA.INP
6 9 6
5 7 10 0
6 1 1 6
4 5 11 6
3 8 10 0
1 9 1 6
3 3 1 0

OGRADA.OUT
13 3
3
5
2


/P.S. AKo trqbva da sravnim s koordiatnata sistema, M=y a N=x/

Ilia Yordanov,
[линк] ; C++ Resources

Moqta ideq za resenie e slednata:
1) Namirame koi darva sa nai-izgodni za rqzane... tova ste stane po formulata:
y/x, kadeto y= za kolko metra ograda stava, x= cenata...
Po tozi nachin razbirame koi sa nai-izgodni da budat otsecheni.
2) Sortirame rezultatite
3) Pochvame ot nai-izgodnite kum po-neizgodnite da pravim proverka. Proverkata se sastoi v tova dali darvoto e otdalecheno ot drugite ili ne... ako da- KLUC! Ako ne- tuk veche trqbva oste proverki da se pravqt...

Tova mi e v obsti linii ideqta...

Vasite kakvi sa?

Ilia Yordanov,
[линк] ; C++ Resources

Идеи на първо четене.
Трябва по-добре да се изследват контурите. Ако са необходими много дървета за оградата и ще трябва да се отсече цял ред по контура, това ще намали дължината на оградата. Ако се маха цял ред, това да бъде скъсяване на по-дългата страна на правоъгълника. Постигат се две цели - първо дърветата там са по-малко и може да бъде постигната по-добра оптимизация при комбиниране с други дървета и второ формата ще се приближи до квадрат, който пък е оптимален по отношение обиколка/площ.

Tova mai ne e triavialna zadacha.
Dokolkoto razbiram se kasae za mnogomerna
optimizatcia. Ako ne sashtestvuva niakoi
dobre izvesten metod za reshavaneto i
moje da se polzva Monte Carlo schema
naprimer:
1) osichame niakolko darveta izbrani sluchaino.
2) presmiatame razhodite
3) ako sa po malki ot prednite opiti
priemame stapkata, ako ne priemame ia s niakakva veroiatnost.
4) na baza na presishnite otsecheni darveta
otsichme niakolko novi i zasajdame niakolko
ot ita deto sme otsiakli (t.e pravim leki izmenenia v nachalnata hipoteza). i povtariame stapkite otnovo.
Po ideia tazi protcedura triabva da e shodiashta kam edno ot vazmojnite reshenia za
dadenia izbor na nachalno razpredelenie
v reshetkata.
Predlojenia metod e po podobie na dobre izvestnia metod Metropolis MC za sluchaia na
model na Izing kogato imame reshetka
s 2 vazmojni sastoiania vav vseki ot aglite na reshetkata (nagore i nadolu).
Ako niakoi se probva na toia metod shte mi e
interesno kakvi razultati se poluchavat.
Samia izbor koi darveta da se otsekat na viska stapka v zavisimost ot predno otsechenite sahto e interesno da se obmisli.

Може би наистина е добре да се използва някакъв подобен метод. Освен очевидната трудност при създаване на математическия модел - функцията, на която ще търсим екстремум, допълнителна трудност е, че една от променливите трябва да е с целочислени стойности - броя на отсечените дървета, а знаеш че целочисленото оптимиране е много рошаво. Ако използваш методи, които ти дават резултат реално число, например 57.9230487, това не означава че решението е 57, нито дори 56. Няма дори гаранция че решението е някъде "наблизо", въпреки, че ако функцията не е някаква много "крива", наистина е тука някъде.

V sluchaia na MC osnovnia problem e che
moje da se popadne v lokalen minimum
za koito ne e garantcia che e globalnia.
Ima razbirase i metodi s koito moje da
se podobriat neshtata za da se tarsi
globalen monimum. Edna druga vazmojnost za
koiato se seshtam e da se napishe programa
izpolzvashta "genetic algorithm".
Tam schemata e podobna na MC, samo che se
praviat kopia na gorata na vsiaka stapka
posle se pravi malka "mutacia" i se izbirat
mutacii koito sa uspeshni a tia koito ne sa
se zabraviat.

ami ima niakolko nachina...
gledam, che veche ima niakolko predlojenia, koito nikak ne sa loshi
az za da ne povtariam nekoe ot tiah bih predlojil slednoto: v nachaloto se priema, che vsichki darveta sa otsecheni (znae se koe kade sedi). sled tova se sortirat po cena i kolichestvo material. zapochva se otzad napred da se postaviat nai-neizgodnite za otsichane darveta. tova se povtaria dokato se izpulni uslovieto za obgrajdane (ili dokato ne svarshat durvetata). ako svurshat bez da e izpulneno uslovieto - togava variant "loobian"

Hmmm mrazim teoritichnite zadachi zashtoto sa strashno nerealni a sa nerealni zashtoto se ochakwa da reshish palniq klas .... ako bqha fiksiran razmera na nqkoe po malko cheslo i naistina mi trqbwashe da se naprawi waprosnata optimizaciq i da e sigurno togawa ne bih se zachudil a wednaga pisha ochewidniq BFMI algoritam i otiwam da piq kafe. kato se warna rezultatite me chakat :))
Ama taq teoriq iziskwa po izwrateni podhodi: reshawash zadachata kato schesh parwo naj ewtinite darweta. reshawash zadachata kato sechesh naj debelite darweta reshawash zadachata kato sechesh naj otdalechenite(ot otchkata na sgastqwane) darweta. reshawash zadachata ckato sechesh optimalnite po dwojki. sortirash rezultatite izbirash naj dobriq i se nadqwash towa da e reshenieto.


sega kato mislq moje da se naprawi optimiziran podhod na tema BFI parwo opredelqsh otsichaki naj debelite kolko e cenata na gorata i pole puskah BFI kato ako senata padne pod taka opredelenata se prawi direktno wrashtane. Ako se stigne do rezultat i senata e po-niska se zapomnq reshenieto i cenata i pak :)) taka sha imame rezultat i toj sha e prawiln pri towa nakysqwajki wremeto na BFI


I love those (1+|k|)GHz processors

hmm...spored men nito edin ot izlozhenite do tuka metodi ne _garantira_ namirane na optimalno reshenie
edin nachin da se nameri winagi optimalno reshenie e da se izpolzwa dinamichno optimirane...loshoto e che twa e i nai-bawnoto wyzmozhno reshenie...ama neshto w momenta ne se seshtam za drugo deto da e s prilichna algoritmichna slozhnost

obshto wzeto problemyt w taq zadacha e che oswen cenata/dylzhinata na dyrwo ima i parametyr dylzhina na ogradata, koito se meni w zawisimost ot tuj kwo se seche...hmm, mozhe da se wywede termin "grupowa obshta dylzhina" i "obshta cena" za dyrweta na edin red i edin stylb kogato sa w kraq na prawoygylnika kato kym sumarnata dylzhina na dyrwetata tam e dobawena i tazi koqto se spestqwa ako te se otsekat, t.e. wsqko dyrwo ot tozi red(stylb) po otdelno ne e nishto osobeno, no ako se otseche celiq red(stylb) rabotata stawa na dalawera...naprimer togawa mozhe wseki red/stylb da se razglezhda kato "obobshteno" dyrwo pri nqkoi ot drugite metodi deto sa spomenati (makar che togawa nqma da se mine bez dinaimchno update-wane na redowete/stylbowete pri otsichane na nqkoe dyrwo ot tqh)...abe izobshto takiwa mi ti raboti mi se wyrtqt iz glawata kato q cheta zadachata - mozhe i gluposti da sa

be maj ne e bash taka... ako osechesh cql stalb pechelish celi.... 2 metra mnogo strashno mnogo! a ot druga strana ako zaradi edno darwo obikolish sto akra polqna sashto ne e dalawersko :))

ami imenno - 2 metra koito mogat da sa na dalawera
pri twa ako razkarash i syotwetniq red koito se presicha tam kelepiryt shte se digne

i zabelezhi che pri toq podhod samotnite yglowi dyrweta shte bydat sred pyrwite izsecheni shtoto pri tqh dalawerata e golqma, t.e. polzata e 2 metra ako ima syseden sttylb, no ako nqma se uwelichawa t.e. "obshtata dylzhina" na stylba se uwelichawa s poweche

da be ama q si predstawi slednoto anti-edem-sko postroqwane na gorata - naj otwanka naj skapite a po-nawyte w centara naj ewtinite i naj debelite :))
izobshto najkata si ebalo (s izwinenie kym detskata publika) za towa naj chisto si e dinamichna optimizaciq i twa e!

abe twa che si ebalo maikata (s i zwinenie kym detskata publika) e qsno ;)
no zabelezhi che oswen "obshtata dylzhina" (s dobaweniq w neq ewentualen kelepir) ima i "obshta cena"...t.e. w ekstremniq sluchaj kogato po kraq sa nai-nai-skypite dyrweta te prosto nqma da postradat shtoto shte se poluchi che ne e na dalawera da se seche celiq red/stylb (koito za nas sa "obobshteni dyrweta") w srawnenie s tiq ewtinii w centyra...demek toq saluchai ne prowalq zamisyla

mnogo interesna zada4ka :-) predlaga mnogo re6eniq no kakwo bi stanalo ako ne e kazano 4e ogradata trqbwa da e prawoygylnik a nqkakwa zatworena kriwa koeto e po gyzrsko :-)
sega po zada4ata: wseki algoritym koito se bazira na ne6to kato towa koeto si predlovil ne garantira wqrno re6enie 'lakomite' algoritmi po princip se izpolzwat kogato e nuvno da e napylno to4no towa koeto se polu4awa naprimer ako trqbwa6e da se izpolzwa otgowora w gorskoto golqma rabota 4e 6te otsekat edno ili dwe dyrweta powe4e no ako trqbwa to4no da se opredeli programer i SDR ti predlagat to4noto re6enie ili pylnoto iz4erpwane da no towa e dosta bawno kato se ima predwid ma6taba na gorata wse pak s dosta optimizacii move da se postigne edna dobra slovnost
ideqta s izsi4aneto na wsi4ki dyrweta sy6to ne e lo6a towa mi hrumna i na men kato widqh zada4ata (malko po dobra e ot mahaneto na dadeno dyrwo poneve kato gi mahne6 wsi4kite ti znae6 kolko plo6t move da se zagradi s tqh i pak po sy6tiq na4im pri postawqneto na dyrwo samo prowerqwa6 s kolko se uweli4awa perimetyra na prawoygylnika no towa e 'lakom' algoritym koito ne winagi dawa prawilni rezultati no pak ti kazwam 4e ima slu4ai w koito e po uda4en naprimer ako wremeto za izpylnenie e re6awa6to)
eto ti i moqta ideq za cqlostno iz4erpwane (gledah da ne se poftarq s predlovenite do sega): move da se izpolzwa fakta 4e igradata e prawoygylnik w nai lo6iq slu4ai ima6 da proweri6 za dosta prawoygylnika no pri malko optimizirane dota move da se ponivi slovnostta w nai dobriq slu4ai s dobra optimizaciq trqbwa da se postigne O(n) = const a w nai lo6iq ne mi se smqta no predpolagam 4e 6te e O(n) = n*n koeto spored men 6te se dostigne mnogo rqdko
towa e algoritym koito wseki move sam da si napi6e za towa nqma da te zanimawam s gluposti samo nqkolko optimizacii: namirame prawoygylnika koito zagravda wsi4ki dyrweta qsno e za6to drugo e ako ima w dwa protiwopolovni ygyla na prawoygylnika dyrweta (trqbwa da se wnimawa da se mahnat i ot dwata diagonala ednowremenno bez da se proweri towa) to sgurno e 4e pone edno ot tqh trqbwa da byde otse4eno pri prowerkata sa krai na rekursiqta ne e nuvno da se prowerqwa 4ak do poslednoto dyrwo move primerno da se syobrazi i fakta 4e ako ima6 4 dyrweta edno do drugo tt kato se otse4e edno ot tqh perimetyra ne
tt
namalqwa (razbira se ako se prilaga towa e dobred da ne e samo za 4 dyrwata) ... move da se izmislqt o6te optimizacii no ne e lo6o predi da se sedni da se misli da se probwa kak se sprawq programata poneve prowertata e dosta oprostena razbira se ne da prowerqwa6 za wseki prawoygylnik kolko to4no dyrweta sa izwyn nego a samo da dobawa6 broq na tezi koito sa se okazali izwyn sled promqnata mu i da wadi6 ot perimetyra stypkata s koqto se promenq a ako znae6 i nqkoq tehnika za optimizirano srawnenie ne e lo6o naprimer 'cmp' e dwa ti po byrzo ot standartnoto C/C++ 'if' razlikata e towa 4e 'if' prawi o6te nqkolko ne6ta oswen 4e wika 'cmp' e osnowata si a i edno mnogo bawno ne6to e preobrazywaneto na tipowe (int)float primerno no towa samo za informaciq move da ne go znae6
stiga tolkowa 4e wseh da pi6a gluposti a rabota me 4aka

neshto ne razbrah sywsem dobre towa deto go razprawqsh...dokolkoto shwanah predlagash prowerka na wyzmozhnite prawoygylnici-ogradi...loshoto e che dori i da namerish prawilniq prawoygylnik towa ne ti dawa dyrwetata koito trqbwa da se otsekat shtoto mozhe da ima takiwa i wytre w prawoygylika...a inache slozhnostta w loshiq sluchai izglezhda da e neshto ot porqdyka na M*M*N*N...

abe rabotata mai naistina e debela(ne che mnogo mi se misli 8-)
spored men pri nalicieto na 3 parametara - daljina, cena ,broi Dynamic Programming dosta zor ste vidi no drugo edva li ste moje da se izmisli. Ako iskash idi na acm.uva.es/problemset tam ima okolo 1000 zadachi za programirane koito se resavat i prastat online i vednaga ti gi oceniavat i vrastat otgovor. Ta potarsi niakoia podobna(ako ia niama veche sastata 8-) i vij klasaciata na resilite ia. Sled tova v bazata im danni im izvleci mailovete i razprastai te ste ti kajat kakvo sa izmislili po vaprosa moje i da ima nesto hitro naistina.

a mejdu drugoto otkade tocno ia izkopa zadachata ?

[линк]

zadachata e davana na ACM sastezanie
tova e saita na sastezanieto vav vremeto na samoto sastezanie nikoi ne e uspial da ia reshi dokolkoto vidiah
inache juri-to sa dali niakakvo reshenie koeto e namirane na Convex Hull+Backtracking
obsto vzeto mrasna rabota ...

mi da - tova e vtorata zadacha - horata $50 davat za neia, ei! :)

sha sa setish