infoarena informatica de performanta

pe vine...

• Lista de probleme
• Siguranta Nationala
• Joc pe grid

Siguranta Nationala

Problema se rezolva prin metoda Greedy. Se parcurge in ordinea crescatoare a capetelor stanga tinand 2 variabile Rss si Rsa:

• Rss - tot intervalul [1,Rss] este acoperit de rachete 'sol-sol'
• Rsa - tot intervalul [1,Rsa] este acoperit de rachete 'sol-aer'

La pasul i avem urmatoarele cazuri (presupunem ca Rss ≤ Rsa):

1. B_i ≤ Rss, in acest caz nu conteaza de ce tip va fi considerat intervalul i, deoarece toate punctele din [1,{B_i}] au fost acoperite anterior
2. B_i > Rss, in acest caz intervalul va fi de tip 'sol-aer', iar Rsa va primi valoarea B_i.

Din pacate limitare memoriei facea imposibila stocarea intervalelor. Din fericire ele erau deja sortate, deci se puteau preprocesa pe parcursul citirii. De asemenea, cand se stabilea tipul unui interval se afisa in fisierul de iesire.

Astfel algoritmul foloseste O(1) memorie si are complexitatea O(n).

Joc pe grid

Aceasta problema are solutii a caror complexitate creste gradat, incercand sa fie accesibila cat mai multor concurenti.

Pentru toate cele trei solutii este necesara urmatoarea observtie: toate segmentele date in fisierul de intrare, care nu formeaza un patrat complet de latura 1, sunt considerate redundante si, deci, trebuie eliminate.

Solutia de 30 de puncte (clasa a 9-a si clasa a 10a nivel incepator)

Pentru N ≤ 13 figurile care se pot forma sunt asemanatoare cu cele ale jocului Tetris:

Astfel sunt doar 12 categorii de constructii ce respecta specificatiile enuntului. Pentru fiecare figura se poate calcula "de mana" daca este castigatoare (negru) sau nu (rosu). Pentru a verifica rapid carei constructii ii corespund segmentele descrise in input, cele 12 configuratii se pot tine in 12 matrici care au elementele 1 sau 0 (vezi exemplul de mai jos).

1 0 0        0 0 0        0 1 0
M1: 1 0 0    M2: 0 1 0    M3: 1 0 1
    1 1 0        1 1 1        0 0 0   ...

In acelasi mod poate fi memorata si figura din input si se poate raspunde in O(N³) la cerinta problemei.

Solutia de 60 de puncte (clasa a 10-a nivel avansat, clasele 11-12 nivel incepator)

Este usor de observat ca, daca N-ul creste, numarul configuratiilor creste si el, iar raspunsurile nu se mai pot precalcula atat de usor.

Sa abordam altfel problema. Pentru N ≤ 23 este intuitiv ca trebuie sa gasim un algoritm de complexitate, aproximativ, O(2^N) (8.388.608 de operatii se incadreaza lejer in limita de timp).
La un moment dat, un segment poate sa fie colorat sau sa nu fie colorat. De aceea, cele N laturi pot fi reprezentate ca un numar in baza 2, in care fiecare bit retine starea unui segment (1-colorat, 0-necolorat). Se observa ca acest numar nu are mai mult de 23 de biti si nu depaseste 8.388.608 (2²³).
Fie A_i = 1 daca pentru configuratia i jucatorul aflat la mutare are strategie de castig sau 0 in caz contrar. Valorile lui A se pot calcula recursiv, dar facand cateva optimizari, pentru a se incadra in limita de timp:

1. (cea mai importanta) vom folosi memoizarea pentru a nu calcula de mai multe ori valoarea pentru acelasi i
2. la fiecare pas se elimina segmentele care nu mai fac parte din niciun patrat de 1×1
3. (sau 2') putem reprezenta figura la un moment dat ca o matrice fiecare celula tinand informatii despre segmentele ce ii definesc conturul; cu alte cuvinte, M_ij va fi un numar cu 4 biti, primul bit reprezentand starea laturii din stanga a patratului (i,j), al doilea - starea laturii de sus, al treilea - starea laturii din dreapta si in final, al patrulea - starea laturii de jos; asadar, matricea va avea elemente doar din multimea {1,2,4,8,15}.

Pentru obtinerea celor 70 de puncte insa, nu era necesara decat prima optimizare.

Dupa ce am calculat elementele lui A, configuratiile de tipul 2^k, 0 ≤ k < N pentru care exista strategie de castig, constituie o posibila prima mutare.

Asadar algoritmul are complexitatea O(N*2^N) folosind O(2^N) memorie.

Solutia de 100 de puncte (clasele 11-12 nivel avansat)

Solutia anterioara poate fi rafinata prin urmatoarea observatie: daca la un moment dat, am colorat o latura, atunci toate laturile patratului (patratelor) de 1×1 de care apartinea pot fi considerate redundante. Cum N ≤ 50 se pot forma doar 20 de patrate de latura 1 (un grid cu 4 linii si 5 coloane). Astfel in loc ca numarul i sa retina in fiecare bit al sau informatii despre segmente, va retine informatii despre patrate. Deci, cand eliminam o latura vom considera ca eliminam toate patratele de care apartine (care pot fi 1 sau 2). In mod evident, pentru a se incadra in timp, sunt necesare optimizarile de la solutia precedenta.

Am obtinut astfel o solutie de complexitate O(N*2^K) folosind O(2^K) memorie, unde K este numarul de patratele (1×1) ce pot fi construite cu segmentele din input.