Solutii Summer Challenge 2009, Runda 1
Joc11
Soluţie: O(N3) Timp, O(N2) 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 LAk şi LBk 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 Tk,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 LAd-k[i], respectiv LBd-k[j]. Dacă jucătorul B are strategie sigură de câştig atunci Tk,i,j este false. Observăm că listele LAd şi LBd sunt identice iar T0,i,j este true pentru toţi i şi j pentru care LAd[i] ≠ LBd[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 NextAk,i lista poziţiilor din LAd-k+1 în care jucătorul A poate muta din poziţia LAd-k[i]. Fie NextBk,i lista definită în mod asemănător pentru jucătorul B. Observaţia precedentă se traduce prin: dacă există un i' din NextAk,i, oricare ar fi j' din NextBk,j, să avem Tk-1,i',j' = true, atunci Tk,i,j este true. Altfel, Tk,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ă Td,1,1 este true.
Soluţia obţine punctajul maxim.
Soluţie: O(N3logN) Timp, O(N3) Memorie
Această soluţie este similară cu cea precedentă, cu diferenţa că vom ţine un dicţionar, cu semnificaţia Tax, 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 (ax, ay) iar B în (bx, by). Dicţionarul adaugă un factor de logN la complexitatea soluţiei şi reţine O(N3) memorie.
Soluţia obţine 60 de puncte.
Soluţie: O(N3) Timp, O(N4) 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 a1x + b1y1 + c1 = 0, avem y = (-ax - c) / b şi y1 = (-a1x - c1) / b1. Dacă x este foarte mic (tinde spre minus infinit) atunci y > y1 dacă -a/b > -a1/b1. 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(N2) 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.