usaco jan2005, silver, watchcow

[•rgrig]

Asta e a doua oara cand particip la usaco si rezultatul e jalnic:
 1. la "sumset" am uitat sa iau modulo 1e+9
 2. la volume am lucrat pe 32b
 3. la "watchcow" am iesit din timp

Problema "watchcow" a fost ceva nou

• pt mine. As vrea sa stiu daca abordarea e proasta sau pur si simplu am implementat prost. Am facut:

Cod:

S = multime vida de cicluri
reprezentare prin liste de adiacenta (cu cate doua muchii orientate pt. fiecare din enunt)
cat timp graf mai are muchii
  fa dfs si gaseste un ciclu C
  pentru fiecare ciclu X din multimea de cicluri S
    daca C il atinge pe X
       uneste C cu X; elimina pe X din S
   adauga pe C la X
scrie unicul (?) ciclu ramas in S

multumesc,
 radu

• nu rideti, n-am facut niciodata informatica in mod formal (i.e. la scoala)

[•rgrig]

oops, am omis:

ultima actiune din ciclul "cat timp" este "sterge muchiile lui C din graf"

[•silviug]

Salutare. Nu am avut rabdare sa vad ce face algoritmul tau. Deci voi trece direct la explicatii: problema se reduce la a gasi un ciclu eulerian intr-un graf orientat. Reamintesc ca prin ciclu eulerian intelegem ciclu care viziteaza fiecare muchie o singura data.

Graful initial este neorientat dar il vom transforma usor intr-unul orientat inlocuind fiecare muchie cu doua muchii orientate opus. Avand graful nou format se face un DFS in care avem grija sa nu parcurgem o muchie de doua ori (in schimb se poate trece printr-un nod de mai multe ori!). Ciclul va fi format din toate nodurile atinse de DFS (cu tot cu repetitii!) scrise in ordine inversa.

DFS-ul ar arata asa:

Cod:

DFS(nod)
{
   pentru fiecare vecin X al lui nod
   {
       sterge muchia (nod, X)
       DFS(X)
   }
   ciclu(count) = nod;
   count = count + 1;
}

Sper ca e clar,

Silviu

[•rgrig]

Multumesc.

[•svalentin]

Dar ai grija in ce complexitate vezi vecinii nodului nod! adica daca vrei sa iti mearga rapid trebuie sa ii tii mine intr-o lista!
ex: daca nodul 5 are 3 vecinii: 1 2 3; poti tine minte ca v[5]={3, 1, 2, 3}
si ca sa nu ai probleme cu memoria lista o poti aloca dinamic
Astfel vei avea o complexitate O(M) (M=nr de muchii)

Si inca ceva ce am observat: daca faci recursiv, chiar si cu lista dinamica, nu iti intra in timp un test (cel putin mie nu mi-a intrat)... de aceea poti sa iti implementezi propria stiva. Adica in loc sa apelezi DFS(X), bagi X in fata stivei, iar in programul principal ai un while (stiva nu e goala) ...
Asta se intampla din cauza ca programului ii mai ia mai mult timp sa bage in stiva reala functia DFS, cu parametru X..
Si asa poti evita si probleme cu memoria (adica la USACO poti sa declari stiva ta global, unde ai 15M!)

[•silviug]

Ce bine le spune Vali.. ca un mare campion

[•rgrig]

Vad ca n-are nici o problema recursiv: cel mai mult dureaza 0.26s. Codul e aproape ca si pseudocodul:

Cod:

void dfs(int x)
{
    while (!g[x].empty())
    {
        int y = g[x].front();
        g[x].pop_front();
        dfs(y);
    }
    cycle.push_back(x+1);
}

[•svalentin]

Poate din cauza ca ai folosit STL-ul iti merge mai bine ca mine...
Asa am facut si eu, doar ca lista aia de muchii aveam eu grija de ea
Aveam un vector int *m[nr de noduri] si pt fiecare element din vector ii alocam memorie cat gradul fiecarui nod * int, apoi puneam in vector (care acum este o matrice bidimensionala) lista de noduri vecine pt fiecare nod.
Poate din cauza ca mai faceam aceste calcule in plus imi merge mai greu...

[•rgrig]

Nu prea cred ca e de la calculele astea. Cum "stergeai" muchiile? Eu tin lista de adiacenta intr-o lista inlantuita:

Cod:

vector<list<int> > g;

[•silviug]

Radule (probabil asa te cheama) ar fi marfa daca ai pune codul pe forum.. poate mai invata si baietii cate ceva (poate chiar si eu). STL stiu foarte putin dintre elevii din Romania si ar cam trebui sa inceapa sa invete..

Nu am vazut offtopic-ul tau despre angajare.. noi il asteptam

Numa bine,

Silviu

[•rgrig]

Asa ma cheama. Postul despre angajare este pus in "Off-topic". Probabil ca nu are un subject prea imbietor

Asta e codul complet (plus cateva comentarii ca sa nu va mirati de niste lucruri care par nenecesare):

Cod:

#include <iostream> // for debug
#include <fstream>
#include <list>
#include <vector>
#include <algorithm>
#include <iterator>

#define ALL(c) (c).begin(), (c).end()

using namespace std;

vector<list<int> > g;
vector<int> cycle;

void dfs(int x)
{
    while (!g[x].empty())
    {
        int y = g[x].front();
        g[x].pop_front();
        dfs(y);
    }
    cycle.push_back(x+1);
}


int main()
{
    ifstream inf("watchcow.in");
    ofstream outf("watchcow.out");
    istream& in = inf; // for debug: just change inf to cin to work with console
    ostream& out = outf; // for debug: just change outf to cout to work with console

    int N, M;
    in >> N >> M;
    g.resize(N);
    int i, j;
    int a, b;
    for (i = 0; i < M; ++i)
    {
        in >> a >> b;
        g[a-1].push_back(b-1);
        g[b-1].push_back(a-1);
    }

    dfs(0);
    copy(ALL(cycle), ostream_iterator<int>(out, "\n"));
}

OBS: daca l-as scrie din nou probabil n-as mai face translatarea range-ului de la 1..N la 0..N-1 si inapoi. Am facut-o doar pentru ca nu-mi place mie numaratul de la 1.

[•svalentin]

Eu "stergeam" muchiile marcandu-le cu -1... da, din cauza asta nu mi-a intrat in timp!