OJI 11-12

[•sanitarium]

au fost criminale!!!!

care a dat problema aia de geometrieeeeeeeee?

te pregatesti un an facand chestii frumoase si iti dau asa ceva si te omoara.

sunt cumva singurul cu punctajul fatidic de 23 de puncte?

[•SleepyOverlord]

Geometria chiar era urata, insa cealalta mi s-a parut facubila. Shi dupa cum am vazut se dadea 30% numai pe determinarea drumului minim. Asa ca..

[•rush]

Prima problema mie mi s-a parut imposibila iar a doua era si ea destul de grea dar aboradabila! 30% pt. timpul minim din prob2. nu era chiar asa usor de obtinut pt. ca nu mergea un simplu roy floyd sau dijktra cum parea la prima vedere! in arges singurul care a luat ceva la prima problema este cel care se duce si la nationala si a facut cu back! Deci spuneti si voi ceva daca mai ramane ceva de zis!!!

[•sanitarium]

problema cu lanterna nu am inteles-o. zicea prin enunt ca primeaza timpul minim, adica nu conteaza puterea ci timpul. si mai scria ca se garanteaza existenta solutiei. nu am prea inteles eu ce cauta k ala pe acolo. nici nu am putut sa intreb pe nimieni pt lamuriri asa ca am facut ce a priceput limba mea romana. bineinteles, nu ceea ce se cerea.

[•SleepyOverlord]

Din ce am inteles eu, k era valoarea maxima in wati.. shi trebuia sa gasesti timpul minim, shi numarul de wati minim, pentru care se obtine timpul minim, care dupa mine se poate gasi cu cautare binara in cel mai rau caz, insa cred ca nu e necesar. Iar geometria nu era imposibila, ci necesita niste cunostinte mai vaste... (o, shi viteza extrem de mare la implementare)

[•rush]

la problema 1 zic eu ca trebuiau niste cunostinte mult mai mult decat vaste pt. rezolvarea ei iar la cealalta trebuia det. timpul minim insa totodata in acest timp trebuia sa folosesti o lanterna de maxim k wati! Lucru care nu era posibil pt. primul timp minim gasit, in majoritatea testelor! De aceea multi n-au luat toate punctele care se dadeau pt. timpul minim!

[Boogieman]

la prima? cunostinte vaste vaste?
era doar mult de lucru
eu mi-am pierdu 2 ore jumate cu ea si pe cealalta care era super simpla nu am mai facut nimic( am crezut ca o sa mearga lejer cu rotfloyd sau dijksta - pe draq) :cry:
deci prima se facea asa:
1)odata ordonai punctele ca sa fie in ordine (vedeai care sunt cele mai apropiate de fiecare punt)
2)faceai o functie de aflare a suprafetei poligonului( il imparteai in triunghiuri si faceai cu formula lui heron si distentele le calculezi cu geometrie analitica
3)dupa care luai fiecare punct si incercai odata sa-l aduci pe mediatoarea segmentului format din cei 2 pari de langa el , si daca ajunge pana acolo si in sus
4)ce am zis la 3 faci odata pt numerele pare, si apoi pt alea impare ( nu e voie sa fie pari unu langa altu mutati) si vezi care ii mai bine
5) afisezii diferenta

cam asa....
ideea e ca eu nu am reusit sa o fac in 3 ore...
nashpa

[•vlad_io]

Algoritmul tau e gresit. Incepi bine (ca sa ordonezi punctele faci infasuratoare convexa), dar nu iei in calcul ca diferenta optima poate fi obtinuta si modificand punctele 1-4-6 sa zicem... Nu e obligatoriu sa le iei numai pe cele pare sau pe cele impare. Ca sa afli diferenta optima faci o programare dinamica simpla, fiecare puncte are doua posibilitati, modificat sau nu...
Daca m-as fi gandit asa si azi dimineata...  

[•sanitarium]

exact asta am facut si eu. le luam din 2 in 2. dar nu era bine! bineinteles ca nu puteam sa imi dau seama decat dupa ce am iesit din concurs! infasuratoarea convexa se putea face cat mai taraneste posibil ca n era min (parca 50). nu mi-a dat prin cap dinaminca aia!!!! daca erau teste ca anul trecut luam vreo 90 de puncte la ea, dar cred ca prea au fost criticati pentru testele proaste de anu' trecut si anu' asta s-au razbunat. si totusi problema cu lanterna era foarte, foarte ambigua  chiar m-am gandit la posibilitatea de a rezolva ce cer ei, dra mi se parea ca textul zice clar ce am facut eu.

[•SleepyOverlord]

Mda, shi pe langa chestiile zise de vlad, mai e o chestie: aria unui triunghi calculezi cu determinant nu cu Heron, shi poate sunt eu putin slab la geometrie dar nu stiu "din prima" ecuatia mediatoarei.

[Boogieman]

de ce sa o stii din prima? ... o  deduci...
afli mijlocul segmentului dupa care gaseti dreapta perpendiculara pe segment care trece prin punctu ala. dupa care vrei ca punctul unde o sa ajungi cu paru  sa fie cat mai aproape, daca nu ajunge pana la dreapta si cat mai departe de segment...

cum cu determinanti?
eu l-am intrebat azi pe profu` de mate si o zis ca nu prea este alta metoda de aflare a ariei unui poligon fara heron( in xOy )

cum cu determinanti ( la nivel de clasa XI) cu ce am facu t pana acum la mate?

aia cu lanterna la mine in satu mare majoritatea au facut dijkstra numai pentru timp ( adica spionu` ramanea dupa un timp fara lanterna) si desi timpul era cel mai scurt nu au reusit sa prinda nici un test (mici exceptii).

in alta ordine de idei... se pare ca aici la mine in satu mare am luat locu` 2 si probabil ma duc la oni

[•sanitarium]

ce aveti mai cu mediatoarea aia. se prelungea segmentul pe inaltime pentru a obtine o arie maximala!
aria triunghiului= baza*inaltimea/2. cum baza era fixa, pentru a creste aria cresteai inaltimea. si doua drepte sunt perpendiculare daca produsul pantelor lor este -1.

[Boogieman]

ca bine zici sanitarium!!!
nu stiu de ce credeam pana acum ca tre sa fie pe mediuatoare.
ca de fapt oriunde asr fi punctu ala (parau care se misca) aria ramane neschimbata ( adica  b*h/2 constant)
si atunci te duci perpendicular in partea opusa segmentului.
corect!

dar mai e o problema care inca nu mi-e foarte clara!
cum faci fara backtracking toate posibilitatile de combinare ( ca sa vezi care e mai buna?

[•vlad_io]

Aria unui poligon oarecare (poate fi si concav) cu n varfuri este jumatate din suma de i de la 1 la n din determinant de:
  xi     yi
xi+1 yi+1
unde xi, yi sunt coordonatelor varfului i. Daca i=n in loc de i+1 se ia 1. Pentru ca sa functioneze punctele trebuie sa fie ordonate in sens orar sau trigonometric. Daca punctele sunt date in sens trigonometric aria da negativa si trebuie sa o iei in modul.

dar mai e o problema care inca nu mi-e foarte clara!
cum faci fara backtracking toate posibilitatile de combinare ( ca sa vezi care e mai buna?

Nu faci backtracking, faci dinamica...  

[Boogieman]

da... se pare ca functioneaza formula ( foarte faina si ajuta mult! )
nu am ajuns pana acolo la mate sau nici nu stiu daca se face in XI asa ca faza cu heron merge daca sunt ordonate in orice sens ( numai sa fie ordonate)... deci se putea si fara determinnati...

poate ca eu is batutu in cap , sau nu am observat... da la mine im manual (tudor sorin) nu scrie nimic de permutari, aranjamente, combinari dinamic facute!  
 poate ma ajutati voi? :lol:

[•sanitarium]

era simpla dinamica. m-am pacalit pentru ca credeam ca e optim sa le iei din 2 in 2.

[•sjulean]

eu is batutu in cap

Nu ai nevoie de permutari, aranjamente, combinari. Daca ai diferentele pentru fiecare punct stocate in float a[], iti mai faci un float d[] astfel:

Cod:

d[0] = a[0];
d[1] = a[1];
for ( i = 2; i < n; i++ )
	d[i] = ( a[i] + a[i-2] < a[i-1] ? a[i-1] : a[i] + a[i-2] );

Valoarea cautata se va afla in d[n-1]. Corectatzi-ma daca gresesc.

[•cavendish]

io zic ca foru ala nu face treaba din momentul in care d nu este definit recursiv

[•sjulean]

nu face treaba

Sunt prost.

Cod:

d[0] = a[0];
d[1] = a[1];
for ( i = 2; i < n; i++ )
   d[i] = ( a[i] + d[i-2] < d[i-1] ? d[i-1] : a[i] + d[i-2] ); 

Sunt prost.

[•cavendish]

asta-i . si poti renunta la d din momentul in care d nu depinde decat de a

[•sjulean]

Ma simt la fel de obligat () sa-ti atrag atentia ca te-ai exprimat cam dubios, tinand cont ca d continua sa fie o recurenta de ordinul 2 - deci depinde de d[i-1] si d[i-2], nu doar de a.

Acestea fiind spuse, intr-adevar se poate renunta la vectorul d, stocand doar ultimele doua valori din acesta:

Cod:

d0 = a[0];
d1 = a[1];
for ( i = 2; i < n; i++ ) {
	d2 = ( a[i] + d0 < d1 ? d1 : a[i] + d0 );
	d0 = d1;
	d1 = d2;
}

In acest caz, valoarea cautata se va afla in d2.
Sec, nu?

[•cavendish]

scuze, nu m-am exprimat 100% clar:
"asta-i . si poti renunta la d din momentul in care d nu depinde decat de a " si nu de a[i-1] sau a[i-2].
deci dupa o iteratie nu mai ai nevoie de a si poti folosi a pt a tine minte d.
atunci

Cod:

d[0] = a[0]; 
d[1] = a[1]; 
for ( i = 2; i < n; i++ ) 
   d[i] = ( a[i] + d[i-2] < d[i-1] ? d[i-1] : a[i] + d[i-2] ); 

devine

Cod:

for ( i = 2; i < n; i++ ) 
   a[i] = ( a[i] + a[i-2] < a[i-1] ? a[i-1] : a[i] + a[i-2] ); 

si chiar nu mai ai nevoie de d.

[•ionutz_info]

d[0] = a[0];
d[1] = a[1];
for ( i = 2; i < n; i++ )
   d = ( a + d[i-2] < d[i-1] ? d[i-1] : a + d[i-2] );
[/code]
devine

Cod:

for ( i = 2; i < n; i++ ) 
   a[i] = ( a[i] + a[i-2] < a[i-1] ? a[i-1] : a[i] + a[i-2] ); 

si chiar nu mai ai nevoie de d. [/quote]
Sigur merge? E o lista circulara, totusi, si d[n] depinde de d[1]!
       
                                          Ionutz_info

[•cavendish]

nu, nu merge, dar e ceva de genu.