TAKMIČENJA IZ PROGRAMIRANJA


Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja možete slati na e-mail:

tak.prog@gmail.com

U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.

rostilj.cpp    4,674 b      izvorni kod rešenja
rostilj.tests.rar    63,835 b      test primeri
rostilj.checker.cpp    1,746 b      program za testiranje

zadatak: Roštilj

Jedan grad na samom jugu Bajtovije je nadaleko poznat po izvanrednom roštilju. Jednom godišnje, održava se festival, kada svi najbolji majstori roštilja dođu i takmiče se u tome ko će bolje pripremiti neke od poslastica: pljeskavice, vešalice, ćevape, ražnjiće, kobasice, batake, pečenje... Svake godine u to vreme vlada nezapamćeni haos u gradu, gužve na ulicama, zakrčenje saobraćaja.

Draganče je predsednik organizacionog komiteta Roštiljijade. On želi da organizuje dva kamiona punih mesa, koji bi se kretali gradom i prodavali đakonije. Zamišljeno je da kamioni krenu zajedno sa jedne raskrsnice i nađu se na drugoj, gde bi se prebrojalo ko je prodao više. Da kamioni ne bi bili jedan drugome direktna konkurencija, odlučeno je da ne smeju proći kroz istu raskrsnicu. Draganče ima mapu grada. Pomozite mu da pronađe dve raskrsnice koje omogućavaju ovakvu akciju.

Poznat je broj raskrsnica, N, ne veći od 5000, kao i to da broj ulica nije veći od 200000. Svaka ulica spaja dve raskrsnice. Neke ulice su jednosmerne, a neke dvosmerne. Sve raskrsnice su numerisane brojevima od 1 do N.

Ulaz:

U prvoj liniji ulaznog fajla rostilj.in se nalazi broj N. Zatim sledi N linija. U J-toj (J = 2, 3, …, N+1) liniji se nalazi najpre prirodan broj K, koji označava da za raskrsnicu J-1 postoji K raskrsnica do kojih se direktno (jednom ulicom) može stići iz raskrsnice J-1. Potom sledi K brojeva iz intervala 1..N, razdvojenih razmakom, koji označavaju te raskrsnice.

Izlaz:

U prvoj i jedinoj liniji izlaznog fajla rostilj.out treba ispisati dva broja X i Y koji kazuju da postoje dva disjunktna puta od X do Y. Putevi su disjunktni ako ne postoji raskrsnica (osim prve i poslednje) koja se nalazi i na jednom i na drugom putu. Garantuje se da će takve dve raskrsnice uvek postojati. U slučaju da postoji više rešenja, ispisati bilo koje. Red završiti oznakom za kraj reda.

Primer:

rostilj.in      rostilj.out
4
2 2 3
1 4
1 4
0
        
1 4

Objašnjenje:

Jedan način je 1 -> 2 -> 4, a drugi 1 -> 3 -> 4.

rešenje

Zadatak se može rešiti na više načina. Najpre ćemo prezentovati rešenje komisije, a potom i ostala rešenja koja su se pokazala jednako dobrim, ako ne i boljim u datom slučaju. Rešenja će biti predstavljena korišćenjem odgovarajuće terminologije iz teorije grafova, kojom se pretpostavlja da učenici više ili manje barataju. Ukoliko ima nejasnoća ili nepoznatih termina, preporučuju se knjige iz oblasti algoritama, kao i Internet kao sveobuhvatna literatura.

Rešenje komisije: Najpre ćemo podeliti graf na jako povezane komponente što se može jednostavno učiniti obilaskom grafa u dubinu i numeracijom čvorova. Problem delimo na dva dela, jedan je da tražimo rešenje kada su oba čvora u istoj kopmponenti, a drugo kada su u različitim komponentama.

  1. Tražimo rešenje u okviru jedne komponente. Izaberemo proizvoljan čvor u komponenti i napravimo dfs stablo od čvorova iz date komponente, sa korenom u izabranom čvoru. Pošto je komponenta jako povezana, dakle, postoji put iz korena do svih ostalih čvorova, svi čvorovi komponente će biti u dfs stablu. Svaka ivica unapred ("forward") ili poprečna ivica ("cross") koju pronađemo u komponenti nam sa sigurnošću daje rešenje. Njih ćemo detektovati i razlikovati na osnovu dfs brojeva koje dodeljujemo čvorovima, kao i markera čvorova koji nam govore da li je određeni čvor obiđen ili nije. Što se tiče povratnih ("back") ivica, sa njima treba vršiti posebnu proveru, zato što jedna povratna ivica ne donosi rešenje. Rešenje ćemo pronaći ako postoji čvor tako da postoje dve povratne ivice koje počinju u njegovim potomcima. To ćemo činiti tako što za svaki čvor pamtimo da li postoji povratna ivica koja počinje u njegovim potomcima i tu informaciju prosleđivati roditelju tog čvora. Kada pronađemo dve povratne ivice, pronašli smo i rešenje, koje rekonstruišemo uz pomoć informacije o roditeljima.
  2. Tražimo rešenje između komponenata. Konstruišemo novi graf koji smo dobili od početnog tako što je svaka komponenta zaseban čvor, a ivica između dve komponente postoji ukoliko postoji ivica između jednog čvora prve i jednog čvora druge komponte. Jasno je da novodobijeni graf neće imati ciklusa, jer bi postojanje ciklusa značilo da komponente nisu dobijene na pravi način. S obzirom da je novi graf acikličan, na njemu možemo primeniti algoritam topološkog sorta. Krenuvši od čvorova koji imaju izlazni stepen 0, za svaki čvor pamtimo listu čvorova čiji je on predak i tu informaciju prosleđujemo njegovim roditeljima. Kada se desi da je neki čvor roditelj dva različita čvora koji su preci jednom istom čvoru, rešenje je pronađeno. Ono što još preostaje je da se pronađu realni čvorovi u datim komponentama koji su početak i završetak ovih puteva. Oni se pronalaze tako što se čvorovi koji su nosioci ivica među komponentama pamte još u startu formiranja grafa komponenata. Još bi trebalo voditi računa u slučajevima kada iz jedne komponente u drugu postoje dve ivice, što nam odmah donosi rešenje.

Ukupna složenost ovog algoritma je u najgorem slučaju O(n2 + m), gde je n broj čvorova, a m broj grana u grafu.

Zadatak je uspešno, sa maksimalnih 100 poena rešilo četiri takmičara, Ilić Andreja, Rajko Nenadov, Stevan Jončić i Slobodan Mitrović. Svaka čast! Ovaj zadatak poseduje i daleko jednostavnije rešenje (rešenja) od zvaničnog rešenja komisije i ta rešenja su upravo implementirali ovi takmičari. Pa ipak postoji razlog zbog kog je gore navedeno rešenje zvanično: Teoretska složenost ovih algoritama u najgorem slučaju je O(n*m). Međutim, u praksi se pokazuje da je jako teško ili gotovo nemoguće napraviti test primere koji razlikuju ova dva rešenja.

Rešenja takmičara su se zasnivala na bfs i dfs pretragama i formiranju odgovarajućih stabala koja su se formirala sa korenom u svakom čvoru. Na sličan način kao u zvaničnom rešenju kada se traži rešenje u jednoj komponenti (prvi slučaj), traže se poprečne ivice i ivice unapred i tako pronalazi rešenje. Svakako, težina zadatka i jeste u tome da se primeti činjenica da ako graf poseduje mnogo ivica, rešenje će brzo biti pronađeno, a ako poseduje malo ivica, onda je n približno sa m, čime se i smanjuje vreme izvršavanja programa.

fajl: rostilj.cpp
#include <stdio.h>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;
const int MAXN = 5010;

vector<int> v[MAXN], kvb[MAXN];
vector<pair<int,int> > tc[MAXN];
int outdg[MAXN];
int n, sccn, dfsn;
int white = 0, grey = 1, black = 2;
int mark[MAXN];
int order[MAXN], low[MAXN], scc[MAXN], prev[MAXN];
int b[MAXN][MAXN];  // grane
int t[MAXN][MAXN];


stack<int> s;
FILE* f;

void init(){
     freopen("rostilj.in","r", stdin);
     f = fopen("rostilj.out","w");
}

void read(){
  int k;
    scanf("%d",&n);
    for (int i = 0; i < n; i++){
        scanf("%d",&k);
        outdg[i] = k;
        for (int j = 0; j < k; j++){
            int a;
            scanf("%d", &a);
            v[i].push_back(a-1);
        }
    }
}

void dfs_strongly(int k){
  s.push(k);
  low[k] = order[k] = dfsn++;
  mark[k] = grey;
  for (int i = 0; i < v[k].size(); i++)
    if (mark[v[k][i]] == white){
      dfs_strongly(v[k][i]);
      low[k] = min(low[k], low[v[k][i]]);
    }
    else{
      if (scc[v[k][i]]==-1) low[k] = min(low[k], order[v[k][i]]);
    }
  if (low[k] == order[k]){
    int x;
    do{
      x = s.top();
      s.pop();
      scc[x] = sccn;
    } while(x != k);
    sccn++;
  }
}

void finish(int a, int b){
  fprintf(f, "%d %d\n", a+1, b+1);
  fclose(stdin);
  fclose(f);
  exit(0);
}

void divide_components(){
  memset(mark, 0, sizeof(mark));
  memset(scc, -1, sizeof(scc));
  sccn = 0; dfsn = 0;
  for (int i = 0; i < n; i++)
    if (!mark[i]){
      dfs_strongly(i);
    }
  memset(outdg, 0, sizeof(outdg));
  memset(b, 0, sizeof(b));
  for(int i = 0; i < n; i++)
    for (int j = 0; j < v[i].size(); j++)
      if (!b[scc[i]][scc[v[i][j]]] && scc[i]!=scc[v[i][j]]){
        b[scc[i]][scc[v[i][j]]] = 1;
        kvb[scc[v[i][j]]].push_back(scc[i]);
        outdg[scc[i]]++;
      }
      else if (scc[i]!=scc[v[i][j]]) finish(i,v[i][j]);
}

int common_ancestor(int a, int b, int* prev){
  int m1[MAXN];
  memset(m1,0,sizeof(m1));
  while(1){
    if (a>-1){
      if (m1[a])
        return a;
      m1[a] = 1;
      a = prev[a];
    }              
    if (b>-1){
      if (m1[b])
        return b;
      m1[b] = 1;
      b = prev[b];
    }
  }
}


int dfs_inside(int k){
  order[k] = dfsn++;
  mark[k] = grey;
  int up = -1;
  for (int i = 0; i < v[k].size(); i++)
    if (scc[v[k][i]] == scc[k])
      if (mark[v[k][i]] == white){
        prev[v[k][i]] = k;
        int up1 = dfs_inside(v[k][i]);
        if (up1 >= 0)
          if (order[up1]<order[k])
            if (up < 0)
              up = up1;
            else 
              if (order[up]>order[up1])
                finish(k, up);
              else
                finish(k,up1);
        
      } else if (mark[v[k][i]]==grey){
        if (up < 0)
          up = v[k][i];
        else
          if (order[up]>order[v[k][i]])
            finish(k,up);
          else
            finish(k,v[k][i]);
      } else{
        finish(common_ancestor(k,v[k][i], prev),v[k][i]);
      }
  mark[k] = black;
  return up;
}

void find_in_components(){
  memset(mark, 0, sizeof(mark));
  memset(order, 0, sizeof(order));
  memset(prev, -1, sizeof(prev));
  dfsn = 1;
  for (int i = 0; i < n; i++)
    if (!mark[i])
      dfs_inside(i);
}

void finish_components(int a, int b, pair<int,int> d){
  int x, y, i, found = 0;
  for (x=0; x < n && !found; x++){
    if (scc[x] == a){
      for (i = 0; i < v[x].size() && scc[v[x][i]]!=b; i++);
          if (i < v[x].size()) found = 1;
        }
    }
    found = 0;
  for (y=0; y < n && !found; y++){
    if (scc[y] == d.second){
      for (i = 0; i < v[y].size() && scc[v[y][i]]!=d.first; i++);
        if (i < v[y].size()) found = 1;
        }
    }
  y = v[y-1][i];
  finish(x-1,y);
}

void find_among_components(){
  int i;
  queue<int> q;
  int order[sccn], topsortnum = 0;
  memset(t,0,sizeof(t));
  for (i = 0; i < sccn; i++)
    if (outdg[i] == 0)
      q.push(i);
  while(q.size()>0){
    int x = q.front();
    q.pop();
    order[x] = topsortnum++;
    pair<int,int> dest(-1,-1); int source = -1;
    for (i = 0; i < kvb[x].size(); i++){
      int y = kvb[x][i];
      pair<int,int> p(x,y);
      tc[x].push_back(p);
      if (--outdg[y] == 0)
        q.push(y);
      for (int j = 0; j < tc[x].size(); j++){
        if (t[y][tc[x][j].first] == 1)
          if (dest.first == -1)
            {dest = tc[x][j];source=y;}
          else
            {dest = order[dest.first]>order[tc[x][j].first]?dest:tc[x][j];source=y;}
        t[y][tc[x][j].first] = 1;
        tc[y].push_back(tc[x][j]);
      }
      tc[x].pop_back();
    }
    if (dest.first != -1) finish_components(source,x,dest);
  }  
}

int main(){
   init();
     read();
   divide_components();
   find_in_components();
   find_among_components();
   for (int i = 0; i < n ;i++)
     printf("%d\n",scc[i]);
   return 0;  
}