A neat probability puzzle

Howdy, it's been a while since I last posted. I saw a neat puzzle on Quora that I'd like to share:

Three people enter a room. Each person is assigned a hat uniformly at random: either red or blue. Each person can see the hats of the two other people, but they can't see their own hats. Each person can either try to guess the color of their own hat or pass. All three do it simultaneously, so there is no way to base their guesses on the guesses of others. 

If nobody guesses incorrectly and at least one person guesses correctly, they all share a big prize. Otherwise they all lose.
One more thing: before the contest, the three people have a meeting, during which they decide their strategy. What is the best strategy to maximize their odds of winning a prize?

Selecting values from a stream at random

Saw an interesting question today at CareerCup:

Given a stream of pairs (id, weight), write a function that selects an id at random, with probability proportional to its weight (compared to the total weight sum when the stream has ended). The stream size is unknown in advance and you're allowed O(1) memory. 

Example: if the stream was {(1,2),(2,2),(3,4),(4,10)}, then id 2 would be returned with probability 1/9.

CodeChef December Long Challenge - Problem Course Selection

In the beginning of the month, I enjoyed participating in CodeChef's December Long Challenge. I was pretty proud to get 33^rd place out of 5726 contestants.

The hardest challenge was the problem Course Selection.

We want to attend N courses over M semesters. There are K course prerequisites (a, b) - we must take course a before b. We're also given a matrix X where X[i][j] is the grade (0..100) obtained if we take course i at semester j or -1 if we can't take the course in that semester.
What is the maximum average grade we can obtain?

It is guaranteed it is possible to take the N courses. Constraints:

• 0 <= N, M, K <= 100
• -1 <= X[i][j] <= 100  

For 20% of the points, a course has at most one prerequisite.

Alterações no blog

Olá de novo!

Não escrevia há muito tempo. Para além das habituais limitações de tempo, estive limitado a escrever devido a ter sido juri de vários concursos ao longo dos últimos meses. Assim, seria inconveniente escrever sobre algo que pudesse aparecer num desses concursos.

Um desses concursos foi o South Western European Regional Contest 2014. Podem ver no site o conjunto de problemas, dicas sobre a resolução e soluções do juri.

Por fim, estive a pensar no formato do blog. Penso que escrever em português é um pouco limitativo. Assim, devo continuar a escrever conteúdos introdutórios em Português mas escrever em Inglês sobre problemas de concursos internacionais.

Final ONI 2005: Problema B - A máquina do Professor ONI

Tem sido difícil arranjar tempo para escrever no blog. Hoje continuo a análise de problemas, desta vez sugiro o problema B da final de 2005 - A máquina do Professor ONI.

Neste problema, temos uma máquina que é constituída por um conjunto de tubos que se bifurcam em L níveis (1 < L < 20). No final dos tubos do último nível, existem baldes, numerados a partir de 1. Existe uma patilha em cada bifurcação. Quando lançamos uma bola no início do primeiro tubo, esta segue a orientação das patilhas. Inicialmente, todas as patilhas estão orientadas para a direita, mas quando uma bola passa numa patilha, a sua orientação inverte-se (direita -> esquerda e vice-versa).

Exemplo de uma máquina com 2 níveis e o resultado do lançamento de 4 bolas.

Assim, o objectivo do problema é saber, após o lançamento de N bolas (1 ≤ N ≤ 1 000 000) numa máquina com L níveis, em que balde é que a N-ésima bola cai.

Final ONI 2005: Problema A - Futebol

Já estão apurados os finalistas das Olimpíadas de Informática 2014. A final é já na próxima semana :)

Mas hoje vou continuar a análise dos problemas que tenho vindo a fazer. Começo a final de 2005, ano do meu 12º, com o problema A - Futebol.

Neste problema, é-nos dada a dimensão de um terreno rectangular com Y linhas e X colunas (1 ≤ Y, X ≤ 1000). Em cada célula do mapa existe relva ou uma árvore. Queremos construir um campo de futebol com L linhas e C colunas. Em que posição do mapa devemos construir o campo, de modo a termos de cortar o mínimo de árvores possível?

Exemplo do enunciado: mapa com 5 linhas e 8 colunas, para um campo de futebol 2x3 basta cortar 1 árvore

Qualificação ONI 2005: Problema C - Descobrindo Anagramas

O último problema da qualificação das ONI 2005 chama-se Descobrindo Anagramas.

Uma classe de anagramas é um conjunto de palavras com as mesmas letras mas por outra ordem. Exemplo: caras, casar e sacar são anagramas, fio e foi formam outra classe.

Dado um texto com no máximo 20 000 palavras distintas, pretende-se saber quantas classes de anagramas existem.

Nos dias de hoje, esta este problema muito frequente em entrevistas de emprego.