Solutii la concursul acm 2013 etapa nationala partea I

Solutii la concursul ACM ICPC 2013 etapa nationala partea I

iar clasamentul 'aici':http://acm.tju.edu.cn/toj/vcontest/ranklist9268.html
La concurs au participat peste 50 echipe iar setul de probleme a fost unul echilibrat.

Voi prezenta in continuare o parte din probleme şi soluţiile acestora

Înainte de concurs au mai avut loc 3 concursuri de pregătire. Problemele le găsiţi 'aici':https://www.facebook.com/download/158072191033228/problems.pdf 'aici':http://acm.tju.edu.cn/toj/vcontest/contest9254.html şi 'aici':http://acm.tju.edu.cn/toj/vcontest/contest9266.html
 
Voi prezenta in continuare o parte din probleme şi soluţiile acestora. Vă invit să contribuiţi la comentarii cu soluţiile voastre

h2. 'G. Election Time':http://acm.tju.edu.cn/toj/vcontest/showp9268_G.html
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 după primul tur rămâneau doar primii k candidati.

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 votur din al doilea tur. Pentru a nu complica implementarea am ales sortarea unui vector de indici in funcţie de numărul de voturi.

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.

== code(cpp) |
#include <iostream>

==code(cpp)|
//Cristian Lambru
#include<iostream>

#include<cstdio>

#include<vector>
using namespace std;

#define ld long double
int N;

int T[MaxN],Fii[MaxN],viz[MaxN];

ld Suma = 0;
int Fii[MaxN],viz[MaxN];

vector<pair<int,int> > A[MaxN];

void citire(void)
{
    int a,b,c;
 
    scanf("%d",&N);
    for(int i=1;i<N;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        A[a].push_back(make_pair(b,c));
        A[b].push_back(make_pair(a,c));
    }
}
 
inline void DF(int nod)

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])
        {

            DF(i->first);
            T[i->first] = nod;

            parcurgere(i->first);

            Fii[nod] += Fii[i->first];

        }
}
inline double suma(void)
{
    ld sum = 0;
 
    for(int i=0;i<=N;i++)
        for(it j=A[i].begin();j<A[i].end();j++)
            if(j->first > i)
            {
                if(T[i] != j->first)
                    sum += (ld)j->second*Fii[j->first]*(N-Fii[j->first]);
                else
                    sum += (ld)j->second*Fii[i]*(N-Fii[i]);
            }
 
    return sum/((ld)N*(N-1)/2);
}
 
inline void sterge(void)
{
    for(int i=0;i<N;i++)
        A[i].clear(), Fii[i] = T[i] = viz[i] = 0;

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

}
int main()
{

    //freopen("test.txt","r",stdin);
    int T;
    scanf("%d",&T);
 
    for(int i=1;i<=T;i++)
    {
        citire();
        DF(0);
 
        printf("%lf\n",suma());
        sterge();
    }

    citire();
    parcurgere(0);

    return 0;

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

}
==

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.

Sursa

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.

==code(cpp)|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define x first
#define y second
#define DN 105
using namespace std;

h2. 'I. More lumber is required':http://acm.tju.edu.cn/toj/vcontest/showp9268_I.html

int n,m,pre[DN];
vector<pair<int,pair<int,int> > > mc;

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.

int find(int x) {
	if(pre[x]==x) return x;
	pre[x]=find(pre[x]);
	return pre[x];
}

Î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ă.

void unite(int x,int y) {
	pre[find(x)]=find(y);
}

h2. 'J. Template Library Management':http://acm.tju.edu.cn/toj/vcontest/showp9268_J.html

int main() {
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	for(;;) {
		cin>>n>>m;
		if(!n && !m) break;
 
		for(int i=0; i<m; ++i) {
			int a,b,c;
			cin>>a>>b>>c;
			mc.push_back(make_pair(c,make_pair(a,b)));
		}
		sort(mc.begin(),mc.end());
		int rez=(1<<30);
		for(int fm=0; fm<mc.size(); ++fm) {
//Alegem muchia care să aibă costul cel mai mic din apm
			int nrm=0,mx;
			for(int i=1; i<=n; ++i) pre[i]=i;
			for(int i=fm; i<mc.size(); ++i) if(find(mc[i].y.x)!=find(mc[i].y.y)) {
				unite(mc[i].y.x,mc[i].y.y);
				mx=mc[i].x;
				++nrm;
			}
			if(nrm==n-1) rez=min(rez,mx-mc[fm].x);
		}
		if(rez!=(1<<30)) cout<<rez<<'\n';
		else cout<<"-1\n";
		mc.clear();
	}
}
==

În această problemă se dă un vector $V$ de $N$ $(N<=100 000)$ $(V[i]<=10^9^)$ 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ă.
 
 
h2. 'K. Fast Arrangement':http://acm.tju.edu.cn/toj/vcontest/showp9268_K.html
 
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':http://www.infoarena.ro/problema/arbint
Pentru a rezolva corect problema trebuia observat că intervalele sunt deschise, deci intervalele $(3,4)$ şi $(4,5)$ nu se suprapun.

public

protected

9016