Diferente pentru blog/acm-2013-etapa-nationala intre reviziile #7 si #27

Diferente intre titluri:

Solutii la concursul acm 2013 etapa nationala partea I
Solutii la concursul ACM ICPC 2013 etapa nationala partea I

Diferente intre continut:

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>
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.
==code(cpp)
==code(cpp)|
//Cristian Lambru
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
 
 
typedef vector<pair<int,int> >::iterator it;
 
#define MaxN 110000
#define ll long double
 
#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(int i=0;i<A[nod].size();i++)
        if(!viz[A[nod][i].first])
    for(it i=A[nod].begin();i<A[nod].end();i++)
        if(!viz[i->first])
        {
            DF(A[nod][i].first);
            T[A[nod][i].first] = nod;
            Fii[nod] += Fii[A[nod][i].first];
            parcurgere(i->first);
            Fii[nod] += Fii[i->first];
 
            Suma += (ld)(i->second)*Fii[i->first]*(N-Fii[i->first]);
        }
}
 
inline double suma(void)
{
    ll sum = 0;
 
    for(int i=0;i<=N;i++)
        for(int j=0;j<A[i].size();j++)
            if(A[i][j].first > i)
            {
                if(T[i] != A[i][j].first)
                    sum += (ll)A[i][j].second*Fii[A[i][j].first]*(N-Fii[A[i][j].first]);
                else
                    sum += (ll)A[i][j].second*Fii[i]*(N-Fii[i]);
            }
 
    return sum/((ll)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;
}
 
 
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();
    }
 
    return 0;
    citire();
    parcurgere(0);
 
    cout << Suma/((ld)N*(N-1)/2);
}
==
==
 
h2. 'E. Slim Span':http://acm.tju.edu.cn/toj/vcontest/showp9268_E.html
 
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.
 
h2. 'I. More lumber is required':http://acm.tju.edu.cn/toj/vcontest/showp9268_I.html
 
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ă.
 
h2. 'J. Template Library Management':http://acm.tju.edu.cn/toj/vcontest/showp9268_J.html
 
Î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.

Diferente intre securitate:

public
protected

Diferente intre topic forum:

 
9016