Solutii Summer Challenge 2009, Runda 1

• Lista de probleme
• Joc11
• Drepte3
• Posta

Joc11

Soluţie: O(N³) Timp, O(N²) Memorie

Să notăm cu D distanţa dintre locurile de start ale celor doi jucători. Cum ambii jucători au de parcurs aceeaşi distanţă, putem presupune, prin absurd, fără a restrânge generalitatea, că jucătorul A va efectua cel puţin D + 1 mutări. Rezultă că, deoarece jucătorul B are un traseu de lungime D, jucătorul A va pierde, efectuând mai multe mutări. Deci, ambii jucători vor căuta să se deplaseze pe unul din drumurile de lungime D dintre locurile de start.

Cum jucătorul A mută primul, acesta va câştiga dacă şi numai dacă jucătorul B nu poate ajunge în acelaşi loc cu jucătorul A în D / 2 mutări. Astfel, dacă D este număr impar, A câştigă. În continuare, vom presupune că D = 2d.

Rezolvăm problema cu ajutorul metodei programării dinamice. Notăm cu LA_k şi LB_k listele de pătrate în care pot ajunge cei doi jucători în k mutări iar adversarul său în D - k mutări. Fie T_k,i,j true dacă după d - k mutări jucătorul A are strategie sigură de câştig iar cei doi participanţi se află pe poziţiile LA_d-k[i], respectiv LB_d-k[j]. Dacă jucătorul B are strategie sigură de câştig atunci T_k,i,j este false. Observăm că listele LA_d şi LB_d sunt identice iar T_0,i,j este true pentru toţi i şi j pentru care LA_d[i] ≠ LB_d[j], condiţie echivalentă cu faptul că cei doi jucători nu sunt în acelaşi pătrat. Recurenţa se deduce din observaţia următoarele: „A are strategie sigură de câştig dacă poate muta într-o poziţie din care oriunde B ar muta acesta ar pierde”. Notăm cu NextA_k,i lista poziţiilor din LA_d-k+1 în care jucătorul A poate muta din poziţia LA_d-k[i]. Fie NextB_k,i lista definită în mod asemănător pentru jucătorul B. Observaţia precedentă se traduce prin: dacă există un i' din NextA_k,i, oricare ar fi j' din NextB_k,j, să avem T_k-1,i',j' = true, atunci T_k,i,j este true. Altfel, T_k,i,j este false. Vom calcula valorile matricei T pentru k = 1,2,..,d. În concluzie, jucătorul A are strategie sigură de câştig dacă T_d,1,1 este true.

Soluţia obţine punctajul maxim.

Soluţie: O(N³logN) Timp, O(N³) Memorie

Această soluţie este similară cu cea precedentă, cu diferenţa că vom ţine un dicţionar, cu semnificaţia T_{ax, ay, bx, by} = true dacă şi numai dacă jucătorul A are strategie sigură de câştig când acesta se află în poziţia (a_x, a_y) iar B în (b_x, b_y). Dicţionarul adaugă un factor de logN la complexitatea soluţiei şi reţine O(N³) memorie.

Soluţia obţine 60 de puncte.

Soluţie: O(N³) Timp, O(N⁴) Memorie

Această soluţie este cea precedentă cu excepţia faptului că foloseşte un tablou 4-dimensional pentru reţinerea stărilor.

Soluţia obţine 40 de puncte.

Drepte3

Dacă avem un algoritm eficient de a găsi intersecţia cu x minim pentru setul nostru de drepte atunci problema este rezolvată, pentru că putem aplica de 4 ori acelaşi algoritm pentru a găsi valorile minime şi maxime pentru x şi y.

Sortăm toate dreptele după ordinea lor pe y dacă ar fi intersectate de o dreaptă verticală cu x-ul foarte mic. Dacă avem două drepte ax + by + c = 0 şi a₁x + b₁y₁ + c₁ = 0, avem y = (-ax - c) / b şi y₁ = (-a₁x - c₁) / b₁. Dacă x este foarte mic (tinde spre minus infinit) atunci y > y₁ dacă -a/b > -a₁/b₁. După ce avem dreptele în ordine sortată, pentru a determina intersecţia dintre ele cu cel mai mic x, este de ajuns să ne uităm la intersecţiile între drepte consecutive în această ordine.

Astfel, soluţia se reduce la o simplă sortare de pante şi un for pe care facem intersecţii de drepte. Complexitatea soluţiei va fi O(n log n).

Posta

Vom considera scrisorile ca puncte in planul "sertare / timp" (Ox / Oy). Astfel, observam ca daca folosim un vagon pentru a lua o scrisoare de la pozitia (x,y), putem folosi acelasi vagon pentru a lua o scrisoare de la pozitia (z,t) daca si numai daca |x-z| ≤ |y-t| (timpul pentru a ajunge de la scrisoarea (x,y) la scrisoare (z,t) este cel putin egal cu diferenta in modul dintre sertare). De asemenea, este evident ca intr-o solutie optima, rutele vagoanelor alese nu se vor intersecta in plan.

O idee ce rezolva problema consta in a sorta punctele dupa suma coordonatelor (diagonala), si apoi sa folosim o abordare de tip greedy. Cum sortarea punctelor dupa diagonala este echivalenta cu rotirea planului la dreapta cu 45 de grade si apoi sortarea punctelor dupa coordonata x, vom efectua aceste operatii pentru simplitatea explicarii algoritmului ce urmeaza.

Presupunem ca am gasit o modalitate optima de aranjare a scrisorilor 1,2,...i-1 in k vagoane, fiecare vagon parcurgand in ordine un set de scrisori. Pentru a determina vagonul care selecteaza scrisoarea i, vom itera pe rand prin cele k vagonane, primul dintre acestea care poate sa-si continue ruta cu i fiind ales. In caz ca nu exista un astfel de vagon, vom incrementa numarul de vagoane, astfel i aflandu-se pe ruta vagonului k+1. Practic, vom atribui scrisoarea i primului vagon ce are ultima scrisoare din ruta la o inaltime de cel mult inaltimea scrisorii i. Aceasta solutie are complexitate O(N²) si aduce in jur de 40p.

Observatia ce ajuta la imbunatatirea solutiei este ca pentru sirul de vagoane, ultima scrisoare din ruta fiecarui vagon i va fi la o inaltime mai mare decat ultima scrisoare din ruta fiecarui vagon j, cu j≥i. Astfel, vom putea mentine un set cu ultimul punct de pe traseul fiecarui vagon, putand determina vagonul corespunzator pentru scrisoarea curenta in O(logN). Complexitatea acestei solutii este O(N logN) si aduce punctajul maxim.