Despre Blog

# Olimpiada Nationala de Informatica pentru Studenti 2014

Teodor Plop
20 mai 2014

In acest weekend, la Bucuresti a avut loc runda finala a primei editii a Olimpiadei Nationale de Informatica pentru Studenti. Au participat peste 20 echipe din tara, doua zile de concurs, aceleasi taste apasate si multe pizza consumate. Felicitari tuturor participantilor si multumiri sponsorilor si partenerilor nostri pentru implicare: Fundatia eMAG, Bitdefender, TechHub, Asociatia Studentilor la Matematica si Informatica, Facultatea de Matematica si Informatica, Universitatea din Bucuresti. Speram ca a fost o experienta placuta pentru toti si va asteptam si la anul, in numar cat mai mare!

Clasament Runda Finala

Clasament ACM-ICPC Faza Nationala

Poze

Categorii:

# Why your bisection search is wrong

Cosmin Negruseri
19 mai 2014

What is bisection search? The bisection method or bisection search is a numerical algorithm for finding a value x such that f(x) = 0, for a given continuous function f. It works by repeatedly bisecting an interval and choosing a subinterval that contains x. It's pretty simple and robust, but it has few gotchas.

Let's solve the following problem:

For a given number c find it's cubic root using the +, -, *, / operations.

Let's choose f(x) = x3 - c. f is continuous and x is the cubic root of c, when f(x) = 0. Thus, we can apply the bisection method.

``````def cubicRoot(c):
lo, hi = 0.0, c
while lo * lo * lo != c:
mid = (lo + hi) / 2
if mid * mid * mid < c:
lo = mid
else:
hi = mid

return lo``````

Any bugs? Well, quite a few. Try to spot as many as you can, before reading on.

You may notice the precision issue right from the start. We'll discuss it a bit later.

What else? The code doesn’t work for negative values of c. This is easily fixable:

``````def cubicRoot(c):
lo, hi = 0.0, c
while lo * lo * lo != c:
mid = (lo + hi) / 2
if mid * mid * mid < c:
lo = mid
else:
hi = mid

return lo

def cubicRoot(c):
if c < 0:
return - _cubicRoot(-c)
else:
return _cubicRoot(c)
}``````

What else? This code doesn't work for c = 1/1000. Why is that? We’re setting the cubic root upper limit to c (line 3). But, the cubic root of c in (0, 1) is larger than c, meaning the upper bound we’re setting is wrong.

Let's fix it:

``````def _cubicRoot(c):
lo, hi = 0.0, max(1, c)

while lo * lo * lo != c:
mid = (lo + hi) / 2
if (mid * mid * mid < c):
lo = mid
else:
hi = mid

return lo

def cubicRoot(c):
if c < 0:
return -_cubicRoot(-c)
else:
return _cubicRootABS(c)``````

Going back back to the precision issue:

If you've read nearly all binary searches and merge sorts are wrong you know that mid = (lo + hi) / 2 has an overflow problem. So we change that line to mid = lo + (hi - lo) / 2.

Testing for equality doesn't work with floating point numbers. The first idea that comes to mind is to use an absolute error comparison (|a - b| < eps).

``while lo * lo * lo != c:``

switch to

``while abs(c - lo * lo * lo) > 1e-3:``

This doesn't work. For large numbers like 1e37 the code goes into an infinite loop. Try to figure out why. Discuss it in the comment section. Let’s try using the relative error (|(a - b) / b| < eps). There are some weird cases when a and b are close or equal to 0. Can the code be cleaner?

After each while loop iteration we learn something new about x’s range. A double has only 64 bits of precision. So instead of a tricky floating point stopping criteria we can run the loop a fixed number of times so that the interval is as small as the precision of our floating point numbers allows.

Tomek Czajka(of topcoder fame) pointed out that my final version was buggy as well. I chose the number of iterations to be 120 but that’s way too small. It doesn't work for c = 1e60.

A double is represented by the mantissa which consists of 52 bits and the exponent which contains 11 bits(signed). One loop iteration either decreases the exponent of our interval by 1 or we find out a new bit of the mantissa. The maximum value of the exponent is 210 and the mantissa has 52 bits. Thus we need about 1100 steps to figure out the answer.

``````def _cubicRoot(c):
lo, hi = 0.0, max(1, c)

for iter in range(0, 1100):
mid = lo + (hi - lo) / 2
if (mid * mid * mid < c):
lo = mid
else:
hi = mid

return lo

def cubicRoot(c):
if c < 0:
return -_cubicRoot(-c)
else:
return _cubicRoot(c)``````

No more epsilon! But now, because of cases with large exponents, the code runs pretty slow on all cases. An idea is to stop as soon as we don't decrease the lo..hi interval, instead of doing a constant number of iterations. So here’s this faster version:

``````def _cubicRoot(c):
lo, hi = 0.0, max(1, c)
prev_range_size = hi - lo
while True:
mid = lo + (hi - lo) / 2
if (mid * mid * mid < c):
lo = mid
else:
hi = mid
if hi - lo == prev_range_size:
break
prev_range_size = hi - lo

return lo

def cubicRoot(c):
if c < 0:
return -_cubicRoot(-c)
else:
return _cubicRoot(c)``````

This is still slow when we’re dealing with large numbers. To address it one can binary search first on the exponent, or get close to the real exponent by dividing the original exponent by 3. Try it out in the comment section.

I'm curious, did your solution have any of these problems?

notes:

• Thanks Tomek for pointing out the iteration problem and possible efficient solutions.
• When c is large, mid * mid * mid will overflow but the algorithm still works.
• We’ve addressed negative numbers, numbers in (0, 1), overflow problems, absolute and relative error problems.
• Some tests for your own code -1, 0, 1, 2, 8, 0.001, 1e30, 1e60
• In practice faster methods like Newton Rapson method are used.
Categorii:

# Binary Search Shortlist

Cosmin Negruseri
16 mai 2014

Figure out an algorithm for each of the following problems. What’s the complexity? Code it.

1. Given A, a sorted int array of length n. How many times does the value x occur in A.
2. Given a real number x, find out it’s cubic root.
3. Given A a sorted array of distinct integers, find out an i such that A[i] == i.
4. Given the +,-,*,/,sqrt operations and a real number x find an algorithm to get log_2(x).
5. Given an array A such that A[ 0] > A[ 1] and A[n-1] > A[n-2] find out a local minimum (find out an i such that A[i-1] > A[i] < A[i + 1]).
6. Let A be a sorted array with distinct elements. A is rotated k positions to the right (k is unknown). Find out k.
7. Let A be a sorted array with distinct elements. A is rotated k positions to the right (k is unknown). Find out if A contains a number x.
8. Given two sorted arrays of length n and m, find out the kth element of their sorted union.
9. An array is bitonic if it is comprised of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Write a program that, given a bitonic array of N distinct int values, determines whether a given integer is in the array.
10. Write a program that, given an array of N distinct int values in ascending order, determines whether a given integer is in the array. You may use only additions and subtractions and a constant amount of extra memory. The running time of your program should be proportional to log N in the worst case.
Categorii:

# Interviu cu romanii acceptati in YCombinator

Cosmin Negruseri
10 aprilie 2014

Razvan si Radu de la stanga la dreapta

Radu Spineanu si Razvan Roman sunt fondatorii companiei Two Tap. Ei au format prima echipa de romani acceptati in YCombinator, cel mai renumit incubator de startups din Silicon Valley. Prin YCombinator au mai trecut companii ca reddit, AirBNB sau dropbox. Acum sunt si in faza de crestere a echipei tehnice, cauta ingineri foarte buni la inceputul carierei. Puteti sa ii contactati la [email protected]

1. Spuneti-ne putin despre voi si despre TwoTap.

Radu: Backgroundul meu este de Network Engineer (am lucrat 5 ani la RoEduNet). Am inceput sa fac companii in timpul facultatii. Printre multe am fondat 2Parale, cea mai mare retea de afiliere din RO. De asemenea am creat prima aplicatie care permitea crearea de cinemagraphs pe iOS, care a fost featured de Apple si a avut in jur de 1 milion de downloaduri). In timpul liber sunt Developer Debian (o distributie Linux).

Razvan: Am invatat sa scriu si sa citesc cand aveam 5 ani pe un HC91 pe care am petrecut mult timp datorita Lode Runner, Dizzy si altele. Odata cu o conexiune broadband multi ani mai tarziu am avut acces la tot ce inseamna knowledge despre startupuri, in perioada in care Napster era hot. Dupa ce am pornit primul startup in liceu a urmat o lunga serie de eforturi cu rezultate mixte dar din care am invatat foarte mult despre factorii care influenteaza succesul unui startup, vazuti din multe perspective: am facut tot, de la copywriting si marketing la sales si programare sau recrutare, atat in RO cat si EU/UK sau US.

Two Tap rezolva o problema fundamentala a ecommerce-ului: in mod traditional daca vrei sa cumperi un produs trebuie sa mergi pe site-ul merchant-ului. Dar cum userii petrec timp pe diverse device-uri in prezent e foarte dificil sa faci o tranzactie oriunde in afara unui browser conventional. Two Tap permite userilor sa cumpere produsele atunci cand iau decizia respectiva, fie ca sunt intr-un FB app, intr-un app nativ sau pe mobile web, practic oriunde se afla. Asta se datoreaza API-ului care sta la baza Two Tap, API care poate plasa comenzi pe platformele retailerilor.

2. Piata angajatorilor in domeniu software e foarte activa. Corporatiile concureaza acerb pentru oameni foarte competenti. Ati refuzat traseul corporatist si ati ales sa fondati un startup. Cum ati luat decizia?

Radu: Intr-o corporatie esti doar o rotita dintr-un sistem enorm. Oportunitatea de a face ceva meaningful pornind de la zero e aproape inexistenta. In final avem doar o viata, si viata trebuie traita. De asta facem ceea ce facem. Pentru ca vrem ca atunci cand avem 80 de ani sa ne numaram cicatricile si traumele psihologice sa radem de fericire fara nici un regret.

Razvan: Impartasim mult perspectiva asta. Cand am o decizie importanta de facut intotdeauna ma gandesc daca voi regreta faptul ca nu am incercat optiunea care pare riscanta peste cativa ani. Daca raspunsul e da atunci las frica deoparte si merg inainte, oricat de dificil poate parea initial. Cred ca e mai dificil decat o cariera conventionala dar asta ma face fericit. Cred totodata ca lucrand cu un startup 2 ani inveti foarte mult fata de acelasi timp petrecut intr-o corporatie.

3. De ce Silicon Valley si nu Romania sau Europa?

Radu: Nu e nimic rau in a face o companie in Romania sau Europa. Prima companie fondata de mine a fost in Romania (se numeste 2Parale) si a fost una din cele mai misto experiente pe care le-am avut.

In acelasi timp e important sa 'always shoot for the stars'. Cand am inceput 2Parale nu stiam nimic despre startupuri, in nici o secunda nu m-am gandit ca as putea sa incep o companie in US. Si apoi incet incet am invatat tot mai multe, lucrurile au devenit mai clare, si drumul a fost evident.

Razvan: Starea economiei impiedica dezvoltarea unui startup pe o traiectorie normala de crestere. Oricat de bun esti exista limite date de piata locala care te obliga sa te plafonezi destul de repede. In Romania (si de multe ori Europa) greu te lovesti de problema de a scala produsul tau la zeci de milioane de useri, pe cand in SV asta e un given, te vei lovi de asta.
E foarte contraintuitiv dar din multe puncte de vedere e mai usor sa faci un startup in SV decat RO odata ce treci de barierele initiale. Daca ai product market fit ai din start o piata locala de 300M de consumatori care vor produsul tau, vorbesc aceeasi limba si au venituri substantiale pe care le pot cheltui.

4. Interviurile pentru intrarea in YCombinator sunt renumite. Povestiti-ne experienta voastra.

Radu: Am aplicat in total de cinci ori si am fost invitat la interviu de trei ori. PG scrie esee despre ceea ce cauta, dar probabil varianta scurta ar fi: echipa (accomplishments notabile, track record, fara accent, a cultural fit cu comunitatea YC), traction (daca compania ta face milioane de dolari pe zi that trumps everything), perseveranta, si un mod specific de a gandi asupra lucrurilor (foarte importanta e intrebarea about hacking a non-computer system).

YC a nimerit perfect momentul in care sa ne accepte ca sa folosim la maxim potentialul programului. O companie poate sa fie prea devreme in dezvoltarea ei, prea tarziu, sau poate sa fie nepotrivita cu viziunea YC. E greu sa iti dai seama cand e acel moment, dar probabil e atunci cand realizezi ca proiectul s-ar putea descurca bine-mersi si fara sa fie acceptat.

Natura interviului si interactiunea depinde de foarte multi factori si e greu de prezis.

5. Cum se compara experienta YCombinator cu munca pe cont propriu?

Razvan: Cel mai mare impact al YCombinator asupra companiei tale e faptul ca iti elimina toate lucrurile care iti pot distrage atentia timp de 3 luni. Elementul asta de focus extrem dublat de faptul ca esti inconjurat de alte echipe care trec prin aceeasi experienta e foarte motivant. Multe din companiile care trec prin program ajung sa fie lideri pe segmentul lor de piata in cele 3 luni.
Imaginati-va cum e sa lucrati la un mail client si sa aveti ca mentor pe Paul Buccheit (creatorul Gmail) sau Geoff Ralston care a fondat Rocket Mail, devenit mai tarziu Yahoo Mail.
In fiecare marti YCombinator organizeaza o cina pentru fondatori, eveniment unde participa oameni foarte influenti din SV, de la Marc Andreessen (creatorul Netscape, primul browser) pana la Ron Conway sau Mark Zuckerberg. Totul intr-o atmosfera casual, off the record si multe discutii la liber. Doar cateva sute de oameni au avut acces la resursele astea pana acum prin YCombinator.

6. Care sunt problemele cele mai grele pe care le rezolvati? Sunt de natura tehnica sau pe partea de business?

Radu: Two Tap rezolva o problema tehnica foarte complicata: cum abstractionezi mii de magazine prost facute intr-un API curat si reliable fara ca ele sa faca nimic (0 integrare). Iar dupa ce ai API-ul cum creezi cea mai buna experienta de shopping din lume pe orice platforma.

La Two Tap creem un layer care sta deasupra tot ce inseamna online ecommerce, care intelege mii de magazine. La core e un scraper hiper inteligent, iar posibilitatile cu ce putem face cu el sunt endless.

7. Ce sfaturi aveti pentru programatorii din comunitatea infoArena?

Radu: Sa nu se angajeze la o multinationala. Cand eram la RoEduNet cineva imi povestea ca cel mai mare pericol de a avea un job e ca devii comfortabil. Te obisnuiesti sa iesi in oras in fiecare seara, sa iti iei haine scumpe, sa mergi in vacante de doua ori pe an, sa iti iei rate, sa te casatoresti.

Este enorm de mult timp sa faci asta la 35-40 de ani. La 20 de ani e momentul sa fii curajos, sa faci chestii care schimba lumea, chiar daca unii le considera idioate sau a long shot. E important sa nu ai nici un regret mai incolo.

Razvan: La ce a zis Radu as adauga faptul ca e important sa se gandeasca foarte bine la parcursul profesional. Barierele lingvistice sau de distanta devin din ce in ce mai insignifiante si e mult mai usor decat pare la prima vedere sa lucreze la ceva care poate avea un impact major si deschide niste drumuri necalcate in loc de a invata o tehnologie proprietara a unei corporatii mari care tot ce vrea e sa maximizeze profiturile.

Mult curaj! Si luati legatura cu noi daca putem ajuta, am fost la randul nostru ajutati de multi oameni de-alungul anilor si ne face mare placere sa pay it forward.

Radu si Razvan, va multumim pentru interviu! Pentru orice startup problema angajarii de oameni buni e esentiala. Two Tap cauta oameni buni la inceputul carierei. Ii puteti contacta pe [email protected]

Categorii:

# Zece

Cosmin Negruseri
28 martie 2014

Infoarena aniverseaza luna aceasta 10 ani!

Categorii:

# Lansarea concursului naţional de algoritmică MindCoding

Petru Trimbitas
20 ianuarie 2014

## Lansarea concursului naţional de algoritmică MindCoding

Concursul Naţional MindCoding este un proiect care vine în atenţia pasionaţilor de informatică din întreaga ţară, indiferent de vârstă, încurajând dezvoltarea unei comunităţi de persoane pasionate de algoritmică, şi nu numai.
Concursul va avea 4 runde online ce se vor desfăşura pe site-ul competiţiei www.mindcoding.ro , urmând ca runda finală să aibă loc în perioada 11-13 aprilie 2014 în municipiul Cluj Napoca.
Fiecare rundă online va fi alcătuită din 4 probleme cu dificultate gradată în 90 de minute.
Prima rundă va avea loc în data de 30 ianuarie 2014, incepând cu orele 19.

Organizatorul acestui concurs este Societatea Hermes (Organizaţia Studenţilor din cadrul Facultăţii de Matematică şi Informatică Cluj Napoca). Mai multe detalii sunt disponibile aici De asemenea ne puteţi urmări pe facebook

Categorii:

# Transpose

Cosmin Negruseri
29 octombrie 2013

Here's an interesting interview question I've heard recently.

You are given an 100G size file on disk which represents a square matrix of 32 bit integers. Design an efficient way to transpose that matrix given that you only have 1G of available memory.

Categorii:

# Distance

Cosmin Negruseri
08 octombrie 2013

Here's a neat problem I solved in 8th grade during the preparation for the high school entrance exam:

Let A1B1C1D1A2B2C2D2 be a cube with A1B1C1D1 being the bottom face and A2B2C2D2 the top face. Given that A1A2 is of length 1 what's the distance between D2A1 and A2B1.

Categorii:

# Solutii la concursul ACM ICPC 2013 etapa nationala partea a doua

Petru Trimbitas
21 iunie 2013

Revin cu partea a doua a articolului cu soluţii la problemele de la faza naţională a concursului ACM ICPC. Acestea sunt problemele grele şi au fost rezolvate de foarte puţine echipe. Vă invit să discutaţi soluţiile la comentarii.

## A. Cubic Eight-Puzzle

Problema ne dă un grid de 3×3 acoperit cu 8 cuburi fiecare aşezat într-una din celule. Fiecare are două dintre feţele opuse colorate cu albastru(B) iar celelalte două colorate cu alb(W) şi cu roşu( R ) . La o mutare poate fi rostogolit unul din cuburi în celula liberă. Problema ne cere să aflăm numărul minim de mutări necesare pentru a ajunge într-o configuraţie dată. Se ştie că iniţial cuburile sunt cu faţa albă in sus iar faţa albastră e în dreapta. Celula goală se află în stânga-jos. Dacă numărul de mutări e mai mare de 30 se va afişa -1

O primă soluţie ar fi să facem o parcurgere în lăţime din starea iniţială făcând maxim 30 mutări. La fiecare pas avem 4 mutări posibile dintre care una ne va duce înapoi deci doar 3 ne interesează. În total vom trece prin 3 30 stări.
Pentru a reduce numărul de stări prin care trecem vom folosi Meet in the middle. În loc să pornim o parcurgere doar din sursă, vom porni una şi din destinaţie şi făcând maxim 15 mutări. Astfel vom încerca să întâlnim din sursă un nod vizitat din destinaţie sau invers. Astfel vom vizita doar 2*3 15 stări.

## B. Manhattan Wiring

În această problemă ni se dă o matrice de NxM ( N<=9 M<=9 ) cu unele celule ocupate. Două dintre celulele matricei sunt marcate cu 2 şi două cu 3. Trebuie afişată suma minimă a lungimii a două lanţuri care nu se intersectează şi unesc cele două celule cu 2 şi cele două cu 3 fără a ieşi din matrice sau a trece prin celulele ocupate.

Recomand citirea acestui articol înainte de citirea soluţiei.

O problemă asemănătoare s-a dat la CEOI 2006. Soluţia ei se găseşte aici

Soluţie

În scrierea soluţiei m-am inspirat de aici

Fiecare celulă poate fi în următoarele stări: goală, ocupată cu un cablu vertical/orizontal sau cu un cablu în L(4 stări). Vom calcula lungimea minima a cablurilor poziţionate până la linia i iar cele din stare sunt legate de linia anterioară( 0 nu există legătură, 1 există legătură iar cablul va fi legat de 2, 2 există legătură iar cablul va fi legat de 3). Pentru a calcula tanziţiile vom genera cu backtracking starea cablurilor de pe coloana următoare şi vom avea grijă să păstrăm următoarea stare corectă.

## C. Power Calculus

Problema ne cere să aflăm numărul minim de operaţii pentru a calcula x n ( n <= 1000 ) pornind de la x fără a folosi puteri negative şi făcând înmulţiri cu numere calculate deja. De exemplu x 31 poate fi calculat cu 7 înmulţiri:
x 2 = x × x, x 4 = x 2 × x 2, x 8 = x 4 × x 4 , x 10 = x 8 × x 2 , x 20 = x 10 × x 10, x 30 = x 20 × x 10 , x 31 = x 30 × x
Acesta poate fi calculat şi cu 6 operaţii (5 înmulţiri şi o împărţire)
x 2 = x × x, x 4 = x 2 × x 2, x 8 = x 4 × x 4 , x 16 = x 8 × x 8 , x 32 = x 16 × x 16 , x 31 = x 32 ÷ x

Soluţie

Deşi iniţial pare complicată, problema se rezolvă cu o parcurgere în lăţime. Se observă că nu are sens să calculăm pentru numere mai mari de 2000. Într-o poziţie din coadă vom reţine toate puterile calculate până la numărul curent. Când dorim să trecem într-o stare nouă trebuie doar să adunăm sau să scădem ultima putere calculată cu una calculată anterior.

``````#include <iostream>
#include <queue>
#include <cstdlib>
using namespace std;

struct drum{
int lst,sz,cst;
int fol[32];
};

int n=-1,dmin[3005];

void ins(queue<drum> &c,drum fr,int nxt) {
if(nxt<2 || nxt>2000) return;
drum next=fr;
++next.cst;
if(next.cst==dmin[nxt]) {
next.fol[++next.sz]=next.lst=nxt;
c.push(next);
}
if(dmin[nxt]>next.cst) {
dmin[nxt]=next.cst;
next.fol[++next.sz]=next.lst=nxt;
c.push(next);
}
}

int main() {
for(int i=2; i<=1000; ++i) dmin[i]=(1<<30);
queue<drum> c;
drum fr; fr.sz=0; fr.lst=1; fr.cst=0; fr.fol[++fr.sz]=1;
for(c.push(fr);c.size(); c.pop()) {
fr=c.front();
for(int i=1; i<=fr.sz; ++i) {
ins(c,fr,fr.lst+fr.fol[i]);
ins(c,fr,fr.lst-fr.fol[i]);
}
}
while(1) {
cin>>n;
if(n==0) break;
cout<<dmin[n]<<'\n';
}
return 0;
}``````

## D. Polygons on the Grid

În această problemă trebuie să aflăm aria maximă a unui poligon cu colţurile în puncte laticeale care are lungimile laturilor date. Poligonul are maxim 6 laturi iar lungimea maximă a unei laturi e 300

Soluţie oferită de Mugurel Ionut Andreica

Ideea soluţiei este încercarea tuturor variantelor: se poate fixa o latură ca fiind prima şi îi încercăm toate orientările spre "dreapta-sus": orizontal, vertical, si, eventual, "oblic" dacă se poate aşeza cu capetele într-un punct întreg). Pe urmă variem ordinea celorlalte laturi ( 5! ) şi pentru fiecare dintre celelalte laturi încercăm orientările posibile care pastrează convexitatea poligonului. În plus mai trebuie folosită următoarea optimizare: Fixăm cea mai mare lungime ca fiind prima latură. Dacă lungimile rămase nu ne ajung să "închidem" poligonul atunci ne oprim.

Categorii:

# Solutii la concursul ACM ICPC 2013 etapa nationala partea I

Petru Trimbitas
17 iunie 2013

Duminică, 16 iunie a avut loc faza naţionala a concursului acm icpc. Pagina concursului o gasiţi aici
iar clasamentul aici
La concurs au participat peste 50 echipe iar setul de probleme a fost unul echilibrat.

Înainte de concurs au mai avut loc 3 concursuri de pregătire. Problemele le găsiţi aici aici şi aici

Voi prezenta in continuare o parte din probleme şi soluţiile acestora. Vă invit să contribuiţi la comentarii cu soluţiile voastre

## G. Election Time

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 î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 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.

``````#include <iostream>
#include <algorithm>
#define DN 50005
using namespace std;

int n,k,ind[DN],a[DN],b[DN];

bool cmp(int x,int y) {
return a[x]>a[y];
}

bool cmp2(int x,int y) {
return b[x]>b[y];
}

int main() {
cin>>n>>k;
for(int i=1; i<=n; ++i) {
cin>>a[i]>>b[i];
ind[i]=i;
}
sort(ind+1,ind+n+1,cmp);
sort(ind+1,ind+k+1,cmp2);
cout<<ind[1]<<'\n';
}``````

## H. Stones II

A doua problema ca dificultate din concurs ne dădea N (N <= 100 000) grămezi de pietre şi ne cerea să le reunim cu un cost cât mai mic. Pentru a putea reuni grămezile putem lipi la un pas două grămezi cu un cost egal cu numărul de pietre din cele două grămezi la un loc.

Pentru a rezolva problema putem aplica o strategie de tip greedy în care la fiecare pas luăm cele mai mici două grămezi şi le reunim. Pentru a se încadra în timp şi pentru a fi corect e necesară folosirea unui multiset şi a tipului de date long long.

## F. Average distance

După cum îi spune şi numele această problemă ne cere sa calculăm costul mediu al muchiilor dintr-un arbore.

Pentru a rezolva problema observăm că costul mediu e egal cu suma costurilor drumurilor din arbore împărţită la numărul total de drumuri.
Numărul de drumuri e egal cu N*(N-1)/2 (Combinări de N luate câte doua, fiecare drum fiind definit de 2 noduri).
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.

``````//Cristian Lambru
#include<iostream>
#include<vector>
using namespace std;

typedef vector<pair<int,int> >::iterator it;

#define MaxN 110000
#define ld long double

int N;
ld Suma = 0;
int Fii[MaxN],viz[MaxN];
vector<pair<int,int> > A[MaxN];

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])
{
parcurgere(i->first);
Fii[nod] += Fii[i->first];

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

int main()
{
citire();
parcurgere(0);

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

## E. Slim Span

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.

## I. More lumber is required

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

## J. Template Library Management

În această problemă se dă un vector V de N (N<=100 000) (V[i]<=109) 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ă.

## K. Fast Arrangement

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
Pentru a rezolva corect problema trebuia observat că intervalele sunt deschise, deci intervalele (3,4) şi (4,5) nu se suprapun.

Categorii:
Vezi pagina: 123456 7891011... 3536373839 (390 rezultate)