Blog infoarena

Zece

Cosmin
Cosmin Negruseri
28 martie 2014

Infoarena aniverseaza luna aceasta 10 ani!

 Comentarii (16)

Categorii:

Lansarea concursului naţional de algoritmică MindCoding

S7012MY
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

 Comentarii (0)

Categorii:

Transpose

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

 Comentarii (3)

Categorii:

Distance

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

 Comentarii (10)

Categorii:

Solutii la concursul ACM ICPC 2013 etapa nationala partea a doua

S7012MY
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

Soluţie oferită de Budau Adrian

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.

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.

 Comentarii (4)

Categorii:

Solutii la concursul ACM ICPC 2013 etapa nationala partea I

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

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.

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.

 Comentarii (13)

Categorii:

C++ compiler upgrades on infoarena

pauldb
Paul-Dan Baltescu
27 aprilie 2013

We now have the --std=c++0x compiler option enabled on infoarena. We also updated our g++ compiler to 4.8.

What does it mean?

C++ users can now use a bunch of cool features, some of which are briefly described below. Keep in mind that these features are not yet available at OJI, ONI, etc., so don't use them at any of these competitions unless they are allowed explicitly by the regulations.

1. auto

You can now let the compiler infer the type of your variables with auto:

auto can also be used with const auto or const auto&. In most cases, auto cannot be used in function signatures.

2. range-based for loops

In C++11, you can write less code to iterate over every element in a list of elements:

If you want to modify the elements in the list, you need to get a reference to the current element:

Note: This code compiles without using &, but the original array is not modified unless a reference is used.

3. initializer lists

Simple one-line initializations with lists of constant values:

Note that in C++11 you no longer need to introduce a space between closing right angle brackets (>>).

4. unordered_set, unordered_map

These are hash-based implementations of the well known set and map containers; the average time complexity on most operations is O(1). (These containers were previously available on infoarena under tr1, but only a small fraction of users were actually using them.)

Using STL vectors, pairs or user defined objects as keys is a little trickier because you also need to provide a hash function.

You don't need to worry about collisions, unordered_set and unordered_map will take care of them for you.

5. lambda functions

You can now define anonymous functions to write less code. A common application is sorting according to multiple criteria.

(Often, a cleaner alternative to using lambda functions for sorting is to define a class holding all the data for each entry and to implement the < operator.)

Let us know in the comments section what are the C++11 features that you use for programming contests. Code snippets illustrating your favorite tricks are welcome.

 Comentarii (6)

Categorii: Features

Bafta la ONI

Cosmin
Cosmin Negruseri
29 martie 2013

Bafta saptamana urmatoare la Olimpiada Nationala de Informatica!

 Comentarii (12)

Categorii:

14 numbers every developer should know

Cosmin
Cosmin Negruseri
26 martie 2013

sidenote Jeff Dean , a famous Google engineer, popularized a list of latency numbers everyone should know. The list is a great resource for designing large scale infrastructure systems.

Algorithms and their complexity often occur in critical parts of computer systems, but I find that few engineers have a good understanding of how a O(n!) algorithm compares to a O(n5) one.

In the coding contest world, competitors think about these tradeoffs all the time. No wonder, there's a set of numbers every algorithm designer should know.

The table below shows the limits that can be reached in a few seconds by algorithms of different complexities, n being the input size. I've added some algorithms and data structure examples for each complexity class.

maximum ncomplexityalgorithmsdata structures
1,000,000,000 and higherlog n, sqrt nbinary search, ternary search, fast exponentiation, euclid algorithm 
10,000,000n, n log log n, n log* nset intersection, Eratosthenes sieve, radix sort, KMP, topological sort, Euler tour, strongly connected components, 2satdisjoint sets, tries, hash_map, rolling hash deque
1,000,000n log nsorting, divide and conquer, sweep line, Kruskal, Dijkstrasegment trees, range trees, heaps, treaps, binary indexed trees, suffix arrays
100,000n log2 ndivide and conquer2d range trees
50,000n1.585, n sqrt nKaratsuba, square root tricktwo level tree
1000 - 10,000n2largest empty rectangle, Dijkstra, Prim (on dense graphs) 
300-500n3all pairs shortest paths, largest sum submatrix, naive matrix multiplication, matrix chain multiplication, gaussian elimination, network flow 
30-50n4, n5, n6  
25 - 403n/2, 2n/2meet in the middlehash tables (for set intersection)
15 - 242nsubset enumeration, brute force, dynamic programming with exponential states 
15 - 20n2 2ndynamic programming with exponential statesbitsets, hash_map
13-173ndynamic programming with exponential stateshash_map (to store the states)
11n!brute force, backtracking, next_permutation 
8nnbrute force, cartesian product 

These numbers aren't very precise, they assume in memory operations and some varying constant factors, but they do give a good starting point in your search for a solution that fits your problem and your data size.

Let's go through an example.

Suppose you work for a GPS company and your project is to improve their directions feature. In school you've learned about using Dijkstra's algorithm to find the shortest path between two nodes in a graph. Knowing these numbers you will understand that it will take seconds to process a graph with millions of edges given that Dijkstra implementations have m log n time complexity (where m is the number of edges and n the number of nodes).

Now you face a few questions:

How fast do you want your code to be? seconds? hundreds of milliseconds?

A response on the web feels fast if it takes less then 500 milliseconds. So let's pick half a second.

How big is the graph? Do you want to solve the problem for a city, a coutry or even a continent?

Each is about a magnitude larger than the other and will be solved by different approaches. Let's say we want to solve the problem for the whole of Europe.

Here are sizes for a few input sets:

inputEuropeUSA/CANUSA (Tiger)
#nodes18 029 72118 741 70524 278 285
#directed edges42 199 58747 244 84958 213 192
#road categories13134

Since we chose half a second to be our execution time and the size of our problem to be about 40 million edges it's clear from our table that m log n is too slow. So pure Dijkstra won't do. We need to look at how other algorithms like A star search or one based on Highway hierarchies behave for this problem.

 Comentarii (7)

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