Bine ai venit pe infoarena!

Suntem o comunitate de tineri pasionaţi de informatică şi programare.
Învăţăm împreună participând la concursuri online de programare, citind ştiri şi articole despre informatică sau discutând pe forum.

» Află mai multe despre noi!

Ultimele însemnări de pe blog

04 May 2016

All aboard the deep learning train and Alien Labs

I've been thinking about deep learning ever since I saw Andrew Ng's talk at Google back in 2012, but somehow never made much progress other than talking to people.

Deep learning has recently ~2010-2012 become very effective across a large set of problems where progress was very slow. It would be a shame not spending some time on it.

I think the infoarena community should move some of it's focus from solving algorithm puzzles to machine learning and deep learning in particular.

Here are some of my notes about this:

Anecdotes:

Shallow field OpenAI CTO: "As Ilya likes to say, deep learning is a shallow field — it's actually relatively easy to pick up and start making contributions.

Interesting concepts:

Some deep learning news:

And some news:

» Citeste restul insemnarii
28 Apr 2016

Problem: Shoe laces

Here's a probability puzzle I've learned from Alex Ku:

There are N shoe laces in a bag. A move consists of randomly picking two shoe lace ends from the bag, tying them together and then placing them back in the bag. We keep going until we can't find any shoe lace ends to tie. What is the expected number of different shoe lace cycles we'll have at the end.

P.S. Please don't spoil the problem if you've seen it before.

» Citeste restul insemnarii
08 Mar 2016

ONIS 2016 Runda 1 Editorial

Prima rundă de calificare a concursului ONIS 2016 s-a încheiat. În cele ce urmează vom prezenta o scurtă analiză a concursului, însoţită de soluţiile oficiale ale problemelor propuse.

În primul rând, felicitări câştigătorilor! Mai exact, primelor cinci echipe de studenţi în ordinea clasamentului:

1. UPB Banu Popa Visan team_name

2. Mafia Unibuc mafia_unibuc

3. UNIBUC Kira96 lockmihai corul_barbatesc

4. UBB Cociorva Popoveniuc Salajan lookingForAChallenge

5. UNIBUC Impaler-009 Challenge costyv87 The_Viper_The_Mountain_And_The_Imp

De-asemenea, primelor 5 echipe de liceu:

1. Oncescu Costin geniucos

2. Tamio Vesa Nakajima tamionv

3. Popa Andrei andreiiii

4. UVS Babalau Rochian Tarniceru enterprise

5. UNIBUC SAVA CHICHIRIM IONESCU Spiromanii_Messi

Încă o rundă de felicitări pentru UPB Banu Popa Visan team_name, singurii care au reuşit să rezolve toate cele 9 probleme din set şi pentru Oncescu Costin geniucos, care a reuşit să iasă de unul singur pe locul 2, după ce o bună perioadă din concurs a condus clasamentul.

» Citeste restul insemnarii
04 Mar 2016

AGM 2016

Am placerea de a anunta faptul ca povestea merge mai departe ! Dupa o prima editie in care initiativa unui grup restrans de oameni (si in special de elevi) din Colegiul National "Spiru Haret" din capitala a fost sustinuta de Youth Bank, Concursul National de Informatica "Adolescent Grigore Moisil" revine cu o a doua editie, de data aceasta cu mentiunea ca acum este inclus acum în Calendarul Concursurilor Naţionale Şcolare ale MECS. Cea de-a doua editie va avea loc pe 26 martie..

De mentionat este faptul ca acum, la sustinerea concursului, contribuie patru mari companii din Romania : Emag (prin Fundatia Emag), Siveco Romania , Qualitance si Rodl & Partner. Evident, invariantul in toata aceasta poveste este comunitatea Infoarena care continua sa sprijine organizarea concursului si sa incurajeze initiativele similare!

Acest concurs se desfasoara pe format ACM-ICPC, noutatea fiind data de faptul ca se adreseaza elevilor de liceu. Echipele pot fi de maxim 3 elevi (toti membrii unei echipe fiind, obligatoriu, legitimati la acelasi liceu).

» Citeste restul insemnarii
21 Feb 2016

Problem: Marble Game - Solution

Here's the statement again:

M marbles are placed in N cups which are arranged in a circle. One move consists in choosing a cup, taking all the marbles within that cup and placing them one by one in the following cups in clockwise order (since the cups are in a circle you might end up putting marbles in the original cup as well).

Given two placements A and B of marbles in cups, how can we tell if we can reach B starting from A.

Solution:

The state with all marbles in the first cup can always be reached. (1)

While we can find another cup with marbles, we apply one move on that cup. Marbles will move around the circle and from time to time fall into the first cup. Since we never make a move on the first cup, eventually all the marbles will end up in it. You guys figured this part in the comments.

Every state A has n outgoing edges (they can be self edges). (2)
We can apply one move on each cup.

» Citeste restul insemnarii
11 Feb 2016

Our bad :(

Regretăm să vă anunţăm că soluţia oficială a problemei Tembelizor de la Runda 2 a Algoritmiadei este greşită. Mai mult decât atât, nu am reuşit să găsim o soluţie corectă care să rezolve problema pentru restricţiile date în concurs. Ne-am aflat astfel într-o poziţie dificilă, întrucât orice decizie ar fi afectat negativ anumiţi concurenţi. În final, am decis să scoatem problema complet din clasament, runda are astfel un punctaj maxim de 300 de puncte şi nu va influenţa ratingul. În acelaşi timp, pentru a atenua pe cât posibil efectele acestei decizii asupra calificărilor în finală, am hotărât să organizăm şi Runda 4 a concursului, într-o perioadă ce urmează a fi determinată.

Suntem foarte dezamăgiţi de ce s-a întâmplat şi ne cerem scuze tuturor participanţilor pentru dificultăţile create :(.

» Citeste restul insemnarii
30 Jan 2016

Problem: Marble Game

Andrei Dragus told me this cute puzzle a year or two ago.

M marbles are placed in N cups which are arranged in a circle. One move consists in choosing a cup, taking all the marbles within that cup and placing them one by one in the following cups in clockwise order (since the cups are in a circle you might end up putting marbles in the original cup as well).

Given two placements A and B of marbles in cups, how can we tell if we can reach B starting from A.

» Citeste restul insemnarii
29 Jan 2016

Central European Olympiad in Informatics 2016 - Call for Tasks

Punem în atenţia voastră anunţul comisiei CEOI 2016 în legătură cu propunerea subiectelor, anunţ publicat iniţial pe olimpiada.info.

CEOI 2016 - Call for tasks !

Comisia stiintifica a CEOI va invita sa propuneti probleme pentru competitia ce va avea loc in 2016, la Piatra Neamt! Problemele propuse trebuie sa fie de natura algoritmica, dar pot fi de orice tip: clasice, interactive sau output-only. Pentru a asigura o competitie cinstita, problemele propuse trebuie sa respecte urmatoarele reguli (similare cu cele de la IOI):

- Problemele trebuie sa nu fie sau sa fi fost vazute de vreun potential participant la CEOI 2016.
- Problemele trebuie sa nu fi fost propuse intr-o competitie similara (online sau on-site).
- Problemele trebuie sa fie rezolvabile de concurenti intr-un timp de maxim 5 ore.
- Enunturile trebuie sa fie clare si usor de inteles.
- Problemele trebuie sa fie originale si/sau inovative.

Pentru a fi acceptata, o propunere de problema trebuie sa contina urmatoarele:

- Enunt in limba romana, in plain-text sau PDF;
- Descrierea solutiei care obtine punctaj maxim (preferabil si solutii partiale);
- Adresa de email a autorului;
- CV-ul autorului, care sa contina si un scurt rezumat al activitatii acestuia in domeniul informaticii.

» Citeste restul insemnarii
25 Jan 2016

Problem: Prime Number Generator

A while back Ovidiu Gheorghioiu told me this neat problem:

How would you build an efficient prime number generator?

Let the generator be an object G with the method nextPrime(). When we call it G.getNextPrime() the first time it returns 2. Every time we call it again it returns the next prime number.

So if we do:
G = PrimeGenerator()
print G.nextPrime()
print G.nextPrime()
print G.nextPrime()

We'll get
2
3
5

» Citeste restul insemnarii
08 Jan 2016

Problem: Resource hog

During this winter break I've spent some time reading through 'Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices' by George Varghese. Thanks Vlad Balan for recommending the book. It's fun to see how algorithms are heavily used in real world networking. I've stumbled upon a cute problem that I'd like to share (I might have seen it CLRS as well). Here it is:

IDENTIFYING A RESOURCE HOG

A software or hardware module needs to keep track of resources required by various users. The module needs a cheap way to find the user consuming the most resources. Since ordinary heaps are too slow, the device designers are willing to relax the system requirements to be off by a factor of 2. Can this relaxation in accuracy requirements be translated into a more efficient algorithm?

To paraphrase, the problem asks for a data structure with the following operations

Using a map in combination with heap gives us a solution with O(log n) time for each of the two operations. Can we do better?

» Citeste restul insemnarii