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.

Bafta saptamana urmatoare la Olimpiada Nationala de Informatica!

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(n⁵) 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.

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:

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.

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.

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

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 stair 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. (⁴, 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. (¹) What is the maximum product for collection of natural numbers that sum up to n.
6. (¹, 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. (⁵, 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. (¹, 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. (¹, 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. (¹, 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. (¹) 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:
¹ 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.
² Ioan Cuculescu "Olimpiadele Internationale de Matematica ale Elevilor"
³ E. A. Morozova, I. S. Petracov, V. A. Skvortov "Olimpiade internationale de matematica"
⁴ "Probleme de matematica traduse din revista sovietica KVANT"
⁵ A. M. Iaglom, I. M. Iaglom "Probleme neelementare tratate elementar"
⁶ Mathematics for computer science

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 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!

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

• Andrei Grigorean •wefgef - preşedinte
• Serban Andrei Stan •savim - vicepreşedinte responsabil cu Algoritmiada
• Budau Adrian •freak93 - vicepreşedinte responsabil cu developmentul
• Dumitran Adrian Marius •marius135 - vicepreşedinte responsabil cu relaţiile cu sponsorii şi PR

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

•Budau Adrian 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.

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.