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.
