Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-02-24 15:19:39.
Revizia anterioară   Revizia următoare  



Cu aceasta runda se incheie editia 2008 a concursului Winter Challenge. Sper ca a fost pe placul tuturor participantilor pe care ii asteptam si anul viitor, la urmatoarea editie.

Fata de Runda 1 punctajele si numarul participantilor au fost mult mai mari, lucru care nu a putut decat sa ne bucure. Am avut si doua punctaje maxime obtinute de Filip Stefan si Victor Rusu au reusit sa rezolve corect ambele probleme. Runda 2 a fost si un bun prilej de antrenament pentru OJI, care bate la usa.

Felicitari tutuor participantilor, iata primii clasati:

PozitieNumeScor
1
ProstuStefan-Alexandru Filip
Prostu
200
1
victorsbVictor Rusu
victorsb
200
3
stef2nStefan Istrate
stef2n
176
4
gcosminGheorghe Cosmin
gcosmin
150

Il felicitam pe Stefan Istrate care nu mai este elev, ci student in anul I la Facultatea de Matematica si Informatica si fost membru al lotului national in ultimii 2 ani. De asemenea ii felicitam pe Filip, Victor si Cosmin care nu mai au nevoie de nicio prezentare.

Vreau ca pe aceasta cale sa ii multumesc si lui Mugurel Ionut Andreica pentru ca a acceptat sa colaboram si in acest an. Ca si in prima runda, le multumesc lui Andrei Grigorean, Adrian Airinei si lui Cristian George Strat pentru sprijinul acordat, cat si intregii echipe infoarena.

Nu in ultimul rand va multumesc voua, cei care ati participat la acest concrus.

Mult succes in continuare si bafta la OJI,
Varu.

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. BiRss, in acest caz nu conteaza de ce tip va fi considerat intervalul i, deoarece toate punctele din [1,{Bi}] au fost acoperite anterior
  2. Bi > Rss, in acest caz intervalul va fi de tip 'sol-aer', iar Rsa va primi valoarea Bi.

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(N3) 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(2N) (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 (223).
Fie Ai = 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, Mij 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 2k, 0 ≤ k < N pentru care exista strategie de castig, constituie o posibila prima mutare.

Asadar algoritmul are complexitatea O(N*2N) folosind O(2N) 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*2K) folosind O(2K) memorie, unde K este numarul de patratele (1×1) ce pot fi construite cu segmentele din input.