Infoarena Monthly 2014, Runda 8

[•Teodor94]

Runda 8 va avea loc Duminica, 31 august la ora 19⁰⁰.
Va uram mult succes!  

[•Teodor94]

Runda s-a incheiat. Clasamentul este public. Problemele au fost adaugate in arhiva! Asteptam primele voastre impresii

Felicitari tuturor participantilor 

[•PlayLikeNeverB4]

Leeerooooooy Jeeenkiiiiiins!   Cine e fan Blizzard/Warcraft?
Ar fi util sa vezi scorul potential la probleme ca la codeforces.

[•xtreme77]

O runda cu probleme super frumoase ! Big up comisiei !  Apropo,imi poate da si mie cineva o indicatie la problema Super Mario ? M am chinuit o ora din concurs sa o dovedesc,dar nu prea a fost cu succes 

[•narcis_vs]

Cred ca a fost runda cu cele mai interesante probleme. Felicitari !!! Si ,ca de obicei, asteptam modificarea ratingului.

[•Mihai22e]

Probabil cea mai reusita runda de anul acesta, felicitari!  Si nu sunt subiectiv, spun asta in conditiile in care mi-a picat a 3-a problema din cauza ca citesc N muchii in loc de N - 1  O intrebare: cum se poate rezolva prima problema daca B - A <= 10^9, in loc de 10^3?

[•andrei_toader]

Cand o sa apara articolul cu solutii?

[•ctlin04]

Daca erau enunturi mai scurte runda era sa fie si mai frumoasa. 

[•narcis_vs]

@Mihai22e .Eu as folosi smenul de la problema cntgcd.

[•a_h1926]

O runda cu probleme super frumoase ! Big up comisiei !  Apropo,imi poate da si mie cineva o indicatie la problema Super Mario ? M am chinuit o ora din concurs sa o dovedesc,dar nu prea a fost cu succes 

Sunt doua solutii oficiale. In continuare voi prezenta una dintre acestea.

Vom defini o functie recursiva, Solve(left, right), care returneaza numarul minim de mutari necesare pentru a distruge toate testoasele din intervalul [left, right], folosind numai testoase din acest interval. Raspunsul va fi dat de Solve(1, N), iar cazurile de baza Solve(i, i) sunt triviale (raspunsul e mereu 1).
Intr-o solutie optima, testoasele vor fi distruse in ordine descrescatoare dupa valori. Astfel, vom incerca sa facem prima mutare in Solve(left, right). Fie pos pozitia pe care se afla testoasa de valoare maxima din intervalul [left, right]. Putem sa o lovim spre stanga sau spre dreapta, iar noi vom alege varianta optima. Astfel, Solve(left, right) va returna min(Solve(left, pos - 1), Solve(pos + 1, right)) + 1. Pentru a determina eficient pos, putem folosi o structura de date precum arborii de intervale. Complexitatea este O(N * logN).

Cealalta solutie oficiala se bazeaza pe programare dinamica si are complexitate liniara.

[•xtreme77]

Iti multumesc foarte mult pentru ajutor!Am sa incep sa o implementez

[•Maarcell]

O runda cu probleme super frumoase ! Big up comisiei !   Apropo,imi poate da si mie cineva o indicatie la problema Super Mario ? M am chinuit o ora din concurs sa o dovedesc,dar nu prea a fost cu succes  

Sunt doua solutii oficiale. In continuare voi prezenta una dintre acestea.

Vom defini o functie recursiva, Solve(left, right), care returneaza numarul minim de mutari necesare pentru a distruge toate testoasele din intervalul [left, right], folosind numai testoase din acest interval. Raspunsul va fi dat de Solve(1, N), iar cazurile de baza Solve(i, i) sunt triviale (raspunsul e mereu 1).
Intr-o solutie optima, testoasele vor fi distruse in ordine descrescatoare dupa valori. Astfel, vom incerca sa facem prima mutare in Solve(left, right). Fie pos pozitia pe care se afla testoasa de valoare maxima din intervalul [left, right]. Putem sa o lovim spre stanga sau spre dreapta, iar noi vom alege varianta optima. Astfel, Solve(left, right) va returna min(Solve(left, pos - 1), Solve(pos + 1, right)) + 1. Pentru a determina eficient pos, putem folosi o structura de date precum arborii de intervale. Complexitatea este O(N * logN).

Cealalta solutie oficiala se bazeaza pe programare dinamica si are complexitate liniara.

Mi-a venit si mie fix aceeasi idee cu Divide et Impera, dar cum pot sa demonstrez corectitudinea algoritmului? In special afirmatia ca cel mai optim mod este sa distrugem testoasele in ordine descrescatoare dupa P[ i ].
Intuitiv inteleg de ce e asa, dar cum as proceda daca as vrea sa fac o demonstratie matematica consistenta? Presupun ca aici trebuie folosita reducerea la absurd dar nu imi vine in cap cum sa construiesc argumentul.

[•Andrei1998]

Inductie dupa lungimea sirului nostru, N:

Cazul de baza: N=1 => Evident, algoritmul nostru e corect aici.

Cazul general: Presupunem ca am demonstrat afirmatia noastra pentru toti 1 <= k < N si acum vrem sa demonstram afirmatia noastra pentru N. In primul rand, daca nu am folosi maximul din vector, nu am avea cum sa ucidem toate testoasele (cum elementele vectorului sunt unice rezulta ca numai maximul se poate elimina pe el insusi). Apoi, daca nu am folosi maximul chiar la inceput, aratam ca am irosit mutari (deci solutia noastra nu este in general optima). Mai exact, presupunem ca maximul e pe pozitia X. Numim stanga lui X intervalul [1,X-1] si dreapta lui X intervalul [X+1,N] (cazurile cand unul din aceste intervale este vid se trateaza analog). Daca nu am folosi maximul chiar la inceput, am face cateva miscari strict in stanga lui X si cateva strict in dreapta lui X (independente fiindca X este maxim), dupa care am folosi maximul in una din directii. Maximul va elimina cu siguranta tot ce exista in aceea directie, deci mutarile facute acolo au fost inutile, iar cele facute in cealalta directie puteau fara a schimba raspunsul sa fie facute si dupa eliminarea maximului. Astfel, am demonstrat ca la pasul curent vom alege mai intai maximul. Dupa alegerea maximului, vectorul nostru se micsoreaza, si cum stim ca am demonstrat afirmatia pentru 1 <= k < N, rezulta ca in continuare vom alegem numai maxime, indiferent cum am orienta primul maxim ales.

Am incercat sa o fac cat de riguros am putut. Oricum, mare parte a demonstratiei e intuitie.  

Edit: Practic am folosit reducerea la absurd, fara insa a folosi formularile clasice.