Blog infoarena

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:

Interactive problems shortlist

Cosmin
Cosmin Negruseri
16 martie 2013

Interactive problems aren't very popular in coding contests because they involve additional effort from the problem writers. But they are usually pretty creative. I've made a shortlist below. Have fun solving them in the comments section!

  1. (CLRS, agora scholarships finals 2004) You are given two arrays A and B of n and m elements. The elements in each array are sorted and distinct. Find the kth element in the union of two arrays using as few comparisons as possible.
  2. (CLRS, interview question) You are given a matrix A with n rows and m columns. The elements in each row and each column are distinct and sorted. One query is what’s the value of A[i][j]. Find out if element x is in the matrix using as few queries as possible.
  3. (CLRS, romanian national olympiad) Given an array A of n integers. Find the 2nd minimum in the array using as few comparisons as possible.
  4. (CLRS) Given an array A of n integers find out the minimum and maximum elements of the array using as few comparisons as possible.
  5. (romanian ioi team selection 2006) You are given a cyclic array A of n distinct elements. query(i, j, k) returns the order of the elements A[i], A[j] and A[k] (for example a result can be A[i] < A[j] < A[k] or A[i] < A[j] > A[k]). Find a local minimum using as few queries as possible.
  6. (Bulgarian OI) You are given a matrix A with n rows and m columns. An cell is considered a local minimum if it’s row and column neighbours have higher values. You can query the value of A[i][j]. Find a local minimum in as few queries as possible.
  7. (folklore) A celebrity in a group of n people is a person that is known by everybody but doesn’t know anybody. Given a group of n people you can query if person x knows person y. Using the fewest number of queries possible, find out if there’s a celebrity in that group.
  8. (CLRS) Professor Diogenes has n supposedly identical integrated-circuit chips that in principle are capable of testing each other. The professor’s test jig accommodates two chips at a time. When the jig is loaded, each chip tests the other and reports whether it is good or bad. A good chip always reports accurately whether the other chip is good or bad, but the professor cannot trust the answer of a bad chip. Less than n/2 chips are bad. Help the professor find the good chips using as few tests as possible. The four possible outcomes of a test are as follows:
    • Chip A says: B is good, Chip B says: A is good, Conclusion: both are good, or both are bad
    • Chip A says: B is good, Chip B says: A is bad, Conclusion: at least one is bad
    • Chip A says: B is bad, Chip B says: A is good, Conclusion: at least one is bad
    • Chip A says: B is bad, Chip B says: A is bad, Conclusion: at least one is bad
  9. (martin gardner, romanian ioi team selection 98) On the bottom floor of a building there are 11 wire ends. On the top floor there are the other 11 ends of the wires. An electrician has to figure out which end above matches with which end below. To accomplish this he can do two things: 1) tie any two ends together on the same floor. 2) test for a closed circuit by applying a device to two ends. What’s a method that minimizes the number of times the electrician needs to climb the stairs.

When I ask for the minimum number of queries I'm talking about worse case behavior.

 Comentarii (17)

Categorii:

Code Pandas

ada_s
Ada-Mihaela Solcan
15 martie 2013

În colaborare cu infoarena, Adobe România organizează Code Pandas, un concurs de programare cu premii, pentru studenţii pasionaţi de tehnologie şi algoritmi.

Premii

Participanţii care vor obţine primele 3 punctaje din concurs vor câştiga următoarele premii :

  • Locul I - un laptop Asus
  • Locul II - o tabletă Google Nexus 7
  • Locul III - un smartphone HTC Windows 8S

Calendarul concursului

  • Etapa I - 30 martie
     Orice student este invitat să participe la prima etapă concursului care se va desfăşura pe infoarena. Aceasta va fi pe 30 martie, între orele 11:00 şi 15:00, şi va consta în 3-4 probleme.
     Primii 20 clasati vor fi invitaţi la etapa finală de la sediul Adobe România.
  • Etapa II - 5 aprilie
     Etapa finală a concursului se va desfăşura la sediul Adobe România pe 5 aprilie, între orele 11:00 şi 15:00, şi va consta tot în 3-4 probleme. Aici concurenţii calificaţi în urma primei etape se vor întrece pentru premiile puse în joc. Departajarea concurenţilor cu acelaşi număr de puncte se va face după timpul de execuţie al programului.

 Comentarii (7)

Categorii:

Combinatorics shortlist

Cosmin
Cosmin Negruseri
10 decembrie 2012

Short lists are often used in math camps to cover some subject by going through a bunch of problems. I've thought of doing the same for programming contests. The first list is related to combinatorics.

Discuss the solutions in the comment section.

  1. (10th grade math course) How many different strings of length 9 are there which contain 3 'a's, 3 'b's and 3 'c's.
  2. How many ways are there to climb a n level staircase if at each step you can climb one or two levels.
  3. (olimpiada online 2001) Given n points on a circle. Draw all possible n(n-1)/2 chords. What’s the maximum number of triangles one can see. Example: With n = 4 there are 8 triangles (4 with 3 of the 4 circle points and 4 with 2 circle points and 1 the intersection of the diagonal).
  4. (4, agora scholarships 2001, infoarena) What is the maximum number of regions the plane can be split into by n lines. (Same problem for n circles, n planes, n spheres) Example: For n = 3 we can get 7 regions.
  5. (1) What is the maximum product for collection of natural numbers that sum up to n.
  6. (1, romanian national olympiad, 10th grade, 2000) How many ways can you tile a 3xn rectangle with dominoes.
  7. (romanian IOI selection, 1999)
    for i1 = 1,n
    _for i2 = i1,n
    __for i3 = i2,n
    ____…
    _____for ik = ik - 1,n
    ______print ‘*’
    How many stars will be printed for a given n and k.
  8. (5, acm.sgu.ru) Count the number of ways k rooks can be placed on a nxn chessboard so that they don’t attack each other.
  9. (1, romanian county olympiad, 11th grade 2000, acm.sgu.ru) Count the number of length n permutations with no fixed points. A fixed point in a permutation p is p(i) = i
  10. (1, county level olympiad, 1994) Count the number of correct bracket sequences of length 2n.
  11. (10th grade math course) Count the number of paths on a grid going from 1,1 to n, m. At each step you can either increase your x coordinate or increase your y coordinate.
  12. Given a permutation of numbers 1 to n, what's the minimum number of swaps one can use to get to the identity permutation.
  13. Count the number of size n permutations such that p^2(i) = i for all i in {1..n}.
  14. (1, infoarena) Given a permutation p what's the minimum k so that p^k(i) = i for all i in {1..n}.
  15. (romanian IOI selection 99, topcoder 2004, infoarena) Find a permutation p of n elements which maximizes k so that p^k(i) = i for all i in {1..n}.
  16. (1) 6 people are at a party. Each two persons can be either friends or enemies. Prove that there is at least a group of three mutual friends or a group of three mutual enemies.
  17. (acm.sgu.ru) Count the number of circular black/white necklaces of length n. (babb is the same with bbab because the first necklace can be rotated to align with the second one)

Some math books useful for programming competition enthusiasts:
1 Ioan Tomescu "Probleme de combinatorica si teoria grafurilor"
Every year during my highschool there was at least one problem in the national olympiad or in the IOI team selection tests from this book.
2 Ioan Cuculescu "Olimpiadele Internationale de Matematica ale Elevilor"
3 E. A. Morozova, I. S. Petracov, V. A. Skvortov "Olimpiade internationale de matematica"
4 "Probleme de matematica traduse din revista sovietica KVANT"
5 A. M. Iaglom, I. M. Iaglom "Probleme neelementare tratate elementar"
6 Mathematics for computer science

 Comentarii (21)

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