100 - Regex
Varianta lunga
1 #!/usr/bin/perl -w 2 use v5.14; 3 4 my $line = <>; 5 if ($line =~ /Yardi/) { 6 say 'YES' 7 } else { 8 say 'NO' 9 }
Varianta normala
1 print <> =~ /Yardi/ ? 'YES' : 'NO'
Varianta scurta
1 print<>=~Yardi?YES:NO(Surse de Marius Gavrilescu)
250 - Ticket
1 #include <iostream> 2 #include <string> 3 #include <map> 4 #include <deque> 5 using namespace std; 6 map<string,string> coresp; 7 map<string,bool> e_nume; 8 deque<string> coada[105]; 9 map<string,int> unde; 10 11 int main() { 12 int n,m,t,i,tip,x; 13 cin>>n>>m; 14 string nume,prenume; 15 for(i=0;i<m;i++) { 16 cin>>nume>>prenume; 17 coresp[nume]=prenume,coresp[prenume]=nume; 18 e_nume[nume]=1; 19 unde[nume]=-1; 20 } 21 cin>>t; 22 for(i=0;i<t;i++){ 23 cin>>tip; 24 if(tip==1) { 25 cin>>x; 26 deque<string>::iterator it; 27 for(it=coada[x].begin();it!=coada[x].end();it++) 28 unde[*it]=-1; 29 coada[x].clear(); 30 } else if(tip==2){ 31 cin>>x>>nume; 32 if(!e_nume[nume]) 33 nume=coresp[nume]; 34 unde[nume]=x; 35 coada[x].push_back(nume); 36 } else if(tip==3){ 37 cin>>x; 38 unde[coada[x].front()]=-1; 39 coada[x].pop_front(); 40 } else if(tip==5){ 41 cin>>nume; 42 if(!e_nume[nume]) 43 nume=coresp[nume]; 44 cout<<unde[nume]<<'\n'; 45 } else{ 46 cin>>x; 47 if(coada[x].empty()){ 48 cout<<"-1\n"; 49 continue; 50 } 51 deque<string>::reverse_iterator it; 52 it=coada[x].rbegin(); 53 cout<<*it<<' '<<coresp[*it]; 54 for(it++;it!=coada[x].rend();it++) 55 cout<<' '<<*it<<' '<<coresp[*it]; 56 cout<<'\n';} 57 } 58 return 0; 59 } 60(Sursa de Andrei Constantinescu)
500 - Matrix
O(n2*m2)
Putem considera matricea ca fiind un graf neorientat, cu noduri in patratele cu 1. Acum, daca construim cate un arbore dfs din fiecare nod al grafului, cel putin un ciclu ce contine nodul din care am pornit parcurgerea dfs va fi format din muchii de arbore si o singura muchie inversa (in cazul in care exista un astfel de ciclu). Se demonstreaza usor ca o muchie de intoarcere cu un capat in nodul de plecare este necesara si suficienta pentru un ciclu din nodul de placere. Aceasta solutie este ineficienta, neincadrandu-se in timp. O(n*m)
Solutia buna se bazeaza pe solutia de mai sus. Problema este strans legata de determinarea punctelor de articulatie ale grafului. Pentru aceasta vom construi arborele dfs al grafului. Vom retine pentru fiecare nod h[i] - inaltimea nodului i din graf si o dinamica low[i] = cea mai mica inaltime la care se poate ajunge plecand din nodul i, mergand pe un lant in jos si apoi pe o muchie de intoarcere. Cu acestea cunoscute (relatia de recurenta este aceasi ca cea de la determinarea punctelor de articulatie), un nod i face parte din cel putin un ciclu daca si numai daca low[i]<=h[i] . Complexitatea toatala este astfel O(n*m), construind cate un astfel de arbore pentru fiecare componenta conexa a grafului. 1 void dfs(int i,int j,int a,int b, int h) { 2 viz[i][j]=1; 3 depth[i][j]=low[i][j]=h; 4 int ok=0; 5 for(int d=0; d<4; ++d) { 6 int ii=i+dx[d],jj=j+dy[d]; 7 if(!isIn(ii,jj) || mt[ii][jj]=='0') continue; 8 if(ii==a && jj==b) continue; 9 if(!viz[ii][jj]) { 10 dfs(ii,jj,i,j,h+1); 11 if(low[ii][jj]<=depth[i][j]) ok=1; 12 low[i][j]=min(low[i][j],low[ii][jj]); 13 }else { 14 low[i][j]=min(low[i][j],depth[ii][jj]); 15 if(depth[ii][jj]<=depth[i][j]) ok=1; 16 } 17 } 18 rez+=ok; 19 } 20
1000 - Worms
De aceasta problema s-a lovit autorul cand a implementat un engine de Worms.
Se realizeaza operatiile de query si update exact cum sunt ele prezentate in enunt, element cu element. Aceasta solutie este prea inceata pentru a trece de testele oficiale, desi a pacalit multa lume, trecand cu succes de preteste.
Vom imparti sirul in bucati de lungime fixa
Solutiile in
O(N*M)
Se realizeaza operatiile de query si update exact cum sunt ele prezentate in enunt, element cu element. Aceasta solutie este prea inceata pentru a trece de testele oficiale, desi a pacalit multa lume, trecand cu succes de preteste. O(NsqrtN)
Vom imparti sirul in bucati de lungime fixa SQ = sqrtN, tinand minte pentru fiecare bucata all[piece] - daca elementele din bucata piece au toate aceeasi valoare si vl[piece] - ce valoare au elementele din acea bucata. Acum la fiecare update daca bucata pe care o consideram este inclusa complet in intervalul curent, vom actualiza all si vl. Insa daca intervalul se intersecteaza cu partea pe care facem update vom lucra cu sirul initial actualizand fiecare element din acesta facand maxim SQ calcule. Aceasta solutie este in opinia unui membru al comisiei bucati de sqrt cu lazy update. O(Nlog2N) si O(NlogN)
Solutiile in O(Nlog2N) si O(NlogN) raman tema cititorului, acestea fiind asemanatoare cu multe probleme propuse la diverse concursuri de informatica. Implementarea acestor solutii era mult mai dificila decat solutia de mai sus, nefiind necesare pentru incadrarea in timp. Solutie bonus
In loc sa retinem tot sirul vom retine in nodurile unei liste simplu inlantuite doar capetele intervalelor umplute cu 0 sau 1 si valoarea din interval. Se observa ca nu e necesar sa retinem nodurile sub forma de interval ci putem sparge intervalula, b in 2 noduri a, b+1. In fiecare nod vom retine valoarea din sir care incepe pe pozitia din nod si se continua pana la pozitia urmatorului nod. De exemplu, pentru sirul: 0 0 1 0, vom avea nodurile (1,0), (3,1), (4,0). La fiecare update vom sparge niste intervale actualizand corespunzator nodurile din lista. Pentru aceasta avem nevoie de cel mai apropiat nod din stanga si din dreapta nodurilor a si b. Pentru aceasta putem folosi un skip list si sa obtinem complexitatea O(NlogN). Aceasta solutie e utila cand nu stim dimensiunea sirului si cand putem avea multe operatii.
