Solutii la concursul ACM ICPC 2013 etapa nationala partea I

Petru Trimbitas
17 iunie 2013

Duminică, 16 iunie a avut loc faza naţionala a concursului acm icpc. Pagina concursului o gasiţi aici
iar clasamentul aici
La concurs au participat peste 50 echipe iar setul de probleme a fost unul echilibrat.

Înainte de concurs au mai avut loc 3 concursuri de pregătire. Problemele le găsiţi aici aici şi aici

Voi prezenta in continuare o parte din probleme şi soluţiile acestora. Vă invit să contribuiţi la comentarii cu soluţiile voastre

G. Election Time

Aceasta a fost cea mai simplă problemă din concurs, fiind rezolvată de marea majoritate a echipelor.
Problema ne cerea să determinăm câştigătorul alegerilor dupa 2 tururi ştiind cate voturi va obţine fiecare candidat in cele 2 tururi. În plus în al doilea tur se calificau doar primii k candidati.

O soluţie ar fi sortarea candidaţilor descresrescător după numărul de voturi primite în primul tur, iar pe urmă sortarea primilor k după numărul de voturi din al doilea tur. Pentru a nu complica implementarea am ales sortarea unui vector de indici in funcţie de numărul de voturi.

#include <iostream>
#include <algorithm>
#define DN 50005
using namespace std;

int n,k,ind[DN],a[DN],b[DN];

bool cmp(int x,int y) {
	return a[x]>a[y];
}

bool cmp2(int x,int y) {
	return b[x]>b[y];
}

int main() {
	cin>>n>>k;
	for(int i=1; i<=n; ++i) {
		cin>>a[i]>>b[i];
		ind[i]=i;
	}
	sort(ind+1,ind+n+1,cmp);
	sort(ind+1,ind+k+1,cmp2);
	cout<<ind[1]<<'\n';
}

H. Stones II

A doua problema ca dificultate din concurs ne dădea N (N <= 100 000) grămezi de pietre şi ne cerea să le reunim cu un cost cât mai mic. Pentru a putea reuni grămezile putem lipi la un pas două grămezi cu un cost egal cu numărul de pietre din cele două grămezi la un loc.

Pentru a rezolva problema putem aplica o strategie de tip greedy în care la fiecare pas luăm cele mai mici două grămezi şi le reunim. Pentru a se încadra în timp şi pentru a fi corect e necesară folosirea unui multiset şi a tipului de date long long.

F. Average distance

După cum îi spune şi numele această problemă ne cere sa calculăm costul mediu al muchiilor dintr-un arbore.

Pentru a rezolva problema observăm că costul mediu e egal cu suma costurilor drumurilor din arbore împărţită la numărul total de drumuri.
Numărul de drumuri e egal cu N*(N-1)/2 (Combinări de N luate câte doua, fiecare drum fiind definit de 2 noduri).
Pentru a calcula suma costurilor drumurilor ne interesează fiecare muchie în câte drumuri apare.
O muchie (A,B) apare in orice drum definit de un nod din subarborele lui A(inclusiv A) şi de un nod care nu e in subarborele lui A.

//Cristian Lambru
#include<iostream>
#include<vector>
using namespace std;

typedef vector<pair<int,int> >::iterator it;

#define MaxN 110000
#define ld long double

int N;
ld Suma = 0;
int Fii[MaxN],viz[MaxN];
vector<pair<int,int> > A[MaxN];

inline void parcurgere(int nod)
{
    viz[nod] = 1;
    Fii[nod] = 1;
    
    for(it i=A[nod].begin();i<A[nod].end();i++)
        if(!viz[i->first])
        {
            parcurgere(i->first);
            Fii[nod] += Fii[i->first];

            Suma += (ld)(i->second)*Fii[i->first]*(N-Fii[i->first]);
        }
}

int main()
{
    citire();    
    parcurgere(0);

    cout << Suma/((ld)N*(N-1)/2);
}

E. Slim Span

Această problemă cere pentru un graf cu N (N<=100) noduri să aflăm diferenţa minimă dintre muchia de cost maxim şi cea de cost minim dintr-un arbore de acoperire al grafului.

Dimensiunea datelor de intrare ne permite ca pentru fiecare muchie să alegem doar muchii de cost mai mare până când obţinem un arbore de acoperire şi să alegem cea mai bună diferenţă dintre toţi arborii de acoperire obţinuţi.

I. More lumber is required

Problema aceasta ne dădea un graf ponderat şi ne cerea să aflăm timpul minim în care putem traversa graful din nodul S în nodul D şi în care strângem cel putin k unităţi de lemn. Atunci când traversăm o muchie primim 10 unităţi de lemn in plus.

În ciuda faptului că problema e o problemă clasică de drum minim, ea a fost rezolvată de puţine echipe. Pentru a rezolva formăm un graf în care nodurile sunt determinate de perechi de forma (nod iniţial, cantitate de lemn). În plus mai observăm că putem împărţi cantităţile de lemn la 10 şi că nu ne interesează cantităţile de lemn mai mari decât ,⌈K/10⌉. Acum trebuie doar să aplicăm un algoritm de drum minim pentru a afla timpul de parcurgere din nodul (S,0) în nodul (D,⌈K/10⌉). Pentru a lua AC era suficienta folosirea algoritmului Bellman Ford cu coadă.

J. Template Library Management

În această problemă se dă un vector V de N (N<=100 000) (V[i]<=10⁹) elemente şi o listă de dimensiune M în care iniţial sunt numerele de la 1 la M. Pentru a trece mai departe de la poziţia i trebuie să avem în listă valoarea V[i]. La orice moment de timp putem înlocui un număr din listă cu orice alt număr care nu se află deja in ea. Problema ne cere numărul minim de înlocuiri cu care putem parcurge vectorul.

Vom încerca să aplicăm o strategie de tip greedy pentru a rezolva problema. La fiecare pas la care elementul de pe poziţia i nu se află în listă trebuie să decidem ce element trebuie să eliminăm. Se observă că este optim să eliminăm elementul din listă care apare în vector pe cea mai din dreapta poziţie sau care nu apare deloc. Pentru a calcula această informaţie vom calcula un vector next[i] cu semnificaţia: prima poziţie > i pe care apare elementul V[i]. Având această informaţie calculată putem simula lista cu un max heap în care vom ţine elementele ordonate în funcţie de poziţiile pe care urmează să apară.

K. Fast Arrangement

Aceasta a fost probabil problema cu cele mai multe submisii incorecte. Aceasta ne cerea să acoperim cu intervale axa ox ştiind că intr-un loc nu pot să se suprapună mai mult de K intervale. Pentru fiecare interval dat (cel mult 100 000) trebuia să se precizeze dacă poate fi plasat iar în caz afirmativ trebuia plasat.

În mod evident problema e una clasică de structuri de date. Avem nevoie de o structură de date care să ne permită adunarea unei valori asupra tuturor elementelor dintr-un interval şi aflarea valorii maxime dintr-un interval. Problema se putea rezolva cu arbori de intervale
Pentru a rezolva corect problema trebuia observat că intervalele sunt deschise, deci intervalele (3,4) şi (4,5) nu se suprapun.