Blog infoarena

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:

Algoritmiada 2013

ada_s
Ada-Mihaela Solcan
25 noiembrie 2012

Infoarena revine cu cea de-a cincea ediţie a concursului Algoritmiada . Algoritmiada este un concurs unic în România care reuneşte pasionaţi de informatică de toate vârstele, începând cu elevi de gimnaziu şi până la persoane care au terminat de mulţi ani facultatea. Participanţii sunt împărţiti în patru grupe : clasele 5-9, clasa a 10-a, clasele 11-12 si Open. Concursul se desfăşoară anual sub forma a 3-4 runde de calificare online, iar primii clasaţi sunt la invitaţi să participe la finala onsite. În paralel cu finala onsite se desfăşoară şi o variantă online a finalei pentru cei care nu au reuşit să se califice.

Algoritmiada este seria de concursuri infoarena care a impresionat nu doar prin calitatea problemelor, dar şi prin organizarea ireproşabilă a rundelor. Acest fapt se datorează unei echipe tehnice şi ştiinţifice extrem de valoroase din punct de vedere academic. Şi în acest an coordonatorii ştiinţifici ai fiecărei runde vor fi foşti olimpici internaţionali sau membrii ai lotului naţional de informatică. Finala Algoritmiada este considerată cel mai important concurs naţional din România, iar acest statut i-a adus colaborări cu diverşi sponsori.

Ediţiile din anii trecuţi

Prima ediţie a concursului Algoritmiada s-a desfăşurat în 2009. La concurs puteau participa atât elevi, cât şi studenţi, fiind primul concurs naţional de acest tip. Au existat 3 runde de calificare, iar cei mai buni concurenţi au fost invitaţi la finala ce s-a desfăşurat la Braşov.

La ediţia din 2010 concurenţii au avut 4 runde de calificare, iar cei cu cele mai bune rezultate au participat la finala de la Iasi. Concursul a fost organizat în parteneriat cu Amazon România şi Adobe România.

Începând cu anul 2011, la cea de a treia ediţie, categoria "studenţi" a fost înlocuită cu "open", astfel la concurs putând participa oricine, indiferent de vârstă. Runda finală a acestei ediţii s-a desfăşurat în Timişoara. Concursul a fost organizat în parteneriat cu Google şi Adobe România.

Anul trecut, Algoritmiada a fost realizată în parteneriat cu Adobe România, Reea, Ixia, uberVU şi MB Telecom. Câştigătorii rundei finale de la Târgu Mureş au fost : Rares Buhai (clasele 5-9), Daniel Constantin Anghel (clasa a 10-a), Gavrila Vlad (clasele 11-12) şi Mugurel-Ionut Andreica (open).

Prima runda Algoritmiada 2013

Prima rundă a ediţiei de anul acesta a concursului Algoritmiada va avea loc pe 8 decembrie 2012. Concursul o să urmeze formatul ediţiei de anul trecut, având patru grupe valorice: clasele 5-9, clasa a 10-a, clasele 11-12 şi open. Participanţii vor avea la dispoziţie 4-5 ore pentru a rezolva 3-4 probleme de natură algoritmică. Aceasta este una din rundele cu rol de calificare pentru finală, aşa că participă şi dovedeşte-ţi talentul şi cunoştiinţele!

 Comentarii (4)

Categorii:

Infoarena și-a ales noua conducere

ada_s
Ada-Mihaela Solcan
13 noiembrie 2012

Infoarena şi-a ales noua conducere. Este vorba despre :

Andrei Grigorean a intrat pentru prima oară pe infoarena la sfârşitul clasei a X-a, după ONI 2005, iar din clasa a XI-a a început să lucreze serios pe site. Din 2007, după ce a termniat liceul, a intrat în echipă. Ca membru al echipei, a propus peste 50 de probleme, a făcut parte din comisiile ştiinţifice de la aproape toate concursurile infoarena şi a lucrat puţin şi la development. A fost preşedinte al primei ediţii a concursului Algoritmiada, în 2009, şi al ediţiei din 2012, iar împreună cu Mihai Duşmanu, a iniţiat concursul Infoarena Monthly. A mai ocupat anterior funcţia de preşedinte infoarena în 2010/2011.

Ca preşedinte, munca lui va fi mai mult una de coordonare şi îi va ajuta pe cei trei vicepreşedinţi să-şi atingă obiectivele pe care şi le-au propus. Îşi doreşte în continuare creşterea echipei infoarena şi apropierea membrilor echipei de comunitate. Va încerca să menţină un contact mai strâns cu sponsorii şi să găsescă noi persoane care vor să se implice pe partea de development. De asemenea, va monitoriza atent activitatea de pe site şi va încerca să cunoască cât mai mulţi utilizatori noi.

Serban Andrei Stan consideră infoarena principalul site de pe care s-a pregătit pentru olimpiade şi concursuri pe parcursul liceului. Datorită acestui fapt, a rezolvat aproape jumatate din problemele din arhivă şi astfel a ajuns extrem de familiar cu site-ul. A organizat, în calitate de membru al comunităţii, concursul .com 2009, alături de Cezar Mocan, Radu Zernoveanu şi alţi utilizatori. Anul trecut, când a fost invitat în cadrul echipei a acceptat cu mult entuziasm. În 2012 a ajutat la organizarea rundelor de Algoritmiada şi Infoarena Cup.

Obiectivele sale pentru următorul an, ca vicepreşedinte responsabil pentru Algoritmiada 2013, sunt păstrarea bunei organizări a concursului, asigurarea unor seturi de probleme care să surprindă nu prin dimensiunea sursei, ci plin originalitatea soluţiei, şi organizarea unei finale mai reuşite decât în anii precedenţi. Pentru fiecare rundă coordonatorii ştiinţifici vor fi foşti olimpici internaţionali ori membri ai lotului naţional de informatică. În plus, finala Algoritmiada este cel mai important concurs naţional din România. Acest statut i-a adus pe parcursului timpului colaborări cu diverşi sponsori, şi sperăm că anul acesta va fi unul rodnic în acest sens.

Îşi propune ca şi Infoarena Cup, care este doar la a doua ediţie, să îşi caştige statutul de "concurs international". Anul trecut, pe lânga concurenţii români a participat şi echipa naţională a Elveţiei. Feedback-ul lor a fost pozitiv, şi prin prisma acestui fapt s-a hotarat ca anul acesta sa se organizeze o ediţie cu mai mulţi participanţi internaţionali. Doreşte ca demersurile de intrare în contact cu reprezentanţii echipelor naţionale de liceu din Europa să fie încununate de succes. În plus, un alt scop îl constituie găsirea unui set de probleme potrivit pentru un concurs de un asemena calibru.

Adrian Budau a intrat anul trecut în echipa infoarena şi a devenit în scurt timp principalul om pe partea de development. Împreună cu Bogdan Tătăroiu, se ocupă de asigurarea unei bune funcţionări a site-ului. Ca membru s-a implicat şi în alte activităţi, cum ar fi: comisiile de la concursurile Algoritmiada şi Infoarena Monthly, dar şi în discuţii cu anumiţi sponsori. De asemenea, în cadrul finalei Algorimiada de anul trecut, s-a ocupat de pregătirea calculatoarelor concurenţilor.

Obiectivul său principal pentru următorul an, ca vicepreşedinte responsabil cu partea de development, este să sa găsească o echipă împreună cu care să lucreze la infoarena 3. Aceasta ar presupune un site multilingv, un design nou, un forum îmbunătăţit, existenţa unor grupuri pentru utilizatori, dar şi a concursurilor create de către useri. De asemenea, îşi propune sa ajute şi să supervizeze pe cei care doresc să se implice la partea de development din cadrul infoarena pe hackers.infoarena.ro.

Dumitran Adrian Marius este implicat de mai mulţi ani în Infoarena, mai ales pentru a facilita comunicarea dintre echipă şi Facultatea de Matematică şi Informatică, atât cu studenţii şi asociaţia studenţilor, cât şi cu profesorii şi conducerea facultăţii. De asemenea, s-a implicat şi în organizare concursurilor Algoritmiada şi Infoarena Cup şi în întreţirea relaţiilor cu sponsorii.

Obiectivul principal al său pentru următorul an este aducerea unor companii puternice alături de infoarena ca parteneri stabili şi nu doar pentru anumite proiecte. Este de părere că ideală ar fi atragerea unei fundaţii importante alături de echipă. Un alt obiectiv îl constituie strângerea legăturilor cu ROSEdu şi Politehnica, unde în acest moment nu mai există membri activi în cadrul infoarena. Importantă este şi o mediatizare mai puternică a brandului infoarena, iar o bună ocazie o constituie organizarea Infoarena Cup la Bucureşti. Pentru a işi atinge aceste obiective doreşte extinderea echipei infoarena şi pe partea de PR.

 Comentarii (1)

Categorii:

Haideti sa imbunatatim Infoarena impreuna!

marius135
Dumitran Adrian Marius
05 noiembrie 2012

Infoarena merge inainte, si chiar daca infoarena 3 este departe, vom incerca sa adaugam noi functionalitati in urmatoarea perioada. Scriem acest mic post pentru ca vrem sa stim ce doriti voi, utilizatorii, sa adaugam la site. Vom incerca sa analizam toate ideile voastre si sa alegem o parte dintre ele pentru a le implementa in urmatoarea perioada. Daca ati avut momente in care v-ati gandit ca siteul are nevoie de x sau de y, acum e momentul vostru. Asteptam cu mare drag ideile voastre.

 Comentarii (73)

Categorii:

Rolling hash, Rabin Karp, palindromes, rsync and others

Cosmin
Cosmin Negruseri
30 octombrie 2012

Rolling hash is a neat idea found in the Rabin-Karp string matching algorithm which is easy to grasp and useful in quite a few different contexts.

As before, the most interesting part of the article is the problem section. Discuss them in the comment section, but first let's go through a few applications.

The Rabin-Karp algorithm

Given a string P of length n and a string S of length m find out all the occurrences of P within S

The algorithm works by building a fingerprint for each substring of S of length n. It checks if any of them match the fingerprint of P. Implementing this directly leads to a O(n*m) solution which isn't faster than the naive matching algorithm (in fact it may be slower).

The insight is that you can efficiently compute the hash value of a substring using the hash value of previous substring if you use the right hash function. A polynomial with the string characters as coefficients works well. Let H(c)=c[0]a^{n-1} + c[1]a^{n-2}+...+c[n-1] be the hash function for the string c.
All the operations are done modulo a prime number so that we don’t have to deal with large integers.

Let’s see what happens when we go from H(S[i..i+n-1]) to H(S[i+1..i+n]):


H(S[i+1..i+n])= S[i+1]a^{n-1}+S[i+2]a^{n-2}+.. + S[i+n]

Adding and substracting S[i]a^n we get


a(S[i]a^{n-1}+S[i+1]a^{n-2}+ S[i+2]a^{n-3}+ .. + S[i+n -1])+S[i+n]-S[i]a^{n} =

aH(S[i..i+n-1])-S[i]a^{n}+S[i+n]

Deleting a character and appending another one corresponds to adding a number and subtracting a number in our hashing algorithm. The complexity of the algorithm is O(n).

If S and P are strings of digits and a is 10, our problem maps to finding numbers in a string of digits.
Let's go through an example.

Let P = 53424, S = 3249753424234837 and a = 10
3249753424234837
32497
 24975 = 10 * 32497 - 3 * 10000 + 5  
  49753 = 10 * 24975 - 2 * 10000 + 3
   97534 = 10 * 49753 - 4 * 10000 + 4 
     ...
     53424 // match
      ...

Here's some code:

an = 1
  rolling_hash = 0
  for i in range(0, n):
    rolling_hash = (rolling_hash * a + S[i]) % MOD
    an = (an * a) % MOD
  if rolling_hash == hash_p:
    print "match"
  for i in range(1, m - n + 1):
    rolling_hash = (rolling_hash * a + S[i + n - 1] - an * S[i - 1]) % MOD
    if rolling_hash == hash_p:
        print "match"

Longest common substring

Given two strings A and B, compute their longest common substring.

Let's solve a simpler problem: Given two strings A and B, and a number X find if they have a common sequence of length X. We use the rolling hash technique to find the hash codes for all X length substrings of A and B. Then we check if there is any common hash code between the two sets, this means A and B share a sequence of length X. We then use binary search to find the largest X.
The complexity of this algorithm is O(n log n).

rsync

The linux utility is used to keep two copies of the same file in sync by copying around deltas. Instead of replicating the whole changed file, rsync segments the file into fixed size chunks, computes a rolling hash for each chunk. On the client side computes rolling hashes for all chunks of the target file including overlapping ones. Then it checks which chunks are already there, which chunks need to be deleted and which chunks need to be copied over. This improves the transfer speed as you only copy over deltas and some chunk fingerprints. Here's a better description from wikipedia.

Largest palindrome

Given a string of length n, find out its largest palindromic substring.

The naive solution is O(n3). For every possible substring it tests in linear time if it's a palindrome.

A smarter solution tries every position in the original string as the center of a palindrome and extends to the left and to the right as long as the corresponding characters match. This solution takes O(n2) time.

There's a O(n log n) solution that involves rolling hash. Given X we can test if there is any substring S' of S of length 2X such that H(S') == H(reverse(S')). The identity means that S contains a palindromic sequence of length at least 2X. What is left is to find out the maximum such X. We can use binary search to do that efficiently. The overall complexity is O(n log n).

Substrings of variable length

The polynomial function can be used to compute hashes for substrings of varying length

Let’s choose H(S[i..j]) = S[i]+S[i+1]a+S[i+2]a{2}+...+S[j]a^{j-i} Then we compute the array h which contains cummulative hashes: h[k]=S[0]+S[1]a+S[2]a^{2}+...+S[k]a^{k}. It’s easy to see that H(S[i..j])=(h[j]-h[i-1])/a^i

After spending O(n) time on preprocessing h, we have an efficient way to compute the hash code for any substring of S.

The division operation modulo a prime needs some number theory insight. You can do it using Fermat's little theorem or using the Extended Euclidean Algorithm. If you need to process a lot of sub strings it's useful to pre process all the values for a^{-i} \bmod{p}.

Caveats

Hashing collisions are a problem. One way to deal with them is to check for a match when two fingerprints are equal, but this makes the solution inefficient if there are lots of matches. Another way is to use more hashing functions to decrease the collision probability.

Alternatives

Suffix trees or suffix arrays are very good tools to tackle string matching problems. I prefer hashing as the code is usually simpler.

Additional problems

  1. Given a string of length n, count the number of palindromic substring of S. Solve better than O(n2).
  2. Given a string of length n, find the longest substring that is repeated at least k times. Solve in O(n log n)
  3. Given a bitmap, find out the largest square that’s repeated in the bitmap.
  4. Given a string S figure out if the string is periodic. (there is a p such that for any i we have that s[i] == s[i + p]) For example abcabcab is periodic with p = 3. O(n log n)
  5. Given two equal length strings, figure out if one is a rotation of the other. O(n)
  6. Given two polygons find out if they are similar polygons. O(n)
  7. Given a string, find it's longest periodic prefix. O(n log n) For aaabaaabcde the answer is aaabaaab
  8. Given a tree T with character labeled nodes and a given string P count how many downward paths match P. O(n)

 Comentarii (9)

Categorii:

Count (distinct) problem

Cosmin
Cosmin Negruseri
24 octombrie 2012

Here's a neat problem from Alexandru Andoni:

You're given a 1GB file containing 64 bit integers.
Come up with an algorithm which estimates the number of distinct integers in the file. You're allowed to use 1024 bytes of memory and you can read the file only once.
How good is your estimation?

 Comentarii (8)

Categorii:

Infoarena lovește din nou!

wefgef
Andrei Grigorean
13 octombrie 2012

Sîmbătă, 13 octombrie 2012, a avut loc faza regională a concursului ACM ICPC, regiunea sud-est europeană. Au participat 78 de echipe de la 47 de universităţi, provenind din 8 ţări diferite. Experienţa ultimilor ani ne învaţă că regiunea noastră este una dintre cele mai puternice din lume, concurenţa fiind foarte mare, în special din partea echipelor din Ucraina. La fel ca la ultima ediţie, concursul s-a desfăşurat în două locuri diferite: la Universitatea Politehnică din Bucureşti şi în Vinnytsia, Ucraina. Pentru evaluare s-a folosit sistemul Ejudge, iar concurenţii trebuiau să submiteze sursele online.

Consideraţi de mulţi principalii candidaţi români pentru calificare, echipa Universităţii din Bucureşti, BigDawgs, a reuşit un rezultat remarcabil. Toţi cei trei membri ai acestei echipe fac parte şi din echipa infoarena:

Cu 8 din 10 probleme rezolvate şi cu o penalizare de 1003 minute, ei au reuşit să se claseze în final pe treapta a doua a podimiului, poziţie care le garantează un loc la faza finală a celui mai de tradiţie concurs de programare din lume. Merită menţionat că au fost detronaţi de pe prima poziţie cu doar 4 minute înainte de finalul probei, altfel am fi asistat la o victorie românească după foarte mulţi ani.

Celelalte echipe româneşti s-au descurcat şi ele foarte bine, Universitatea din Bucureşti ocupînd de asemenea locurile 9 şi 11, prin echipele Smecheria şi Aproape Oltenia (ambele cu 7 probleme rezolvate). Şi Politehnica s-a descurcat onorabil, Angry Pink Bunnies terminînd pe 18, iar Retired But Dangerous pe 19 (ambele cu 6 probleme rezolvate).

Îi felicităm pe toţi şi le ţinem pumnii celor trei la faza finală care va avea loc în iulie 2013, în Sankt Petersburg!

 Comentarii (9)

Categorii:
Vezi pagina: 12345678 910111213... 3637383940 (397 rezultate)