Și mie mi s-a părut limita de timp foarte strânsă.

Inițial am folosit baza 300001 și calculele le-am făcut modulo două numere prime mari (1 000 000 007 și 1 000 000 009). Am luat 80p.

Apoi m-am gândit puțin și am modificat sursa astfel: am folosit două baze (1 000 000 007 și 1 000 000 009) și calculele modulo 2^32 (prin overflow/underflow), eliminând astfel toate operațiile modulo. Am luat 100p cu 372ms și la statistici.

În foarte scurt timp, un elev de-al meu a trimis o sursă cu parsare care a luat 296ms, iar eu am ajuns pe la statistici.

@Duta Vlad:
Eu sunt autorul clasei Huge la care ai facut referire. Cu certitudine mai poate fi imbunatatita.

Inteleg ca nu aprobi o implementare de forma:
Obiect ceva()
{
 Obiect a;
 bla bla bla;
 return a;
}
din motive de performanta.

Am doua intrebari:
(1) Cum poti implementa mai bine supraincarcarea operatorilor?
(2) La ce te referi cand spui ca "ai sanse mari sa o dai in balarii"? (presupunem constructorul de copiere implementat corect si eficient)

Cunosc acest argument și, cel puțin pentru mine, nu este convingător. Contraargumentul pe care îl prezint este destul de simplu: (în 2007 România a intrat în Uniunea Europeana împreună cu Ungaria și) Microsoft a creat acest patch:

http://www.microsoft.com/download/en/details.aspx?DisplayLang=en&id=16083

pentru Windows XP, pe care orice român ar trebui să-l aibă instalat, dacă folosește Windows XP.

Propun ca Infoarena să ducă o mini-campanie de folosire corectă a caracterelor românești, încurajându-și utilizatorii să facă simplul exercițiu de a instala acest patch, dacă folosesc Windows XP! Dacă se dorește cu adevărat, un mesaj de avertisment atunci când scriem caracterele turcești pe paginile wiki ar fi foarte util, încurajând utilizatorii să utilizeze aranjamentul corect de tastatură.

Dacă nu veți ține cont de contraargumentul meu, atunci măcar fiți consecvenți și aplicați aceleași măsuri și pe forum.

Caracterele românești "ș" și "ț" lipsesc de pe Infoarena! Se pare ca ele apar doar pe forum (și în comentarii), dar nu și în partea wiki a site-ului. Se pare că dacă insiști să le introduci (cum am făcut eu), constați că sunt automat înlocuite cu caracterele turcești "ş" respectiv "ţ".

Îi rog pe administratori să facă această înlocuire automată invers (din caractere turcești în carcatere românești) pentru că... suntem români . Și, de asemenea, să facă o înlocuire generală în toată baza de date cu pagini wiki.

Mulțumesc!

Vă rog să adăugați și testul:

acdbdbacabdca

cu raspunsul corect:

acdbdbacabdcacdbacabdbdca

deoarece am observat că există o sursă (643532) care a obținut 100p, deși pică acest test.

Vă mulțumesc.

Multumesc comisiei pentru raspunsurile primite!

Consider ca am inteles problema, dar nu am gasit o solutie buna. Astept jurizarea si solutia oficiala!

LE: Noaptea a trecut, jurizarea s-a facut, solutia oficiala s-a dezvaluit!

Propun spre analiza comisiei urmatorul test:

Cod:

7 1000 250 7
0 101
0 0
0 250
0 250
0 250
1 0
0 0
1 2 1 100
2 3 1 1
3 4 1 1
4 5 1 1
5 2 1 1
2 6 1 100
2 7 1 100

cu solutia
1 8
si drumul
1 2 3 2 6 2 5 2 7

[REAlimentam in A]

Eu am intrebat si mi s-a raspuns:
1) Daca ambasadorul ajunge pe o planeta, alimenteaza nava, face un ciclu si revine pe planeta de pe care a alimentat, mai poate REalimenta? - DA

Citez din enunt:
Dacă o dată ajuns pe o planetă Ambasadorul se decide să alimenteze cu combustibil, el va face de fiecare dată plinul rezervorului în limita cantității de deuteriu prezentă pe planetă și a capacității C a rezervorului.

Din cele doua, se poate deduce ca in situatia descrisa in raspunsul explicativ de la intrebarea (4) putem face urmatoarele:
Pornim cu rezervorul cu 30.
1) Alimentam in A (R: 30 + 50 = 80)
2) Mergem in B (R: 80 - 30 = 50)
3) Alimentam in B (R: 50 + 100 = 150 (120))
4) Ne intoarcem in A (R: 120 - 30 = 90)
5) REAlimentam in A (R: 90 + 50 = 140 (120))
Si putem porni spre C cu rezervorul plin (120)!

Care este interpretarea raspunsului afirmativ de la prima intrebare? Daca pot realimenta, la realimentare cu cat pot realimenta? Cu cantitatea de combustibil din datele problemei? Sau doar cu cantitatea de combustibil ramasa in urma primei alimentari?

Bleah... mi se pare mult prea complicata problema asta .

Alternativ, daca realimentarea nu se poate face decat in limita combustibilului ramas, atunci ar putea exista urmatorul scenariu:
1) Alimentam in A (R: 30 + 20 = 50) - si pastram in A 30
2) Mergem in B (R: 50 - 30 = 20)
3) Alimentam in B (R: 20 + 100 = 120)
4) Ne intoarcem in A (R: 120 - 30 = 90)
5) REAlimentam in A (R: 90 + 30 = 120) - si nu mai ramane nimic in A

Insa! Aceasta problema devine foarte... complicata, pentru ca, la fel de bine, putem presupune urmatorul scenariu:
Sa spunem ca in A avem 60 de combustibil. Atunci avem scenariul:
1) Alimentam in A (R: 30 + 20 = 50) - si pastram in A 40
2) Mergem in B (R: 50 - 30 = 20)
3) Alimentam in B (R: 20 + 100 = 120)
4) Ne intoarcem in A (R: 120 - 30 = 90)
5) REAlimentam in A (R: 90 + 30 = 120) - si pastram in A 10
Insa, in scenarii derivate acestuia, putem sa pastram 5 in A si 5 in B, sau 3 in A si 7 in B samd.; iar daca B are legaturi si cu alte planete, o revenire a mea in B, prin aceste alte planete s-ar putea sa fie posibila plastrand un pic de combustibil si acolo - la fel de bine, s-ar putea sa vreau sa revin in A si sa am nevoie de combustibil si de acolo - si chiar trebuie sa analizez toate aceste cazuri: 5/5, 3/7 etc.

Intrebare:
De ce aceasta problema pare sa fie atat de complicata? Nu inteleg eu ceva sau autorul problemei chiar vrea sa ma chinuie?

Ma surprinde raspunsul afirmativ de la prima intrebare. Asta inseamna ca nu are sens sa nu alimentezi... Sau nu-l vad eu. Asa ca intreb:

4) Are sens sa nu alimentezi, cand te afli pe o planeta?

Si o sa mai intreb:

5a) La plecare, ambasadorul porneste intotdeauna cu rezervorul la capacitate maxima?
5b) La plecare, ambasadorul porneste cu rezervorul la Min(capacitatea rezervorului, cantitatea de combustibil de pe planeta 1)?

6) Ambasadorul se poate reintoarce pe planeta 1, sa REalimenteze?

Problema "drum":

1) Daca ambasadorul ajunge pe o planeta, alimenteaza nava, face un ciclu si revine pe planeta de pe care a alimentat, mai poate REalimenta?

2) Daca ambasadorul ajunge pe o planeta, NU alimenteaza nava, face un ciclu si revine pe planeta de pe care NU a alimentat, mai poate alimenta?

3) Daca ambasadorul poate ajunge pe Pamant cu aceeasi cantitate maxima de minerale, dar prin mai multe drumuri (cu timpi diferiti) ce timp se afiseaza? Timpul minim?

1) Fie testul:

2 1
1 1 0 1
2 1 999999999 1000000001

Este valid? Extremitatile 1000000001 si 1 sunt... distincte? Sau sunt aceeasi extremitate si testul este invalid?

2) Fie testul:

2 1
1 1 0 2
10 1 999999999 1000000001

2) Mergand initial spre pilonul 0, fizicienii se opresc in marginea zidului [0;2]? Sau se opresc mai departe in al doilea zid?

Fie testul:

2 1
1 1 999999999 1000000001
2 1 999999999 1000000001

cu semnificatia: doi pereti la nord, cu 3 piloni fiecare.

Fizicienii fac un pas la nord, un pas in dreapta (sau stanga) si apoi...
Intrebare: au scapat? sau trebuie sa mai faca un pas la nord, pana la zidul de raza 2?

Un alt mod de a formula intrebarea: Fizicienii pot sa plece de pe marginea unui zid si sa ajunga pe marginea altuia si apoi sa-si continue drumul pe al doilea?

[I. Solutia evidenta (pentru mine):]

Am citit multe discutii in contradictoriu pe tema problemei safeu si marturisesc ca imi plac discutiile in contradictoriu, insa, am imbatranit si stiu ca nu aduc nimic bun. Eu va propun sa incheiem discutia si sa ramanem cu un algoritm dragut. Concret, am sa va prezint optimizările pe care le-au găsit băieții cu 0.1s.

I. Solutia evidenta (pentru mine):
Complexitate timp: O(N*M*N*M)
Complexitate spatiu: O(N*M*N*M)

Se observa ca, deoarece pe tabla exista un singur seif cu Pocalul (X) si un singur spatiu liber (.), indiferent ce secventa de mutari am realiza, vom ajunge intr-o stare care poate fi caracterizata in mod unic prin pozitiile spatiului liber si al seifului.

Astfel, identificam o functie bijectiva intre o stare si multimea [1;N]x[1;M]x[1;N]x[1;M].

In continuare, stiind ca un seif obisnuit (c) si seiful cu Pocalul (X) se pot muta peste spatiul liber (.), putem concluziona ca urmatoarele tranzitii intre stari sunt permise:
1) mutarea spatiului liber (.) peste un vecin, daca vecinul este un safu obisnuit (c)
2) interchimbarea spatiului liber (.) cu seiful cu Pocalul (X), daca acestea sunt vecine

In final, stim ca starea initiala a seifurile se gaseste in fisierul de intrare, iar starea finala este de forma: (1,1,x,y)

Am construit un graf cu N*M*N*M varfuri si cel mult 4*N*M*N*M, in care avem de calculat cel mai scurt drum de la starea initiala la una din starile finale, stiind ca muchiile sunt ponderate egal. Cu o parcurgere in latime obtinem timpul optim pentru rezolvarea acestei probleme.

II. O Solutie interesanta:
Complexitate timp: O(N*M*N*M)
Complexitate spatiu: O(N*M)

Observam (dupa ce descoperim ca sursa anterioara nu intra in 0,1s pentru N = 50, M = 50) ca, in principal, trebuie sa cautam o modalitate prin care sa mutam seiful cu Pocalul (X) de pe o pozitie oarecare, pe o pozitie invecinata. Insa, acest lucru nu se poate face direct. Pe drumul optim, intre doua mutari succesive ale seifului cu Pocalul (X) trebuie sa mutam de cateva ori spatiul liber (.). Mai precis, imediat dupa ce a fost mutat seiful cu Pocalul (X), spatiul liber (.) ocupa unul din vecinii seifului cu Pocalul (X) (pozitia din care a venit), iar inainte sa fie mutat din nou, spatiul liber (.) ocupa un alt vecin (pozitia pe care se va duce).

Astfel, observam ca, daca pentru o pozitie fixata a seifului cu Pocalul (X), vom calcula toate drumurile optime prin care spatiul liber (.) se poate muta din orice pozitie vecina a seifului cu Pocalul (X) in orice alta pozitie vecina a seifului cu Pocalul (X), fara a muta seiful cu Pocalul (X), vom putea reformula problema astfel:

Reducem numarul de stari la multimea [1;N]x[1;M]x[1;4], reprezentand pozitia seifului cu Pocalul (X) si pozitia spatiului liber (.), stiind ca acesta nu poate fi decat vecin seifului cu Pocalul (X).

Observam ca folosind operatia de interschimbare si in baza timpilor de mutare a spatiului liber (.), putem determina tranzitiile dintre stari.

In final, observam ca starea initiala s-ar putea sa nu faca parte din multimea starilor reduse, si trebuie sa calculam distanta de la starea initiala la cele 4 stari similare ale ei, acestea devenind starile initiale din noua problema, iar costul de a plecare din ele este nenul. Starea finala este (1,1,x).

Am construit un graf cu N*M varfuri si cel mult 4*N*M, in care avem de calculat cel mai scurt drum de la una din starile initiale la una din starile finale, stiind ca muchiile sunt ponderate. Cu un algoritm eficient de calcularea a drumului optim, putem realiza acest lucru intr-o complexitate rezonabila.


III. Solutia mai buna (o fi una si mai buna?):
Complexitate timp - cazul mediu: O(N*M)
Complexitate timp - cazul defavorabil: O(N*M*N*M)
Complexitate spatiu: O(N*M*N*M)

Am observat in solutia anterioara aparent mult efort pentru nimic. Dar, solutia anterioara are ceva buna si ceva rau... poate putem sa facem o solutie in care pastram ce e bun si scapam de ce e rau!

Ce e bun: Reduce numarul de stari ale problemei! Era evident ca solutia I nu putea fi optimizata, decat prin reducerea numarului de stari (sau prin artificii in assembler care nu fac obiectul algoritmicii)! Acest lucru vine cu un pret: suntem obligati sa calculam distantele dintre cele 4 stari cu aceeasi pozitie a seifului cu Pocalul (X) - acest lucru trebuie sa-l facem de N*M ori iar o astfel de operatie dureaza O(N*M) timp, deci... nu am rezolvat nimic! Dar, stai! Oare asa sa fie si pe cazul mediu? Nu cumva, pe cazul mediu, mutarea spatiului liber (.) intre pozitiile vecine ale seifului cu Pocalul (X) se face in foarte putini pasi? Si nu cumva si timpul de executie este proportional cu lungimea drumului? BA DA! Evirka! (la 0:30, cand te chinui sa-ti intre problema in 0.1s).

Ce e rau:
1. Graful obtinul la final are muchii ponderate si nu putem folosi parcurgerea in latime;
2. Trebuie sa calculam separat timpii de mutare a spatiului liber (.);
3. Trebuie sa calculam timpii de pornire din starile initiale.

Ce putem face sa scapam de ce e rau?

Putem pastra intacta multimea starilor [1;N]x[1;M]x[1;N]x[1;M] si putem sa o folosim pentru a calcula in ea timpii de mutare a spatiului liber si timpii de pornire din starile initiale! Si putem sa calculam drumul minim in graful ponderat printr-o parcurgere in latime! Cum?

Foarte simplu - ajustam solutia I, folosind doar ceea ce e bun din solutia II:

Parcurgand in latime multimea a starilor ([1;N]x[1;M]x[1;N]x[1;M]), tinem si o structura paralela a multimii starilor reduse ([1;N]x[1;M]x[1;4]), in care marcam starile prin care a trecut parcurgerea in latime. Daca pentru o pozitie a seifului cu Pocalul (X) au fost marcate toate cele 4 stari asociate din multimea starilor reduse, atunci parcurgerea in latime este oprita pentru toate starile cu acea pozitie a Pocalului.

In incheiere:
Eu sunt autorul solutiei propuse si a sursei trimisa spre evaluare si nu o consider o optimizare, ci un alt algoritm, cu un alt grad de complexitate (pe cazul mediu).

Probabil ca voi fi atacat, reprosandumi-se ca atata timp cat cu reduc cazul defavorabil, solutia mea nu este mai buna. Daca intentionati sa ma atacati, atunci va aduc aminte ca cel mai fecvent utilizat algoritm pe scara larga a fost pana nu demult QuickSort, care, in ciuda timpului dezastruos pe cazul defavorabil, a fost preferat HeapSortului, doar pentru ca are o constanta mai mica.

Si eu sunt adeptul timpilor lejeri, iar pozitia lui Mihai Calancea mi se pare cea mai buna:

In general se considera fair-play sa lasi limita mai libera pentru ca implementarile mai neingrijite (dar nu grosolan) sa nu-ti afecteze prea tare punctajul. Atata timp cat nu exista pericolul ca solutiile proaste sa ia mai mult.

Considerand ca am inventat o solutie mai buna (dpdv teoretic si nu cu artificii de limbaj), mi se pare ca timpul a fost marit suficient de mult cat sa permita si solutiilor in O(N*M*N*M) sa obtina 200p, ceea ce e incorect pentru solutia mea. Insa, afland ca de fapt a avut loc o greseala in randul comisiei, iar solutia oficiala era tot in O(N*M*N*M), marirea timpului de executie mi se pare decizia corecta!

Cu aceasta ocazie, tin sa multumesc organizatorilor pentru acest concurs, deoarece m-a facut sa-mi dau seama ca inca mai stiu algoritmi! Si le spun si eu sa aiba un pic mai multa grija pe viitor, pentru ca noi, concurentii, putem sa busim si nu ne mai calificam, insa organizatorii, cand gresesc, trebuie sa-i impace pe toti nemultumitii... si... e mai complicat :-ss.

Imi pare rau pentru cei care "s-au fript", facand surse partial gresite, dar care sa intre in timp (vanatorii de puncte ).

In ceea ce ma priveste, inteleg ca nu suntem la lotul national sau la vreo olimpiada internationala organizata de o tara capabila sa propuna probleme imposibile, astfel ca se mai intampla sa descoperi un algoritm mai bun decat al comisiei, caz in care nu poti decat sa te bucuri! Am impartit cu toata lumea solutia mea si sper sa va bucurati de ea, asa cum ma bucur si eu!

Sper ca v-a placut idea mea, pentru ca mie mi-a placut problema!
PS: Daca limita nu era de 0,1s, atunci nu m-as fi gandit la solutiile II si III.

[O(N log D)]

Solutia are o complexitate teoretica chiar mai proasta: O(N log D), unde D = 2*10^9, diferenta maxima dintre doua numere consecutive. Si totusi... Testul 10 - 640ms. Timpii de executie depind, in cazuri atat de fine, de complexitatea structurilor de date folosite si calitatea implementarii.

Am participat la concurs on-site si, apoi, am ascultat solutiile oficiale. Propun o solutie alternativa, cu care am obtinut punctaj maxim:

Se cauta binar solutia. In acest sens, trebuie implementata o functie prin care sa se verifice daca pentru un numar D, exista o subsecventa a sirului de intrare de lungime cel putin N - K, in care oricare doua elemente consecutive au diferenta <= D.

Astept pareri despre corectitudine, timpul de executie si dificultatea de implementare.

Am participat la concurs on-site si, apoi, am ascultat solutiile oficiale. Propun o solutie alternativa, cu care am obtinut punctaj maxim:

1. Se parcurge sirul pana cand V[ i ] >= V[ i + 1 ] sau se termina.
2. Se parcurge sirul pana cand V[ i ] <= V[ i + 1 ] sau se termina.
3. Se revine la 1.

Solutia se incrementeaza la pasii 1 si 2.
Cand se termina sirul, se afiseaza solutia.

Astept pareri despre corectitudine, timpul de executie si dificultatea de implementare.

M-ati dezamagit . Nu ati modificat nimic in enuntul problemei...  

Eu am reusit sa iau in final 100 de puncte, insa initial ma obtinut doar 70 . Dupa ce am depanat ultimele buguri aveam 2 TLE (testele 9 si 10) si un RUN ERROR (testul 6).

Dupa o multime de submit-uri, am reusit sa-mi dau seama ca TLE-urile erau cauzate de dreptunghiuri cu costul 0 (si nu mi se pare normal sa am probleme din cauza unor astfel de teste, in special daca nu apar mentionate in enunt - de aceea este foarte important ca testele sa respecte restrictiile din enunt ).

In final, am corectat si testul 6 si am constatat ca sursa mea ar fi avut probleme cu dreptunghiurile cu proprietatea Y1 - DY + 1 > Y2 - 1. Oricum, eu mi-am corectat sursa, astfel incat sa functioneze si in unele conditii extreme...

Urmatoarele teste mergeau bine pe sursa mea veche:
Y1 - DY + 1 <= Y2 - 1 =>
Y1 <= Y2 + DY - 2 =>
Y2 < Y2 + DY - 1 =>
Daca 0 < DY atunci Y2 < Y2

Am gresit ceva?

Oricum, este la fel de posibil ca testul 6 sa aiba o alta proprietate ciudata, pentru care am luat aceal RUN ERROR, asa ca nu o sa mai insist. Dar, nu uitati sa modificati enuntul .

E clar ca fie testele fie enuntul sunt gresite...

Am gasit teste (9 si 10) in care exista dreptunghiuri de cost 0, iar in enunt scrie:

0 < C ≤ 200 000

Mai mult decat atat... am mai gasit ceva! Testul 6 nu respecta una din urmatoarele conditii (nu stiu exact care):

0 < DY
y1 < y2 (pentru cel putin unul dintre dreptunghiuri)

Foarte grea problema asta!

Pt. cei care au probleme cu testul 1 - solutia este "0.000" si eu afisam "0.001"  

Spor!

"Intamplator", am dat peste urmatorul borderou, pentru aceasta problema. De unde cele 4 puncte?  

TEST 1   ...[0.01s]...   Numarul de intersectii nu e bun!
TEST 2   ...[0.01s]...   Numarul de intersectii nu e bun!
TEST 3   ...[0.01s]...   Numarul de intersectii nu e bun!
TEST 4   ...[0.01s]...   Numarul de intersectii nu e bun!
TEST 5   ...[0.03s]...   Numarul de intersectii nu e bun!
TEST 6   ...[0.05s]...   Numarul de intersectii nu e bun!
TEST 7   ...[0.11s]...   Numarul de intersectii nu e bun!
TEST 8   ...[0.15s]...   Numarul de intersectii nu e bun!
TEST 9   ...[0.37s]...   Numarul de intersectii nu e bun!
TEST 10   ...[0.01s]...   Treci pe o strada inexistenta!

Daca tot se acorda punctaje partiale, mentionati in enunt.

Cum tratezi cazul in care ai doi politisti la aceleasi coordonate?

Enuntul e dubios in privinta asta... ne intreaba pe noi ce se intampla... daca ar fi dupa mine, nu i-as lua in considerare, pentru ca se ciocnesc.

M-am prins si eu ca am o greseala pe undeva.
Din cauza asta ceream un hint legat de structura primului test.

[X = (__int64)1000000000 * 1000000000;]

Eu fac alfel, si merge intotdeauna

X = (__int64)1000000000 * 1000000000;
sau
X = (long long)1000000000 * 1000000000;
Incearca si:
X = (__int64)1000000000000000000;
sau
X = (long long)1000000000000000000;
dar nu garantez pentru asta.

Tipul folosit difera in functie de compilator
Spor!

Tx. for the advice

Eu am incercat s-o fac clasic, ca pentru limite mai mari

Mai exact:
1) pun intr-o lista punctele care:
- definesc un poligon si sunt in interiorul celuilalt;
- rezulta din intersectia a doua laturi, apartinand una unui poligon si cealalta celuilalt
2) pentru punctele din lista, aplic infasuratoare convexa
3) Calculez aria poligonului rezultat

Teoretic ar trebui sa mearga pe orice test . Ma gandesc ca poate am gresit un detaliu stupid... si eram curis ce (din greseli se invata ).

Cred ca o sa fac si eu cu baleiere... damn...

Si totusi... daca faci cu baleiere, nu e posibil sa pierzi precizie? (Ma gandesc asa: daca micsorezi eps-ul, creste precizia, dar scade timpul de executie, si invers...)

Problema asta mi se pare cea mai grea de pe siteul asta

In special testul 1!

Poate cineva sa-mi dea macar un hint, cu ce este?

Eu am incercat foarte multe teste si toate au fost ok! Am incercat si tot felul de cazuri particulare (poligon in poligon, poligoanele au o latura comuna, poligoanele sunt identice, poligoanele au un pct. comun - oare ce n-am incercat???) si nimic...

Trebuie sa afisez ceva deosebit, intr-un anumit caz? (ex.: 0, in loc de 0.000, atunci cand poligoanele nu se intersecteaza?)

Ar fi interesanta o demonstratie pentru formula

Dar, o astfel de demonstratie nu-si are locul aici, pentru ca ar trebui facuta publica formula

Oricum, interesante problema si formula!